1 // Copyright (c) 2005,2006,2007,2009,2010,2011 Tel-Aviv University (Israel). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org). 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Arrangement_on_surface_2/include/CGAL/Arrangement_2/Arr_traits_adaptor_2.h $ 7 // $Id: Arr_traits_adaptor_2.h 03a2d28 2020-06-14T10:47:45+03:00 Efi Fogel 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // $Date$ 10 // 11 // Author(s): Ron Wein <wein@post.tau.ac.il>s 12 // Efi Fogel <efif@post.tau.ac.il> 13 // Eric Berberich <eric@mpi-inf.mpg.de> 14 // (based on old version by Iddo Hanniel 15 // Eyal Flato 16 // Oren Nechushtan 17 // Efi Fogel 18 // Ron Wein 19 // Idit Haran) 20 21 #ifndef CGAL_ARR_TRAITS_ADAPTOR_2_H 22 #define CGAL_ARR_TRAITS_ADAPTOR_2_H 23 24 #include <CGAL/license/Arrangement_on_surface_2.h> 25 26 /*! \file 27 * Definitions of the adaptor classes for the arrangement traits class. 28 */ 29 30 #include <list> 31 32 #include <CGAL/config.h> 33 #include <CGAL/tags.h> 34 #include <CGAL/Arr_enums.h> 35 #include <CGAL/Arr_tags.h> 36 #include <CGAL/Arrangement_2/Arr_traits_adaptor_2_dispatching.h> 37 38 namespace CGAL { 39 40 /*! \class 41 * A traits-class adaptor that extends the basic traits-class interface. 42 */ 43 template <typename ArrangementBasicTraits_> 44 class Arr_traits_basic_adaptor_2 : public ArrangementBasicTraits_ { 45 public: 46 // Traits-class geometric types. 47 typedef ArrangementBasicTraits_ Base; 48 typedef Arr_traits_basic_adaptor_2<Base> Self; 49 typedef typename Base::X_monotone_curve_2 X_monotone_curve_2; 50 typedef typename Base::Point_2 Point_2; 51 typedef typename Base::Multiplicity Multiplicity; 52 53 // Categories 54 typedef typename Base::Has_left_category Has_left_category; 55 typedef typename Base::Has_do_intersect_category Has_do_intersect_category; 56 57 typedef typename internal::Arr_complete_left_side_category< Base >::Category 58 Left_side_category; 59 typedef typename internal::Arr_complete_bottom_side_category< Base >::Category 60 Bottom_side_category; 61 typedef typename internal::Arr_complete_top_side_category< Base >::Category 62 Top_side_category; 63 typedef typename internal::Arr_complete_right_side_category< Base >::Category 64 Right_side_category; 65 66 protected: 67 // All sides 68 typedef typename Arr_are_all_sides_oblivious_tag<Left_side_category, 69 Bottom_side_category, 70 Top_side_category, 71 Right_side_category>::result 72 Are_all_sides_oblivious_category; 73 74 // left-right dispatch 75 typedef CGAL::internal::Arr_left_right_implementation_dispatch< 76 Left_side_category, Right_side_category > LR; 77 78 typedef typename LR::Parameter_space_in_x_2_curve_end_tag 79 Psx_2_curve_end_tag; 80 typedef typename LR::Parameter_space_in_x_2_curve_tag Psx_2_curve_tag; 81 typedef typename LR::Parameter_space_in_x_2_point_tag Psx_2_point_tag; 82 typedef typename LR::Is_on_y_identification_2_curve_tag Ioyi_2_curve_tag; 83 typedef typename LR::Is_on_y_identification_2_point_tag Ioyi_2_point_tag; 84 typedef typename LR::Compare_y_on_boundary_2_points_tag 85 Cmp_y_ob_2_points_tag; 86 typedef typename LR::Compare_y_near_boundary_2_curve_ends_tag 87 Cmp_y_nb_2_curve_ends_tag; 88 89 // bottom-top dispatch 90 typedef CGAL::internal::Arr_bottom_top_implementation_dispatch< 91 Bottom_side_category, Top_side_category > BT; 92 93 typedef typename BT::Parameter_space_in_y_2_curve_end_tag 94 Psy_2_curve_end_tag; 95 typedef typename BT::Parameter_space_in_y_2_curve_tag Psy_2_curve_tag; 96 typedef typename BT::Parameter_space_in_y_2_point_tag Psy_2_point_tag; 97 typedef typename BT::Is_on_x_identification_2_curve_tag Ioxi_2_curve_tag; 98 typedef typename BT::Is_on_x_identification_2_point_tag Ioxi_2_point_tag; 99 100 typedef typename BT::Compare_x_at_limit_2_point_curve_end_tag 101 Cmp_x_al_2_point_curve_end_tag; 102 typedef typename BT::Compare_x_at_limit_2_curve_ends_tag 103 Cmp_x_al_2_curve_ends_tag; 104 typedef typename BT::Compare_x_near_limit_2_curve_ends_tag 105 Cmp_x_nl_2_curve_ends_tag; 106 107 typedef typename BT::Compare_x_on_boundary_2_points_tag 108 Cmp_x_ob_2_points_tag; 109 typedef typename BT::Compare_x_on_boundary_2_point_curve_end_tag 110 Cmp_x_ob_2_point_curve_end_tag; 111 typedef typename BT::Compare_x_on_boundary_2_curve_ends_tag 112 Cmp_x_ob_2_curve_ends_tag; 113 typedef typename BT::Compare_x_near_boundary_2_curve_ends_tag 114 Cmp_x_nb_2_curve_ends_tag; 115 116 public: 117 118 /// \name Construction. 119 //@{ 120 /*! Default constructor. */ Arr_traits_basic_adaptor_2()121 Arr_traits_basic_adaptor_2() : Base() {} 122 123 /*! Constructor from a base-traits class. */ Arr_traits_basic_adaptor_2(const Base & traits)124 Arr_traits_basic_adaptor_2(const Base& traits) : Base(traits) {} 125 //@} 126 127 // Inherited functors: 128 typedef typename Base::Compare_x_2 Compare_x_2; 129 typedef typename Base::Compare_xy_2 Compare_xy_2; 130 typedef typename Base::Compare_y_at_x_2 Compare_y_at_x_2; 131 typedef typename Base::Construct_min_vertex_2 Construct_min_vertex_2; 132 typedef typename Base::Construct_max_vertex_2 Construct_max_vertex_2; 133 typedef typename Base::Is_vertical_2 Is_vertical_2; 134 typedef typename Base::Compare_y_at_x_right_2 Compare_y_at_x_right_2; 135 typedef typename Base::Equal_2 Equal_2; 136 137 /// \name Overriden functors for bounded boundaries. 138 //@{ 139 140 /*! A functor that compares the y-coordinates of two x-monotone curves 141 * immediately to the left of their intersection point. 142 */ 143 class Compare_y_at_x_left_2 { 144 public: 145 /*! 146 * Compare two curves immediately to the left of their intersection point. 147 * \param xcv1 The first curve. 148 * \param xcv2 The second curve. 149 * \param p The query point. 150 * \pre The two curves intersect at p, and they are defined to its left. 151 * \return SMALLER if xcv1 lies below xcv2 to the left of q; 152 * LARGER if xcv1 lies above xcv2 to the left of q; 153 * EQUAL in case of an overlap to the left of q. 154 */ operator()155 Comparison_result operator()(const X_monotone_curve_2& xcv1, 156 const X_monotone_curve_2& xcv2, 157 const Point_2& p) const 158 { 159 // The function is implemented based on the Has_left category. If the 160 // category indicates that the "left" version is available, it calls the 161 // function with same name defined in the base class. Otherwise, it 162 // uses other predicates to provide this comparison. 163 return _compare_y_at_x_left_imp(xcv1, xcv2, p, Has_left_category()); 164 } 165 166 protected: 167 //! The base traits. 168 const Self* m_self; 169 170 /*! Constructor. 171 * \param tr The base traits class. It must be passed, to handle non 172 * stateless traits objects, (which stores data). 173 * The constructor is declared private to allow only the functor 174 * obtaining function, which is a member of the nesting class, 175 * constructing it. 176 */ Compare_y_at_x_left_2(const Self * self)177 Compare_y_at_x_left_2(const Self* self) : m_self(self) {} 178 179 //! Allow its functor obtaining function calling the private constructor. 180 friend class Arr_traits_basic_adaptor_2<Base>; 181 182 /*! 183 * Implementation of the operator() in case the HasLeft tag is true. 184 */ _compare_y_at_x_left_imp(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,const Point_2 & p,Tag_true)185 Comparison_result _compare_y_at_x_left_imp(const X_monotone_curve_2& xcv1, 186 const X_monotone_curve_2& xcv2, 187 const Point_2& p, 188 Tag_true) const 189 { 190 const Base* base = m_self; 191 return (base->compare_y_at_x_left_2_object()(xcv1, xcv2, p)); 192 } 193 194 /*! 195 * Implementation of the operator() in case the HasLeft tag is false. 196 */ 197 Comparison_result _compare_y_at_x_left_imp(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,const Point_2 & CGAL_assertion_code (p),Tag_false)198 _compare_y_at_x_left_imp(const X_monotone_curve_2& xcv1, 199 const X_monotone_curve_2& xcv2, 200 const Point_2& CGAL_assertion_code(p), 201 Tag_false) const 202 { 203 Parameter_space_in_x_2 ps_x = m_self->parameter_space_in_x_2_object(); 204 Parameter_space_in_y_2 ps_y = m_self->parameter_space_in_y_2_object(); 205 Construct_min_vertex_2 min_vertex = 206 m_self->construct_min_vertex_2_object(); 207 Equal_2 equal = m_self->equal_2_object(); 208 209 // Check if the left ends of the curves are bounded endpoints. 210 const Arr_parameter_space ps_x1 = ps_x(xcv1, ARR_MIN_END); 211 const Arr_parameter_space ps_y1 = 212 (ps_x1 != ARR_INTERIOR ? ARR_INTERIOR : ps_y(xcv1, ARR_MIN_END)); 213 const bool has_left1 = (ps_x1 == ARR_INTERIOR && ps_y1 == ARR_INTERIOR); 214 215 const Arr_parameter_space ps_x2 = ps_x(xcv2, ARR_MIN_END); 216 const Arr_parameter_space ps_y2 = 217 (ps_x2 != ARR_INTERIOR ? ARR_INTERIOR : ps_y(xcv2, ARR_MIN_END)); 218 const bool has_left2 = (ps_x2 == ARR_INTERIOR && ps_y2 == ARR_INTERIOR); 219 220 CGAL_assertion(ps_x1 != ARR_RIGHT_BOUNDARY && 221 ps_x2 != ARR_RIGHT_BOUNDARY); 222 223 // Make sure that p lies on both curves, and that both are defined to its 224 // right (so their right endpoint is lexicographically larger than p). 225 CGAL_precondition_code( 226 Compare_xy_2 compare_xy = m_self->compare_xy_2_object(); 227 Compare_y_at_x_2 compare_y_at_x = m_self->compare_y_at_x_2_object(); 228 ); 229 230 CGAL_precondition(compare_y_at_x(p, xcv1) == EQUAL && 231 compare_y_at_x(p, xcv2) == EQUAL); 232 233 CGAL_precondition((! has_left1 || 234 compare_xy(min_vertex(xcv1), p) == SMALLER) && 235 (! has_left2 || 236 compare_xy(min_vertex(xcv2), p) == SMALLER)); 237 238 // If one of the curves is vertical, it is below the other one. 239 Is_vertical_2 is_vertical = m_self->is_vertical_2_object(); 240 241 if (is_vertical(xcv1)) return (is_vertical(xcv2)) ? EQUAL : SMALLER; 242 else if (is_vertical(xcv2)) return (LARGER); 243 244 // Perform the comparison based on the existence of bounded left 245 // endpoints. 246 if (has_left1 && has_left2) { 247 // Obtain the left endpoints of xcv1 and xcv2. 248 Point_2 left1 = min_vertex(xcv1); 249 Point_2 left2 = min_vertex(xcv2); 250 251 if (equal(left1, left2)) 252 // The two curves have a common left endpoint: 253 // Compare them to the right of this point. 254 return (m_self->compare_y_at_x_right_2_object()(xcv1, xcv2, left1)); 255 } 256 257 // We now that the curves do not share a common endpoint, and we can 258 // compare their relative y-position (which does not change to the left 259 // of the given point p). 260 return (m_self->compare_y_position_2_object()(xcv1, xcv2)); 261 } 262 }; 263 264 /*! Obtain a Compare_y_at_x_left_2 function object. */ compare_y_at_x_left_2_object()265 Compare_y_at_x_left_2 compare_y_at_x_left_2_object() const 266 { return Compare_y_at_x_left_2(this); } 267 268 /*! A functor that determines whether two x-monotone curves intersect. 269 */ 270 class Do_intersect_2 { 271 public: 272 /*! 273 * Determine whether two x-monotone curves intersect. 274 * \param xcv1 the first curve. 275 * \param xcv2 the second curve. 276 * \return true if xcv1 and xcv2 intersect false otherwise. 277 */ operator()278 bool operator()(const X_monotone_curve_2& xcv1, 279 const X_monotone_curve_2& xcv2) const 280 { 281 // The function is implemented based on the Has_do_intersect category. 282 // If the category indicates that "do_intersect" is available, it calls 283 // the function with same name defined in the base class. Otherwise, it 284 // uses the intersection construction to implement this predicate. 285 return _do_intersect_imp(xcv1, xcv2, Has_do_intersect_category()); 286 } 287 288 protected: 289 //! The base traits. 290 const Self* m_self; 291 292 /*! Constructor. 293 * \param self The traits adaptor class. It must be passed, to handle 294 * non stateless traits objects, (which stores data). 295 * The constructor is declared private to allow only the functor 296 * obtaining function, which is a member of the nesting class, 297 * constructing it. 298 */ Do_intersect_2(const Self * self)299 Do_intersect_2(const Self* self) : m_self(self) {} 300 301 //! Allow its functor obtaining function calling the private constructor. 302 friend class Arr_traits_basic_adaptor_2<Base>; 303 304 /*! 305 * Implementation of the operator() in case the HasDoIntersect tag is true. 306 */ _do_intersect_imp(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,Tag_true)307 bool _do_intersect_imp(const X_monotone_curve_2& xcv1, 308 const X_monotone_curve_2& xcv2, 309 Tag_true) const 310 { 311 const Base* base = m_self; 312 return (base->do_intersect_2_object()(xcv1, xcv2)); 313 } 314 315 /*! 316 * Implementation of the operator() in case the HasDoIntersect tag is false. 317 */ _do_intersect_imp(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,Tag_false)318 bool _do_intersect_imp(const X_monotone_curve_2& xcv1, 319 const X_monotone_curve_2& xcv2, 320 Tag_false) const 321 { 322 typedef std::pair<Point_2, Multiplicity> Intersection_point; 323 typedef boost::variant<Intersection_point, X_monotone_curve_2> 324 Intersection_result; 325 std::list<Intersection_result> intersections; 326 m_self->intersect_2_object()(xcv1, xcv2, back_inserter(intersections)); 327 return ! intersections.empty(); 328 } 329 }; 330 331 /*! Obtain a Compare_y_at_x_left_2 function object. */ do_intersect_2_object()332 Do_intersect_2 do_intersect_2_object() const { return Do_intersect_2(this); } 333 334 //@} 335 336 337 /// \name Overriden functors for boundaries. 338 //@{ 339 340 // left-right 341 342 /*! A functor that determines the location of a geometric object 343 * with respect to the parameter space along the x axis. 344 */ 345 class Parameter_space_in_x_2 { 346 public: 347 348 /*! 349 * Obtain the location of the given curve end in x. 350 * \param xcv The curve. 351 * \param ind ARR_MIN_END if we refer to xcv's minimal end, 352 * ARR_MAX_END if we refer to its maximal end. 353 * \return The location of the curve end. 354 */ operator()355 Arr_parameter_space operator()(const X_monotone_curve_2& xcv, 356 Arr_curve_end ind) const 357 { 358 // The function is implemented based on the tag dispatching 359 // If the traits class does not support special boundaries, we just 360 // return ARR_INTERIOR. 361 return parameter_space_in_x(xcv, ind, Psx_2_curve_end_tag()); 362 } 363 364 /*! 365 * Obtain the location of the given curve end in x. 366 * \param xcv The curve. 367 * \return The location of the curve end in x direction. 368 */ operator()369 Arr_parameter_space operator()(const X_monotone_curve_2& xcv) const 370 { 371 // The function is implemented based on the tag dispatching. 372 // If the traits class does not support special boundaries, we just 373 // return ARR_INTERIOR. 374 return parameter_space_in_x(xcv, Psx_2_curve_tag()); 375 } 376 377 /*! 378 * Obtain the location of the given point end in x. 379 * \param p The point. 380 * \return The location of the point end in x direction. 381 */ operator()382 Arr_parameter_space operator()(const Point_2& p) const 383 { 384 // The function is implemented based on the tag dispatching 385 // If the traits class does not support special boundaries, we just 386 // return ARR_INTERIOR. 387 return parameter_space_in_x(p, Psx_2_point_tag()); 388 } 389 390 391 protected: 392 //! The base traits. 393 const Base* m_base; 394 395 /*! Constructor. 396 * \param base The base traits class. It must be passed, to handle non 397 * stateless traits objects, (which stores data). 398 * The constructor is declared private to allow only the functor 399 * obtaining function, which is a member of the nesting class, 400 * constructing it. 401 */ Parameter_space_in_x_2(const Base * base)402 Parameter_space_in_x_2(const Base* base) : m_base(base) {} 403 404 //! Allow its functor obtaining function calling the private constructor. 405 friend class Arr_traits_basic_adaptor_2<Base>; 406 407 /*! 408 * Implementation of the operator() in case the base should be used. 409 */ parameter_space_in_x(const X_monotone_curve_2 & xcv,Arr_curve_end ind,Arr_use_traits_tag)410 Arr_parameter_space parameter_space_in_x(const X_monotone_curve_2& xcv, 411 Arr_curve_end ind, 412 Arr_use_traits_tag) const 413 { return (m_base->parameter_space_in_x_2_object()(xcv, ind)); } 414 415 /*! 416 * Implementation of the operator() in case the dummy should be used. 417 */ parameter_space_in_x(const X_monotone_curve_2 &,Arr_curve_end,Arr_use_dummy_tag)418 Arr_parameter_space parameter_space_in_x(const X_monotone_curve_2&, 419 Arr_curve_end, 420 Arr_use_dummy_tag) const 421 { return ARR_INTERIOR; } 422 423 /*! 424 * Implementation of the operator() in case the base should be used. 425 */ parameter_space_in_x(const X_monotone_curve_2 & xcv,Arr_use_traits_tag)426 Arr_parameter_space parameter_space_in_x(const X_monotone_curve_2& xcv, 427 Arr_use_traits_tag) const 428 { return (m_base->parameter_space_in_x_2_object()(xcv)); } 429 430 /*! 431 * Implementation of the operator() in case the dummy should be used. 432 */ parameter_space_in_x(const X_monotone_curve_2 &,Arr_use_dummy_tag)433 Arr_parameter_space parameter_space_in_x(const X_monotone_curve_2&, 434 Arr_use_dummy_tag) const 435 { return ARR_INTERIOR; } 436 437 /*! 438 * Implementation of the operator() in case the base should be used. 439 */ parameter_space_in_x(const Point_2 & p,Arr_use_traits_tag)440 Arr_parameter_space parameter_space_in_x(const Point_2& p, 441 Arr_use_traits_tag) const 442 { return m_base->parameter_space_in_x_2_object()(p); } 443 444 /*! 445 * Implementation of the operator() in case the dummy should be used. 446 */ parameter_space_in_x(const Point_2 &,Arr_use_dummy_tag)447 Arr_parameter_space parameter_space_in_x(const Point_2&, 448 Arr_use_dummy_tag) const 449 { return ARR_INTERIOR; } 450 }; 451 452 /*! Obtain an Parameter_space_in_x_2 function object. */ parameter_space_in_x_2_object()453 Parameter_space_in_x_2 parameter_space_in_x_2_object() const 454 { 455 return Parameter_space_in_x_2(this); 456 } 457 458 /*! A function object that determines whether an x-monotone curve or a 459 * point coincide with the vertical identification curve. 460 */ 461 class Is_on_y_identification_2 { 462 protected: 463 //! The base traits. 464 const Base* m_base; 465 466 /*! Constructor. 467 * \param base The base traits class. It must be passed, to handle non 468 * stateless traits objects, (which stores data). 469 * The constructor is declared private to allow only the functor 470 * obtaining function, which is a member of the nesting class, 471 * constructing it. 472 */ Is_on_y_identification_2(const Base * base)473 Is_on_y_identification_2(const Base* base) : m_base(base) {} 474 475 //! Allow its functor obtaining function calling the private constructor. 476 friend class Arr_traits_basic_adaptor_2<Base>; 477 478 public: 479 /*! Determones whether a point lies on the vertical identification curve 480 * \param p the point. 481 * \return true if p lies on the vertical identification curve, and 482 * false otherwise. 483 */ operator()484 bool operator()(const Point_2& p) const 485 { return is_on_y_idn(p, Ioyi_2_point_tag()); } 486 487 /*! Determones whether an x-monotone curve coicide with the vertical 488 * identification curve 489 * \param xcv the point. 490 * \return true if xcv coincides with an identification curve, 491 * and false otherwise. 492 */ operator()493 bool operator()(const X_monotone_curve_2& xcv) const 494 { return is_on_y_idn(xcv, Ioyi_2_curve_tag()); } 495 496 private: is_on_y_idn(const Point_2 & p,Arr_use_traits_tag)497 bool is_on_y_idn(const Point_2& p, Arr_use_traits_tag) const 498 { return m_base->is_on_y_identification_2_object()(p); } 499 is_on_y_idn(const Point_2 &,Arr_use_dummy_tag)500 bool is_on_y_idn(const Point_2&, Arr_use_dummy_tag) const 501 { 502 CGAL_error(); 503 return SMALLER; 504 } 505 is_on_y_idn(const X_monotone_curve_2 & xcv,Arr_use_traits_tag)506 bool is_on_y_idn(const X_monotone_curve_2& xcv, Arr_use_traits_tag) const 507 { return m_base->is_on_y_identification_2_object()(xcv); } 508 is_on_y_idn(const X_monotone_curve_2 &,Arr_use_dummy_tag)509 bool is_on_y_idn(const X_monotone_curve_2&, Arr_use_dummy_tag) const 510 { 511 CGAL_error(); 512 return SMALLER; 513 } 514 }; 515 516 /*! Obtain a Is_on_y_identification_2 function object. */ is_on_y_identification_2_object()517 Is_on_y_identification_2 is_on_y_identification_2_object() const 518 { 519 return Is_on_y_identification_2(this); 520 } 521 522 /*! A function object that compares the y-coordinates of curve ends near the 523 * boundary of the parameter space. 524 */ 525 class Compare_y_near_boundary_2 { 526 protected: 527 //! The base traits. 528 const Base* m_base; 529 530 /*! Constructor. 531 * \param base The base traits class. It must be passed, to handle non 532 * stateless traits objects, (which stores data). 533 * The constructor is declared private to allow only the functor 534 * obtaining function, which is a member of the nesting class, 535 * constructing it. 536 */ Compare_y_near_boundary_2(const Base * base)537 Compare_y_near_boundary_2(const Base* base) : m_base(base) {} 538 539 //! Allow its functor obtaining function calling the private constructor. 540 friend class Arr_traits_basic_adaptor_2<Base>; 541 542 /*! 543 * Implementation of the operator() in case the base should used. 544 */ comp_y_near_bnd(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce,Arr_use_traits_tag)545 Comparison_result comp_y_near_bnd(const X_monotone_curve_2& xcv1, 546 const X_monotone_curve_2& xcv2, 547 Arr_curve_end ce, 548 Arr_use_traits_tag) const 549 { return m_base->compare_y_near_boundary_2_object()(xcv1, xcv2, ce); } 550 551 /*! 552 * Implementation of the operator() in case the dummy should be used. 553 */ comp_y_near_bnd(const X_monotone_curve_2 &,const X_monotone_curve_2 &,Arr_curve_end,Arr_use_dummy_tag)554 Comparison_result comp_y_near_bnd(const X_monotone_curve_2&, 555 const X_monotone_curve_2&, 556 Arr_curve_end, Arr_use_dummy_tag) const 557 { 558 CGAL_error(); 559 return EQUAL; 560 } 561 562 public: 563 /*! 564 * Compare the relative y-positions of two curve ends. 565 * \param xcv1 The first curve. 566 * \param xcv2 The second curve. 567 * \param ce The relevant end of xcv1 and xcv2. 568 * \pre Both curve ends have a special boundary in x. 569 * \return SMALLER if xcv1 lies below xcv2; 570 * LARGER if xcv1 lies above xcv2; 571 * EQUAL in case of an overlap. 572 */ operator()573 Comparison_result operator()(const X_monotone_curve_2& xcv1, 574 const X_monotone_curve_2& xcv2, 575 Arr_curve_end ce) const 576 { 577 // The function is implemented based on the tag disatching 578 // If the traits class does not support open curves, we just 579 // return EQUAL, as this comparison will not be invoked anyway. 580 return comp_y_near_bnd(xcv1, xcv2, ce, Cmp_y_nb_2_curve_ends_tag()); 581 } 582 }; 583 584 /*! Obtain a Compare_y_near_boundary_2 functor. */ compare_y_near_boundary_2_object()585 Compare_y_near_boundary_2 compare_y_near_boundary_2_object() const 586 { return Compare_y_near_boundary_2(this); } 587 588 /*! A function object that compares the y-coordinate of two given points 589 * that lie on vertical boundaries. 590 */ 591 class Compare_y_on_boundary_2 { 592 protected: 593 //! The base traits. 594 const Base* m_base; 595 596 /*! Constructor. 597 * \param base The base traits class. It must be passed, to handle non 598 * stateless traits objects, (which stores data). 599 * The constructor is declared private to allow only the functor 600 * obtaining function, which is a member of the nesting class, 601 * constructing it. 602 */ Compare_y_on_boundary_2(const Base * base)603 Compare_y_on_boundary_2(const Base* base) : m_base(base) {} 604 605 //! Allow its functor obtaining function calling the private constructor. 606 friend class Arr_traits_basic_adaptor_2<Base>; 607 608 /*! 609 * Implementation of the operator() in case the base should be used. 610 */ comp_y_on_bnd(const Point_2 & p1,const Point_2 & p2,Arr_use_traits_tag)611 Comparison_result comp_y_on_bnd(const Point_2& p1, const Point_2& p2, 612 Arr_use_traits_tag) const 613 { return m_base->compare_y_on_boundary_2_object()(p1, p2); } 614 615 /*! 616 * Implementation of the operator() in case the dummy should be used. 617 */ comp_y_on_bnd(const Point_2 &,const Point_2 &,Arr_use_dummy_tag)618 Comparison_result comp_y_on_bnd(const Point_2&, const Point_2&, 619 Arr_use_dummy_tag) const 620 { 621 CGAL_error(); 622 return SMALLER; 623 } 624 625 public: 626 /*! Compare the relative y-positions of two points. 627 * \param p1 The first point. 628 * \param p2 The second point. 629 * \pre Both points lie on vertical boundaries. 630 * \return SMALLER if xcv1 lies below xcv2; 631 * LARGER if xcv1 lies above xcv2; 632 * EQUAL in case of an overlap. 633 */ operator()634 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 635 { 636 // The function is implemented based on the tag dispatching. 637 // If the traits class does not support open curves, we just 638 // return EQUAL, as this comparison will not be invoked anyway. 639 return comp_y_on_bnd(p1, p2, Cmp_y_ob_2_points_tag()); 640 } 641 }; 642 643 /*! Obtain a Compare_y_on_boundary_2 function object. */ compare_y_on_boundary_2_object()644 Compare_y_on_boundary_2 compare_y_on_boundary_2_object() const 645 { return Compare_y_on_boundary_2(this); } 646 647 // bottom-top 648 649 /*! A functor that determines the location of a geometric object 650 * with respect to the parameter space along the y axis. 651 */ 652 class Parameter_space_in_y_2 { 653 public: 654 /*! 655 * Obtain the location of the given curve end in y. 656 * \param xcv The curve. 657 * \param ind ARR_MIN_END if we refer to xcv's minimal end, 658 * ARR_MAX_END if we refer to its maximal end. 659 * \return The location of the curve end. 660 */ operator()661 Arr_parameter_space operator()(const X_monotone_curve_2& xcv, 662 Arr_curve_end ind) const 663 { 664 // The function is implemented based on the tag dispatching. 665 // If the traits class does not support special boundaries, we just 666 // return ARR_INTERIOR. 667 return parameter_space_in_y(xcv, ind, Psy_2_curve_end_tag()); 668 } 669 670 /*! 671 * Obtain the location of the given curve end in y. 672 * \param xcv The curve. 673 * \return The location of the curve end in y direction. 674 */ operator()675 Arr_parameter_space operator()(const X_monotone_curve_2& xcv) const 676 { 677 // The function is implemented based on the tag dispatching. 678 // If the traits class does not support special boundaries, we just 679 // return ARR_INTERIOR. 680 return parameter_space_in_y(xcv, Psy_2_curve_tag()); 681 } 682 683 /*! 684 * Obtain the location of the given point end in y. 685 * \param p The point. 686 * \return The location of the point end in y direction. 687 */ operator()688 Arr_parameter_space operator()(const Point_2& p) const 689 { return parameter_space_in_y(p, Psy_2_point_tag()); } 690 691 protected: 692 //! The base traits. 693 const Base* m_base; 694 695 /*! Constructor. 696 * \param base The base traits class. It must be passed, to handle non 697 * stateless traits objects, (which stores data). 698 * The constructor is declared private to allow only the functor 699 * obtaining function, which is a member of the nesting class, 700 * constructing it. 701 */ Parameter_space_in_y_2(const Base * base)702 Parameter_space_in_y_2(const Base* base) : m_base(base) {} 703 704 //! Allow its functor obtaining function calling the private constructor. 705 friend class Arr_traits_basic_adaptor_2<Base>; 706 707 /*! 708 * Implementation of the operator() in case the base should be used. 709 */ parameter_space_in_y(const X_monotone_curve_2 & xcv,Arr_curve_end ind,Arr_use_traits_tag)710 Arr_parameter_space parameter_space_in_y(const X_monotone_curve_2& xcv, 711 Arr_curve_end ind, 712 Arr_use_traits_tag) const 713 { return m_base->parameter_space_in_y_2_object()(xcv, ind); } 714 715 /*! 716 * Implementation of the operator() in case the dummy should be used. 717 */ parameter_space_in_y(const X_monotone_curve_2 &,Arr_curve_end,Arr_use_dummy_tag)718 Arr_parameter_space parameter_space_in_y(const X_monotone_curve_2&, 719 Arr_curve_end, 720 Arr_use_dummy_tag) const 721 { return ARR_INTERIOR; } 722 723 /*! 724 * Implementation of the operator() in case the base should be used. 725 */ parameter_space_in_y(const X_monotone_curve_2 & xcv,Arr_use_traits_tag)726 Arr_parameter_space parameter_space_in_y(const X_monotone_curve_2& xcv, 727 Arr_use_traits_tag) const 728 { return (m_base->parameter_space_in_x_2_object()(xcv)); } 729 730 /*! 731 * Implementation of the operator() in case the dummy should be used. 732 */ parameter_space_in_y(const X_monotone_curve_2 &,Arr_use_dummy_tag)733 Arr_parameter_space parameter_space_in_y(const X_monotone_curve_2&, 734 Arr_use_dummy_tag) const 735 { return ARR_INTERIOR; } 736 737 /*! 738 * Implementation of the operator() in case the base should be used. 739 */ parameter_space_in_y(const Point_2 & p,Arr_use_traits_tag)740 Arr_parameter_space parameter_space_in_y(const Point_2& p, 741 Arr_use_traits_tag) const 742 { return m_base->parameter_space_in_y_2_object()(p); } 743 744 /*! 745 * Implementation of the operator() in case the dummy should be used. 746 */ parameter_space_in_y(const Point_2 &,Arr_use_dummy_tag)747 Arr_parameter_space parameter_space_in_y(const Point_2&, 748 Arr_use_dummy_tag) const 749 { return ARR_INTERIOR; } 750 }; 751 752 /*! Obtain an Parameter_space_in_y_2 function object. */ parameter_space_in_y_2_object()753 Parameter_space_in_y_2 parameter_space_in_y_2_object() const 754 { return Parameter_space_in_y_2(this); } 755 756 /*! A function object that determines whether an x-monotone curve or a 757 * point coincide with the horizontal identification curve. 758 */ 759 class Is_on_x_identification_2 { 760 protected: 761 //! The base traits. 762 const Base* m_base; 763 764 /*! Constructor. 765 * \param base The base traits class. It must be passed, to handle non 766 * stateless traits objects, (which stores data). 767 * The constructor is declared private to allow only the functor 768 * obtaining function, which is a member of the nesting class, 769 * constructing it. 770 */ Is_on_x_identification_2(const Base * base)771 Is_on_x_identification_2(const Base* base) : m_base(base) {} 772 773 //! Allow its functor obtaining function calling the private constructor. 774 friend class Arr_traits_basic_adaptor_2<Base>; 775 776 public: 777 /*! Determones whether a point lies on the horizontal identification curve 778 * \param p the point. 779 * \return true if p lies on the vertical identification curve, and 780 * false otherwise. 781 */ operator()782 bool operator()(const Point_2& p) const 783 { return is_on_idn(p, Ioxi_2_point_tag()); } 784 785 /*! Determones whether an x-monotone curve coicide with the horizontal 786 * identification curve 787 * \param xcv the point. 788 * \return true if xcv coincides with an identification curve, 789 * and false otherwise. 790 */ operator()791 bool operator()(const X_monotone_curve_2& xcv) const 792 { return is_on_x_idn(xcv, Ioxi_2_curve_tag()); } 793 794 private: is_on_x_idn(const Point_2 & p,Arr_use_traits_tag)795 bool is_on_x_idn(const Point_2& p, Arr_use_traits_tag) const 796 { return m_base->is_on_x_identification_2_object()(p); } 797 is_on_x_idn(const Point_2 &,Arr_use_dummy_tag)798 bool is_on_x_idn(const Point_2&, Arr_use_dummy_tag) const 799 { 800 CGAL_error(); 801 return SMALLER; 802 } 803 is_on_x_idn(const X_monotone_curve_2 & xcv,Arr_use_traits_tag)804 bool is_on_x_idn(const X_monotone_curve_2& xcv, Arr_use_traits_tag) const 805 { return m_base->is_on_x_identification_2_object()(xcv); } 806 is_on_x_idn(const X_monotone_curve_2 &,Arr_use_dummy_tag)807 bool is_on_x_idn(const X_monotone_curve_2&, Arr_use_dummy_tag) const 808 { 809 CGAL_error(); 810 return SMALLER; 811 } 812 }; 813 814 /*! Obtain a Is_on_x_identification_2 function object. */ is_on_x_identification_2_object()815 Is_on_x_identification_2 is_on_x_identification_2_object() const 816 { return Is_on_x_identification_2(this); } 817 818 /*! A functor that compares the x-limits of curve ends near the 819 * boundary of the parameter space 820 */ 821 class Compare_x_at_limit_2 { 822 protected: 823 //! The base traits. 824 const Base * m_base; 825 826 /*! Constructor. 827 * \param base The base traits class. It must be passed, to handle non 828 * stateless traits objects, (which stores data). 829 * The constructor is declared private to allow only the functor 830 * obtaining function, which is a member of the nesting class, 831 * constructing it. 832 */ Compare_x_at_limit_2(const Base * base)833 Compare_x_at_limit_2(const Base * base) : m_base(base) {} 834 835 //! Allow its functor obtaining function calling the private constructor. 836 friend class Arr_traits_basic_adaptor_2<Base>; 837 838 /*! 839 * Implementation of the operator() in case the base should be used. 840 */ _compare_point_curve(const Point_2 & p,const X_monotone_curve_2 & xcv,Arr_curve_end ce,Arr_use_traits_tag)841 Comparison_result _compare_point_curve(const Point_2& p, 842 const X_monotone_curve_2& xcv, 843 Arr_curve_end ce, 844 Arr_use_traits_tag) const 845 { return (m_base->compare_x_at_limit_2_object()(p, xcv, ce)); } 846 847 /*! 848 * Implementation of the operator() in case the dummy should be used. 849 */ _compare_point_curve(const Point_2 &,const X_monotone_curve_2 &,Arr_curve_end,Arr_use_dummy_tag)850 Comparison_result _compare_point_curve(const Point_2&, 851 const X_monotone_curve_2&, 852 Arr_curve_end, 853 Arr_use_dummy_tag) const 854 { 855 CGAL_error(); 856 return EQUAL; 857 } 858 859 /*! 860 * Implementation of the operator() in case the base should be used. 861 */ _compare_curves(const X_monotone_curve_2 & xcv1,Arr_curve_end ce1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce2,Arr_use_traits_tag)862 Comparison_result _compare_curves(const X_monotone_curve_2& xcv1, 863 Arr_curve_end ce1, 864 const X_monotone_curve_2& xcv2, 865 Arr_curve_end ce2, 866 Arr_use_traits_tag) const 867 { return m_base->compare_x_at_limit_2_object()(xcv1, ce1, xcv2, ce2); } 868 869 /*! 870 * Implementation of the operator() in case the dummy should be used. 871 */ _compare_curves(const X_monotone_curve_2 &,Arr_curve_end,const X_monotone_curve_2 &,Arr_curve_end,Arr_use_dummy_tag)872 Comparison_result _compare_curves(const X_monotone_curve_2&, 873 Arr_curve_end, 874 const X_monotone_curve_2&, 875 Arr_curve_end, 876 Arr_use_dummy_tag) const 877 { 878 CGAL_error(); 879 return EQUAL; 880 } 881 882 public: 883 /*! Compare the x-limits of a vertical curve and another given 884 * curve end. 885 * \param p A reference point; we refer to a vertical line incident to p. 886 * \param xcv The compared curve. 887 * \param ind ARR_MIN_END if we refer to xcv's minimal end; 888 * ARR_MAX_END if we refer to its maximal end. 889 * \pre xcv's relevant end has a special boundary in y. 890 * \return SMALLER if p lies to the left of xcv; 891 * LARGER if p lies to the right xcv; 892 * EQUAL in case of an overlap. 893 */ operator()894 Comparison_result operator()(const Point_2& p, 895 const X_monotone_curve_2& xcv, 896 Arr_curve_end ce) const 897 { 898 return _compare_point_curve(p, xcv, ce, Cmp_x_al_2_point_curve_end_tag()); 899 } 900 901 /*! Compare the x-limits of two curve ends on the boundary. 902 * \param xcv1 The first curve. 903 * \param ind1 ARR_MIN_END if we refer to xcv1's minimal end; 904 * ARR_MAX_END if we refer to its maximal end. 905 * \param xcv2 The second curve. 906 * \param ind2 ARR_MIN_END if we refer to xcv2's minimal end; 907 * ARR_MAX_END if we refer to its maximal end. 908 * \pre Both curve ends have a special boundary in y. 909 * \return SMALLER if xcv1 lies to the left of xcv2; 910 * LARGER if xcv1 lies to the right xcv2; 911 * EQUAL in case of an overlap. 912 */ operator()913 Comparison_result operator()(const X_monotone_curve_2& xcv1, 914 Arr_curve_end ce1, 915 const X_monotone_curve_2& xcv2, 916 Arr_curve_end ce2) const 917 { 918 return _compare_curves(xcv1, ce1, xcv2, ce2, Cmp_x_al_2_curve_ends_tag()); 919 } 920 }; 921 922 /*! Obtain a Compare_x_at_limit_2 function object. */ compare_x_at_limit_2_object()923 Compare_x_at_limit_2 compare_x_at_limit_2_object() const 924 { return Compare_x_at_limit_2(this); } 925 926 /*! A functor that compares the x-coordinates of curve ends near the 927 * boundary of the parameter space 928 */ 929 class Compare_x_near_limit_2 { 930 protected: 931 //! The base traits. 932 const Base* m_base; 933 934 /*! Constructor. 935 * \param base The base traits class. It must be passed, to handle non 936 * stateless traits objects,(which stores data). 937 * The constructor is declared private to allow only the functor 938 * obtaining function, which is a member of the nesting class, 939 * constructing it. 940 */ Compare_x_near_limit_2(const Base * base)941 Compare_x_near_limit_2(const Base* base) : m_base(base) {} 942 943 //! Allow its functor obtaining function calling the private constructor. 944 friend class Arr_traits_basic_adaptor_2<Base>; 945 946 /*! 947 * Implementation of the operator() in case the base should be used. 948 */ _compare_curves(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce,Arr_use_traits_tag)949 Comparison_result _compare_curves(const X_monotone_curve_2& xcv1, 950 const X_monotone_curve_2& xcv2, 951 Arr_curve_end ce, 952 Arr_use_traits_tag) const 953 { return m_base->compare_x_near_limit_2_object()(xcv1, xcv2, ce); } 954 955 /*! 956 * Implementation of the operator() in case the dummy should be used. 957 */ _compare_curves(const X_monotone_curve_2 &,const X_monotone_curve_2 &,Arr_curve_end,Arr_use_dummy_tag)958 Comparison_result _compare_curves(const X_monotone_curve_2&, 959 const X_monotone_curve_2&, 960 Arr_curve_end, 961 Arr_use_dummy_tag) const 962 { 963 CGAL_error(); 964 return EQUAL; 965 } 966 967 public: 968 /*! Compare the relative x-positions of two curve ends. 969 * \param xcv1 The first curve. 970 * \param xcv2 The second curve. 971 * \param ce ARR_MIN_END if we refer to the curves' minimal end; 972 * ARR_MAX_END if we refer to the curves' maximal end. 973 * \pre Both curve ends have a special boundary in y. 974 * \return SMALLER if xcv1 lies to the left of xcv2; 975 * LARGER if xcv1 lies to the right xcv2; 976 * EQUAL in case of an overlap. 977 */ operator()978 Comparison_result operator()(const X_monotone_curve_2& xcv1, 979 const X_monotone_curve_2& xcv2, 980 Arr_curve_end ce) const 981 { return _compare_curves(xcv1, xcv2, ce, Cmp_x_nl_2_curve_ends_tag()); } 982 }; 983 984 /*! Obtain a Compare_x_near_limit_2 function object. */ compare_x_near_limit_2_object()985 Compare_x_near_limit_2 compare_x_near_limit_2_object() const 986 { return Compare_x_near_limit_2(this); } 987 988 /*! A function object that compares the x-coordinate of two given points 989 * that lie on horizontal boundaries. 990 */ 991 class Compare_x_on_boundary_2 { 992 protected: 993 //! The base traits. 994 const Base* m_base; 995 996 /*! Constructor. 997 * \param base The base traits class. It must be passed, to handle non 998 * stateless traits objects, (which stores data). 999 * The constructor is declared private to allow only the functor 1000 * obtaining function, which is a member of the nesting class, 1001 * constructing it. 1002 */ Compare_x_on_boundary_2(const Base * base)1003 Compare_x_on_boundary_2(const Base* base) : m_base(base) {} 1004 1005 //! Allow its functor obtaining function calling the private constructor. 1006 friend class Arr_traits_basic_adaptor_2<Base>; 1007 1008 public: 1009 /*! Compare the x-coordinate of two given points projected onto the 1010 * horizontal boundaries 1011 * \param p1 the first point. 1012 * \param p2 the second point. 1013 */ operator()1014 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 1015 { return comp_x_on_bnd(p1, p2, Cmp_x_ob_2_points_tag()); } 1016 1017 /*! Compare the x-coordinate of a point and a curve-end projected onto the 1018 * horizontal boundaries 1019 * \param pt the point. 1020 * \param xcv the curve 1021 * \param ce the curve-end 1022 */ operator()1023 Comparison_result operator()(const Point_2& pt, 1024 const X_monotone_curve_2& xcv, 1025 Arr_curve_end ce) const 1026 { return comp_x_on_bnd(pt, xcv, ce, Cmp_x_ob_2_point_curve_end_tag()); } 1027 1028 /*! Compare the x-coordinates of two curve-ends projected onto the horizontal 1029 * boundaries 1030 * \param xcv1 the curve 1031 * \param ce1 the curve-end 1032 * \param xcv2 the curve 1033 * \param ce2 the curve-end 1034 */ operator()1035 Comparison_result operator()(const X_monotone_curve_2& xcv1, 1036 Arr_curve_end ce1, 1037 const X_monotone_curve_2& xcv2, 1038 Arr_curve_end ce2) const 1039 { return comp_x_on_bnd(xcv1, ce1, xcv2, ce2, Cmp_x_ob_2_curve_ends_tag()); } 1040 1041 private: comp_x_on_bnd(const Point_2 & p1,const Point_2 & p2,Arr_use_traits_tag)1042 Comparison_result comp_x_on_bnd(const Point_2& p1, const Point_2& p2, 1043 Arr_use_traits_tag) const 1044 { return m_base->compare_x_on_boundary_2_object()(p1, p2); } 1045 comp_x_on_bnd(const Point_2 &,const Point_2 &,Arr_use_dummy_tag)1046 Comparison_result comp_x_on_bnd(const Point_2&, const Point_2&, 1047 Arr_use_dummy_tag) const 1048 { 1049 CGAL_error(); 1050 return SMALLER; 1051 } 1052 comp_x_on_bnd(const Point_2 & pt,const X_monotone_curve_2 & xcv,Arr_curve_end ce,Arr_use_traits_tag)1053 Comparison_result comp_x_on_bnd(const Point_2& pt, 1054 const X_monotone_curve_2& xcv, 1055 Arr_curve_end ce, 1056 Arr_use_traits_tag) const 1057 { return m_base->compare_x_on_boundary_2_object()(pt, xcv, ce); } 1058 comp_x_on_bnd(const Point_2 &,const X_monotone_curve_2 &,Arr_curve_end,Arr_use_dummy_tag)1059 Comparison_result comp_x_on_bnd(const Point_2&, 1060 const X_monotone_curve_2& /* xcv */, 1061 Arr_curve_end /* ce */, 1062 Arr_use_dummy_tag) const 1063 { 1064 CGAL_error(); 1065 return SMALLER; 1066 } 1067 1068 comp_x_on_bnd(const X_monotone_curve_2 & xcv1,Arr_curve_end ce1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce2,Arr_use_traits_tag)1069 Comparison_result comp_x_on_bnd(const X_monotone_curve_2& xcv1, 1070 Arr_curve_end ce1, 1071 const X_monotone_curve_2& xcv2, 1072 Arr_curve_end ce2, 1073 Arr_use_traits_tag) const 1074 { return m_base->compare_x_on_boundary_2_object()(xcv1, ce1, xcv2, ce2); } 1075 comp_x_on_bnd(const X_monotone_curve_2 &,Arr_curve_end,const X_monotone_curve_2 &,Arr_curve_end,Arr_use_dummy_tag)1076 Comparison_result comp_x_on_bnd(const X_monotone_curve_2& /* xcv1 */, 1077 Arr_curve_end /* ce1 */, 1078 const X_monotone_curve_2& /* xcv2 */, 1079 Arr_curve_end /* ce2 */, 1080 Arr_use_dummy_tag) const 1081 { 1082 CGAL_error(); 1083 return SMALLER; 1084 } 1085 }; 1086 1087 /*! Obtain a Compare_x_on_boundary_2 function object. */ compare_x_on_boundary_2_object()1088 Compare_x_on_boundary_2 compare_x_on_boundary_2_object() const 1089 { return Compare_x_on_boundary_2(this); } 1090 1091 /*! A functor that compares the x-coordinates of curve ends near the 1092 * boundary of the parameter space 1093 */ 1094 class Compare_x_near_boundary_2 { 1095 protected: 1096 //! The base traits. 1097 const Base* m_base; 1098 1099 /*! Constructor. 1100 * \param base The base traits class. It must be passed, to handle non 1101 * stateless traits objects, (which stores data). 1102 * The constructor is declared private to allow only the functor 1103 * obtaining function, which is a member of the nesting class, 1104 * constructing it. 1105 */ Compare_x_near_boundary_2(const Base * base)1106 Compare_x_near_boundary_2(const Base* base) : m_base(base) {} 1107 1108 //! Allow its functor obtaining function calling the private constructor. 1109 friend class Arr_traits_basic_adaptor_2<Base>; 1110 1111 /*! 1112 * Implementation of the operator() in case the base should be used. 1113 */ _compare_curves(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce,Arr_use_traits_tag)1114 Comparison_result _compare_curves(const X_monotone_curve_2& xcv1, 1115 const X_monotone_curve_2& xcv2, 1116 Arr_curve_end ce, 1117 Arr_use_traits_tag) const 1118 { return m_base->compare_x_near_boundary_2_object()(xcv1, xcv2, ce); } 1119 1120 /*! 1121 * Implementation of the operator() in case the dummy should be used. 1122 */ _compare_curves(const X_monotone_curve_2 &,const X_monotone_curve_2 &,Arr_curve_end,Arr_use_dummy_tag)1123 Comparison_result _compare_curves(const X_monotone_curve_2&, 1124 const X_monotone_curve_2&, 1125 Arr_curve_end, 1126 Arr_use_dummy_tag) const 1127 { 1128 CGAL_error(); 1129 return EQUAL; 1130 } 1131 1132 public: 1133 1134 /*! Compare the relative x-positions of two curve ends. 1135 * \param xcv1 The first curve. 1136 * \param xcv2 The second curve. 1137 * \param ce ARR_MIN_END if we refer to the curves' minimal end; 1138 * ARR_MAX_END if we refer to the curves' maximal end. 1139 * \pre Both curve ends have a special boundary in y. 1140 * \return SMALLER if xcv1 lies to the left of xcv2; 1141 * LARGER if xcv1 lies to the right xcv2; 1142 * EQUAL in case of an overlap. 1143 */ operator()1144 Comparison_result operator()(const X_monotone_curve_2& xcv1, 1145 const X_monotone_curve_2& xcv2, 1146 Arr_curve_end ce) const 1147 { return _compare_curves(xcv1, xcv2, ce, Cmp_x_nb_2_curve_ends_tag()); } 1148 }; 1149 1150 /*! Obtain a Compare_x_near_boundary_2 function object. */ compare_x_near_boundary_2_object()1151 Compare_x_near_boundary_2 compare_x_near_boundary_2_object() const 1152 { return Compare_x_near_boundary_2(this); } 1153 1154 1155 // special non-public comparison functors 1156 1157 1158 /*! A functor that compares the y-coordinates of curve ends near the 1159 * boundary of the parameter space 1160 */ 1161 class Compare_y_curve_ends_2 { 1162 protected: 1163 //! The base traits. 1164 const Self* m_self; 1165 1166 /*! Constructor. 1167 * \param base The base traits class. It must be passed, to handle non 1168 * stateless traits objects, (which stores data). 1169 * The constructor is declared private to allow only the functor 1170 * obtaining function, which is a member of the nesting class, 1171 * constructing it. 1172 */ Compare_y_curve_ends_2(const Self * self)1173 Compare_y_curve_ends_2(const Self* self) : m_self(self) {} 1174 1175 //! Allow its functor obtaining function calling the private constructor. 1176 friend class Arr_traits_basic_adaptor_2<Base>; 1177 1178 protected: 1179 // for open _compare_curve_ends(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce,Arr_open_side_tag)1180 Comparison_result _compare_curve_ends(const X_monotone_curve_2& xcv1, 1181 const X_monotone_curve_2& xcv2, 1182 Arr_curve_end ce, 1183 Arr_open_side_tag) const 1184 { 1185 Comparison_result res = 1186 m_self->compare_y_near_boundary_2_object()(xcv1, xcv2, ce); 1187 return res; 1188 } 1189 1190 // for non-open _compare_curve_ends(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce,Arr_oblivious_side_tag)1191 Comparison_result _compare_curve_ends(const X_monotone_curve_2& xcv1, 1192 const X_monotone_curve_2& xcv2, 1193 Arr_curve_end ce, 1194 Arr_oblivious_side_tag) const 1195 { 1196 Comparison_result res = 1197 m_self->compare_y_on_boundary_2_object()( 1198 m_self->construct_vertex_at_curve_end_2_object()(xcv1, ce), 1199 m_self->construct_vertex_at_curve_end_2_object()(xcv2, ce) 1200 ); 1201 return res; 1202 } 1203 1204 public: 1205 /*! Compare the relative y-positions of two curve ends. 1206 * \param xcv1 The first curve. 1207 * \param ind1 ARR_MIN_END if we refer to xcv1's minimal end; 1208 * ARR_MAX_END if we refer to its maximal end. 1209 * \param xcv2 The second curve. 1210 * \param ind2 ARR_MIN_END if we refer to xcv2's minimal end; 1211 * ARR_MAX_END if we refer to its maximal end. 1212 * \pre Both curve ends have a special boundary in y. 1213 * \return SMALLER if xcv1 lies to the left of xcv2; 1214 * LARGER if xcv1 lies to the right xcv2; 1215 * EQUAL in case of an overlap. 1216 */ operator()1217 Comparison_result operator()(const X_monotone_curve_2& xcv1, 1218 const X_monotone_curve_2& xcv2, 1219 Arr_curve_end ce) const 1220 { 1221 1222 Arr_parameter_space ps1 = 1223 m_self->parameter_space_in_x_2_object()(xcv1, ce); 1224 1225 CGAL_precondition(ps1 != ARR_INTERIOR); 1226 1227 CGAL_assertion_code( 1228 Arr_parameter_space ps2 = 1229 m_self->parameter_space_in_x_2_object()(xcv2, ce); 1230 ); 1231 CGAL_assertion(ps1 == ps2); 1232 1233 switch (ps1) { 1234 case ARR_LEFT_BOUNDARY: 1235 return _compare_curve_ends(xcv1, xcv2, ce, Left_side_category()); 1236 1237 case ARR_RIGHT_BOUNDARY: 1238 return _compare_curve_ends(xcv1, xcv2, ce, Right_side_category()); 1239 1240 case ARR_INTERIOR: // fall-through 1241 default: 1242 CGAL_error(); // never reached 1243 return CGAL::EQUAL; 1244 } 1245 } 1246 }; 1247 1248 /*! Obtain a Compare_y_curve_ends_2 function object. */ compare_y_curve_ends_2_object()1249 Compare_y_curve_ends_2 compare_y_curve_ends_2_object() const 1250 { return Compare_y_curve_ends_2(this); } 1251 1252 /*! A functor that compares the x-coordinates of curve ends near the 1253 * boundary of the parameter space 1254 */ 1255 class Compare_x_point_curve_end_2 { 1256 protected: 1257 //! The base traits. 1258 const Self* m_self; 1259 1260 /*! Constructor. 1261 * \param base The base traits class. It must be passed, to handle non 1262 * stateless traits objects, (which stores data). 1263 * The constructor is declared private to allow only the functor 1264 * obtaining function, which is a member of the nesting class, 1265 * constructing it. 1266 */ Compare_x_point_curve_end_2(const Self * self)1267 Compare_x_point_curve_end_2(const Self* self) : m_self(self) {} 1268 1269 //! Allow its functor obtaining function calling the private constructor. 1270 friend class Arr_traits_basic_adaptor_2<Base>; 1271 1272 protected: 1273 // for open _compare_point_curve_end(const Point_2 & pt,const X_monotone_curve_2 & xcv,Arr_curve_end ce,Arr_open_side_tag)1274 Comparison_result _compare_point_curve_end(const Point_2& pt, 1275 const X_monotone_curve_2& xcv, 1276 Arr_curve_end ce, 1277 Arr_open_side_tag) const 1278 { 1279 Comparison_result res = 1280 m_self->compare_x_at_limit_2_object()(pt, xcv, ce); 1281 if ((res != EQUAL) || m_self->is_vertical_2_object()(xcv)) return res; 1282 1283 // look at the side from which the 1284 // vertical asymptote is approached 1285 res = ((ce == CGAL::ARR_MIN_END) ? CGAL::SMALLER : CGAL::LARGER); 1286 return res; 1287 } 1288 1289 // for contraction _compare_point_curve_end(const Point_2 & pt,const X_monotone_curve_2 & xcv,Arr_curve_end ce,Arr_contracted_side_tag)1290 Comparison_result _compare_point_curve_end(const Point_2& pt, 1291 const X_monotone_curve_2& xcv, 1292 Arr_curve_end ce, 1293 Arr_contracted_side_tag) const 1294 { 1295 Comparison_result res = 1296 m_self->compare_x_on_boundary_2_object()(pt, xcv, ce); 1297 if ((res != EQUAL) || m_self->is_vertical_2_object()(xcv)) return res; 1298 1299 // look at the side from which the 1300 // vertical asymptote is approached 1301 res = ((ce == CGAL::ARR_MIN_END) ? CGAL::SMALLER : CGAL::LARGER); 1302 return res; 1303 } 1304 1305 // for others _compare_point_curve_end(const Point_2 & pt,const X_monotone_curve_2 & xcv,Arr_curve_end ce,Arr_oblivious_side_tag)1306 Comparison_result _compare_point_curve_end(const Point_2& pt, 1307 const X_monotone_curve_2& xcv, 1308 Arr_curve_end ce, 1309 Arr_oblivious_side_tag) const 1310 { 1311 Comparison_result res = 1312 m_self->compare_x_on_boundary_2_object() 1313 (pt, m_self->construct_vertex_at_curve_end_2_object()(xcv, ce)); 1314 return res; 1315 } 1316 1317 public: 1318 /*! Compare the relative x-positions of a point and a curve end. 1319 * \param pt The point 1320 * \param xcv The curve. 1321 * \param ce ARR_MIN_END if we refer to xcv's minimal end; 1322 * ARR_MAX_END if we refer to its maximal end. 1323 * \pre The curve end has a special boundary in y. 1324 * \return SMALLER if pt lies to the left of xcv; 1325 * LARGER if pt lies to the right xcv; 1326 * EQUAL in case of an overlap. 1327 */ operator()1328 Comparison_result operator()(const Point_2& pt, 1329 const X_monotone_curve_2& xcv, 1330 Arr_curve_end ce) const 1331 { 1332 Arr_parameter_space ps = m_self->parameter_space_in_y_2_object()(xcv, ce); 1333 1334 CGAL_precondition(ps != ARR_INTERIOR); 1335 1336 switch (ps) { 1337 1338 case ARR_BOTTOM_BOUNDARY: 1339 return _compare_point_curve_end(pt, xcv, ce, Bottom_side_category()); 1340 1341 case ARR_TOP_BOUNDARY: 1342 return _compare_point_curve_end(pt, xcv, ce, Top_side_category()); 1343 1344 case ARR_INTERIOR: 1345 // fall-through 1346 default: 1347 CGAL_error(); // never reached 1348 return CGAL::EQUAL; 1349 } 1350 } 1351 }; 1352 1353 /*! Obtain a Compare_x_point_curve_end_2 function object. */ compare_x_point_curve_end_2_object()1354 Compare_x_point_curve_end_2 compare_x_point_curve_end_2_object() const 1355 { return Compare_x_point_curve_end_2(this); } 1356 1357 /*! A functor that compares the x-coordinates of curve ends near the 1358 * boundary of the parameter space 1359 */ 1360 class Compare_x_curve_ends_2 { 1361 protected: 1362 //! The base traits. 1363 const Self* m_self; 1364 1365 /*! Constructor. 1366 * \param base The base traits class. It must be passed, to handle non 1367 * stateless traits objects, (which stores data). 1368 * The constructor is declared private to allow only the functor 1369 * obtaining function, which is a member of the nesting class, 1370 * constructing it. 1371 */ Compare_x_curve_ends_2(const Self * self)1372 Compare_x_curve_ends_2(const Self* self) : m_self(self) {} 1373 1374 //! Allow its functor obtaining function calling the private constructor. 1375 friend class Arr_traits_basic_adaptor_2<Base>; 1376 1377 protected: _compare_curve_ends_same_x(const X_monotone_curve_2 & xcv1,Arr_curve_end ce1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce2)1378 Comparison_result _compare_curve_ends_same_x(const X_monotone_curve_2& xcv1, 1379 Arr_curve_end ce1, 1380 const X_monotone_curve_2& xcv2, 1381 Arr_curve_end ce2) const 1382 { 1383 CGAL::Comparison_result res = CGAL::EQUAL; 1384 1385 CGAL::Arr_parameter_space loc1 = 1386 m_self->parameter_space_in_y_2_object()(xcv1, ce1); 1387 CGAL::Arr_parameter_space loc2 = 1388 m_self->parameter_space_in_y_2_object()(xcv2, ce2); 1389 bool vert1 = m_self->is_vertical_2_object()(xcv1); 1390 bool vert2 = m_self->is_vertical_2_object()(xcv2); 1391 1392 // now we are in the open case: ARR_MIN_END > vertical > ARR_MAX_END 1393 if (vert1) { 1394 if (!vert2) { 1395 res = ((ce2 == CGAL::ARR_MIN_END) ? CGAL::SMALLER : CGAL::LARGER); 1396 return res; 1397 } 1398 // both are vertical 1399 if (loc1 == loc2) { // both ends converge to the same infinity 1400 res = CGAL::EQUAL; 1401 return res; 1402 } 1403 res = (loc1 == CGAL::ARR_BOTTOM_BOUNDARY ? 1404 CGAL::SMALLER : CGAL::LARGER); 1405 return res; 1406 } 1407 1408 if (vert2) { 1409 res = ((ce1 == CGAL::ARR_MIN_END) ? CGAL::LARGER : CGAL::SMALLER); 1410 return res; 1411 } 1412 1413 // otherwise: both ends have asymptotic behaviour 1414 if (ce1 == ce2) { // both ends approach asymptote from one side 1415 if (loc1 == loc2) { // need special y-comparison 1416 res = m_self->compare_x_near_limit_2_object()(xcv1, xcv2, ce2); 1417 return res; 1418 } 1419 // else: order can be determined without y-comparison 1420 res = CGAL::EQUAL; 1421 return res; 1422 } 1423 // curve ends approach vertical asymptote (or singularity) from 1424 // different sides => no comparisons required 1425 res = ((ce1 == CGAL::ARR_MIN_END) ? CGAL::LARGER : CGAL::SMALLER); 1426 return res; 1427 } 1428 1429 // for open _compare_curve_ends(const X_monotone_curve_2 & xcv1,Arr_curve_end ce1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce2,Arr_open_side_tag)1430 Comparison_result _compare_curve_ends(const X_monotone_curve_2& xcv1, 1431 Arr_curve_end ce1, 1432 const X_monotone_curve_2& xcv2, 1433 Arr_curve_end ce2, 1434 Arr_open_side_tag) const { 1435 1436 Comparison_result res = 1437 m_self->compare_x_at_limit_2_object()(xcv1, ce1, xcv2, ce2); 1438 if (res == EQUAL) res = _compare_curve_ends_same_x(xcv1, ce1, xcv2, ce2); 1439 return res; 1440 } 1441 1442 // for contracted _compare_curve_ends(const X_monotone_curve_2 & xcv1,Arr_curve_end ce1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce2,Arr_contracted_side_tag)1443 Comparison_result _compare_curve_ends(const X_monotone_curve_2& xcv1, 1444 Arr_curve_end ce1, 1445 const X_monotone_curve_2& xcv2, 1446 Arr_curve_end ce2, 1447 Arr_contracted_side_tag) const { 1448 1449 Comparison_result res = 1450 m_self->compare_x_on_boundary_2_object()(xcv1, ce1, xcv2, ce2); 1451 if (res == EQUAL) res = _compare_curve_ends_same_x(xcv1, ce1, xcv2, ce2); 1452 return res; 1453 } 1454 1455 // for others _compare_curve_ends(const X_monotone_curve_2 & xcv1,Arr_curve_end ce1,const X_monotone_curve_2 & xcv2,Arr_curve_end ce2,Arr_oblivious_side_tag)1456 Comparison_result _compare_curve_ends(const X_monotone_curve_2& xcv1, 1457 Arr_curve_end ce1, 1458 const X_monotone_curve_2& xcv2, 1459 Arr_curve_end ce2, 1460 Arr_oblivious_side_tag) const 1461 { 1462 Comparison_result res = 1463 m_self->compare_x_on_boundary_2_object() 1464 (m_self->construct_vertex_at_curve_end_2_object()(xcv1, ce1), 1465 m_self->construct_vertex_at_curve_end_2_object()(xcv2, ce2)); 1466 return res; 1467 } 1468 1469 public: 1470 /*! Compare the relative x-positions of two curve ends. 1471 * \param xcv1 The first curve. 1472 * \param ind1 ARR_MIN_END if we refer to xcv1's minimal end; 1473 * ARR_MAX_END if we refer to its maximal end. 1474 * \param xcv2 The second curve. 1475 * \param ind2 ARR_MIN_END if we refer to xcv2's minimal end; 1476 * ARR_MAX_END if we refer to its maximal end. 1477 * \pre Both curve ends have a special boundary in y. 1478 * \return SMALLER if xcv1 lies to the left of xcv2; 1479 * LARGER if xcv1 lies to the right xcv2; 1480 * EQUAL in case of an overlap. 1481 */ operator()1482 Comparison_result operator()(const X_monotone_curve_2& xcv1, 1483 Arr_curve_end ce1, 1484 const X_monotone_curve_2& xcv2, 1485 Arr_curve_end ce2) const 1486 { 1487 bool first_open = !m_self->is_closed_2_object()(xcv1, ce1); 1488 bool second_open = !m_self->is_closed_2_object()(xcv2, ce2); 1489 1490 if (first_open) { 1491 if (second_open) 1492 return _compare_curve_ends(xcv1, ce1, xcv2, ce2, 1493 // both sides are open, so pick one 1494 Bottom_side_category()); 1495 1496 return CGAL::opposite 1497 (m_self->compare_x_point_curve_end_2_object() 1498 (m_self->construct_vertex_at_curve_end_2_object()(xcv2, ce2), 1499 xcv1, ce1)); 1500 } 1501 1502 if (second_open) 1503 return m_self->compare_x_point_curve_end_2_object() 1504 (m_self->construct_vertex_at_curve_end_2_object()(xcv1, ce1), 1505 xcv2, ce2); 1506 1507 return _compare_curve_ends(xcv1, ce1, xcv2, ce2, 1508 // both sides are non-open, so pick one 1509 Bottom_side_category()); 1510 } 1511 }; 1512 1513 /*! Obtain a Compare_x_curve_ends_2 function object. */ compare_x_curve_ends_2_object()1514 Compare_x_curve_ends_2 compare_x_curve_ends_2_object() const 1515 { return Compare_x_curve_ends_2(this); } 1516 1517 class Construct_vertex_at_curve_end_2 { 1518 protected: 1519 //! The base traits. 1520 const Self* m_self; 1521 1522 /*! Constructor. 1523 * \param base The base traits class. It must be passed, to handle non 1524 * stateless traits objects, (which stores data). 1525 * The constructor is declared private to allow only the functor 1526 * obtaining function, which is a member of the nesting class, 1527 * constructing it. 1528 */ Construct_vertex_at_curve_end_2(const Self * self)1529 Construct_vertex_at_curve_end_2(const Self* self) : m_self(self) {} 1530 1531 //! Allow its functor obtaining function calling the private constructor. 1532 friend class Arr_traits_basic_adaptor_2<Base>; 1533 1534 public: operator()1535 Point_2 operator()(const X_monotone_curve_2& xcv, Arr_curve_end ce) const 1536 { 1537 return (ce == ARR_MIN_END) ? 1538 m_self->construct_min_vertex_2_object()(xcv) : 1539 m_self->construct_max_vertex_2_object()(xcv); 1540 } 1541 }; 1542 1543 /*! Obtain a Construct_vertex_at_curve_end_2 function object. */ construct_vertex_at_curve_end_2_object()1544 Construct_vertex_at_curve_end_2 construct_vertex_at_curve_end_2_object() const 1545 { return Construct_vertex_at_curve_end_2(this); } 1546 1547 /*! A function object that determines whether a curve end is closed. */ 1548 class Is_closed_2 { 1549 protected: 1550 //! The self traits. 1551 const Self* m_self; 1552 1553 /*! Constructor. 1554 * \param self The traits class itself. It must be passed, to handle non 1555 * stateless traits objects, (which stores data). 1556 * The constructor is declared private to allow only the functor 1557 * obtaining function, which is a member of the nesting class, 1558 * constructing it. 1559 */ Is_closed_2(const Self * self)1560 Is_closed_2(const Self* self) : m_self(self) {} 1561 1562 //! Allow its functor obtaining function calling the private constructor. 1563 friend class Arr_traits_basic_adaptor_2<Base>; 1564 _is_closed(Arr_oblivious_side_tag)1565 inline bool _is_closed(Arr_oblivious_side_tag) const { return true; } 1566 _is_closed(Arr_open_side_tag)1567 inline bool _is_closed(Arr_open_side_tag) const { return false; } 1568 1569 inline _is_closed(const X_monotone_curve_2 & xcv,Arr_curve_end ce)1570 bool _is_closed(const X_monotone_curve_2& xcv, Arr_curve_end ce) const 1571 { 1572 Arr_parameter_space ps = m_self->parameter_space_in_x_2_object()(xcv, ce); 1573 if (ARR_INTERIOR == ps) 1574 ps = m_self->parameter_space_in_y_2_object()(xcv, ce); 1575 1576 switch (ps) { 1577 case ARR_LEFT_BOUNDARY: return _is_closed(Left_side_category()); 1578 case ARR_BOTTOM_BOUNDARY: return _is_closed(Bottom_side_category()); 1579 case ARR_TOP_BOUNDARY: return _is_closed(Top_side_category()); 1580 case ARR_RIGHT_BOUNDARY: return _is_closed(Right_side_category()); 1581 case ARR_INTERIOR: // fall-through 1582 default: return true; 1583 } 1584 } 1585 1586 public: 1587 /*! Is the end of an x-monotone curve bounded? 1588 * \param xcv The x-monotone curve. 1589 * \param ce The end of xcv identifier. 1590 * \return true is the curve end is bounded, and false otherwise 1591 */ operator()1592 bool operator()(const X_monotone_curve_2& xcv, Arr_curve_end ce) const 1593 { return _is_closed(xcv, ce); } 1594 }; 1595 1596 /*! Obtain a Is_closed_2 function object. */ is_closed_2_object()1597 Is_closed_2 is_closed_2_object() const 1598 { return Is_closed_2(this); } 1599 1600 //@} 1601 1602 /// \name Additional auxiliary functors. 1603 //@{ 1604 class Is_in_x_range_2 { 1605 public: 1606 /*! 1607 * Check whether the given point is in the x-range of the given x-monotone 1608 * curve. 1609 * \param xcv The x-monotone curve. 1610 * \param p The point. 1611 * \return true if x(xcv_left) <= x(p) <= x(xcv_right), false otherwise. 1612 */ operator()1613 bool operator()(const X_monotone_curve_2& xcv, const Point_2& p) const 1614 { 1615 Parameter_space_in_x_2 ps_x = m_self->parameter_space_in_x_2_object(); 1616 Parameter_space_in_y_2 ps_y = m_self->parameter_space_in_y_2_object(); 1617 Compare_x_2 compare_x = m_self->compare_x_2_object(); 1618 Compare_x_point_curve_end_2 1619 compare_x_point_curve_end = m_self->compare_x_point_curve_end_2_object(); 1620 1621 // Compare p to the position of the left end of the curve. 1622 // Note that if the left end of xcv lies at x boundary, p is obviously to 1623 // its right. 1624 Arr_parameter_space bx = ps_x(xcv, ARR_MIN_END); 1625 if (bx == ARR_INTERIOR) { 1626 Arr_parameter_space by = ps_y(xcv, ARR_MIN_END); 1627 1628 Comparison_result res = (by == ARR_INTERIOR) ? 1629 // The left endpoint of xcv is a normal point. 1630 compare_x(p, m_self->construct_min_vertex_2_object()(xcv)) : 1631 // The left end of xcv lies at y boundary. 1632 compare_x_point_curve_end(p, xcv, ARR_MIN_END); 1633 1634 // If p is to the left of the x-range return false. 1635 // If p is equal, return true. 1636 if (res == SMALLER) return false; 1637 else if (res == EQUAL) return true; 1638 } 1639 1640 // If necessary, compare p to the right end of the curve. 1641 // Note that if this end lies at x boundary, p is obviously to its left. 1642 bx = ps_x(xcv, ARR_MAX_END); 1643 if (bx != ARR_INTERIOR) return true; 1644 1645 Arr_parameter_space by = ps_y(xcv, ARR_MAX_END); 1646 1647 Comparison_result res = (by == ARR_INTERIOR) ? 1648 // The right endpoint of xcv is a normal point. 1649 compare_x(p, m_self->construct_max_vertex_2_object()(xcv)) : 1650 // The right end of xcv lies at y boundary: 1651 compare_x_point_curve_end(p, xcv, ARR_MAX_END); 1652 1653 return (res != LARGER); 1654 } 1655 1656 /*! 1657 * Check whether the x-ranges of the given x-monotone curves overlap. 1658 * \param xcv1 The first x-monotone curve. 1659 * \param xcv2 The second x-monotone curve. 1660 * \return (true) if there is an overlap in the x-ranges of the given 1661 * curves; (false) otherwise. 1662 */ operator()1663 bool operator()(const X_monotone_curve_2& xcv1, 1664 const X_monotone_curve_2& xcv2) const 1665 { 1666 Parameter_space_in_x_2 ps_x = m_self->parameter_space_in_x_2_object(); 1667 Parameter_space_in_y_2 ps_y = m_self->parameter_space_in_y_2_object(); 1668 Compare_x_2 compare_x = m_self->compare_x_2_object(); 1669 Construct_min_vertex_2 min_vertex = 1670 m_self->construct_min_vertex_2_object(); 1671 Construct_max_vertex_2 max_vertex = 1672 m_self->construct_max_vertex_2_object(); 1673 Compare_x_point_curve_end_2 compare_x_point_curve_end = 1674 m_self->compare_x_point_curve_end_2_object(); 1675 Compare_x_curve_ends_2 compare_x_curve_ends = 1676 m_self->compare_x_curve_ends_2_object(); 1677 1678 // Locate the rightmost of the two left endpoints of the two curves. 1679 // Note that we guard for curve ends with special boundary. 1680 Arr_parameter_space ps_x1, ps_y1; 1681 Arr_parameter_space ps_x2, ps_y2; 1682 const X_monotone_curve_2* xcv_left; 1683 Arr_parameter_space by_left; 1684 Comparison_result res; 1685 1686 ps_x1 = ps_x(xcv1, ARR_MIN_END); 1687 ps_x2 = ps_x(xcv2, ARR_MIN_END); 1688 1689 if (ps_x1 != ARR_INTERIOR) { 1690 // If both curves are defined at x boundary, they obviously overlap in 1691 // their x-ranges. 1692 if (ps_x2 != ARR_INTERIOR) return true; 1693 1694 // As xcv2 is not defined at x boundary, take its left end as the 1695 // rightmost of the two left curve ends. 1696 xcv_left = &xcv2; 1697 by_left = ps_y(xcv2, ARR_MIN_END); 1698 } 1699 else if (ps_x2 != ARR_INTERIOR) { 1700 // As xcv1 is not defined at x boundary, take its left end as the 1701 // rightmost of the two left curve ends. 1702 xcv_left = &xcv1; 1703 by_left = ps_y(xcv1, ARR_MIN_END); 1704 } 1705 else { 1706 // Compare the (finite) x-coordinates of the two left ends. 1707 // We take special care of the case of boundaries in y. 1708 ps_y1 = ps_y(xcv1, ARR_MIN_END); 1709 ps_y2 = ps_y(xcv2, ARR_MIN_END); 1710 1711 if (ps_y1 == ARR_INTERIOR) { 1712 res = (ps_y2 == ARR_INTERIOR) ? 1713 compare_x(min_vertex(xcv1), min_vertex(xcv2)) : 1714 compare_x_point_curve_end(min_vertex(xcv1), xcv2, ARR_MIN_END); 1715 } 1716 else { 1717 res = (ps_y2 == ARR_INTERIOR) ? 1718 opposite(compare_x_point_curve_end(min_vertex(xcv2), xcv1, 1719 ARR_MIN_END)): 1720 compare_x_curve_ends(xcv1, ARR_MIN_END, xcv2, ARR_MIN_END); 1721 } 1722 1723 if (res == LARGER) { 1724 xcv_left = &xcv1; 1725 by_left = ps_y1; 1726 } 1727 else { 1728 xcv_left = &xcv2; 1729 by_left = ps_y2; 1730 } 1731 } 1732 1733 // Locate the leftmost of the two right endpoints of the two curves. 1734 // Note that we guard for curve ends with special boundary. 1735 const X_monotone_curve_2* xcv_right; 1736 Arr_parameter_space by_right; 1737 1738 ps_x1 = ps_x(xcv1, ARR_MAX_END); 1739 ps_x2 = ps_x(xcv2, ARR_MAX_END); 1740 1741 if (ps_x1 != ARR_INTERIOR) { 1742 // If both curves are defined at x boundary, they obviously overlap in 1743 // their x-ranges. 1744 if (ps_x2 != ARR_INTERIOR) return true; 1745 1746 // As xcv2 is not defined at x boundary, take its right end as the 1747 // leftmost of the two right curve ends. 1748 xcv_right = &xcv2; 1749 by_right = ps_y(xcv2, ARR_MAX_END); 1750 } 1751 else if (ps_x2 != ARR_INTERIOR) { 1752 // As xcv1 is not defined at x boundary, take its right end as the 1753 // leftmost of the two right curve ends. 1754 xcv_right = &xcv1; 1755 by_right = ps_y(xcv1, ARR_MAX_END); 1756 } 1757 else { 1758 // Compare the (finite) x-coordinates of the two right ends. 1759 // We take special care of the case of boundaries in y. 1760 ps_y1 = ps_y(xcv1, ARR_MAX_END); 1761 ps_y2 = ps_y(xcv2, ARR_MAX_END); 1762 1763 if (ps_y1 == ARR_INTERIOR) { 1764 res = (ps_y2 == ARR_INTERIOR) ? 1765 compare_x(max_vertex(xcv1), max_vertex(xcv2)) : 1766 compare_x_point_curve_end(max_vertex(xcv1), xcv2, ARR_MAX_END); 1767 } 1768 else { 1769 res = (ps_y2 == ARR_INTERIOR) ? 1770 opposite(compare_x_point_curve_end(max_vertex(xcv2), xcv1, 1771 ARR_MAX_END)): 1772 compare_x_curve_ends(xcv1, ARR_MAX_END, xcv2, ARR_MAX_END); 1773 } 1774 1775 if (res == SMALLER) { 1776 xcv_right = &xcv1; 1777 by_right = ps_y1; 1778 } 1779 else { 1780 xcv_right = &xcv2; 1781 by_right = ps_y2; 1782 } 1783 } 1784 1785 // Now compare the (finite) x-coordiates of the left end of xcv_left and 1786 // the right end of xcv_right. 1787 if (by_left == ARR_INTERIOR) { 1788 res = (by_right == ARR_INTERIOR) ? 1789 compare_x(min_vertex(*xcv_left), max_vertex(*xcv_right)) : 1790 compare_x_point_curve_end(min_vertex(*xcv_left), *xcv_right, 1791 ARR_MAX_END); 1792 } 1793 else { 1794 res = (by_right == ARR_INTERIOR) ? 1795 opposite(compare_x_point_curve_end(max_vertex(*xcv_right), 1796 *xcv_left, ARR_MIN_END)) : 1797 compare_x_curve_ends(*xcv_left, ARR_MIN_END, *xcv_right, ARR_MAX_END); 1798 } 1799 1800 // The two curves overlap in their x-range if and only if the left end 1801 // of xcv_left is not to the right if the right end of xcv_right. 1802 return (res != LARGER); 1803 } 1804 1805 protected: 1806 //! The traits itself. 1807 const Self* m_self; 1808 1809 /*! Constructor. 1810 * \param self The traits class itself. It must be passed, to handle non 1811 * stateless traits objects, (which stores data). 1812 * The constructor is declared private to allow only the functor 1813 * obtaining function, which is a member of the nesting class, 1814 * constructing it. 1815 */ Is_in_x_range_2(const Self * self)1816 Is_in_x_range_2(const Self* self) : m_self(self) {} 1817 1818 //! Allow its functor obtaining function calling the private constructor. 1819 friend class Arr_traits_basic_adaptor_2<Base>; 1820 }; 1821 1822 /*! Obtain an Is_in_x_range_2 function object. */ is_in_x_range_2_object()1823 Is_in_x_range_2 is_in_x_range_2_object() const 1824 { return Is_in_x_range_2(this); } 1825 1826 class Compare_y_position_2 { 1827 public: 1828 /*! 1829 * Obtain the relative of two x-monotone curves with overlapping x-ranges 1830 * that are disjoint in their interiors. 1831 * \param xcv1 The first x-monotone curve. 1832 * \param xcv2 The second x-monotone curve. 1833 * \pre The x-ranges of the two curves overlap. 1834 * \return SMALLER if xcv1 lies below xcv2; 1835 * LARGER if xcv1 lies above xcv2; 1836 * EQUAL in case the common x-range is a single point. 1837 */ operator()1838 Comparison_result operator()(const X_monotone_curve_2& xcv1, 1839 const X_monotone_curve_2& xcv2) const 1840 { 1841 CGAL_precondition_code( 1842 Is_in_x_range_2 is_in_x_range = m_self->is_in_x_range_2_object(); 1843 ); 1844 CGAL_precondition(is_in_x_range(xcv1, xcv2)); 1845 1846 /* The traits class which the basic traits adaptor accepts as a template 1847 * parameter is a model of the ArrangementBasicTraits_2 concept so it 1848 * needs not to support intersections at all, therefor it is complicated 1849 * to check if the x-curves are disjoint in their interiors. Moreover, 1850 * compare_y_position functor is called only from the arrangement class 1851 * itself (and some related point-location algorithms), and used only 1852 * for two curves associated with two arrangement halfedges. These curves 1853 * are guaranteed to be interior-disjoint. So, it seems that there is no 1854 * gain in checking the precondition, and it is left unimplemented. 1855 */ 1856 1857 Parameter_space_in_x_2 ps_x = m_self->parameter_space_in_x_2_object(); 1858 Parameter_space_in_y_2 ps_y = m_self->parameter_space_in_y_2_object(); 1859 Compare_y_at_x_2 compare_y_at_x = m_self->compare_y_at_x_2_object(); 1860 Construct_min_vertex_2 min_vertex = 1861 m_self->construct_min_vertex_2_object(); 1862 Compare_x_point_curve_end_2 1863 compare_x_point_curve_end = m_self->compare_x_point_curve_end_2_object(); 1864 Compare_x_curve_ends_2 1865 compare_x_curve_ends = m_self->compare_x_curve_ends_2_object(); 1866 Compare_y_near_boundary_2 1867 compare_y_near_bnd = m_self->compare_y_near_boundary_2_object(); 1868 1869 // First check whether any of the curves is defined at x boundary. 1870 const Arr_parameter_space ps_x1 = ps_x(xcv1, ARR_MIN_END); 1871 const Arr_parameter_space ps_x2 = ps_x(xcv2, ARR_MIN_END); 1872 Comparison_result res; 1873 1874 CGAL_assertion((ps_x1 != ARR_RIGHT_BOUNDARY) && 1875 (ps_x2 != ARR_RIGHT_BOUNDARY)); 1876 1877 if (ps_x1 != ARR_INTERIOR) { 1878 if (ps_x2 != ARR_INTERIOR) 1879 // Compare the relative position of the curves at x boundary. 1880 return (compare_y_near_bnd(xcv1, xcv2, ARR_MIN_END)); 1881 1882 // Check if the left end of xcv2 lies at y boundary. 1883 const Arr_parameter_space ps_y2 = ps_y(xcv2, ARR_MIN_END); 1884 1885 // if xcv2 is below xcv1, return LARGER. 1886 // if xcv2 is above xcv1, return SMALLER. 1887 if (ps_y2 == ARR_BOTTOM_BOUNDARY) return (LARGER); 1888 else if (ps_y2 == ARR_TOP_BOUNDARY) return (SMALLER); 1889 1890 // Compare the position of the left end of xcv2 (which is a normal 1891 // point) to xcv1. 1892 res = compare_y_at_x(min_vertex(xcv2), xcv1); 1893 1894 // Swap the result. 1895 if (res == EQUAL) return (EQUAL); 1896 return ((res == SMALLER) ? LARGER : SMALLER); 1897 } 1898 1899 if (ps_x2 != ARR_INTERIOR) { 1900 // Check if the left end of xcv1 lies at y boundary. 1901 const Arr_parameter_space ps_y1 = ps_y(xcv1, ARR_MIN_END); 1902 1903 // If xcv1 is below xcv2 return SMALLER. 1904 // If xcv1 is above xcv2 return LARGER. 1905 if (ps_y1 == ARR_BOTTOM_BOUNDARY) return (SMALLER); 1906 else if (ps_y1 == ARR_TOP_BOUNDARY) return (LARGER); 1907 1908 // Compare the position of the left end of xcv1 (which is a normal 1909 // point) to xcv2. 1910 res = compare_y_at_x(min_vertex(xcv1), xcv2); 1911 return (res); 1912 } 1913 1914 // Check if the left curve end lies at y = +/- oo. 1915 const Arr_parameter_space ps_y1 = ps_y(xcv1, ARR_MIN_END); 1916 const Arr_parameter_space ps_y2 = ps_y(xcv2, ARR_MIN_END); 1917 Comparison_result l_res; 1918 1919 if (ps_y1 != ARR_INTERIOR) { 1920 if (ps_y2 != ARR_INTERIOR) { 1921 // The curve ends have special boundary with oposite signs in y, 1922 // we readily know their relative position (recall that they do not 1923 // instersect). 1924 if ((ps_y1 == ARR_BOTTOM_BOUNDARY) && (ps_y2 == ARR_TOP_BOUNDARY)) 1925 return (SMALLER); 1926 else if ((ps_y1 == ARR_TOP_BOUNDARY) && (ps_y2 == ARR_BOTTOM_BOUNDARY)) 1927 return (LARGER); 1928 1929 // Both curves have vertical asymptotes with the same sign in y. 1930 // Check which asymptote is the rightmost. Note that in this case 1931 // the vertical asymptotes cannot be equal. 1932 l_res = compare_x_curve_ends(xcv1, ARR_MIN_END, xcv2, ARR_MIN_END); 1933 CGAL_assertion(l_res != EQUAL); 1934 1935 if (ps_y1 == ARR_TOP_BOUNDARY) return (l_res); 1936 else return ((l_res == SMALLER) ? LARGER : SMALLER); 1937 } 1938 1939 // xcv1 has a vertical asymptote and xcv2 has a normal left endpoint. 1940 // Compare the x-positions of this endpoint and the asymptote. 1941 const Point_2& left2 = min_vertex(xcv2); 1942 1943 l_res = compare_x_point_curve_end(left2, xcv1, ARR_MIN_END); 1944 if (l_res == LARGER) { 1945 // left2 lies in the x-range of xcv1, so it is safe to compare: 1946 res = compare_y_at_x(left2, xcv1); 1947 1948 // Swap the result. 1949 if (res == EQUAL) return (EQUAL); 1950 return ((res == SMALLER) ? LARGER : SMALLER); 1951 } 1952 return ((ps_y1 == ARR_BOTTOM_BOUNDARY) ? SMALLER : LARGER); 1953 } 1954 1955 if (ps_y2 != ARR_INTERIOR) { 1956 // xcv2 has a vertical asymptote and xcv1 has a normal left endpoint. 1957 // Compare the x-positions of this endpoint and the asymptote. 1958 const Point_2& left1 = min_vertex(xcv1); 1959 1960 l_res = compare_x_point_curve_end(left1, xcv2, ARR_MIN_END); 1961 // left1 lies in the x-range of xcv2, so it is safe to compare: 1962 if (l_res == LARGER) return (compare_y_at_x(left1, xcv2)); 1963 else return (ps_y2 == ARR_BOTTOM_BOUNDARY) ? LARGER : SMALLER; 1964 } 1965 1966 // In this case we compare two normal points. 1967 Compare_xy_2 compare_xy = m_self->compare_xy_2_object(); 1968 Compare_y_at_x_right_2 compare_y_at_x_right = 1969 m_self->compare_y_at_x_right_2_object(); 1970 1971 // Obtain the left endpoints of xcv1 and xcv2. 1972 const Point_2& left1 = min_vertex(xcv1); 1973 const Point_2& left2 = min_vertex(xcv2); 1974 1975 // Locate the rightmost point of left1 and left2 and compare its position 1976 // to the other curve. 1977 l_res = compare_xy(left1, left2); 1978 1979 if (l_res != SMALLER) { 1980 // left1 is in the x-range of xcv2: 1981 res = compare_y_at_x(left1, xcv2); 1982 if (res == EQUAL) 1983 // The two curves intersect at left1. If both curves are defined to 1984 // the right of the reference point, we can compare them to its 1985 // right. Otherwise, their share a common endpoint (which is the only 1986 // overlap in their x-ranges) and are really equal. 1987 if (l_res == EQUAL) res = compare_y_at_x_right(xcv1, xcv2, left1); 1988 return (res); 1989 } 1990 // left2 is in the x-range of xcv1: 1991 res = compare_y_at_x(left2, xcv1); 1992 1993 // The two curves share a common endpoint (which is the only overlap 1994 // in their x-ranges) and are really equal. 1995 if (res == EQUAL) return (EQUAL); 1996 1997 // Swap the result: 1998 return ((res == SMALLER) ? LARGER : SMALLER); 1999 } 2000 2001 protected: 2002 //! The base traits. 2003 const Self* m_self; 2004 2005 /*! Constructor. 2006 * \param base The base traits class. It must be passed, to handle non 2007 * stateless traits objects, (which stores data). 2008 * The constructor is declared private to allow only the functor 2009 * obtaining function, which is a member of the nesting class, 2010 * constructing it. 2011 */ Compare_y_position_2(const Self * self)2012 Compare_y_position_2(const Self* self) : m_self(self) {} 2013 2014 //! Allow its functor obtaining function calling the private constructor. 2015 friend class Arr_traits_basic_adaptor_2<Base>; 2016 }; 2017 2018 /*! Obtain a Compare_y_position_2 function object. */ compare_y_position_2_object()2019 Compare_y_position_2 compare_y_position_2_object() const 2020 { return Compare_y_position_2(this); } 2021 2022 class Is_between_cw_2 { 2023 public: 2024 /*! 2025 * Check whether the given query curve is encountered when rotating the 2026 * first curve in a clockwise direction around a given point until reaching 2027 * the second curve. 2028 * \param xcv The query curve. 2029 * \param xcv_to_right Is xcv directed from left to right (that is, the 2030 * common vertex is xcv's left endpoint). 2031 * \param xcv1 The first curve. 2032 * \param xcv1_to_right Is xcv1 directed from left to right. 2033 * \param xcv2 The second curve. 2034 * \param xcv2_to_right Is xcv2 directed from left to right. 2035 * \param p The point around which we rotate xcv1. 2036 * \param xcv_equal_xcv1 Output: does xcv equal xcv1. 2037 * \param xcv_equal_xcv2 Output: does xcv equal xcv2. 2038 * \pre p is an end-point of all three curves. 2039 * \return (true) if xcv is between xcv1 and xcv2; (false) otherwise. 2040 * If xcv overlaps xcv1 or xcv2 the result is always (false). 2041 * If xcv1 and xcv2 overlap, the result is (true), unless xcv 2042 * also overlaps them. 2043 */ operator()2044 bool operator()(const X_monotone_curve_2& xcv, bool xcv_to_right, 2045 const X_monotone_curve_2& xcv1, bool xcv1_to_right, 2046 const X_monotone_curve_2& xcv2, bool xcv2_to_right, 2047 const Point_2& p, 2048 bool& xcv_equal_xcv1, 2049 bool& xcv_equal_xcv2) const 2050 { 2051 Compare_y_at_x_left_2 compare_y_at_x_left = 2052 m_self->compare_y_at_x_left_2_object(); 2053 Compare_y_at_x_right_2 compare_y_at_x_right = 2054 m_self->compare_y_at_x_right_2_object(); 2055 2056 // Initialize output flags. 2057 xcv_equal_xcv1 = false; 2058 xcv_equal_xcv2 = false; 2059 2060 // Take care of the general 4 cases: 2061 Comparison_result l_res, r_res; 2062 Comparison_result res1, res2; 2063 2064 if (!xcv1_to_right && !xcv2_to_right) { 2065 // Case 1: Both xcv1 and xcv2 are defined to the left of p. 2066 l_res = compare_y_at_x_left(xcv1, xcv2, p); 2067 2068 if (l_res == LARGER) { 2069 // Case 1(a) : xcv1 is above xcv2. 2070 if (!xcv_to_right) { 2071 res1 = compare_y_at_x_left(xcv1, xcv, p); 2072 res2 = compare_y_at_x_left(xcv2, xcv, p); 2073 if (res1 == EQUAL) xcv_equal_xcv1 = true; 2074 if (res2 == EQUAL) xcv_equal_xcv2 = true; 2075 return (res1 == SMALLER || res2 == LARGER); 2076 } 2077 return true; 2078 } 2079 2080 if (l_res == SMALLER) { 2081 // Case 1(b): xcv1 is below xcv2. 2082 if (!xcv_to_right) { 2083 res1 = compare_y_at_x_left(xcv1, xcv, p); 2084 res2 = compare_y_at_x_left(xcv2, xcv, p); 2085 if (res1 == EQUAL) xcv_equal_xcv1 = true; 2086 if (res2 == EQUAL) xcv_equal_xcv2 = true; 2087 return (res1 == SMALLER && res2 == LARGER); 2088 } 2089 return false; 2090 } 2091 2092 // Overlapping segments. 2093 if (!xcv_to_right) { 2094 res1 = compare_y_at_x_left(xcv1, xcv, p); 2095 if (res1 == EQUAL) { 2096 xcv_equal_xcv1 = true; 2097 xcv_equal_xcv2 = true; 2098 return false; 2099 } 2100 return true; 2101 } 2102 return true; 2103 } 2104 2105 if (xcv1_to_right && xcv2_to_right) { 2106 // Case 2: Both xcv1 and xcv2 are defined to the right of p. 2107 r_res = compare_y_at_x_right(xcv1, xcv2, p); 2108 2109 if (r_res == LARGER) { 2110 // Case 2(a) : xcv1 is above xcv2. 2111 if (xcv_to_right) { 2112 res1 = compare_y_at_x_right(xcv1, xcv, p); 2113 res2 = compare_y_at_x_right(xcv2, xcv, p); 2114 if (res1 == EQUAL) xcv_equal_xcv1 = true; 2115 if (res2 == EQUAL) xcv_equal_xcv2 = true; 2116 return (res1 == LARGER && res2 == SMALLER); 2117 } 2118 return false; 2119 } 2120 2121 if (r_res == SMALLER) { 2122 // Case 2(b): xcv1 is below xcv2. 2123 if (xcv_to_right) { 2124 res1 = compare_y_at_x_right(xcv1, xcv, p); 2125 res2 = compare_y_at_x_right(xcv2, xcv, p); 2126 if (res1 == EQUAL) xcv_equal_xcv1 = true; 2127 if (res2 == EQUAL) xcv_equal_xcv2 = true; 2128 return ((res1 == LARGER) || (res2 == SMALLER)); 2129 } 2130 return true; 2131 } 2132 2133 // Overlapping segments. 2134 if (xcv_to_right) { 2135 res1 = compare_y_at_x_right(xcv1, xcv, p); 2136 if (res1 == EQUAL) { 2137 xcv_equal_xcv1 = true; 2138 xcv_equal_xcv2 = true; 2139 return false; 2140 } 2141 return true; 2142 } 2143 return true; 2144 } 2145 2146 if (!xcv1_to_right && xcv2_to_right) { 2147 // Case 3: xcv1 is defined to the left of p, and xcv2 to its right. 2148 if (!xcv_to_right) { 2149 res1 = compare_y_at_x_left(xcv1, xcv, p); 2150 if (res1 == EQUAL) xcv_equal_xcv1 = true; 2151 return (res1 == SMALLER); 2152 } 2153 2154 res2 = compare_y_at_x_right(xcv2, xcv, p); 2155 if (res2 == EQUAL) xcv_equal_xcv2 = true; 2156 return (res2 == SMALLER); 2157 } 2158 2159 CGAL_assertion(xcv1_to_right && !xcv2_to_right); 2160 2161 // Case 4: xcv1 is defined to the right of p, and xcv2 to its left. 2162 if (xcv_to_right) { 2163 res1 = compare_y_at_x_right(xcv1, xcv, p); 2164 if (res1 == EQUAL) xcv_equal_xcv1 = true; 2165 return (res1 == LARGER); 2166 } 2167 2168 res2 = compare_y_at_x_left(xcv2, xcv, p); 2169 if (res2 == EQUAL) xcv_equal_xcv2 = true; 2170 return (res2 == LARGER); 2171 } 2172 2173 protected: 2174 //! The base traits. 2175 const Self* m_self; 2176 2177 /*! Constructor. 2178 * \param base The base traits class. It must be passed, to handle non 2179 * stateless traits objects, (which stores data). 2180 * The constructor is declared private to allow only the functor 2181 * obtaining function, which is a member of the nesting class, 2182 * constructing it. 2183 */ Is_between_cw_2(const Self * self)2184 Is_between_cw_2(const Self* self) : m_self(self) {} 2185 2186 //! Allow its functor obtaining function calling the private constructor. 2187 friend class Arr_traits_basic_adaptor_2<Base>; 2188 }; 2189 2190 /*! Obtain an Is_between_cw_2 function object. */ is_between_cw_2_object()2191 Is_between_cw_2 is_between_cw_2_object() const 2192 { return Is_between_cw_2(this); } 2193 2194 class Compare_cw_around_point_2 { 2195 public: 2196 /*! 2197 * Compare the two interior disjoint x-monotone curves in a clockwise 2198 * order around their common endpoint. 2199 * \param xcv1 The first curve. 2200 * \param xcv1_to_right Is xcv1 directed from left to right. 2201 * \param xcv2 The second curve. 2202 * \param xcv2_to_right Is xcv2 directed from left to right. 2203 * \param p The common endpoint. 2204 * \param from_top (true) if we start from 12 o'clock, 2205 * (false) if we start from 6 o'clock. 2206 * \pre The point p is an endpoint of both curves. 2207 * \return SMALLER if we encounter xcv1 before xcv2; 2208 * LARGER if we encounter xcv2 before xcv1; 2209 * EQUAL otherwise. 2210 */ operator()2211 Comparison_result operator()(const X_monotone_curve_2& xcv1, 2212 bool xcv1_to_right, 2213 const X_monotone_curve_2& xcv2, 2214 bool xcv2_to_right, 2215 const Point_2& p, 2216 bool from_top = true) const 2217 { 2218 // Act according to where xcv1 and xcv2 lie. 2219 if (!xcv1_to_right && !xcv2_to_right) 2220 // Both are defined to the left of p, and we encounter xcv1 before 2221 // xcv2 if it is below xcv2: 2222 return (m_self->compare_y_at_x_left_2_object()(xcv1, xcv2, p)); 2223 2224 if (xcv1_to_right && xcv2_to_right) 2225 // Both are defined to the right of p, and we encounter xcv1 before 2226 // xcv2 if it is above xcv2. We therefore reverse the order of the 2227 // curves when we invoke compare_y_at_x_right: 2228 return (m_self->compare_y_at_x_right_2_object()(xcv2, xcv1, p)); 2229 2230 if (!xcv1_to_right && xcv2_to_right) 2231 // If we start from the top, we encounter the right curve (which 2232 // is xcv2) first. If we start from the bottom, we encounter xcv1 first. 2233 return (from_top ? LARGER : SMALLER); 2234 2235 CGAL_assertion(xcv1_to_right && !xcv2_to_right); 2236 2237 // If we start from the top, we encounter the right curve (which 2238 // is xcv1) first. If we start from the bottom, we encounter xcv2 first. 2239 return (from_top ? SMALLER : LARGER); 2240 } 2241 2242 protected: 2243 //! The base traits. 2244 const Self* m_self; 2245 2246 /*! Constructor. 2247 * \param base The base traits class. It must be passed, to handle non 2248 * stateless traits objects, (which stores data). 2249 * The constructor is declared private to allow only the functor 2250 * obtaining function, which is a member of the nesting class, 2251 * constructing it. 2252 */ Compare_cw_around_point_2(const Self * self)2253 Compare_cw_around_point_2(const Self* self) : m_self(self) {} 2254 2255 //! Allow its functor obtaining function calling the private constructor. 2256 friend class Arr_traits_basic_adaptor_2<Base>; 2257 }; 2258 2259 /*! Obtain a Compare_cw_around_point_2 function object. */ compare_cw_around_point_2_object()2260 Compare_cw_around_point_2 compare_cw_around_point_2_object() const 2261 { return Compare_cw_around_point_2(this); } 2262 //@} 2263 }; 2264 2265 /*! \class 2266 * A traits-class adaptor that extends the basic traits-class interface. 2267 */ 2268 template <class ArrangementTraits_> 2269 class Arr_traits_adaptor_2 : 2270 public Arr_traits_basic_adaptor_2<ArrangementTraits_> 2271 { 2272 public: 2273 // Traits-class geometric types. 2274 typedef ArrangementTraits_ Base_traits_2; 2275 typedef Arr_traits_basic_adaptor_2<Base_traits_2> Base; 2276 typedef Arr_traits_adaptor_2<Base_traits_2> Self; 2277 2278 typedef typename Base_traits_2::Curve_2 Curve_2; 2279 typedef typename Base::X_monotone_curve_2 X_monotone_curve_2; 2280 typedef typename Base::Point_2 Point_2; 2281 typedef typename Base::Multiplicity Multiplicity; 2282 2283 // Categories. 2284 typedef typename Base::Has_left_category Has_left_category; 2285 typedef typename Base::Has_merge_category Has_merge_category; 2286 typedef typename Base::Has_do_intersect_category Has_do_intersect_category; 2287 2288 typedef typename Base::Left_side_category Left_side_category; 2289 typedef typename Base::Bottom_side_category Bottom_side_category; 2290 typedef typename Base::Top_side_category Top_side_category; 2291 typedef typename Base::Right_side_category Right_side_category; 2292 2293 typedef typename Base::Are_all_sides_oblivious_category 2294 Are_all_sides_oblivious_category; 2295 2296 /// \name Construction. 2297 //@{ 2298 /*! Default constructor. */ Arr_traits_adaptor_2()2299 Arr_traits_adaptor_2() : Base() {} 2300 2301 /*! Constructor from a base-traits class. */ Arr_traits_adaptor_2(const Base_traits_2 & traits)2302 Arr_traits_adaptor_2(const Base_traits_2& traits) : Base(traits) {} 2303 //@} 2304 2305 // Inherited functors: 2306 typedef typename Base::Compare_x_2 Compare_x_2; 2307 // typedef typename Base::Compare_xy_2 Compare_xy_2; 2308 typedef typename Base::Construct_min_vertex_2 Construct_min_vertex_2; 2309 typedef typename Base::Construct_max_vertex_2 Construct_max_vertex_2; 2310 typedef typename Base::Is_vertical_2 Is_vertical_2; 2311 typedef typename Base::Compare_y_at_x_2 Compare_y_at_x_2; 2312 typedef typename Base::Compare_y_at_x_right_2 Compare_y_at_x_right_2; 2313 typedef typename Base::Compare_y_at_x_left_2 Compare_y_at_x_left_2; 2314 typedef typename Base::Equal_2 Equal_2; 2315 2316 // Note that the basic adaptor does not have to support these functors: 2317 typedef typename Base_traits_2::Make_x_monotone_2 Make_x_monotone_2; 2318 typedef typename Base_traits_2::Split_2 Split_2; 2319 typedef typename Base_traits_2::Intersect_2 Intersect_2; 2320 2321 /// \name Overriden functors. 2322 //@{ 2323 2324 /*! A functor that compares two points or two x-monotone curves 2325 * lexigoraphically. Twp points are compared firest by their x-coordinates, 2326 * then by their y-coordinates. Two curves are compared first their left-most 2327 * endpoint, then by the graphs, and finally by their right-most endpoint. 2328 */ 2329 class Compare_xy_2 { 2330 typedef std::pair<Point_2, Multiplicity> Intersection_point; 2331 typedef boost::variant<Intersection_point, X_monotone_curve_2> 2332 Intersection_result; 2333 2334 public: 2335 /*! Compare two points lexigoraphically: by x, then by y. 2336 * \param p1 the first point. 2337 * \param p2 the second point. 2338 * \return SMALLER - x(p1) < x(p2); 2339 * SMALLER - x(p1) = x(p2) and y(p1) < y(p2); 2340 * EQUAL - x(p1) = x(p2) and y(p1) = y(p2); 2341 * LARGER - x(p1) = x(p2) and y(p1) > y(p2); 2342 * LARGER - x(p1) > x(p2). 2343 * \pre p1 does not lie on the boundary. 2344 * \pre p2 does not lie on the boundary. 2345 */ operator()2346 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 2347 { 2348 Base base(m_self); 2349 return base.compare_xy_2_object()(p1, p2); 2350 } 2351 2352 /*! Compare two x-monotone curves lexigoraphically. 2353 * Input: C1, C2, intersections = empty 2354 * compare(C1, C2, intersections) 2355 * Compare the left-most points of C1 and C2. 2356 * If not equal return the comparison result. 2357 * Otherwise (the left-most points are equal) 2358 * Compare C1 and C2 to the right of the point. 2359 * If not equal return the comparison result. 2360 * Otherwise (they overlap) 2361 * If intersection is empty, compute the intersections, 2362 * Remove the first overlapping section from c1, c2, and intersections. 2363 * If intersections is empty 2364 * Compare the right-most point and return the result. 2365 * return compare(C1, C2, intersections). 2366 */ operator()2367 Comparison_result operator()(const X_monotone_curve_2& c1, 2368 const X_monotone_curve_2& c2) const 2369 { 2370 std::list<Intersection_result> intersections; 2371 return operator()(c1, c2, intersections, 2372 Are_all_sides_oblivious_category()); 2373 } 2374 2375 protected: 2376 //! The base traits. 2377 const Self& m_self; 2378 2379 /*! Constructor. 2380 * \param trait The base traits class. It must be passed, to handle non 2381 * stateless traits objects, (which stores data). 2382 * The constructor is declared private to allow only the functor 2383 * obtaining function, which is a member of the nesting class, 2384 * constructing it. 2385 */ Compare_xy_2(const Self & self)2386 Compare_xy_2(const Self& self) : m_self(self) {} 2387 2388 //! Allow its functor obtaining function calling the private constructor. 2389 friend class Arr_traits_adaptor_2<Base_traits_2>; 2390 2391 /// Point-curve 2392 //@{ 2393 /*! Compare a point and a curve end. 2394 * Dispatch calls to traits that handle open and close boundaries, resp. 2395 * The only reason for this dispatcher is the poor choice of different 2396 * names for the Traits functors that handle close and open boundaries: 2397 * Open boundary traits use: Compare_x_at_limit_2 2398 * Close boundary traits use: Compare_x_on_boundary_2 2399 */ cmp_x_on_bnd(const Point_2 & p,const X_monotone_curve_2 & c,Arr_curve_end ce)2400 Comparison_result cmp_x_on_bnd(const Point_2& p, 2401 const X_monotone_curve_2& c, 2402 Arr_curve_end ce) const 2403 { 2404 // The complete code would need to check whether ce is bottom or top and 2405 // use the corresponding dispatching criterion, but 2406 // (i) in all out traits if bottom is open, so is top, and 2407 // (ii) this is going to change soon.... 2408 return cmp_x_on_bnd(p, c, ce, Bottom_side_category()); 2409 } 2410 2411 // Open cmp_x_on_bnd(const Point_2 & p,const X_monotone_curve_2 & c,Arr_curve_end ce,Arr_open_side_tag)2412 Comparison_result cmp_x_on_bnd(const Point_2& p, 2413 const X_monotone_curve_2& c, 2414 Arr_curve_end ce, 2415 Arr_open_side_tag) const 2416 { return m_self.compare_x_at_limit_2_object()(p, c, ce); } 2417 2418 // Close cmp_x_on_bnd(const Point_2 & p,const X_monotone_curve_2 & c,Arr_curve_end ce,Arr_oblivious_side_tag)2419 Comparison_result cmp_x_on_bnd(const Point_2& p, 2420 const X_monotone_curve_2& c, 2421 Arr_curve_end ce, 2422 Arr_oblivious_side_tag) const 2423 { return m_self.compare_x_on_boundary_2_object()(p, c, ce); } 2424 //@} 2425 2426 /// curve-curve 2427 //@{ 2428 /*! Compare a curve end and a curve end. 2429 * Dispatch calls to traits that handle open and close boundaries, resp. 2430 * The only reason for this dispatcher is the poor choice of different 2431 * names for the Traits functors that handle close and open boundaries: 2432 * Open boundary traits use: Compare_x_at_limit_2 2433 * Close boundary traits use: Compare_x_on_boundary_2 2434 */ cmp_x_on_bnd(const X_monotone_curve_2 & c1,Arr_curve_end ce1,const X_monotone_curve_2 & c2,Arr_curve_end ce2)2435 Comparison_result cmp_x_on_bnd(const X_monotone_curve_2& c1, 2436 Arr_curve_end ce1, 2437 const X_monotone_curve_2& c2, 2438 Arr_curve_end ce2) const 2439 { 2440 // The complete code would need to check the combination of ce1 and ce2, 2441 // whther they are (booton,bottom), (bottom,top), (top,bottom) or 2442 // (top,top) and use the corresponding dispatching criteria, but we don't 2443 // even have the interface to handle mixed (e.g., open bottom and 2444 // closed top. Anyway, this is going to change soon.... 2445 return cmp_x_on_bnd(c1, ce1, c2, ce2, Bottom_side_category()); 2446 } 2447 2448 // Open cmp_x_on_bnd(const X_monotone_curve_2 & c1,Arr_curve_end ce1,const X_monotone_curve_2 & c2,Arr_curve_end ce2,Arr_open_side_tag)2449 Comparison_result cmp_x_on_bnd(const X_monotone_curve_2& c1, 2450 Arr_curve_end ce1, 2451 const X_monotone_curve_2& c2, 2452 Arr_curve_end ce2, 2453 Arr_open_side_tag) const 2454 { return m_self.compare_x_at_limit_2_object()(c1, ce1, c2, ce2); } 2455 2456 // Close cmp_x_on_bnd(const X_monotone_curve_2 & c1,Arr_curve_end ce1,const X_monotone_curve_2 & c2,Arr_curve_end ce2,Arr_oblivious_side_tag)2457 Comparison_result cmp_x_on_bnd(const X_monotone_curve_2& c1, 2458 Arr_curve_end ce1, 2459 const X_monotone_curve_2& c2, 2460 Arr_curve_end ce2, 2461 Arr_oblivious_side_tag) const 2462 { return m_self.compare_x_on_boundary_2_object()(c1, ce1, c2, ce2); } 2463 //@} 2464 2465 /*! Compare the max end of two x-monotone curves lexigoraphically. 2466 */ compare_max_end(const X_monotone_curve_2 & c1,const X_monotone_curve_2 & c2,Arr_all_sides_oblivious_tag)2467 Comparison_result compare_max_end(const X_monotone_curve_2& c1, 2468 const X_monotone_curve_2& c2, 2469 Arr_all_sides_oblivious_tag) const 2470 { 2471 typedef typename Self::Construct_max_vertex_2 Construct_max_vertex_2; 2472 Construct_max_vertex_2 ctr_max = 2473 m_self.construct_max_vertex_2_object(); 2474 const Point_2& p1 = ctr_max(c1); 2475 const Point_2& p2 = ctr_max(c2); 2476 return operator()(p1, p2); 2477 } 2478 2479 /*! Compare the max (right) end of two x-monotone curves lexigoraphically. 2480 * \pre the curve overlap 2481 */ compare_max_end(const X_monotone_curve_2 & c1,const X_monotone_curve_2 & c2,Arr_not_all_sides_oblivious_tag)2482 Comparison_result compare_max_end(const X_monotone_curve_2& c1, 2483 const X_monotone_curve_2& c2, 2484 Arr_not_all_sides_oblivious_tag) const 2485 { 2486 typedef typename Base::Parameter_space_in_x_2 Parameter_space_in_x_2; 2487 typedef typename Base::Parameter_space_in_y_2 Parameter_space_in_y_2; 2488 Parameter_space_in_x_2 psx = m_self.parameter_space_in_x_2_object(); 2489 Parameter_space_in_y_2 psy = m_self.parameter_space_in_y_2_object(); 2490 2491 Arr_parameter_space px1 = psx(c1, ARR_MAX_END); 2492 Arr_parameter_space py1 = psy(c1, ARR_MAX_END); 2493 2494 Arr_parameter_space px2 = psx(c2, ARR_MAX_END); 2495 Arr_parameter_space py2 = psy(c2, ARR_MAX_END); 2496 2497 // Handle the trivial cases: 2498 if ((px1 == ARR_LEFT_BOUNDARY) && (px2 != ARR_LEFT_BOUNDARY)) 2499 return SMALLER; 2500 2501 if ((px2 == ARR_LEFT_BOUNDARY) && (px1 != ARR_LEFT_BOUNDARY)) 2502 return LARGER; 2503 2504 if ((px1 == ARR_RIGHT_BOUNDARY) && (px2 != ARR_RIGHT_BOUNDARY)) 2505 return LARGER; 2506 2507 if ((px2 == ARR_RIGHT_BOUNDARY) && (px1 != ARR_RIGHT_BOUNDARY)) 2508 return SMALLER; 2509 2510 // The only casese left are px1,px2 = (I,I), (L,L), and (R,R) 2511 2512 if (px1 == ARR_INTERIOR) { 2513 CGAL_assertion(px2 == ARR_INTERIOR); 2514 2515 if ((py1 == ARR_INTERIOR) && (py2 == ARR_INTERIOR)) 2516 return compare_max_end(c1, c2, Arr_all_sides_oblivious_tag()); 2517 2518 // px1, px2, py1 are interior 2519 if (py1 == ARR_INTERIOR) { 2520 CGAL_assertion(py2 != ARR_INTERIOR); 2521 #if 0 2522 // This code is retained (commented out) because in the future, when 2523 // Compare_x_at_limit_2 and Compare_x_on_boundary will be consolidated, 2524 // say, to Compare_x_on_boundary, it will replace the call below. 2525 typedef typename Self::Compare_x_on_boundary_2 Compare_x_on_boundary_2; 2526 Compare_x_on_boundary_2 cmp_x_on_bnd = 2527 m_self.compare_x_on_boundary_2_object(); 2528 #endif 2529 const Point_2& c1_max = m_self.construct_max_vertex_2_object()(c1); 2530 Comparison_result res = cmp_x_on_bnd(c1_max, c2, ARR_MAX_END); 2531 if (res != EQUAL) return res; 2532 2533 return (py2 == ARR_TOP_BOUNDARY) ? SMALLER : LARGER; 2534 } 2535 2536 // px1, px2, py2 are interior 2537 if (py2 == ARR_INTERIOR) { 2538 CGAL_assertion(py1 != ARR_INTERIOR); 2539 #if 0 2540 // This code is retained (commented out) because in the future, when 2541 // Compare_x_at_limit_2 and Compare_x_on_boundary will be consolidated, 2542 // say, to Compare_x_on_boundary, it will replace the call below. 2543 typedef typename Self::Compare_x_on_boundary_2 Compare_x_on_boundary_2; 2544 Compare_x_on_boundary_2 cmp_x_on_bnd = 2545 m_self.compare_x_on_boundary_2_object(); 2546 #endif 2547 const Point_2& c2_max = m_self.construct_max_vertex_2_object()(c2); 2548 Comparison_result res = cmp_x_on_bnd(c2_max, c1, ARR_MAX_END); 2549 if (res != EQUAL) return CGAL::opposite(res); 2550 2551 return (py1 == ARR_BOTTOM_BOUNDARY) ? SMALLER : LARGER; 2552 } 2553 2554 // Both py1 and py2 not interior 2555 #if 0 2556 // This code is retained (commented out) because in the future, when 2557 // Compare_x_at_limit_2 and Compare_x_on_boundary will be consolidated, 2558 // say, to Compare_x_on_boundary, it will replace the call below. 2559 typedef typename Self::Compare_x_on_boundary_2 Compare_x_on_boundary_2; 2560 Compare_x_on_boundary_2 cmp_x_on_bnd = 2561 m_self.compare_x_on_boundary_2_object(); 2562 #endif 2563 Comparison_result res = cmp_x_on_bnd(c1, ARR_MAX_END, c2, ARR_MAX_END); 2564 if (res != EQUAL) return res; 2565 2566 if ((py1 == ARR_BOTTOM_BOUNDARY) && (py2 != ARR_BOTTOM_BOUNDARY)) 2567 return SMALLER; 2568 if ((py1 == ARR_TOP_BOUNDARY) && (py2 != ARR_TOP_BOUNDARY)) 2569 return LARGER; 2570 return EQUAL; 2571 } 2572 2573 // Both endpoints lie either on the left boundary or on the right 2574 // boundary, which means that their x-coordinates are equal. 2575 // Handle the trivial cases: 2576 if ((py1 == ARR_BOTTOM_BOUNDARY) && (py2 != ARR_BOTTOM_BOUNDARY)) 2577 return SMALLER; 2578 if ((py1 == ARR_TOP_BOUNDARY) && (py2 != ARR_TOP_BOUNDARY)) 2579 return LARGER; 2580 2581 typedef typename Self::Compare_y_on_boundary_2 Compare_y_on_boundary_2; 2582 Compare_y_on_boundary_2 cmp_y_on_bnd = 2583 m_self.compare_y_on_boundary_2_object(); 2584 const Point_2& c1_max = m_self.construct_max_vertex_2_object()(c1); 2585 const Point_2& c2_max = m_self.construct_max_vertex_2_object()(c2); 2586 Comparison_result res = cmp_y_on_bnd(c1_max, c2_max); 2587 return res; 2588 } 2589 2590 /*! Split 2 given curves that overlap and have a common sub-curve on their 2591 * right. Then compare the remaining portions of the curves, respectively. 2592 */ 2593 Comparison_result compare_remainder(const X_monotone_curve_2 & c1,const X_monotone_curve_2 & c2,std::list<Intersection_result> & intersections)2594 compare_remainder(const X_monotone_curve_2& c1, 2595 const X_monotone_curve_2& c2, 2596 std::list<Intersection_result>& intersections) const 2597 { 2598 // Right-most sections are equal. 2599 // Advance to the next respective sections: 2600 if (intersections.empty()) { 2601 typedef typename Self::Intersect_2 Intersect_2; 2602 Intersect_2 intersect = m_self.intersect_2_object(); 2603 intersect(c1, c2, std::back_inserter(intersections)); 2604 } 2605 // Verify the first intersection is an overlap, remove it, and 2606 // recursively call. 2607 const X_monotone_curve_2* xcv = 2608 boost::get<X_monotone_curve_2>(&(intersections.front())); 2609 if (! xcv) { 2610 CGAL_error_msg("The first intersection is not an overlap!"); 2611 return SMALLER; 2612 } 2613 intersections.pop_front(); 2614 if (intersections.empty()) 2615 return compare_max_end(c1, c2, Are_all_sides_oblivious_category()); 2616 2617 // Otherwise, split and continue. 2618 typedef typename Self::Split_2 Split_2; 2619 Split_2 split = m_self.split_2_object(); 2620 X_monotone_curve_2 c11, c12, c21, c22; 2621 Construct_max_vertex_2 ctr_max = m_self.construct_max_vertex_2_object(); 2622 const Point_2& p1 = ctr_max(*xcv); 2623 const Point_2& p2 = ctr_max(*xcv); 2624 split(c1, p1, c11, c12); 2625 split(c2, p2, c21, c22); 2626 return operator()(c12, c22, intersections, 2627 Are_all_sides_oblivious_category()); 2628 } 2629 2630 /*! Compare two x-monotone curves lexigoraphically. 2631 */ operator()2632 Comparison_result operator()(const X_monotone_curve_2& c1, 2633 const X_monotone_curve_2& c2, 2634 std::list<Intersection_result>& intersections, 2635 Arr_all_sides_oblivious_tag) const 2636 { 2637 const Point_2& c1_min = m_self.construct_min_vertex_2_object()(c1); 2638 const Point_2& c2_min = m_self.construct_min_vertex_2_object()(c2); 2639 2640 Comparison_result res = operator()(c1_min, c2_min); 2641 if (res != EQUAL) return res; 2642 2643 // Left-most points are equal. 2644 // Compare their y-coordinates to their right: 2645 res = m_self.compare_y_at_x_right_2_object()(c1, c2, c1_min); 2646 if (res != EQUAL) return res; 2647 2648 return compare_remainder(c1, c2, intersections); 2649 } 2650 2651 /*! Compare two x-monotone curves lexigoraphically. 2652 */ operator()2653 Comparison_result operator()(const X_monotone_curve_2& c1, 2654 const X_monotone_curve_2& c2, 2655 std::list<Intersection_result>& intersections, 2656 Arr_not_all_sides_oblivious_tag) const 2657 { 2658 typedef typename Base::Parameter_space_in_x_2 Parameter_space_in_x_2; 2659 typedef typename Base::Parameter_space_in_y_2 Parameter_space_in_y_2; 2660 Parameter_space_in_x_2 psx = m_self.parameter_space_in_x_2_object(); 2661 Parameter_space_in_y_2 psy = m_self.parameter_space_in_y_2_object(); 2662 2663 Arr_parameter_space min_px1 = psx(c1, ARR_MIN_END); 2664 Arr_parameter_space min_py1 = psy(c1, ARR_MIN_END); 2665 2666 Arr_parameter_space min_px2 = psx(c2, ARR_MIN_END); 2667 Arr_parameter_space min_py2 = psy(c2, ARR_MIN_END); 2668 2669 // Handle the trivial cases: 2670 if ((min_px1 == ARR_LEFT_BOUNDARY) && (min_px2 != ARR_LEFT_BOUNDARY)) 2671 return SMALLER; 2672 2673 if ((min_px2 == ARR_LEFT_BOUNDARY) && (min_px1 != ARR_LEFT_BOUNDARY)) 2674 return LARGER; 2675 2676 if ((min_px1 == ARR_RIGHT_BOUNDARY) && (min_px2 != ARR_RIGHT_BOUNDARY)) 2677 return LARGER; 2678 2679 if ((min_px2 == ARR_RIGHT_BOUNDARY) && (min_px1 != ARR_RIGHT_BOUNDARY)) 2680 return SMALLER; 2681 2682 // The only casese left are px1,px2 = (I,I), (L,L), and (R,R) 2683 2684 if (min_px1 == ARR_INTERIOR) { 2685 CGAL_assertion(min_px2 == ARR_INTERIOR); 2686 2687 if ((min_py1 == ARR_INTERIOR) && (min_py2 == ARR_INTERIOR)) { 2688 return operator()(c1, c2, intersections, 2689 Arr_all_sides_oblivious_tag()); 2690 } 2691 2692 // 2693 if (min_py1 == ARR_INTERIOR) { 2694 CGAL_assertion(min_py2 != ARR_INTERIOR); 2695 #if 0 2696 // This code is retained (commented out) because in the future, when 2697 // Compare_x_at_limit_2 and Compare_x_on_boundary will be consolidated, 2698 // say, to Compare_x_on_boundary, it will replace the call below. 2699 typedef typename Self::Compare_x_on_boundary_2 Compare_x_on_boundary_2; 2700 Compare_x_on_boundary_2 cmp_x_on_bnd = 2701 m_self.compare_x_on_boundary_2_object(); 2702 #endif 2703 const Point_2& c1_min = m_self.construct_min_vertex_2_object()(c1); 2704 Comparison_result res = cmp_x_on_bnd(c1_min, c2, ARR_MIN_END); 2705 if (res != EQUAL) return res; 2706 2707 return (min_py2 == ARR_TOP_BOUNDARY) ? SMALLER : LARGER; 2708 } 2709 2710 if (min_py2 == ARR_INTERIOR) { 2711 CGAL_assertion(min_py1 != ARR_INTERIOR); 2712 #if 0 2713 // This code is retained (commented out) because in the future, when 2714 // Compare_x_at_limit_2 and Compare_x_on_boundary will be consolidated, 2715 // say, to Compare_x_on_boundary, it will replace the call below. 2716 typedef typename Self::Compare_x_on_boundary_2 Compare_x_on_boundary_2; 2717 Compare_x_on_boundary_2 cmp_x_on_bnd = 2718 m_self.compare_x_on_boundary_2_object(); 2719 #endif 2720 const Point_2& c2_min = m_self.construct_min_vertex_2_object()(c2); 2721 2722 Comparison_result res = cmp_x_on_bnd(c2_min, c1, ARR_MIN_END); 2723 if (res != EQUAL) return CGAL::opposite(res); 2724 2725 return (min_py1 == ARR_BOTTOM_BOUNDARY) ? SMALLER : LARGER; 2726 } 2727 2728 // Both min_py1 and min_py2 not interior 2729 #if 0 2730 // This code is retained (commented out) because in the future, when 2731 // Compare_x_at_limit_2 and Compare_x_on_boundary will be consolidated, 2732 // say, to Compare_x_on_boundary, it will replace the call below. 2733 typedef typename Self::Compare_x_on_boundary_2 Compare_x_on_boundary_2; 2734 Compare_x_on_boundary_2 cmp_x_on_bnd = 2735 m_self.compare_x_on_boundary_2_object(); 2736 #endif 2737 Comparison_result res = cmp_x_on_bnd(c1, ARR_MIN_END, c2, ARR_MIN_END); 2738 if (res != EQUAL) return res; 2739 2740 if ((min_py1 == ARR_BOTTOM_BOUNDARY) && (min_py2 == ARR_TOP_BOUNDARY)) 2741 return SMALLER; 2742 if ((min_py1 == ARR_TOP_BOUNDARY) && (min_py2 == ARR_BOTTOM_BOUNDARY)) 2743 return LARGER; 2744 2745 // Left-most points are equal. 2746 // Compare their x-coordinates near the common left endpoint. 2747 res = m_self.compare_x_near_boundary_2_object()(c1, c2, ARR_MIN_END); 2748 if (res != EQUAL) return res; 2749 2750 return compare_remainder(c1, c2, intersections); 2751 } 2752 2753 2754 if ((min_py1 == ARR_BOTTOM_BOUNDARY) && (min_py2 != ARR_BOTTOM_BOUNDARY)) 2755 return SMALLER; 2756 if ((min_py1 == ARR_TOP_BOUNDARY) && (min_py2 != ARR_TOP_BOUNDARY)) 2757 return LARGER; 2758 2759 if (min_px1 == ARR_LEFT_BOUNDARY) { 2760 // The min points of the two curves lie on the left boundary. 2761 CGAL_assertion(min_px2 == ARR_LEFT_BOUNDARY); 2762 typedef typename Self::Compare_y_on_boundary_2 Compare_y_on_boundary_2; 2763 Compare_y_on_boundary_2 cmp_y_on_bnd = 2764 m_self.compare_y_on_boundary_2_object(); 2765 const Point_2& c1_min = m_self.construct_min_vertex_2_object()(c1); 2766 const Point_2& c2_min = m_self.construct_min_vertex_2_object()(c2); 2767 Comparison_result res = cmp_y_on_bnd(c1_min, c2_min); 2768 if (res != EQUAL) return res; 2769 2770 typedef typename Self::Is_vertical_2 Is_vertical_2; 2771 Is_vertical_2 is_vert = m_self.is_vertical_2_object(); 2772 bool vert1 = is_vert(c1); 2773 bool vert2 = is_vert(c2); 2774 if (vert1 && ! vert2) return SMALLER; 2775 if (vert2 && ! vert1) return LARGER; 2776 if (vert1 && vert2) { 2777 const Point_2& c1_max = m_self.construct_max_vertex_2_object()(c1); 2778 const Point_2& c2_max = m_self.construct_max_vertex_2_object()(c2); 2779 res = cmp_y_on_bnd(c1_max, c2_max); 2780 if (res == SMALLER) return SMALLER; 2781 } 2782 // Compare slightly to the right near the boundary. 2783 typedef typename Self::Compare_y_near_boundary_2 2784 Compare_y_near_boundary_2; 2785 Compare_y_near_boundary_2 cmp_y_near_bnd = 2786 m_self.compare_y_near_boundary_2_object(); 2787 res = cmp_y_near_bnd(c1, c2, CGAL::ARR_MIN_END); 2788 if (res != EQUAL) return res; 2789 2790 // The two curves overlap on their right. 2791 // Intersect them, and recursively compare the remaining portions, 2792 // respectively. 2793 return compare_remainder(c1, c2, intersections); 2794 } 2795 2796 CGAL_assertion(min_px1 == ARR_RIGHT_BOUNDARY); 2797 CGAL_assertion(min_px2 == ARR_RIGHT_BOUNDARY); 2798 // The min points of the two curves lie on the right boundary. 2799 // It implies that the entire curves lie on the right boundary, and 2800 // thus both are vertical. 2801 2802 typedef typename Self::Compare_y_on_boundary_2 Compare_y_on_boundary_2; 2803 Compare_y_on_boundary_2 cmp_y_on_bnd = 2804 m_self.compare_y_on_boundary_2_object(); 2805 const Point_2& c1_min = m_self.construct_min_vertex_2_object()(c1); 2806 const Point_2& c2_min = m_self.construct_min_vertex_2_object()(c2); 2807 Comparison_result res = cmp_y_on_bnd(c1_min, c2_min); 2808 if (res != EQUAL) return res; 2809 2810 const Point_2& c1_max = m_self.construct_max_vertex_2_object()(c1); 2811 const Point_2& c2_max = m_self.construct_max_vertex_2_object()(c2); 2812 res = cmp_y_on_bnd(c1_max, c2_max); 2813 return res; 2814 } 2815 }; 2816 2817 /*! Obtain a Compare_xy_2 function object */ compare_xy_2_object()2818 Compare_xy_2 compare_xy_2_object() const { return Compare_xy_2(*this); } 2819 2820 /*! A functor that tests whether two x-monotone curves can be merged. */ 2821 class Are_mergeable_2 { 2822 public: 2823 /*! 2824 * Check whether it is possible to merge two given x-monotone curves. 2825 * \param xcv1 The first curve. 2826 * \param xcv2 The second curve. 2827 * \return (true) if the two curves are mergeable - if they are supported 2828 * by the same line and share a common endpoint; (false) otherwise. 2829 */ operator()2830 bool operator()(const X_monotone_curve_2& xcv1, 2831 const X_monotone_curve_2& xcv2) const 2832 { 2833 // The function is implemented based on the Has_merge category. 2834 return (_are_mergeable_imp(xcv1, xcv2, Has_merge_category())); 2835 } 2836 2837 protected: 2838 //! The base traits. 2839 const Base* m_base; 2840 2841 /*! Constructor. 2842 * \param base The base traits class. It must be passed, to handle non 2843 * stateless traits objects, (which stores data). 2844 * The constructor is declared private to allow only the functor 2845 * obtaining function, which is a member of the nesting class, 2846 * constructing it. 2847 */ Are_mergeable_2(const Base * base)2848 Are_mergeable_2(const Base* base) : m_base(base) {} 2849 2850 //! Allow its functor obtaining function calling the private constructor. 2851 friend class Arr_traits_adaptor_2<Base_traits_2>; 2852 2853 /*! 2854 * Implementation of the operator() in case the Has_merge tag is true. 2855 */ _are_mergeable_imp(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,Tag_true)2856 bool _are_mergeable_imp(const X_monotone_curve_2& xcv1, 2857 const X_monotone_curve_2& xcv2, Tag_true) const 2858 { return (m_base->are_mergeable_2_object()(xcv1, xcv2)); } 2859 2860 /*! 2861 * Implementation of the operator() in case the Has_merge tag is false. 2862 */ _are_mergeable_imp(const X_monotone_curve_2 &,const X_monotone_curve_2 &,Tag_false)2863 bool _are_mergeable_imp(const X_monotone_curve_2&, 2864 const X_monotone_curve_2&, Tag_false) const 2865 { 2866 // Curve merging is not supported: 2867 return false; 2868 } 2869 }; 2870 2871 /*! Obtain an Are_mergeable_2 function object. */ are_mergeable_2_object()2872 Are_mergeable_2 are_mergeable_2_object() const 2873 { return Are_mergeable_2(this); } 2874 2875 /*! A functor that merges two x-monotone curves into one. */ 2876 class Merge_2 { 2877 public: 2878 /*! 2879 * Merge two given x-monotone curves into a single curve. 2880 * \param xcv1 The first curve. 2881 * \param xcv2 The second curve. 2882 * \param c Output: The merged curve. 2883 * \pre The two curves are mergeable, that is they are supported by the 2884 * curve line and share a common endpoint. 2885 */ operator()2886 void operator()(const X_monotone_curve_2& xcv1, 2887 const X_monotone_curve_2& xcv2, 2888 X_monotone_curve_2& c) const 2889 { 2890 // The function is implemented based on the Has_merge category. 2891 _merge_imp(xcv1, xcv2, c, Has_merge_category()); 2892 } 2893 2894 protected: 2895 //! The base traits. 2896 const Base* m_base; 2897 2898 /*! Constructor. 2899 * \param base The base traits class. It must be passed, to handle non 2900 * stateless traits objects, (which stores data). 2901 * The constructor is declared private to allow only the functor 2902 * obtaining function, which is a member of the nesting class, 2903 * constructing it. 2904 */ Merge_2(const Base * base)2905 Merge_2(const Base* base) : m_base(base) {} 2906 2907 //! Allow its functor obtaining function calling the private constructor. 2908 friend class Arr_traits_adaptor_2<Base_traits_2>; 2909 2910 /*! 2911 * Implementation of the operator() in case the HasMerge tag is true. 2912 */ _merge_imp(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,X_monotone_curve_2 & c,Tag_true)2913 void _merge_imp(const X_monotone_curve_2& xcv1, 2914 const X_monotone_curve_2& xcv2, 2915 X_monotone_curve_2& c, Tag_true) const 2916 { return (m_base->merge_2_object()(xcv1, xcv2, c)); } 2917 2918 /*! 2919 * Implementation of the operator() in case the HasMerge tag is false. 2920 */ _merge_imp(const X_monotone_curve_2 &,const X_monotone_curve_2 &,X_monotone_curve_2 &,Tag_false)2921 void _merge_imp(const X_monotone_curve_2&, const X_monotone_curve_2&, 2922 X_monotone_curve_2&, Tag_false) const 2923 { 2924 // This function should never be called! 2925 CGAL_error_msg( "Merging curves is not supported."); 2926 return; 2927 } 2928 }; 2929 2930 /*! Obtain a Merge_2 function object. */ merge_2_object()2931 Merge_2 merge_2_object() const { return Merge_2(this); } 2932 //@} 2933 }; 2934 2935 } //namespace CGAL 2936 2937 #endif 2938