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