1 // Copyright (c) 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/Surface_sweep_2/Arr_basic_insertion_traits_2.h $ 7 // $Id: Arr_basic_insertion_traits_2.h 0626eb0 2020-06-11T12:32:33+03:00 Efi Fogel 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Baruch Zukerman <baruchzu@post.tau.ac.il> 12 // Ron Wein <wein@post.tau.ac.il> 13 // Efi Fogel <efif@post.tau.ac.il> 14 // Eric Berberich <eric@mpi-inf.mpg.de> 15 16 #ifndef CGAL_ARR_BASIC_INSERTION_TRAITS_2_H 17 #define CGAL_ARR_BASIC_INSERTION_TRAITS_2_H 18 19 #include <CGAL/license/Arrangement_on_surface_2.h> 20 21 /*! \file 22 * 23 * Defintion of the Arr_basic_insertion_traits_2<Traits,Arrangement> class. 24 */ 25 26 #include <CGAL/Arr_tags.h> 27 28 #include <list> 29 #include <iterator> 30 31 namespace CGAL { 32 33 /*! A basic meta-traits class that stores a halfedge handle with every 34 * x-monotone curve, and a vertex handle with each point. This information is 35 * used to speed up the aggregated insertion process. 36 */ 37 template <typename GeometryTraits_2, typename Arrangement_> 38 class Arr_basic_insertion_traits_2 { 39 public: 40 typedef GeometryTraits_2 Geometry_traits_2; 41 typedef Arrangement_ Arrangement_2; 42 43 private: 44 typedef Geometry_traits_2 Gt2; 45 46 public: 47 typedef typename Arrangement_2::Halfedge_handle Halfedge_handle; 48 typedef typename Arrangement_2::Vertex_handle Vertex_handle; 49 50 typedef typename Gt2::X_monotone_curve_2 Base_x_monotone_curve_2; 51 typedef typename Gt2::Point_2 Base_point_2; 52 typedef typename Gt2::Construct_min_vertex_2 Base_construct_min_vertex_2; 53 typedef typename Gt2::Construct_max_vertex_2 Base_construct_max_vertex_2; 54 typedef typename Gt2::Compare_x_2 Base_compare_x_2; 55 typedef typename Gt2::Compare_xy_2 Base_compare_xy_2; 56 typedef typename Gt2::Compare_y_at_x_2 Base_compare_y_at_x_2; 57 typedef typename Gt2::Compare_y_at_x_right_2 Base_compare_y_at_x_right_2; 58 typedef typename Gt2::Equal_2 Base_equal_2; 59 typedef typename Gt2::Is_vertical_2 Base_is_vertical_2; 60 61 typedef typename Gt2::Multiplicity Multiplicity; 62 63 typedef typename Gt2::Has_do_intersect_category 64 Has_do_intersect_category; 65 66 67 typedef typename internal::Arr_complete_left_side_category< Gt2>::Category 68 Left_side_category; 69 typedef typename internal::Arr_complete_bottom_side_category< Gt2>::Category 70 Bottom_side_category; 71 typedef typename internal::Arr_complete_top_side_category< Gt2>::Category 72 Top_side_category; 73 typedef typename internal::Arr_complete_right_side_category< Gt2>::Category 74 Right_side_category; 75 76 /* Insertion is implemented as surface-sweep visitor. The surface-sweep 77 * algorithm never uses Compare_y_at_x_left_2. 78 */ 79 typedef Tag_false Has_left_category; 80 81 protected: 82 //! The base traits. 83 const Gt2* m_base_traits; 84 85 public: 86 /*! Constructor. */ Arr_basic_insertion_traits_2(const Gt2 & tr)87 Arr_basic_insertion_traits_2(const Gt2& tr) : 88 m_base_traits(&tr) 89 {} 90 91 /*! 92 * Nested extension of the x-monotone curve type. 93 */ 94 class Ex_x_monotone_curve_2 { 95 public: 96 typedef Base_x_monotone_curve_2 Base; 97 98 protected: 99 Base m_base_xcv; // The base x-monotone curve. 100 Halfedge_handle m_he_handle; // The corresponding arrangement edge 101 // (may be invalid). 102 bool m_overlap; // Does this curve represent and overlap 103 // of two other curves. 104 105 public: 106 Ex_x_monotone_curve_2()107 Ex_x_monotone_curve_2(): 108 m_base_xcv(), 109 m_he_handle(), 110 m_overlap(false) 111 {} 112 Ex_x_monotone_curve_2(const Base & xcv)113 Ex_x_monotone_curve_2(const Base& xcv): 114 m_base_xcv(xcv), 115 m_he_handle(), 116 m_overlap(false) 117 {} 118 Ex_x_monotone_curve_2(const Base & xcv,Halfedge_handle he)119 Ex_x_monotone_curve_2(const Base& xcv, Halfedge_handle he) : 120 m_base_xcv(xcv), 121 m_he_handle(he), 122 m_overlap(false) 123 { 124 CGAL_precondition(he == Halfedge_handle() || 125 he->direction() == ARR_RIGHT_TO_LEFT); 126 } 127 base()128 const Base& base() const { return m_base_xcv; } 129 base()130 Base& base() { return m_base_xcv; } 131 132 operator const Base& () const { return m_base_xcv; } 133 134 Ex_x_monotone_curve_2& operator=(const Base& xcv) 135 { 136 m_base_xcv = xcv; 137 m_he_handle = Halfedge_handle(); 138 return (*this); 139 } 140 halfedge_handle()141 Halfedge_handle halfedge_handle() const { return m_he_handle; } 142 set_halfedge_handle(Halfedge_handle he)143 void set_halfedge_handle(Halfedge_handle he) 144 { 145 CGAL_precondition(he == Halfedge_handle() || 146 he->direction() == ARR_RIGHT_TO_LEFT); 147 m_he_handle = he; 148 } 149 is_overlapping()150 bool is_overlapping() const { return m_overlap; } 151 set_overlapping()152 void set_overlapping() { m_overlap = true; } 153 }; 154 155 typedef Ex_x_monotone_curve_2 X_monotone_curve_2; 156 157 // For debugging purposes: 158 friend std::ostream& operator<<(std::ostream& os, 159 const X_monotone_curve_2& xcv) 160 { 161 os << xcv.base(); 162 return (os); 163 } 164 165 /*! 166 * Nested extension of the point type. 167 */ 168 class Ex_point_2 { 169 public: 170 typedef Base_point_2 Base; 171 172 protected: 173 Base m_base_pt; // The base point. 174 Vertex_handle m_v; // The corresponding arrangement vertex 175 // (may be invalid). 176 177 public: Ex_point_2()178 Ex_point_2() : 179 m_base_pt(), 180 m_v() 181 {} 182 Ex_point_2(const Base & pt)183 Ex_point_2(const Base& pt) : 184 m_base_pt(pt), 185 m_v() 186 {} 187 Ex_point_2(const Base & pt,Vertex_handle v)188 Ex_point_2(const Base& pt, Vertex_handle v) : 189 m_base_pt(pt), 190 m_v(v) 191 {} 192 base()193 const Base& base() const { return m_base_pt; } 194 195 operator const Base& () const { return m_base_pt; } 196 vertex_handle()197 Vertex_handle vertex_handle() const { return m_v; } 198 set_vertex_handle(Vertex_handle v)199 void set_vertex_handle(Vertex_handle v) { m_v = v; } 200 }; 201 202 typedef Ex_point_2 Point_2; 203 204 // For debugging purposes: 205 friend std::ostream& operator<<(std::ostream& os, const Point_2& pt) 206 { 207 os << pt.base(); 208 return os; 209 } 210 211 /*! A functor that obtains the left endpoint of an x-monotone curve. */ 212 class Construct_min_vertex_2 { 213 protected: 214 Base_construct_min_vertex_2 m_base_min_v; 215 Base_equal_2 m_base_equal; 216 Halfedge_handle invalid_he; 217 218 /*! Constructor. 219 * The constructor is declared private to allow only the functor 220 * obtaining function, which is a member of the nesting class, 221 * constructing it. 222 */ Construct_min_vertex_2(const Base_construct_min_vertex_2 & base_min_v,const Base_equal_2 & base_equal)223 Construct_min_vertex_2(const Base_construct_min_vertex_2& base_min_v, 224 const Base_equal_2& base_equal) : 225 m_base_min_v(base_min_v), 226 m_base_equal(base_equal), 227 invalid_he() 228 {} 229 230 //! Allow its functor obtaining function calling the private constructor. 231 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 232 233 public: operator()234 Point_2 operator()(const X_monotone_curve_2& xcv) 235 { 236 // If there is not halfedge associated with the curve, just return 237 // a point with invalid halfedge handle. 238 const Base_point_2& base_p = m_base_min_v(xcv.base()); 239 240 if (xcv.halfedge_handle() == invalid_he) return (Point_2(base_p)); 241 242 // Note that the halfedge associated with the curve is always directed 243 // from right to left, so its target is the leftmost vertex. 244 // We probably have to associate the point with the target vertex of 245 // the halfedge associated with the curve. 246 Vertex_handle vh = xcv.halfedge_handle()->target(); 247 248 if (! xcv.is_overlapping()) return (Point_2(base_p, vh)); 249 250 // In case of an overlapping curve, make sure the curve endpoint equals 251 // the point associated with the vertex. If not, we attach an invalid 252 // vertex to the extended point. 253 if (! vh->is_at_open_boundary() && m_base_equal(base_p, vh->point())) 254 return (Point_2(base_p, vh)); 255 else return (Point_2(base_p)); 256 } 257 }; 258 259 /*! Obtain a Construct_min_vertex_2 function object */ construct_min_vertex_2_object()260 Construct_min_vertex_2 construct_min_vertex_2_object() const 261 { 262 return (Construct_min_vertex_2 263 (m_base_traits->construct_min_vertex_2_object(), 264 m_base_traits->equal_2_object())); 265 } 266 267 /*! A functor that obtains the right endpoint of an x-monotone curve. */ 268 class Construct_max_vertex_2 { 269 protected: 270 Base_construct_max_vertex_2 m_base_max_v; 271 Base_equal_2 m_base_equal; 272 Halfedge_handle invalid_he; 273 274 /*! Constructor. 275 * The constructor is declared private to allow only the functor 276 * obtaining function, which is a member of the nesting class, 277 * constructing it. 278 */ Construct_max_vertex_2(const Base_construct_max_vertex_2 & base_max_v,const Base_equal_2 & base_equal)279 Construct_max_vertex_2(const Base_construct_max_vertex_2& base_max_v, 280 const Base_equal_2& base_equal) : 281 m_base_max_v(base_max_v), 282 m_base_equal(base_equal), 283 invalid_he() 284 {} 285 286 287 //! Allow its functor obtaining function calling the private constructor. 288 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 289 290 public: operator()291 Point_2 operator()(const X_monotone_curve_2& xcv) 292 { 293 // If there is not halfedge associated with the curve, just return 294 // a point with invalid halfedge handle. 295 const Base_point_2& base_p = m_base_max_v(xcv.base()); 296 297 if (xcv.halfedge_handle() == invalid_he) return (Point_2(base_p)); 298 299 // Note that the halfedge associated with the curve is always directed 300 // from right to left, so its source is the rightmost vertex. 301 // We probably have to associate the point with the source vertex of 302 // the halfedge associated with the curve. 303 Vertex_handle vh = xcv.halfedge_handle()->source(); 304 305 if (! xcv.is_overlapping()) return (Point_2(base_p, vh)); 306 307 // In case of an overlapping curve, make sure the curve endpoint equals 308 // the point associated with the vertex. If not, we attach an invalid 309 // vertex to the extended point. 310 if (! vh->is_at_open_boundary() && m_base_equal(base_p, vh->point())) 311 return (Point_2(base_p, vh)); 312 else return (Point_2(base_p)); 313 } 314 }; 315 316 /*! Obtain a Construct_max_vertex_2 function object */ construct_max_vertex_2_object()317 Construct_max_vertex_2 construct_max_vertex_2_object() const 318 { 319 return (Construct_max_vertex_2 320 (m_base_traits->construct_max_vertex_2_object(), 321 m_base_traits->equal_2_object())); 322 } 323 324 /*! A functor that compares two points lexigoraphically: by x, then by y. */ 325 class Compare_xy_2 { 326 protected: 327 Base_compare_xy_2 m_base_cmp_xy; 328 329 /*! Constructor. 330 * The constructor is declared private to allow only the functor 331 * obtaining function, which is a member of the nesting class, 332 * constructing it. 333 */ Compare_xy_2(const Base_compare_xy_2 & base)334 Compare_xy_2(const Base_compare_xy_2& base) : m_base_cmp_xy(base) {} 335 336 //! Allow its functor obtaining function calling the private constructor. 337 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 338 339 public: operator()340 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 341 { 342 if(p1.vertex_handle() == p2.vertex_handle() && 343 p1.vertex_handle() != Vertex_handle()) 344 return EQUAL; 345 346 return (m_base_cmp_xy(p1.base(), p2.base())); 347 } 348 }; 349 350 /*! Obtain a Compare_xy_2 function object */ compare_xy_2_object()351 Compare_xy_2 compare_xy_2_object() const 352 { return (Compare_xy_2(m_base_traits->compare_xy_2_object())); } 353 354 /*! A functor that compares the y-coordinates of a point and an 355 * x-monotone curve at the point x-coordinate. 356 */ 357 class Compare_y_at_x_2 { 358 protected: 359 Base_compare_y_at_x_2 m_base_cmp_y_at_x; 360 361 /*! Constructor. 362 * The constructor is declared private to allow only the functor 363 * obtaining function, which is a member of the nesting class, 364 * constructing it. 365 */ Compare_y_at_x_2(const Base_compare_y_at_x_2 & base)366 Compare_y_at_x_2(const Base_compare_y_at_x_2& base) : 367 m_base_cmp_y_at_x(base) 368 {} 369 370 //! Allow its functor obtaining function calling the private constructor. 371 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 372 373 public: operator()374 Comparison_result operator()(const Point_2& p, 375 const X_monotone_curve_2& xcv) const 376 { return (m_base_cmp_y_at_x(p.base(), xcv.base())); } 377 }; 378 379 /*! Obtain a Compare_y_at_x_2 function object */ compare_y_at_x_2_object()380 Compare_y_at_x_2 compare_y_at_x_2_object() const 381 { return (Compare_y_at_x_2(m_base_traits->compare_y_at_x_2_object())); } 382 383 /*! A functor that compares compares the y-coordinates of two x-monotone 384 * curves immediately to the right of their intersection point. 385 */ 386 class Compare_y_at_x_right_2 { 387 protected: 388 Base_compare_y_at_x_right_2 m_base_cmp_y_at_x_right; 389 390 /*! Constructor. 391 * The constructor is declared private to allow only the functor 392 * obtaining function, which is a member of the nesting class, 393 * constructing it. 394 */ Compare_y_at_x_right_2(const Base_compare_y_at_x_right_2 & base)395 Compare_y_at_x_right_2(const Base_compare_y_at_x_right_2& base) : 396 m_base_cmp_y_at_x_right(base) 397 {} 398 399 //! Allow its functor obtaining function calling the private constructor. 400 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 401 402 public: operator()403 Comparison_result operator()(const X_monotone_curve_2& xcv1, 404 const X_monotone_curve_2& xcv2, 405 const Point_2& p) const 406 { return (m_base_cmp_y_at_x_right(xcv1.base(), xcv2.base(), p.base())); } 407 }; 408 409 /*! Obtain a Compare_y_at_x_right_2 function object */ compare_y_at_x_right_2_object()410 Compare_y_at_x_right_2 compare_y_at_x_right_2_object() const 411 { 412 return (Compare_y_at_x_right_2 413 (m_base_traits->compare_y_at_x_right_2_object())); 414 } 415 416 /*! A functor that checks whether two points and two x-monotone curves are 417 * identical. 418 */ 419 class Equal_2 { 420 protected: 421 Base_equal_2 m_base_eq; 422 423 /*! Constructor. 424 * The constructor is declared private to allow only the functor 425 * obtaining function, which is a member of the nesting class, 426 * constructing it. 427 */ Equal_2(const Base_equal_2 & base)428 Equal_2(const Base_equal_2& base) : m_base_eq(base) {} 429 430 //! Allow its functor obtaining function calling the private constructor. 431 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 432 433 public: 434 /*! Check if two curves are the same. */ operator()435 bool operator()(const X_monotone_curve_2& xcv1, 436 const X_monotone_curve_2& xcv2) const 437 { return (m_base_eq(xcv1.base(), xcv2.base())); } 438 439 /*! Check if the two points are the same. */ operator()440 bool operator()(const Point_2& p1, const Point_2& p2) const 441 { return (m_base_eq(p1.base(), p2.base())); } 442 }; 443 444 /*! Obtain a Equal_2 function object */ equal_2_object()445 Equal_2 equal_2_object() const 446 { return (Equal_2(m_base_traits->equal_2_object())); } 447 448 /*! A functor that compares the x-coordinates of two points */ 449 class Compare_x_2 { 450 protected: 451 Base_compare_x_2 m_base_cmp_x; 452 453 /*! Constructor. 454 * The constructor is declared private to allow only the functor 455 * obtaining function, which is a member of the nesting class, 456 * constructing it. 457 */ Compare_x_2(const Base_compare_x_2 & base)458 Compare_x_2(const Base_compare_x_2& base) : m_base_cmp_x(base) {} 459 460 //! Allow its functor obtaining function calling the private constructor. 461 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 462 463 public: operator()464 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 465 { return (m_base_cmp_x(p1.base(), p2.base())); } 466 }; 467 468 /*! Obtain a Compare_x_2 function object */ compare_x_2_object()469 Compare_x_2 compare_x_2_object() const 470 { return (Compare_x_2(m_base_traits->compare_x_2_object())); } 471 472 /*! A functor that checks whether a given x-monotone curve is vertical. */ 473 class Is_vertical_2 { 474 protected: 475 Base_is_vertical_2 m_base_is_vert; 476 477 /*! Constructor. 478 * The constructor is declared private to allow only the functor 479 * obtaining function, which is a member of the nesting class, 480 * constructing it. 481 */ Is_vertical_2(const Base_is_vertical_2 & base)482 Is_vertical_2(const Base_is_vertical_2& base) : m_base_is_vert(base) {} 483 484 //! Allow its functor obtaining function calling the private constructor. 485 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 486 487 public: operator()488 bool operator()(const X_monotone_curve_2& xcv) const 489 { return (m_base_is_vert(xcv.base())); } 490 }; 491 492 /*! Obtain a Is_vertical_2 function object */ is_vertical_2_object()493 Is_vertical_2 is_vertical_2_object() const 494 { return (Is_vertical_2(m_base_traits->is_vertical_2_object())); } 495 496 // left-right 497 498 /*! A functor that determines whether an endpoint of an x-monotone curve lies 499 * on a boundary of the parameter space along the x axis. 500 */ 501 class Parameter_space_in_x_2 { 502 protected: 503 //! The base traits. 504 const Gt2* m_base; 505 506 /*! Constructor. 507 * \param tr The base traits class. It must be passed, to handle non 508 * stateless traits objects, (which stores data). 509 * The constructor is declared private to allow only the functor 510 * obtaining function, which is a member of the nesting class, 511 * constructing it. 512 */ Parameter_space_in_x_2(const Gt2 * tr)513 Parameter_space_in_x_2(const Gt2* tr) : m_base(tr) {} 514 515 //! Allow its functor obtaining function calling the private constructor. 516 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 517 518 public: operator()519 Arr_parameter_space operator()(const X_monotone_curve_2& xcv, 520 Arr_curve_end ce) const 521 { return (m_base->parameter_space_in_x_2_object()(xcv.base(), ce)); } 522 operator()523 Arr_parameter_space operator()(const Point_2& p) const 524 { return m_base->parameter_space_in_x_2_object()(p.base()); } 525 operator()526 Arr_parameter_space operator()(const X_monotone_curve_2& xcv) const 527 { return m_base->parameter_space_in_x_2_object()(xcv.base()); } 528 }; 529 530 /*! Obtain a Parameter_space_in_x_2 function object */ parameter_space_in_x_2_object()531 Parameter_space_in_x_2 parameter_space_in_x_2_object() const 532 { return Parameter_space_in_x_2(m_base_traits); } 533 534 /*! A function object that determines whether an x-monotone curve or a 535 * point coincide with the vertical identification curve. 536 */ 537 class Is_on_x_identification_2 { 538 protected: 539 //! The base traits. 540 const Gt2* m_base; 541 542 /*! Constructor. 543 * \param tr The base traits class. It must be passed, to handle non 544 * stateless traits objects, (which stores data). 545 * The constructor is declared private to allow only the functor 546 * obtaining function, which is a member of the nesting class, 547 * constructing it. 548 */ Is_on_x_identification_2(const Gt2 * tr)549 Is_on_x_identification_2(const Gt2* tr) : m_base(tr) {} 550 551 //! Allow its functor obtaining function calling the private constructor. 552 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 553 554 public: operator()555 bool operator()(const Point_2& p) const 556 { return m_base->is_on_x_identification_2_object()(p.base()); } 557 operator()558 bool operator()(const X_monotone_curve_2& xcv) const 559 { return m_base->is_on_x_identification_2_object()(xcv.base()); } 560 }; 561 562 /*! Obtain a Is_on_x_identification_2 function object */ is_on_x_identification_2_object()563 Is_on_x_identification_2 is_on_x_identification_2_object() const 564 { return Is_on_x_identification_2(m_base_traits); } 565 566 /*! A functor that compares the y-coordinates of two points on vertical 567 * boundaries. 568 */ 569 class Compare_y_on_boundary_2 { 570 protected: 571 //! The base traits. 572 const Gt2* m_base; 573 574 /*! Constructor. 575 * \param base The base traits class. It must be passed, to handle non 576 * stateless traits objects, (which stores data). 577 * The constructor is declared private to allow only the functor 578 * obtaining function, which is a member of the nesting class, 579 * constructing it. 580 */ Compare_y_on_boundary_2(const Gt2 * base)581 Compare_y_on_boundary_2(const Gt2* base) : m_base(base) {} 582 583 //! Allow its functor obtaining function calling the private constructor. 584 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 585 586 public: 587 /*! Use tag dispatching to avoid compilation errors in case the functor 588 * is not defined 589 */ operator()590 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 591 { return m_base->compare_y_on_boundary_2_object()(p1.base(), p2.base()); } 592 }; 593 594 /*! Obtain a Compare_y_on_boundary_2 object 595 */ compare_y_on_boundary_2_object()596 Compare_y_on_boundary_2 compare_y_on_boundary_2_object() const 597 { return Compare_y_on_boundary_2(m_base_traits); } 598 599 /*! A functor that compares the y-coordinates of curve ends near the 600 * boundary of the parameter space. 601 */ 602 class Compare_y_near_boundary_2 { 603 protected: 604 //! The base traits. 605 const Gt2* m_base; 606 607 /*! Constructor. 608 * \param base The base traits class. It must be passed, to handle non 609 * stateless traits objects, (which stores data). 610 * The constructor is declared private to allow only the functor 611 * obtaining function, which is a member of the nesting class, 612 * constructing it. 613 */ Compare_y_near_boundary_2(const Gt2 * base)614 Compare_y_near_boundary_2(const Gt2* base) : m_base(base) {} 615 616 //! Allow its functor obtaining function calling the private constructor. 617 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 618 619 public: 620 /*! Use tag dispatching to avoid compilation errors in case the functor 621 * is not defined 622 */ operator()623 Comparison_result operator()(const X_monotone_curve_2& xcv1, 624 const X_monotone_curve_2& xcv2, 625 Arr_curve_end ce) const 626 { 627 return m_base->compare_y_near_boundary_2_object()(xcv1.base(), 628 xcv2.base(), ce); 629 } 630 631 }; 632 633 /*! Obtain a Compare_y_near_boundary_2 object 634 */ compare_y_near_boundary_2_object()635 Compare_y_near_boundary_2 compare_y_near_boundary_2_object() const 636 { return Compare_y_near_boundary_2(m_base_traits); } 637 638 // bottom-top 639 640 /*! A functor that determines whether an endpoint of an x-monotone arc lies 641 * on a boundary of the parameter space along the y axis. 642 */ 643 class Parameter_space_in_y_2 { 644 protected: 645 //! The base traits. 646 const Gt2* m_base; 647 648 /*! Constructor. 649 * \param tr The base traits class. It must be passed, to handle non 650 * stateless traits objects, (which stores data). 651 * The constructor is declared private to allow only the functor 652 * obtaining function, which is a member of the nesting class, 653 * constructing it. 654 */ Parameter_space_in_y_2(const Gt2 * tr)655 Parameter_space_in_y_2(const Gt2* tr) : m_base(tr) {} 656 657 //! Allow its functor obtaining function calling the private constructor. 658 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 659 660 public: operator()661 Arr_parameter_space operator()(const X_monotone_curve_2& xcv, 662 Arr_curve_end ce) const 663 { return m_base->parameter_space_in_y_2_object()(xcv.base(), ce); } 664 operator()665 Arr_parameter_space operator()(const Point_2& p) const 666 { return m_base->parameter_space_in_y_2_object()(p.base()); } 667 operator()668 Arr_parameter_space operator()(const X_monotone_curve_2& xcv) const 669 { return m_base->parameter_space_in_y_2_object()(xcv.base()); } 670 671 }; 672 673 /*! Obtain a Parameter_space_in_y_2 function object */ parameter_space_in_y_2_object()674 Parameter_space_in_y_2 parameter_space_in_y_2_object() const 675 { return Parameter_space_in_y_2(m_base_traits); } 676 677 /*! A function object that determines whether an x-monotone curve or a 678 * point coincide with the horizontal identification curve. 679 */ 680 class Is_on_y_identification_2 { 681 protected: 682 //! The base traits. 683 const Gt2* m_base; 684 685 /*! Constructor. 686 * \param tr The base traits class. It must be passed, to handle non 687 * stateless traits objects, (which stores data). 688 * The constructor is declared private to allow only the functor 689 * obtaining function, which is a member of the nesting class, 690 * constructing it. 691 */ Is_on_y_identification_2(const Gt2 * tr)692 Is_on_y_identification_2(const Gt2* tr) : m_base(tr) {} 693 694 //! Allow its functor obtaining function calling the private constructor. 695 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 696 697 public: operator()698 bool operator()(const Point_2& p) const 699 { return m_base->is_on_y_identification_2_object()(p.base()); } 700 operator()701 bool operator()(const X_monotone_curve_2 & xcv) const 702 { return m_base->is_on_y_identification_2_object()(xcv.base()); } 703 }; 704 705 /*! Obtain a Is_on_y_identification_2 function object */ is_on_y_identification_2_object()706 Is_on_y_identification_2 is_on_y_identification_2_object() const 707 { return Is_on_y_identification_2(m_base_traits); } 708 709 /*! A functor that compares the x-limits of curve ends on the 710 * boundary of the parameter space. 711 */ 712 class Compare_x_at_limit_2 { 713 protected: 714 //! The base traits. 715 const Gt2* m_base; 716 717 /*! Constructor. 718 * \param base The base traits class. It must be passed, to handle non 719 * stateless traits objects, (which stores data). 720 * The constructor is declared private to allow only the functor 721 * obtaining function, which is a member of the nesting class, 722 * constructing it. 723 */ Compare_x_at_limit_2(const Gt2 * base)724 Compare_x_at_limit_2(const Gt2* base) : m_base(base) {} 725 726 //! Allow its functor obtaining function calling the private constructor. 727 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 728 729 public: 730 /*! Use tag dispatching to avoid compilation errors in case the functor 731 * is not defined 732 */ operator()733 Comparison_result operator()(const Point_2& p, 734 const X_monotone_curve_2& xcv, 735 Arr_curve_end ce) const 736 { return m_base->compare_x_at_limit_2_object()(p.base(), xcv.base(), ce); } 737 738 /*! Use tag dispatching to avoid compilation errors in case the functor 739 * is not defined 740 */ operator()741 Comparison_result operator()(const X_monotone_curve_2& xcv1, 742 Arr_curve_end ce1, 743 const X_monotone_curve_2& xcv2, 744 Arr_curve_end ce2) const 745 { 746 return m_base->compare_x_at_limit_2_object()(xcv1.base(), ce1, 747 xcv2.base(), ce2); 748 } 749 }; 750 751 /*! Obtain a Compare_x_at_limit_2 object 752 */ compare_x_at_limit_2_object()753 Compare_x_at_limit_2 compare_x_at_limit_2_object() const 754 { return Compare_x_at_limit_2(m_base_traits); } 755 756 757 /*! A functor that compares the x-coordinates of curve ends near the 758 * boundary of the parameter space. 759 */ 760 class Compare_x_near_limit_2 { 761 protected: 762 //! The base traits. 763 const Gt2* m_base; 764 765 /*! Constructor. 766 * \param base The base traits class. It must be passed, to handle non 767 * stateless traits objects, (which stores data). 768 * The constructor is declared private to allow only the functor 769 * obtaining function, which is a member of the nesting class, 770 * constructing it. 771 */ Compare_x_near_limit_2(const Gt2 * base)772 Compare_x_near_limit_2(const Gt2* base) : m_base(base) {} 773 774 //! Allow its functor obtaining function calling the private constructor. 775 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 776 777 public: 778 /*! Use tag dispatching to avoid compilation errors in case the functor 779 * is not defined 780 */ operator()781 Comparison_result operator()(const X_monotone_curve_2& xcv1, 782 const X_monotone_curve_2& xcv2, 783 Arr_curve_end ce) const 784 { 785 return m_base->compare_x_near_limit_2_object()(xcv1.base(), xcv2.base(), 786 ce); 787 } 788 789 }; 790 791 /*! Obtain a Compare_x_near_limit_2 object 792 */ compare_x_near_limit_2_object()793 Compare_x_near_limit_2 compare_x_near_limit_2_object() const 794 { return Compare_x_near_limit_2(m_base_traits); } 795 796 /*! A functor that compares the x-coordinates of two points on vertical 797 * boundaries. 798 */ 799 class Compare_x_on_boundary_2 800 { 801 protected: 802 //! The base traits. 803 const Gt2* m_base; 804 805 /*! Constructor. 806 * \param base The base traits class. It must be passed, to handle non 807 * stateless traits objects, (which stores data). 808 * The constructor is declared private to allow only the functor 809 * obtaining function, which is a member of the nesting class, 810 * constructing it. 811 */ Compare_x_on_boundary_2(const Gt2 * base)812 Compare_x_on_boundary_2(const Gt2* base) : m_base(base) {} 813 814 //! Allow its functor obtaining function calling the private constructor. 815 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 816 817 public: 818 /*! Use tag dispatching to avoid compilation errors in case the functor 819 * is not defined 820 */ operator()821 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 822 { return m_base->compare_x_on_boundary_2_object()(p1.base(), p2.base()); } 823 824 /*! Use tag dispatching to avoid compilation errors in case the functor 825 * is not defined 826 */ operator()827 Comparison_result operator()(const Point_2 & pt, 828 const X_monotone_curve_2& xcv, 829 Arr_curve_end ce) const 830 { 831 return m_base->compare_x_on_boundary_2_object()(pt.base(), xcv.base(), ce); 832 } 833 834 /*! Use tag dispatching to avoid compilation errors in case the functor 835 * is not defined 836 */ operator()837 Comparison_result operator()(const X_monotone_curve_2& xcv1, 838 Arr_curve_end ce1, 839 const X_monotone_curve_2& xcv2, 840 Arr_curve_end ce2) const 841 { 842 return m_base->compare_x_on_boundary_2_object()(xcv1.base(), ce1, 843 xcv2.base(), ce2); 844 } 845 }; 846 847 /*! Obtain a Compare_x_on_boundary_2 object 848 */ compare_x_on_boundary_2_object()849 Compare_x_on_boundary_2 compare_x_on_boundary_2_object() const 850 { return Compare_x_on_boundary_2(m_base_traits); } 851 852 /*! A functor that compares the x-coordinates of curve ends near the 853 * boundary of the parameter space. 854 */ 855 class Compare_x_near_boundary_2 { 856 protected: 857 //! The base traits. 858 const Gt2* m_base; 859 860 /*! Constructor. 861 * \param base The base traits class. It must be passed, to handle non 862 * stateless traits objects, (which stores data). 863 * The constructor is declared private to allow only the functor 864 * obtaining function, which is a member of the nesting class, 865 * constructing it. 866 */ Compare_x_near_boundary_2(const Gt2 * base)867 Compare_x_near_boundary_2(const Gt2* base) : m_base(base) {} 868 869 //! Allow its functor obtaining function calling the private constructor. 870 friend class Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_>; 871 872 public: 873 /*! Use tag dispatching to avoid compilation errors in case the functor 874 * is not defined 875 */ operator()876 Comparison_result operator()(const X_monotone_curve_2& xcv1, 877 const X_monotone_curve_2& xcv2, 878 Arr_curve_end ce) const 879 { 880 return m_base->compare_x_near_boundary_2_object()(xcv1.base(), 881 xcv2.base(), ce); 882 } 883 }; 884 885 /*! Obtain a Compare_x_near_boundary_2 object 886 */ compare_x_near_boundary_2_object()887 Compare_x_near_boundary_2 compare_x_near_boundary_2_object() const 888 { return Compare_x_near_boundary_2(m_base_traits); } 889 }; 890 891 } //namespace CGAL 892 893 #endif 894