1 // Copyright (c) 2007,2008,2009,2010,2011 Max-Planck-Institute Saarbruecken (Germany), 2 // and Tel-Aviv University (Israel). 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/Curved_kernel_via_analysis_2/Sweep_curves_adapter_2.h $ 7 // $Id: Sweep_curves_adapter_2.h 2aa0c9c 2020-07-02T19:11:30+03:00 Efi Fogel 8 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Pavel Emeliyanenko <asm@mpi-sb.mpg.de> 12 13 #ifndef CGAL_CURVED_KERNEL_VIA_ANALYSIS_2_SWEEP_CURVES_ADAPTER_2_H 14 #define CGAL_CURVED_KERNEL_VIA_ANALYSIS_2_SWEEP_CURVES_ADAPTER_2_H 1 15 16 /*!\file include/CGAL/Curved_kernel_via_analysis_2/Sweep_curves_adapter_2.h 17 * \brief defines class \c Sweep_curves_adapter_2 18 * 19 * provides a valid model of \c SoX::CurveSweepTraits_2 to use 20 * \c Curved_kernel_via_analysis_2 with \c SoX::sweep_curves 21 */ 22 23 #include <CGAL/config.h> 24 25 #include <boost/optional.hpp> 26 #include <boost/none.hpp> 27 #include <CGAL/iterator.h> 28 #include <CGAL/Handle_with_policy.h> 29 30 #include <CGAL/Arr_enums.h> 31 32 #include <CGAL/Curved_kernel_via_analysis_2/Generic_point_2.h> 33 #include <CGAL/Curved_kernel_via_analysis_2/Generic_arc_2.h> 34 35 #ifndef SCA_CERR 36 //#define SCA_DEBUG_PRINT_CERR 37 #ifdef SCA_DEBUG_PRINT_CERR 38 #define SCA_CERR(x) std::cerr << x 39 #else 40 #define SCA_CERR(x) static_cast<void>(0) 41 #endif 42 #endif 43 44 namespace CGAL { 45 46 // defines a set of functors required by CurveSweepTraits_2 concept 47 namespace Sweep_curves_functors { 48 49 template < class SweepCurvesAdapter_2 > 50 class Compare_xy_2 51 { 52 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 53 54 public: 55 typedef CGAL::Comparison_result result_type; 56 57 //! standard constructor Compare_xy_2(SweepCurvesAdapter_2 * adapter)58 Compare_xy_2(SweepCurvesAdapter_2 *adapter) : 59 _m_adapter(adapter) { 60 CGAL_assertion(adapter != nullptr); 61 } 62 operator()63 result_type operator()(const Point_2& p1, const Point_2& p2) const { 64 result_type res = (*this)(p1, p2, true); 65 SCA_CERR("Result: " << res << "\n"); 66 return res; 67 } 68 69 /*! 70 * Compares two points lexigoraphically: by x, then by y. 71 * \param p1 The first point. 72 * \param p2 The second point. 73 * \return LARGER if x(p1) > x(p2), or if x(p1) = x(p2) and y(p1) > y(p2); 74 * SMALLER if x(p1) \< x(p2), or if x(p1) = x(p2) and 75 * y(p1) \< y(p2); 76 * EQUAL if the two points are equal. 77 */ operator()78 result_type operator()(const Point_2& p1, const Point_2& p2, bool) const 79 { 80 if(p1.is_identical(p2)) 81 return CGAL::EQUAL; 82 83 typedef typename SweepCurvesAdapter_2::Native_arc_2 Native_arc_2; 84 typename SweepCurvesAdapter_2::Native_point_2 pt; 85 Native_arc_2 arc; 86 CGAL::Arr_curve_end end; 87 CGAL::Arr_parameter_space loc1, loc2; 88 bool inverse = false; 89 90 SCA_CERR("Compare_xy_2: p1: " << p1 << "\n p2: " << p2 << std::endl); 91 92 if(p1.is_finite()) { 93 if(p2.is_finite()) 94 return (_m_adapter->kernel().compare_xy_2_object()(p1.point(), 95 p2.point())); 96 pt = p1.point(); 97 arc = p2.arc(); 98 end = p2.curve_end(); 99 loc1 = arc.location(end); 100 } else { 101 arc = p1.arc(); 102 end = p1.curve_end(); 103 loc1 = arc.location(end); 104 105 if(!p2.is_finite()) { // both points lie at infinity 106 loc2 = p2.arc().location(p2.curve_end()); 107 if(Native_arc_2::is_on_left_right(loc1)) { 108 if(loc1 != loc2) // cmp + and -oo in x 109 return (loc1 == CGAL::ARR_LEFT_BOUNDARY ? 110 CGAL::SMALLER : CGAL::LARGER); 111 return (_m_adapter->kernel(). 112 compare_y_curve_ends_2_object()(arc, p2.arc(), end)); 113 } 114 // compare curve ends at +/-oo in y 115 if(Native_arc_2::is_on_bottom_top(loc2)) { 116 CGAL::Comparison_result res = (_m_adapter->kernel(). 117 compare_x_curve_ends_2_object() 118 (arc, end, p2.arc(), p2.curve_end())); 119 if(res == CGAL::EQUAL && end == p2.curve_end() && 120 loc1 != loc2) { 121 return (loc1 == CGAL::ARR_BOTTOM_BOUNDARY ? 122 CGAL::SMALLER : CGAL::LARGER); 123 } 124 return res; 125 } 126 return (loc2 == CGAL::ARR_LEFT_BOUNDARY ? CGAL::LARGER : 127 CGAL::SMALLER); 128 } 129 pt = p2.point(); 130 inverse = true; // inverse result since we compare p2 against p1 131 } 132 CGAL::Comparison_result res; 133 if(Native_arc_2::is_on_left_right(loc1)) // p1 (point) against p2 (arc) 134 res = (loc1 == CGAL::ARR_LEFT_BOUNDARY ? CGAL::LARGER : 135 CGAL::SMALLER); 136 else { 137 // point is p1, arc is p2 138 // compares a finite point with a curve end at y=+/-oo: 139 res = _m_adapter->kernel().kernel().compare_1_object() 140 (pt.x(), arc.curve_end_x(end)); 141 142 if(res == CGAL::EQUAL) // in case of equality use boundary types: 143 res = (loc1 == CGAL::ARR_BOTTOM_BOUNDARY ? CGAL::LARGER : 144 CGAL::SMALLER); 145 } 146 return (inverse ? -res : res); 147 } 148 149 private: 150 SweepCurvesAdapter_2 *_m_adapter; 151 }; 152 153 template < class SweepCurvesAdapter_2 > 154 class Less_xy_2 155 { 156 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 157 158 public: 159 typedef bool result_type; 160 161 //! standard constructor Less_xy_2(SweepCurvesAdapter_2 * adapter)162 Less_xy_2(SweepCurvesAdapter_2 *adapter) : 163 _m_adapter(adapter) { 164 CGAL_assertion(adapter != nullptr); 165 } 166 167 /*! 168 * returns \c true if p1 \< p2 lexicographical 169 */ operator()170 result_type operator()(const Point_2& p1, const Point_2& p2) const { 171 return (_m_adapter->compare_xy_2_object()(p1, p2) == CGAL::SMALLER); 172 } 173 174 private: 175 SweepCurvesAdapter_2 *_m_adapter; 176 }; 177 178 template < class SweepCurvesAdapter_2 > 179 class Compare_y_at_x_2 180 { 181 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 182 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 183 184 public: 185 typedef CGAL::Comparison_result result_type; 186 187 //! standard constructor Compare_y_at_x_2(SweepCurvesAdapter_2 * adapter)188 Compare_y_at_x_2(SweepCurvesAdapter_2 *adapter) : 189 _m_adapter(adapter) { 190 CGAL_assertion(adapter != nullptr); 191 } 192 operator()193 result_type operator()(const Arc_2& cv, const Point_2& p) const { 194 result_type res = (*this)(cv, p, true); 195 SCA_CERR("Result: " << res << "\n"); 196 return res; 197 } 198 199 /*! 200 * Return the location of the given point with respect to the input curve. 201 * \param cv The curve. 202 * \param p The point. 203 * \pre p is in the x-range of cv. 204 * \return SMALLER if y(p) \< cv(x(p)), i.e. the point is below the curve; 205 * LARGER if y(p) > cv(x(p)), i.e. the point is above the curve; 206 * EQUAL if p lies on the curve. 207 */ operator()208 result_type operator()(const Arc_2& cv, const Point_2& p, bool) const { 209 210 SCA_CERR("Compare_y_at_x_2: cv: " << cv << "\n point: " << 211 p << std::endl); 212 213 typedef typename SweepCurvesAdapter_2::Native_arc_2 Native_arc_2; 214 typename SweepCurvesAdapter_2::Native_point_2 pt; 215 typename SweepCurvesAdapter_2::Native_point_2::Coordinate_1 x; 216 if(cv.is_degenerate()) { 217 218 if(!cv.source().is_finite()) { // degenerate arc at inf 219 CGAL_precondition(!p.is_finite()); // p must also lie at inf 220 return (_m_adapter->compare_xy_2_object()(p, cv.source())); 221 } 222 pt = cv.source().point(); 223 CGAL_precondition_code( 224 x = (p.is_finite() ? p.point().x() : 225 p.arc().curve_end_x(p.curve_end())); 226 ); 227 // cv.source().x() must be accessible here 228 CGAL_precondition(x == pt.x()); 229 if(p.is_finite()) 230 return (_m_adapter->kernel().compare_xy_2_object() 231 (p.point(), pt)); 232 // for infinite curve end: return inversed result 233 return -(_m_adapter->kernel().compare_y_at_x_2_object()(pt, 234 p.arc())); 235 } 236 if(p.is_finite()) 237 return _m_adapter->kernel().compare_y_at_x_2_object()(p.point(), 238 cv.arc()); 239 240 CGAL::Arr_curve_end end = p.curve_end(), end2; 241 // CGAL::Boundary_type bnd_x = p.arc().boundary_in_x(end); 242 CGAL::Arr_parameter_space locp = p.arc().location(end); 243 244 if(Native_arc_2::is_on_left_right(locp)) { 245 CGAL_precondition(locp == cv.arc().location(end)); 246 // compare two curve ends at +/-oo in x 247 return _m_adapter->kernel().compare_y_curve_ends_2_object() 248 (p.arc(), cv.arc(), end); 249 } 250 // p.arc() has vertical asymptote; cases: 251 // 1. cv.arc() is vertical => cv.arc().x == p.curve_end_x() 252 // 2. cv.arc() has no vertical asymptote at p.curve_end_x() 253 // 3. cv.arc() has vertical asymptote at p.curve_end_x() 254 // cases 1. and 3. relate to comparison of two inf curve ends 255 x = p.arc().curve_end_x(end); 256 bool eq_min, eq_max, in_x_range = cv.arc().is_in_x_range(x, &eq_min, 257 &eq_max); 258 end2 = CGAL::ARR_MIN_END; // relevant cv.arc()'s end for comparison 259 (void)in_x_range; 260 CGAL_precondition(in_x_range); 261 262 if(!cv.arc().is_vertical()) { 263 if(eq_max && Native_arc_2::is_on_bottom_top( 264 cv.arc().location(CGAL::ARR_MAX_END))) { 265 end2 = CGAL::ARR_MAX_END; 266 } else if(!eq_min || !Native_arc_2::is_on_bottom_top( 267 cv.arc().location(CGAL::ARR_MIN_END))) { 268 // compare finite point against asymptotic or vertical curve end 269 return (locp == CGAL::ARR_BOTTOM_BOUNDARY ? CGAL::SMALLER : 270 CGAL::LARGER); 271 } 272 } else { 273 CGAL_precondition_msg(p.arc().is_vertical(), 274 "p.arc is not within vertical arc x-range!!"); 275 // arc is vertical => infinite end coincides 276 return CGAL::EQUAL; // two vertical arcs => coincide 277 } 278 279 CGAL_precondition_msg(end == end2, "Point is not within the arc's " 280 "x-range"); 281 282 if(locp != cv.arc().location(end2)) 283 return (locp == CGAL::ARR_BOTTOM_BOUNDARY ? 284 CGAL::SMALLER : CGAL::LARGER); 285 // compare either two asymptotic ends or one vertical arc + asymptote 286 // check whether result need to be reversed 287 CGAL::Comparison_result res = 288 (_m_adapter->kernel().compare_x_curve_ends_2_object() 289 (p.arc(), end, cv.arc(), end2)); 290 291 if(locp == cv.arc().location(end2) && 292 !p.arc().is_vertical() && !cv.arc().is_vertical()) 293 if((end == CGAL::ARR_MAX_END && locp == CGAL::ARR_TOP_BOUNDARY) || 294 (end == CGAL::ARR_MIN_END && locp == CGAL::ARR_BOTTOM_BOUNDARY)) 295 res = -res; 296 return res; 297 } 298 299 private: 300 SweepCurvesAdapter_2 *_m_adapter; 301 302 }; 303 304 template < class SweepCurvesAdapter_2 > 305 class Equal_y_at_x_2 306 { 307 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 308 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 309 310 public: 311 typedef bool result_type; 312 313 //! standard constructor Equal_y_at_x_2(SweepCurvesAdapter_2 * adapter)314 Equal_y_at_x_2(SweepCurvesAdapter_2 *adapter) : 315 _m_adapter(adapter) { 316 CGAL_assertion(adapter != nullptr); 317 } 318 319 /*! 320 * returns true if \c p lies on curve \c cv 321 */ operator()322 result_type operator()(const Arc_2& cv, const Point_2& p) const 323 { 324 return (_m_adapter->compare_y_at_x_2_object()(cv, p) == CGAL::EQUAL); 325 } 326 327 private: 328 SweepCurvesAdapter_2 *_m_adapter; 329 330 }; 331 332 template < class SweepCurvesAdapter_2 > 333 class Multiplicity_of_intersection_2 { 334 335 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 336 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 337 338 public: 339 typedef int result_type; 340 341 //! standard constructor Multiplicity_of_intersection_2(SweepCurvesAdapter_2 *)342 Multiplicity_of_intersection_2(SweepCurvesAdapter_2 *) { 343 } 344 345 /*!\brief 346 * multiplicity of intersection 347 * 348 * The intersection multiplicity of \c *this and \c cv2 at point \c p is 349 * returned. 350 * 351 * \pre \c p must be an intersection point. 352 * \pre both arcs are not degenerate 353 */ operator()354 result_type operator()(const Arc_2& cv1, const Arc_2& cv2, 355 const Point_2& p) const { 356 357 SCA_CERR("Multiplicity_of_intersection_2: cv1: " << cv1 << "\n cv2: " 358 << cv2 << std::endl); 359 360 CGAL_precondition(!cv1.is_degenerate()); 361 CGAL_precondition(!cv2.is_degenerate()); 362 CGAL_precondition(p.is_finite()); 363 return cv1.arc().multiplicity_of_intersection(cv2.arc(), p.point()); 364 } 365 }; 366 367 template < class SweepCurvesAdapter_2 > 368 class Compare_y_right_of_point_2 369 { 370 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 371 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 372 373 public: 374 typedef CGAL::Comparison_result result_type; 375 376 //! standard constructor Compare_y_right_of_point_2(SweepCurvesAdapter_2 *)377 Compare_y_right_of_point_2(SweepCurvesAdapter_2 *) { 378 } 379 380 /*! 381 * Compares the y value of two x-monotone curves immediately 382 * to the right of their intersection point. If one of the curves is 383 * vertical (emanating upward from p), it's always considered to be above 384 * the other curve. 385 * \param cv1 The first curve. 386 * \param cv2 The second curve. 387 * \param p The intersection point. 388 * \pre The point p lies on both curves, and both of them must be 389 * also be defined (lexicographically) to its right. 390 * \return The relative position of cv1 with respect to 391 * cv2 immdiately to the right of p: SMALLER, LARGER or EQUAL. 392 */ operator()393 result_type operator()(const Arc_2& cv1, const Arc_2& cv2, 394 const Point_2& p) const { 395 396 SCA_CERR("Compare_y_right_of_point_2: cv1: " << cv1 << "\n cv2: " << 397 cv2 << "\n pt: " << p << std::endl); 398 399 CGAL_precondition(!cv1.is_degenerate()); 400 CGAL_precondition(!cv2.is_degenerate()); 401 CGAL_precondition(p.is_finite()); 402 return (cv1.arc().compare_y_at_x_right(cv2.arc(), p.point())); 403 } 404 }; 405 406 407 template < class SweepCurvesAdapter_2 > 408 class Source_2 409 { 410 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 411 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 412 413 public: 414 typedef Point_2 result_type; 415 416 //! standard constructor Source_2(SweepCurvesAdapter_2 * adapter)417 Source_2(SweepCurvesAdapter_2 *adapter) : 418 _m_adapter(adapter) { 419 CGAL_assertion(adapter != nullptr); 420 } 421 422 /*! 423 * returns a minimal end of a curve arc 424 */ operator()425 result_type operator()(const Arc_2& cv) const { 426 return cv.source(); 427 } 428 429 private: 430 SweepCurvesAdapter_2 *_m_adapter; 431 432 }; 433 434 template < class SweepCurvesAdapter_2 > 435 class Target_2 436 { 437 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 438 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 439 440 public: 441 typedef Point_2 result_type; 442 443 //! standard constructor Target_2(SweepCurvesAdapter_2 * adapter)444 Target_2(SweepCurvesAdapter_2 *adapter) : 445 _m_adapter(adapter) { 446 CGAL_assertion(adapter != nullptr); 447 } 448 449 /*! 450 * returns a maximal end of a curve arc 451 */ operator()452 result_type operator()(const Arc_2& cv) const { 453 return cv.target(); 454 } 455 456 private: 457 SweepCurvesAdapter_2 *_m_adapter; 458 459 }; 460 461 template < class SweepCurvesAdapter_2 > 462 class Construct_segment_2 463 { 464 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 465 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 466 467 public: 468 typedef Arc_2 result_type; 469 470 //! standard constructor Construct_segment_2(SweepCurvesAdapter_2 *)471 Construct_segment_2(SweepCurvesAdapter_2 *) { 472 } 473 474 /*! 475 * constructs a degenerate segment from a given point 476 */ operator()477 result_type operator()(const Point_2& p) const { 478 479 // SCA_CERR("Construct_segment_2: arc@" << aa.id() << 480 // "; point@" << p.id() << std::endl); 481 return Arc_2(p); 482 } 483 }; 484 485 template < class SweepCurvesAdapter_2 > 486 class Is_degenerate_2 487 { 488 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 489 490 public: 491 typedef bool result_type; 492 493 //! standard constructor Is_degenerate_2(SweepCurvesAdapter_2 *)494 Is_degenerate_2(SweepCurvesAdapter_2 *) { 495 } 496 497 /*! 498 * checks whether this arc represents an isolated point (i.e., degenerate) 499 */ operator()500 result_type operator()(const Arc_2& cv) const { 501 502 return cv.is_degenerate(); 503 } 504 }; 505 506 template < class SweepCurvesAdapter_2 > 507 class Do_overlap_2 508 { 509 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 510 511 public: 512 typedef bool result_type; 513 514 //! standard constructor Do_overlap_2(SweepCurvesAdapter_2 *)515 Do_overlap_2(SweepCurvesAdapter_2 *) { 516 } 517 518 /*!\brief 519 * checks whether two curve arcs have infinitely many intersection points, 520 * i.e., they overlap 521 */ operator()522 result_type operator()(const Arc_2& cv1, const Arc_2& cv2) const { 523 524 if(cv1.is_degenerate() || cv2.is_degenerate()) 525 return false; 526 return cv1.arc().do_overlap(cv2.arc()); 527 } 528 }; 529 530 template < class SweepCurvesAdapter_2 > 531 class New_endpoints_2 { 532 533 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 534 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 535 536 public: 537 typedef Arc_2 result_type; 538 539 //! standard constructor New_endpoints_2(SweepCurvesAdapter_2 * adapter)540 New_endpoints_2(SweepCurvesAdapter_2 *adapter) : 541 _m_adapter(adapter) { 542 CGAL_assertion(adapter != nullptr); 543 } 544 545 /*!\brief 546 * returns the input segment with new - but equal - endpoints 547 */ operator()548 result_type operator()(const Arc_2& cv, const Point_2& p, 549 const Point_2& q) const { 550 551 SCA_CERR("New_endpoints_2: cv: " << cv << "\n p: " << 552 p << "\n q: " << q << std::endl); 553 554 CGAL_precondition( 555 _m_adapter->compare_xy_2_object()(cv.source(), p) == CGAL::EQUAL 556 ); 557 CGAL_precondition( 558 _m_adapter->compare_xy_2_object()(cv.target(), q) == CGAL::EQUAL 559 ); 560 561 cv.new_endpoints(p, q); 562 return cv; 563 } 564 565 private: 566 SweepCurvesAdapter_2 *_m_adapter; 567 568 }; 569 570 template < class SweepCurvesAdapter_2 > 571 class New_endpoints_opposite_2 { 572 573 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 574 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 575 576 public: 577 typedef Arc_2 result_type; 578 579 //! standard constructor New_endpoints_opposite_2(SweepCurvesAdapter_2 *)580 New_endpoints_opposite_2(SweepCurvesAdapter_2 *) { 581 } 582 583 /*!\brief 584 * returns the input segment with new - but equal - endpoints 585 * lexicographic order of endpoints is ensured automatically, hence no 586 * special handling is required 587 */ operator()588 result_type operator()(const Arc_2& cv, 589 const Point_2& /* p */, 590 const Point_2& /* q */) const { 591 SCA_CERR("\n\nWARNING!! New_endpoints_opposite_2: cv: " << cv << 592 "\n p: " << p << "\n q: " << q << std::endl); 593 CGAL_error_msg("New_endpoints_opposite_2 deprecated and must not be \ 594 called\n"); 595 //CGAL_precondition(p.is_finite() && q.is_finite()); 596 //return cv.new_endpoints(p.point(), q.point()); 597 return cv; 598 } 599 }; 600 601 template < class SweepCurvesAdapter_2 > 602 class Intersect_2 { 603 604 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 605 606 public: 607 //typedef bool result_type; 608 609 //! standard constructor Intersect_2(SweepCurvesAdapter_2 *)610 Intersect_2(SweepCurvesAdapter_2 *) { 611 } 612 613 /*!\brief 614 * computes intersection points of \c *this and \c cv2, writes the result 615 * to the output iterator \c oi 616 */ 617 template <class OutputIterator> operator()618 OutputIterator operator()(const Arc_2& cv1, const Arc_2& cv2, 619 OutputIterator oi) { 620 621 SCA_CERR("Intersect_2: cv1: " << cv1 << "\n cv2: " << 622 cv2 << std::endl); 623 624 return cv1.intersect(cv2, oi); 625 } 626 }; 627 628 template < class SweepCurvesAdapter_2 > 629 class Intersect_right_of_point_2 { 630 631 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 632 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Arc_2; 633 634 public: 635 typedef bool result_type; 636 637 //! standard constructor Intersect_right_of_point_2(SweepCurvesAdapter_2 * adapter)638 Intersect_right_of_point_2(SweepCurvesAdapter_2 *adapter) : 639 _m_adapter(adapter) { 640 CGAL_assertion(adapter != nullptr); 641 } 642 643 /*!\brief 644 * computes the next intersection of \c cv1 and \c cv2 right of \c ref 645 * in lexicographical order and returns it through \c res argument 646 * 647 * intersect_right_of_point is not called when using sweep_curves() with 648 * intersection dictionary and without validation of internal structures 649 * (as is standard). Hence we can be lazy here for the moment 650 * without losing performance. 651 */ operator()652 result_type operator()(const Arc_2& cv1, const Arc_2& cv2, 653 const Point_2& ref, Point_2& res) const { 654 655 SCA_CERR("Intersect_right_of_point_2: cv1: " << cv1 << "\n cv2: " << 656 cv2 << "\n ref: " << ref << std::endl); 657 658 typedef std::vector<Point_2> Point_container; 659 Point_container tmp; 660 cv1.intersect(cv2, back_inserter(tmp)); 661 662 for(typename Point_container::const_iterator it = tmp.begin(); 663 it != tmp.end(); it++) { 664 // assume points are sorted lexicographical 665 if(_m_adapter->compare_xy_2_object()(*it, ref) == CGAL::LARGER) { 666 res = *it; 667 SCA_CERR("intersection found: " << res << "\n"); 668 return true; 669 } 670 } 671 return false; 672 } 673 674 private: 675 SweepCurvesAdapter_2 *_m_adapter; 676 677 }; 678 679 template < class SweepCurvesAdapter_2 > 680 class Make_x_monotone_2 681 { 682 typedef typename SweepCurvesAdapter_2::Curve_2 Curve_2; 683 typedef typename SweepCurvesAdapter_2::Generic_point_2 Point_2; 684 typedef typename SweepCurvesAdapter_2::Generic_arc_2 Generic_arc_2; 685 686 public: 687 typedef CGAL::cpp98::iterator<std::output_iterator_tag, Generic_arc_2> 688 result_type; 689 690 //! standard constructor Make_x_monotone_2(SweepCurvesAdapter_2 * adapter)691 Make_x_monotone_2(SweepCurvesAdapter_2 *adapter) : 692 _m_adapter(adapter) { 693 CGAL_assertion(adapter != nullptr); 694 } 695 696 /*! 697 * decompose a given arc into list of x-monotone pieces 698 * (subcurves) and insert them to the output iterator. Since \c Arc_2 699 * is by definition x-monotone, an input arc is passed to the 700 * output iterator directly. 701 * \param cv The curve. 702 * \param oi The output iteratorfor the result. Its dereference type is a 703 * variant that wraps a \c Point_2 or an \c X_monotone_curve_2 704 * objects.. 705 * \return The past-the-end output iterator. 706 */ 707 template<class OutputIterator> operator()708 OutputIterator operator()(const Generic_arc_2& cv, OutputIterator oi) const 709 { 710 *oi++ = cv; 711 return oi; 712 } 713 714 /*! 715 * decompose a given curve into list of x-monotone pieces 716 * (subcurves) and insert them to the output iterator. 717 * \param cv The curve. 718 * \param oi the output iterator for the result. Its dereference type is a 719 * variant that wraps a \c Point_2 or an \c X_monotone_curve_2 720 * objects. 721 * \return The past-the-end output iterator. 722 */ 723 template<class OutputIterator> operator()724 OutputIterator operator()(const Curve_2& cv, OutputIterator oi) const { 725 726 typedef typename SweepCurvesAdapter_2::Native_arc_2 Native_arc_2; 727 typedef typename SweepCurvesAdapter_2::Native_point_2 Native_point_2; 728 typedef typename SweepCurvesAdapter_2::Generic_point_2 Generic_point_2; 729 typedef boost::variant<Native_arc_2, Native_point_2> 730 Make_x_monotone_result; 731 732 std::vector<Make_x_monotone_result> objs; 733 auto make_x_monotone = _m_adapter->kernel().make_x_monotone_2_object(); 734 make_x_monotone(cv, std::back_inserter(objs)); 735 // sort out normal and degenerate arcs 736 for (auto& obj : objs) { 737 if (auto* arc = boost::get<Native_arc_2>(&obj)) { 738 *oi++ = Generic_arc_2(*arc); 739 continue; 740 } 741 auto* pt = boost::get<Native_point_2>(&obj); 742 CGAL_assertion(pt); 743 *oi++ = Generic_arc_2(Generic_point_2(*pt)); 744 } 745 return oi; 746 } 747 748 private: 749 SweepCurvesAdapter_2 *_m_adapter; 750 }; 751 752 } // Sweep_curves_functors 753 754 //! \brief a wrapper class for \c Curved_kernel_via_analysis_2 755 template < class CurvedKernelViaAnalysis_2 > 756 class Sweep_curves_adapter_2 { 757 //: public Curved_kernel_via_analysis_2<CurveKernel_2> { 758 759 public: 760 //! \name public typedefs 761 //!@{ 762 763 //! this instance's template parameter 764 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 765 766 //! type of curve kernel 767 typedef typename Curved_kernel_via_analysis_2::Curve_kernel_2 768 Curve_kernel_2; 769 770 //! myself 771 typedef Sweep_curves_adapter_2< Curved_kernel_via_analysis_2 > Self; 772 773 //!@} 774 775 public: 776 //! \name Constructors 777 //!@{ 778 779 //! default constructor Sweep_curves_adapter_2()780 Sweep_curves_adapter_2() { 781 } 782 783 //! construct using specific \c CKvA_2 instance (for controlling) Sweep_curves_adapter_2(const Curved_kernel_via_analysis_2 & kernel)784 Sweep_curves_adapter_2(const Curved_kernel_via_analysis_2& kernel) : 785 _m_kernel(kernel) { 786 } 787 788 //!@} 789 790 //!\name embedded types and predicates for \c CurveSweepTraits 791 //!@{ 792 793 //! native Curved_kernel_via_analysis_2 objects 794 typedef typename Curved_kernel_via_analysis_2::Curve_2 Curve_2; 795 typedef typename Curved_kernel_via_analysis_2::Point_2 Native_point_2; 796 typedef typename Curved_kernel_via_analysis_2::Arc_2 Native_arc_2; 797 798 //! generic point (supports infinity) 799 typedef internal::Generic_point_2<Self> Generic_point_2; 800 801 //! generic arc (supports isolated points) 802 typedef internal::Generic_arc_2<Self> Generic_arc_2; 803 804 //! type of point in model of \c CurveSweepTraits_2 805 typedef Generic_point_2 Point_2; 806 807 //! type of segment in model of \c CurveSweepTraits_2 808 typedef Generic_arc_2 Segment_2; 809 810 // declares functors, for each functor defines a member function 811 // returning an instance of this functor 812 #define CGAL_Sweep_curves_pred(Y, Z) \ 813 typedef Sweep_curves_functors::Y<Self> Y; \ 814 Y Z() const { return Y((Sweep_curves_adapter_2 *)this); } 815 #define CGAL_Sweep_curves_cons(Y, Z) CGAL_Sweep_curves_pred(Y, Z) 816 CGAL_Sweep_curves_pred(Compare_xy_2,compare_xy_2_object)817 CGAL_Sweep_curves_pred(Compare_xy_2, compare_xy_2_object) 818 CGAL_Sweep_curves_pred(Less_xy_2, less_xy_2_object) 819 CGAL_Sweep_curves_pred(Is_degenerate_2, is_degenerate_2_object) 820 821 CGAL_Sweep_curves_pred(Do_overlap_2, do_overlap_2_object) 822 CGAL_Sweep_curves_pred(Compare_y_at_x_2, compare_y_at_x_2_object) 823 CGAL_Sweep_curves_pred(Equal_y_at_x_2, equal_y_at_x_2_object) 824 825 CGAL_Sweep_curves_pred(Multiplicity_of_intersection_2, 826 multiplicity_of_intersection_2_object) 827 CGAL_Sweep_curves_pred(Compare_y_right_of_point_2, 828 compare_y_right_of_point_2_object) 829 830 CGAL_Sweep_curves_cons(Source_2, source_2_object) 831 CGAL_Sweep_curves_cons(Target_2, target_2_object) 832 CGAL_Sweep_curves_cons(Construct_segment_2, construct_segment_2_object) 833 834 CGAL_Sweep_curves_cons(New_endpoints_2, new_endpoints_2_object) 835 CGAL_Sweep_curves_cons(New_endpoints_opposite_2, 836 new_endpoints_opposite_2_object) 837 838 CGAL_Sweep_curves_cons(Intersect_2, intersect_2_object) 839 CGAL_Sweep_curves_cons(Intersect_right_of_point_2, 840 intersect_right_of_point_2_object) 841 842 CGAL_Sweep_curves_cons(Make_x_monotone_2, make_x_monotone_2_object) 843 844 #undef CGAL_Sweep_curves_pred 845 #undef CGAL_Sweep_curves_cons 846 847 const Curved_kernel_via_analysis_2& kernel() const { 848 return _m_kernel; 849 } 850 851 //!@} 852 853 protected: 854 //!\name private members 855 //!@{ 856 857 //! reference to Curved_kernel_via_analysis_2 object 858 Curved_kernel_via_analysis_2 _m_kernel; 859 860 //!@} 861 }; // class Sweep_curves_adapter_2 862 863 } //namespace CGAL 864 865 #endif // CGAL_CURVED_KERNEL_VIA_ANALYSIS_2_SWEEP_CURVES_ADAPTER_2 866 // EOF 867