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/Curved_kernel_via_analysis_2_functors.h $ 7 // $Id: Curved_kernel_via_analysis_2_functors.h 4e519a3 2021-05-05T13:15:37+02:00 Sébastien Loriot 8 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Eric Berberich <eric@mpi-inf.mpg.de> 12 // Pavel Emeliyanenko <asm@mpi-sb.mpg.de> 13 14 #ifndef CGAL_CURVED_KERNEL_VIA_ANALYSIS_2_FUNCTORS_H 15 #define CGAL_CURVED_KERNEL_VIA_ANALYSIS_2_FUNCTORS_H 16 17 /*!\file include/CGAL/Curved_kernel_via_analysis_2/Curved_kernel_via_analysis_2_functors.h 18 * \brief defines Curved_kernel_via_analysis_2 function objects + class 19 */ 20 21 #include <CGAL/config.h> 22 #include <CGAL/Curved_kernel_via_analysis_2/Make_x_monotone_2.h> 23 #include <CGAL/iterator.h> 24 namespace CGAL { 25 26 namespace internal { 27 28 #ifndef CERR 29 //#define CKvA_DEBUG_PRINT_CERR 30 #ifdef CKvA_DEBUG_PRINT_CERR 31 #define CERR(x) std::cerr << x 32 #else 33 #define CERR(x) static_cast<void>(0) 34 #endif 35 #endif 36 37 /*!\brief 38 * Collects main functors for Curved_kernel_via_analysis_2 39 */ 40 namespace Curved_kernel_via_analysis_2_Functors { 41 42 /*!\brief 43 * Base functor class for inheritance 44 */ 45 template < class CurvedKernelViaAnalysis_2 > 46 class Curved_kernel_via_analysis_2_functor_base { 47 48 public: 49 //!\name Public types 50 //!@{ 51 52 //! this instance's template parameter 53 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 54 55 //! the point type 56 typedef typename Curved_kernel_via_analysis_2::Point_2 Point_2; 57 58 //! the arc type 59 typedef typename Curved_kernel_via_analysis_2::Arc_2 Arc_2; 60 61 //! type of curve kernel 62 typedef typename Curved_kernel_via_analysis_2::Curve_kernel_2 63 Curve_kernel_2; 64 65 //! type of curve analaysis 66 typedef typename Curve_kernel_2::Curve_analysis_2 Curve_analysis_2; 67 68 //! the x-coordinate type 69 typedef typename Point_2::Coordinate_1 Coordinate_1; 70 //typedef typename Point_2::Y_coordinate_1 Y_coordinate_1; 71 72 73 //!@} 74 75 public: 76 //!\name Constructors 77 //!@{ 78 79 /*!\brief 80 * Constructs base functor 81 * 82 * \param kernel The kernel instance 83 */ Curved_kernel_via_analysis_2_functor_base(Curved_kernel_via_analysis_2 * kernel)84 Curved_kernel_via_analysis_2_functor_base( 85 Curved_kernel_via_analysis_2 *kernel) : 86 _m_curved_kernel(kernel) { 87 CGAL_precondition(kernel != nullptr); 88 } 89 90 //!@} 91 92 protected: 93 //!\name Access members 94 //!@{ 95 96 /*!\brief 97 * Return pointer to curved kernel 98 * \return Pointer to stored kernel 99 */ _ckva()100 Curved_kernel_via_analysis_2* _ckva() const { 101 return _m_curved_kernel; 102 } 103 104 //!@} 105 106 protected: 107 //!\name Data members 108 //!@{ 109 110 //! stores pointer to \c Curved_kernel_via_analysis_2 111 Curved_kernel_via_analysis_2 *_m_curved_kernel; 112 113 //!@} 114 }; 115 116 #define CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES \ 117 typedef typename Base::Point_2 Point_2; \ 118 typedef typename Base::Arc_2 Arc_2; \ 119 typedef typename Base::Curve_analysis_2 Curve_analysis_2; \ 120 typedef typename Base::Coordinate_1 Coordinate_1; \ 121 //typedef typename Base::Y_coordinate_1 Y_coordinate_1; 122 123 /*!\brief 124 * Functor to construct a point on a curve 125 */ 126 template < class CurvedKernelViaAnalysis_2 > 127 class Construct_point_2 : public 128 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 129 130 public: 131 //! this instance' first template parameter 132 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 133 134 //! the base type 135 typedef 136 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 137 Base; 138 139 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 140 141 //! the result type 142 typedef Point_2 result_type; 143 144 /*!\brief 145 * Standard constructor 146 * 147 * \param kernel The kernel 148 */ Construct_point_2(Curved_kernel_via_analysis_2 * kernel)149 Construct_point_2(Curved_kernel_via_analysis_2 *kernel) : 150 Base(kernel) { 151 } 152 153 /*!\brief 154 * Constructs an interior point 155 * 156 * \param x x-coordinate 157 * \param c The supporting curve 158 * \param arcno Arcnumber on curve 159 * \return The constructed point 160 */ operator()161 Point_2 operator()(const Coordinate_1& x, 162 const Curve_analysis_2& c, 163 int arcno) { 164 Point_2 pt(x, c, arcno); 165 return pt; 166 } 167 operator()168 Point_2 operator()(const Coordinate_1& x, 169 const Arc_2& a) { 170 CGAL_precondition(a.is_in_x_range(x)); 171 Point_2 pt(x, a.curve(), a.arcno(x)); 172 return pt; 173 } 174 175 176 template <typename T> operator()177 Point_2 operator() (const T& x, 178 const T& y) { 179 Point_2 pt(x,y); 180 return pt; 181 } 182 183 184 }; 185 186 187 /*!\brief 188 * Functor to construct point on an arc 189 */ 190 template < class CurvedKernelViaAnalysis_2 > 191 class Construct_point_on_arc_2 : public 192 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 193 194 public: 195 //! this instance' first template parameter 196 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 197 198 //! the base type 199 typedef 200 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 201 Base; 202 203 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 204 205 //! the result type 206 typedef Point_2 result_type; 207 208 /*!\brief 209 * Standard constructor 210 * 211 * \param kernel The kernel 212 */ Construct_point_on_arc_2(Curved_kernel_via_analysis_2 * kernel)213 Construct_point_on_arc_2(Curved_kernel_via_analysis_2 *kernel) : 214 Base(kernel) { 215 } 216 217 /*!\brief 218 * Constructs point on an arc 219 * 220 * \param x x-coordinate of point 221 * \param c The supporting curve 222 * \param arcno Arcnumber on curve 223 * \param arc Can be used to query meta data 224 * \return The constructed point 225 */ operator()226 Point_2 operator()( 227 const Coordinate_1& x, 228 const Curve_analysis_2& c, int arcno, const Arc_2& arc 229 ) { 230 231 // avoid compiler warning 232 (void)arc; 233 234 //CGAL::IO::set_pretty_mode(std::cerr); 235 CERR("Construct_pt_on_arc: " << CGAL::to_double(x) << ", " << arcno << 236 ", " << c.id() << "\narc = " << arc << "\n"); 237 238 //CGAL_assertion(c.id() == arc.curve().id()); 239 //CGAL_assertion(arcno == arc.arcno(x)); 240 241 Point_2 pt = Base::_ckva()->construct_point_2_object()(x, c, arcno); 242 243 // here we can modify the point wrt "data stored in arc", 244 // if we want to 245 return pt; 246 } 247 }; 248 249 250 /*!\brief 251 * Functor to construct an x-monotone arc 252 */ 253 template < class CurvedKernelViaAnalysis_2 > 254 class Construct_arc_2 : public 255 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 256 257 public: 258 //! this instance' first template parameter 259 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 260 261 //! the base type 262 typedef 263 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 264 Base; 265 266 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 267 268 //! the result type 269 typedef Arc_2 result_type; 270 271 /*!\brief 272 * Standard constructor 273 * 274 * \param kernel The kernel 275 */ Construct_arc_2(Curved_kernel_via_analysis_2 * kernel)276 Construct_arc_2(Curved_kernel_via_analysis_2 *kernel) : 277 Base(kernel) { 278 } 279 280 //!\name Constructing non-vertical arcs 281 //!@{ 282 283 /*!\brief 284 * Constructs a non-vertical arc with two interior end-points (segment). 285 * 286 * \param p first endpoint 287 * \param q second endpoint 288 * \param c The supporting curve 289 * \param arcno The arcnumber wrt \c c in the interior of the arc 290 * \param arcno_p The arcnumber wrt \c c of the arc at \c p 291 * \param arcno_q The arcnumber wrt \c c of the arc at \c q 292 * \returns The constructed segment 293 * 294 * \pre p.x() != q.x() 295 * 296 */ operator()297 Arc_2 operator()(const Point_2& p, const Point_2& q, 298 const Curve_analysis_2& c, 299 int arcno, int arcno_p, int arcno_q) { 300 Arc_2 arc(p, q, c, arcno, arcno_p, arcno_q); 301 return arc; 302 } 303 304 /*!\brief 305 * Constructs a non-vertical arc with one interior end-point and whose 306 * other end approaches the left or right boundary of the parameter space 307 * (ray I) 308 * 309 * \param origin The interior end-point of the ray 310 * \param inf_end Defining whether the arc emanates from the left or right 311 * boundary 312 * \param c The supporting curve 313 * \param arcno The arcnumber wrt \c c in the interior of the arc 314 * \param arcno_o The arcnumber wrt \c c of the arc at \c origin 315 * \return The constructed ray 316 */ operator()317 Arc_2 operator()(const Point_2& origin, CGAL::Arr_curve_end inf_end, 318 const Curve_analysis_2& c, int arcno, int arcno_o) { 319 Arc_2 arc(origin, inf_end, c, arcno, arcno_o); 320 return arc; 321 } 322 323 /*!\brief 324 * Constructs a non-vertical arc with one interior end-point and whose 325 * other end approaches a vertical asymptote (ray II) 326 * 327 * \param origin The interior end-point 328 * \param asympt_x The x-coordinate of the vertical asymptote 329 * \param inf_end Arc is approaching the bottom or top boundary 330 * \param c The supporting curve 331 * \param arcno The arcnumber wrt \c c in the interior of the arc 332 * \param arcno_o The arcnumber wrt \c c of the arc at \c origin 333 * \return The constructed ray 334 * 335 * \pre origin.x() != asympt_x 336 */ operator()337 Arc_2 operator()(const Point_2& origin, const Coordinate_1& asympt_x, 338 CGAL::Arr_curve_end inf_end, 339 const Curve_analysis_2& c, int arcno, 340 int arcno_o) { 341 Arc_2 arc(origin, asympt_x, inf_end, c, arcno, arcno_o); 342 return arc; 343 } 344 345 /*!\brief 346 * Constructs a non-vertical arc with two non-interior ends at 347 * the left and right boundary (branch I) 348 * 349 * \param c The supporting curve 350 * \param arcno The arcnumber wrt to \c c in the interior of the arc 351 * \return The constructed branch 352 */ operator()353 Arc_2 operator()(const Curve_analysis_2& c, int arcno) { 354 Arc_2 arc(c, arcno); 355 return arc; 356 } 357 358 /*!\brief 359 * Constructs a non-vertical arc with two ends approaching vertical 360 * asymptotes (branch II). 361 * 362 * \param asympt_x1 The x-coordinate of the first asymptote 363 * \param inf_end1 Arc is approaching the bottom or top boundary at 364 * \c asympt_x1 365 * \param asympt_x2 The x-coordinate of the second asymptote 366 * \param inf_end2 Arc is approaching the bottom or top boundary at 367 * \c asympt_x2 368 * \return The constructed branch 369 * 370 * \pre asympt_x1 != asympt_x2 371 */ operator()372 Arc_2 operator()(const Coordinate_1& asympt_x1, 373 CGAL::Arr_curve_end inf_end1, 374 const Coordinate_1& asympt_x2, 375 CGAL::Arr_curve_end inf_end2, 376 const Curve_analysis_2& c, int arcno) { 377 Arc_2 arc(asympt_x1, inf_end1, asympt_x2, inf_end2, c, arcno); 378 return arc; 379 } 380 381 /*!\brief 382 * Construct a non-vertical arc with one left- or right-boundary end 383 * and one end that approaches a vertical asymptote (branch III) 384 * 385 * \param inf_endx Defining whether the arc emanates from the left or right 386 * boundary 387 * \param asympt_x The x-coordinate of the asymptote 388 * \param inf_endy Arc is approaching the bottom or top boundary at 389 * asympt_x 390 * \return The constructed branch 391 */ operator()392 Arc_2 operator()(CGAL::Arr_curve_end inf_endx, 393 const Coordinate_1& asympt_x, 394 CGAL::Arr_curve_end inf_endy, 395 const Curve_analysis_2& c, int arcno) { 396 Arc_2 arc(inf_endx, asympt_x, inf_endy, c, arcno); 397 return arc; 398 } 399 400 //!@} 401 //!\name Constructing vertical arcs 402 //!@{ 403 404 /*!\brief 405 * Constructs a vertical arc with two interior end-points 406 * (vertical segment) 407 * 408 * \param p The first end-point 409 * \param q The second end-point 410 * \param c The supporting curve 411 * \return The constructed arc 412 * 413 * \pre p != q && p.x() == q.x() 414 * \pre c must have a vertical component at this x 415 */ operator()416 Arc_2 operator()(const Point_2& p, const Point_2& q, 417 const Curve_analysis_2& c) { 418 Arc_2 arc(p,q,c); 419 return arc; 420 } 421 422 /*!\brief 423 * Constructs a vertical arc with one interior end-point and 424 * one that reaches the bottom or top boundary (vertical ray) 425 * 426 * \param origin The interior end-point 427 * \param inf_end Ray emanates from bottom or top boundary 428 * \return The constructed ray 429 * 430 * \pre c must have a vertical line component at this x 431 */ operator()432 Arc_2 operator()(const Point_2& origin, CGAL::Arr_curve_end inf_end, 433 const Curve_analysis_2& c) { 434 435 Arc_2 arc(origin, inf_end, c); 436 return arc; 437 } 438 439 /*!\brief 440 * Constructs a vertical arc that connects bottom with top boundary 441 * (vertical branch) 442 * 443 * \param x The x-coordinate of the branch 444 * \return The constructed branch 445 * 446 * \pre c must have a vertical line component at this x 447 */ operator()448 Arc_2 operator()(const Coordinate_1& x, const Curve_analysis_2& c) { 449 Arc_2 arc(x, c); 450 return arc; 451 } 452 453 //!@} 454 }; 455 456 /*!\brief 457 * Functor that checks whether a given arc is vertical 458 */ 459 template < class CurvedKernelViaAnalysis_2 > 460 class Is_vertical_2 : public 461 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 462 463 public: 464 //! this instance' first template parameter 465 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 466 467 //! the base type 468 typedef 469 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 470 Base; 471 472 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 473 474 //! the result type 475 typedef bool result_type; 476 477 //! the arity of the functor 478 479 /*!\brief 480 * Standard constructor 481 * 482 * \param kernel The kernel 483 */ Is_vertical_2(Curved_kernel_via_analysis_2 * kernel)484 Is_vertical_2(Curved_kernel_via_analysis_2 *kernel) : 485 Base(kernel) { 486 } 487 488 /*!\brief 489 * Check whether the given x-monotone arc \c cv is a vertical segment. 490 * 491 * \param cv The curve. 492 * \return \c true if the curve is a vertical segment, \c false otherwise. 493 */ operator()494 result_type operator()(const Arc_2& cv) const { 495 return cv.is_vertical(); 496 } 497 }; 498 499 /*!\brief 500 * Functor constructing minimum point of an arc (if interior) 501 */ 502 template < class CurvedKernelViaAnalysis_2 > 503 class Construct_min_vertex_2 : public 504 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 505 506 public: 507 //! this instance' first template parameter 508 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 509 510 //! the base type 511 typedef 512 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 513 Base; 514 515 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 516 517 //! the result type 518 typedef Point_2 result_type; 519 520 //! the arity of the functor 521 522 /*!\brief 523 * Standard constructor 524 * 525 * \param kernel The kernel 526 */ Construct_min_vertex_2(Curved_kernel_via_analysis_2 * kernel)527 Construct_min_vertex_2(Curved_kernel_via_analysis_2 *kernel) : 528 Base(kernel) { 529 } 530 531 /*!\brief 532 * Get the minimum end-point of the arc 533 * 534 * \param cv The arc. 535 * \return The minimum end-point. 536 * 537 * \pre minimum end-point is interior 538 */ operator()539 result_type operator()(const Arc_2& cv) const { 540 541 return cv.curve_end(CGAL::ARR_MIN_END); 542 } 543 }; 544 545 /*!\brief 546 * Functor constructing maximum point of an arc (if interior) 547 */ 548 template < class CurvedKernelViaAnalysis_2 > 549 class Construct_max_vertex_2 : public 550 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 551 552 public: 553 //! this instance' first template parameter 554 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 555 556 //! the base type 557 typedef 558 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 559 Base; 560 561 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 562 563 //! the result type 564 typedef Point_2 result_type; 565 566 //! the arity of the functor 567 568 /*!\brief 569 * Standard constructor 570 * 571 * \param kernel The kernel 572 */ Construct_max_vertex_2(Curved_kernel_via_analysis_2 * kernel)573 Construct_max_vertex_2(Curved_kernel_via_analysis_2 *kernel) : 574 Base(kernel) { 575 } 576 577 /*!\brief 578 * Get the maximum end-point of the arc. 579 * 580 * \param cv The arc. 581 * \return The maximum end-point. 582 * 583 * \pre maximum end-point is interior 584 */ operator()585 result_type operator()(const Arc_2& cv) const { 586 587 return cv.curve_end(CGAL::ARR_MAX_END); 588 } 589 }; 590 591 /*!\brief 592 * Functor constructing an interior point of on an arc. 593 */ 594 template < class CurvedKernelViaAnalysis_2 > 595 class Construct_interior_vertex_2 : public 596 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 597 598 public: 599 //! this instance' first template parameter 600 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 601 602 //! the base type 603 typedef 604 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 605 Base; 606 607 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 608 609 //! the result type 610 typedef Point_2 result_type; 611 612 /*!\brief 613 * Standard constructor 614 * 615 * \param kernel The kernel 616 */ Construct_interior_vertex_2(Curved_kernel_via_analysis_2 * kernel)617 Construct_interior_vertex_2(Curved_kernel_via_analysis_2 *kernel) : 618 Base(kernel) { 619 } 620 621 /*!\brief 622 * Get an interior point on the arc. 623 * 624 * \param arc The arc. 625 * \return A point on the interior of the arc. 626 */ operator()627 result_type operator()(const Arc_2& arc) const { 628 Point_2 p = compute_interior_vertex(arc); 629 CGAL_postcondition(this->_ckva()->is_on_2_object()(p,arc)); 630 return p; 631 } 632 633 634 private: 635 compute_interior_vertex(const Arc_2 & arc)636 result_type compute_interior_vertex(const Arc_2& arc) const { 637 638 typedef typename Curved_kernel_via_analysis_2::Curve_2 Curve_analysis_2; 639 640 typedef typename Curved_kernel_via_analysis_2::Curve_kernel_2 641 Algebraic_curve_kernel_2; 642 typedef typename Algebraic_curve_kernel_2::Bound Bound; 643 typedef typename Algebraic_curve_kernel_2::Coordinate_1 Coordinate_1; 644 645 typedef CGAL::Polynomial< Bound > Poly_rat_1; 646 typedef CGAL::Polynomial< Poly_rat_1 > Poly_rat_2; 647 648 typedef CGAL::Polynomial_traits_d< Poly_rat_1 > PT_rat_1; 649 typedef CGAL::Polynomial_traits_d< Poly_rat_2 > PT_rat_2; 650 651 typedef CGAL::Fraction_traits< Poly_rat_2 > FT_2; 652 653 if (!arc.is_vertical()) 654 { 655 Bound x_coord = arc.boundary_in_x_range_interior(); 656 int arcno = arc.arcno(); 657 const Curve_analysis_2& ca = arc.curve(); 658 659 Point_2 p = Curved_kernel_via_analysis_2::instance(). 660 construct_point_on_arc_2_object() 661 (Coordinate_1(x_coord), ca, arcno, arc); 662 return p; 663 } 664 665 Bound y_coord = 0; 666 if (arc.is_finite(ARR_MIN_END)) 667 { 668 if (arc.is_finite(ARR_MAX_END)) 669 { 670 // We need torefine the interval because there is a chance that 671 // the low of the upper point is below the high of the lower point. 672 y_coord = Curved_kernel_via_analysis_2::instance().kernel(). 673 bound_between_y_2_object() (arc.curve_end(ARR_MIN_END).xy(), 674 arc.curve_end(ARR_MAX_END).xy()); 675 } 676 else 677 { 678 std::pair<Bound,Bound> approx_pair = 679 Curved_kernel_via_analysis_2::instance().kernel(). 680 approximate_relative_y_2_object() 681 (arc.curve_end(ARR_MIN_END).xy(),4); 682 y_coord = approx_pair.second + Bound(1); 683 684 } 685 } 686 else 687 { 688 if (arc.is_finite(ARR_MAX_END)) 689 { 690 std::pair<Bound,Bound> approx_pair = 691 Curved_kernel_via_analysis_2::instance().kernel(). 692 approximate_relative_y_2_object() 693 (arc.curve_end(ARR_MAX_END).xy(),4); 694 y_coord = approx_pair.first-Bound(1); 695 } 696 } 697 698 /*! \todo Try to remove this polynomial stuff */ 699 typename PT_rat_1::Construct_polynomial cp1; 700 Poly_rat_2 poly2 = typename PT_rat_2::Construct_polynomial() 701 (cp1(-y_coord), cp1(Bound(1))); 702 703 typename FT_2::Denominator_type dummy; 704 typename FT_2::Numerator_type curve_poly; 705 typename FT_2::Decompose() (poly2, curve_poly, dummy); 706 707 Curve_analysis_2 curve = Curved_kernel_via_analysis_2::instance(). 708 kernel().construct_curve_2_object()(curve_poly); 709 Point_2 p = Curved_kernel_via_analysis_2::instance(). 710 construct_point_on_arc_2_object()(arc.x(), curve, 0, arc); 711 return p; 712 } 713 }; 714 715 716 /*!\brief 717 * Functor that compares x-coordinates of two interior points 718 */ 719 template < class CurvedKernelViaAnalysis_2 > 720 class Compare_x_2 : public 721 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 722 723 public: 724 //! this instance' first template parameter 725 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 726 727 //! the base type 728 typedef 729 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 730 Base; 731 732 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 733 734 //! the result type 735 typedef CGAL::Comparison_result result_type; 736 737 //! the arity of the functor 738 739 /*!\brief 740 * Standard constructor 741 * 742 * \param kernel The kernel 743 */ Compare_x_2(Curved_kernel_via_analysis_2 * kernel)744 Compare_x_2(Curved_kernel_via_analysis_2 *kernel) : 745 Base(kernel) { 746 } 747 748 /*!\brief 749 * Compare the x-coordinates of two points. 750 * 751 * \param p1 The first point. 752 * \param p2 The second point. 753 * \return CGAL::LARGER if x(p1) > x(p2); 754 * CGAL::SMALLER if x(p1) \< x(p2); 755 * CGAL::EQUAL if x(p1) = x(p2). 756 */ operator()757 result_type operator()(const Point_2 &p1, const Point_2 &p2) const { 758 return Curved_kernel_via_analysis_2::instance(). 759 kernel().compare_1_object() 760 (p1.x(), p2.x()); 761 } 762 }; 763 764 /*!\brief 765 * Functor that compares coordinates of two interior points lexicographically 766 */ 767 template < class CurvedKernelViaAnalysis_2 > 768 class Compare_xy_2 : public 769 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 770 771 public: 772 //! this instance' first template parameter 773 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 774 775 //! the base type 776 typedef 777 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 778 Base; 779 780 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 781 782 //! the result type 783 typedef CGAL::Comparison_result result_type; 784 785 //! the arity of the functor 786 787 /*!\brief 788 * Standard constructor 789 * 790 * \param kernel The kernel 791 */ Compare_xy_2(Curved_kernel_via_analysis_2 * kernel)792 Compare_xy_2(Curved_kernel_via_analysis_2 *kernel) : 793 Base(kernel) { 794 } 795 796 /*!\brief 797 * Compares two points lexigoraphically: by x, then by y. 798 * \param p1 The first point. 799 * \param p2 The second point. 800 * \return CGAL::LARGER if x(p1) > x(p2), 801 * or if x(p1) = x(p2) and y(p1) > y(p2); 802 * CGAL::SMALLER if x(p1) \< x(p2), 803 * or if x(p1) = x(p2) and y(p1) \< y(p2); 804 * CGAL::EQUAL if the two points are equal. 805 */ operator()806 result_type operator()(const Point_2& p1, const Point_2& p2, 807 bool equal_x = false) const { 808 // TODO add CGAL_precondition(p1.location() == CGAL::ARR_INTERIOR); 809 // TODO add CGAL_precondition(p2.location() == CGAL::ARR_INTERIOR); 810 811 CERR("\ncompare_xy; p1: " << p1 812 << ";\n p2:" << p2 << ""); 813 814 if (p1.id() == p2.id()) { 815 result_type res = CGAL::EQUAL; 816 CERR("result: " << res << "\n"); 817 return res; 818 } 819 820 result_type res = 821 (Curved_kernel_via_analysis_2::instance(). 822 kernel().compare_xy_2_object() 823 (p1.xy(), p2.xy(), equal_x)); 824 825 CERR("result: " << res << "\n"); 826 827 return res; 828 } 829 }; 830 831 /*!\brief 832 * Functor that computes relative vertical alignment of an interior point and 833 * an arc 834 */ 835 template < class CurvedKernelViaAnalysis_2 > 836 class Compare_y_at_x_2 : public 837 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 838 839 public: 840 //! this instance' first template parameter 841 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 842 843 //! the base type 844 typedef 845 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 846 Base; 847 848 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 849 850 //! the result type 851 typedef CGAL::Comparison_result result_type; 852 853 //! the arity of the functor 854 855 /*!\brief 856 * Standard constructor 857 * 858 * \param kernel The kernel 859 */ Compare_y_at_x_2(Curved_kernel_via_analysis_2 * kernel)860 Compare_y_at_x_2(Curved_kernel_via_analysis_2 *kernel) : 861 Base(kernel) { 862 } 863 864 /*!\brief 865 * Return the relative vertical alignment of a point with an arc 866 * 867 * \param p The point 868 * \param cv The arc 869 * \return CGAL::SMALLER if y(p) \< cv(x(p)), i.e., 870 * the point is below the arc; 871 * CGAL::LARGER if y(p) > cv(x(p)), i.e., 872 * the point is above the arc; 873 * CGAL::EQUAL if p lies on the arc 874 * 875 * \pre p is in the x-range of cv. 876 * 877 */ operator()878 result_type operator()(const Point_2& p, const Arc_2& cv) const { 879 880 CGAL_precondition(p.is_finite()); 881 882 CERR("\ncompare_y_at_x; p: " << p << ";\n cv:" << cv << "\n"); 883 884 bool eq_min, eq_max; 885 CGAL_assertion_code ( 886 bool in_x_range = 887 ) 888 cv.is_in_x_range(p.x(), &eq_min, &eq_max); 889 CGAL_assertion(in_x_range); 890 891 // TODO replace with this->compare_xy_2_object()? 892 typename Base::Curve_kernel_2::Compare_xy_2 cmp_xy( 893 Base::_ckva()->kernel().compare_xy_2_object()); 894 895 if (cv.is_vertical()) { 896 897 if (cv.is_finite(CGAL::ARR_MIN_END)) { 898 899 // for vertical arcs we can ask for .xy() member 900 if (cmp_xy(p.xy(), cv._minpoint().xy(), true) == 901 CGAL::SMALLER) { 902 CERR("cmp result: " << CGAL::SMALLER << "\n"); 903 return CGAL::SMALLER; 904 } 905 } 906 907 if (cv.is_finite(CGAL::ARR_MAX_END)) { 908 if (cmp_xy(p.xy(), cv._maxpoint().xy(), true) == 909 CGAL::LARGER) { 910 CERR("cmp result: " << CGAL::LARGER << "\n"); 911 return CGAL::LARGER; 912 } 913 } 914 CERR("cmp result: " << CGAL::EQUAL << "\n"); 915 return CGAL::EQUAL; // p lies on a vertical arc 916 } 917 CGAL::Comparison_result res; 918 if (eq_min) { 919 if(cv._minpoint().is_finite()){ 920 res = cmp_xy(p.xy(), cv._minpoint().xy(), true); 921 }else{ 922 res = (cv.location(CGAL::ARR_MIN_END)==ARR_TOP_BOUNDARY)? 923 CGAL::SMALLER : CGAL::LARGER; 924 } 925 } else if (eq_max) { 926 CGAL_precondition(p.is_finite()); 927 if(cv._maxpoint().is_finite()){ 928 res = cmp_xy(p.xy(), cv._maxpoint().xy(), true); 929 }else{ 930 res = (cv.location(CGAL::ARR_MAX_END)==ARR_TOP_BOUNDARY)? 931 CGAL::SMALLER : CGAL::LARGER; 932 } 933 } else { 934 Point_2 point_on_s = 935 Base::_ckva()->construct_point_on_arc_2_object() 936 (p.x(), cv.curve(), cv.arcno(), cv ); 937 938 CGAL_precondition(p.is_finite()); 939 CGAL_precondition(point_on_s.is_finite()); 940 res = cmp_xy(p.xy(), point_on_s.xy(), true); 941 } 942 CERR("cmp result: " << res << "\n"); 943 return res; 944 } 945 }; 946 947 /*!\brief 948 * Functor that computes the relative vertical aligment of two arcs left 949 * of a point 950 */ 951 template < class CurvedKernelViaAnalysis_2 > 952 class Compare_y_at_x_left_2 : public 953 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 954 955 public: 956 //! this instance' first template parameter 957 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 958 959 //! the base type 960 typedef 961 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 962 Base; 963 964 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 965 966 //! the result type 967 typedef CGAL::Comparison_result result_type; 968 969 //! the arity of the functor 970 971 /*!\brief 972 * Standard constructor 973 * 974 * \param kernel The kernel 975 */ Compare_y_at_x_left_2(Curved_kernel_via_analysis_2 * kernel)976 Compare_y_at_x_left_2(Curved_kernel_via_analysis_2 *kernel) : 977 Base(kernel) { 978 } 979 980 /*!\brief 981 * Compares the relative vertical alignment of two arcs 982 * immediately to the left of one of their intersection points. 983 * 984 * If one of the arcs is vertical (emanating downward from p), it is 985 * always considered to be below the other curve. 986 * 987 * \param cv1 The first arc 988 * \param cv2 The second arc 989 * \param p The intersection point. 990 * \return The relative vertical alignment of cv1 with respect to cv2 991 * immediately to the left of p: CGAL::SMALLER, CGAL::LARGER or 992 CGAL::EQUAL. 993 * 994 * \pre The point p lies on both curves, and both of them must be also be 995 * defined (lexicographically) to its left. 996 */ operator()997 result_type operator() (const Arc_2& cv1, const Arc_2& cv2, 998 const Point_2& p) const { 999 1000 CERR("\ncompare_y_at_x_left(cv2); cv1: " << cv1 << "; cv2: " << 1001 cv2 << "; p: " << p << "\n"); 1002 1003 // ensure that p lies on both arcs 1004 CGAL_precondition(cv1.compare_y_at_x(p) == CGAL::EQUAL); 1005 CGAL_precondition(cv2.compare_y_at_x(p) == CGAL::EQUAL); 1006 1007 // check whether both arcs indeed lie to the left of p 1008 CGAL_precondition( 1009 (cv1.is_vertical() && 1010 cv1.location(CGAL::ARR_MIN_END) == 1011 CGAL::ARR_BOTTOM_BOUNDARY) || 1012 cv1._same_arc_compare_xy(cv1._minpoint(), p) == CGAL::SMALLER 1013 ); 1014 CGAL_precondition( 1015 (cv2.is_vertical() && 1016 cv2.location(CGAL::ARR_MIN_END) == CGAL::ARR_BOTTOM_BOUNDARY) 1017 || 1018 cv2._same_arc_compare_xy(cv2._minpoint(), p) == CGAL::SMALLER 1019 ); 1020 if (cv1.is_vertical()) { 1021 // if both are vertical (they overlap), we return EQUAL 1022 if(cv2.is_vertical()) { 1023 return CGAL::EQUAL; 1024 } 1025 // a vertical arc is always smaller than the arc extending to the 1026 // left 1027 return CGAL::SMALLER; 1028 } 1029 // a vertical arc is always smaller than the arc extending to the left; 1030 // due to the order, we have to return the opposite 1031 if (cv2.is_vertical()) { 1032 return CGAL::LARGER; 1033 } 1034 1035 if (cv1.is_singular()) {// singularity in y 1036 CGAL_error_msg("Handling singularity in y is not yet implemented"); 1037 } 1038 1039 // vertical line immediately to the left of p: if p lies on boundary 1040 // get the vertical line over the last interval; otherwise 1041 // obtain the interval w.r.t. point's x-coordinate (this also valid 1042 // for discontinuity in y) 1043 /*if(bndp_x == CGAL::BEFORE_SINGULARITY || 1044 bndp_x == CGAL::BEFORE_DISCONTINUITY) 1045 return _compare_arc_numbers(cv2, bndp_x); 1046 else*/ 1047 1048 CGAL::Comparison_result res = 1049 cv1._compare_arc_numbers(cv2, 1050 CGAL::ARR_INTERIOR, 1051 p.x(), CGAL::NEGATIVE); 1052 CERR("result: " << res << "\n"); 1053 return res; 1054 } 1055 }; 1056 1057 1058 /*!\brief 1059 * Functor that computes the relative vertical aligment of two arcs right 1060 * of a point 1061 */ 1062 template < class CurvedKernelViaAnalysis_2 > 1063 class Compare_y_at_x_right_2 : public 1064 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 1065 1066 public: 1067 //! this instance' first template parameter 1068 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1069 1070 //! the base type 1071 typedef 1072 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1073 Base; 1074 1075 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1076 1077 //! the result type 1078 typedef CGAL::Comparison_result result_type; 1079 1080 //! the arity of the functor 1081 1082 /*!\brief 1083 * Standard constructor 1084 * 1085 * \param kernel The kernel 1086 */ Compare_y_at_x_right_2(Curved_kernel_via_analysis_2 * kernel)1087 Compare_y_at_x_right_2(Curved_kernel_via_analysis_2 *kernel) : 1088 Base(kernel) { 1089 } 1090 1091 /*!\brief 1092 * Compares the relative vertical alignment of two arcs 1093 * immediately to the right of one of their intersection points. 1094 * 1095 * If one of the arcs is vertical (emanating downward from p), it is 1096 * always considered to be below the other curve. 1097 * 1098 * \param cv1 The first arc 1099 * \param cv2 The second arc 1100 * \param p The intersection point. 1101 * \return The relative vertical alignment of cv1 with respect to cv2 1102 * immediately to the right of p: CGAL::SMALLER, CGAL::LARGER or 1103 CGAL::EQUAL. 1104 * 1105 * \pre The point p lies on both curves, and both of them must be also be 1106 * defined (lexicographically) to its right. 1107 */ operator()1108 result_type operator()(const Arc_2& cv1, const Arc_2& cv2, 1109 const Point_2& p) const { 1110 1111 CERR("\ncompare_y_at_x_right; cv1: " << cv1 << "; cv2: " << 1112 cv2 << "; p: " << p << "\n"); 1113 1114 // ensure that p lies on both arcs and doesn't lie on the positive 1115 // boundary 1116 CGAL_precondition(cv1.compare_y_at_x(p) == CGAL::EQUAL); 1117 CGAL_precondition(cv2.compare_y_at_x(p) == CGAL::EQUAL); 1118 1119 // check whether both arcs indeed lie to the left of p 1120 CGAL_precondition( 1121 (cv1.is_vertical() && 1122 cv1.location(CGAL::ARR_MAX_END) == CGAL::ARR_TOP_BOUNDARY) || 1123 cv1._same_arc_compare_xy(p, cv1._maxpoint()) == CGAL::SMALLER 1124 ); 1125 CGAL_precondition( 1126 (cv2.is_vertical() && 1127 cv2.location(CGAL::ARR_MAX_END) == CGAL::ARR_TOP_BOUNDARY) || 1128 cv2._same_arc_compare_xy(p, cv2._maxpoint()) == CGAL::SMALLER 1129 ); 1130 1131 if (cv1.is_vertical()) { 1132 // if both are vertical (they overlap), we return EQUAL 1133 if (cv2.is_vertical()) { 1134 return CGAL::EQUAL; 1135 } 1136 // a vertical arc is always LARGER than arc extending to the 1137 // right 1138 return CGAL::LARGER; 1139 } 1140 // a vertical arc is always LARGER than arc extending to the right; 1141 // due to the order, we have to return the opposite 1142 if (cv2.is_vertical()) { 1143 return CGAL::SMALLER; 1144 } 1145 1146 if (cv1.is_singular()) {// singularity in y 1147 CGAL_error_msg("Handling singularity in y is not yet \ 1148 implemented"); 1149 } 1150 1151 // vertical line immediately to the right of p: if p lies on boundary 1152 // get the vertical line over the first interval; otherwise 1153 // obtain the interval w.r.t. point's x-coordinate (this also valid 1154 // for discontinuity in y) 1155 /*if(bndp_x == CGAL::AFTER_SINGULARITY || 1156 bndp_x == CGAL::AFTER_DISCONTINUITY) 1157 return _compare_arc_numbers(cv2, bndp_x); 1158 else*/ 1159 CGAL::Comparison_result res = 1160 cv1._compare_arc_numbers(cv2, 1161 CGAL::ARR_INTERIOR, 1162 p.x(), 1163 CGAL::POSITIVE); 1164 CERR("result: " << res << "\n"); 1165 return res; 1166 } 1167 }; 1168 1169 /*!\brief 1170 * Functor that checks whether a point is in the x-range of an arc 1171 */ 1172 template < class CurvedKernelViaAnalysis_2 > 1173 class Is_in_x_range_2 : public 1174 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 1175 1176 public: 1177 //! this instance' first template parameter 1178 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1179 1180 //! the base type 1181 typedef 1182 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1183 Base; 1184 1185 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1186 1187 //! the result type 1188 typedef bool result_type; 1189 1190 //! the arity of the functor 1191 1192 /*!\brief 1193 * Standard constructor 1194 * 1195 * \param kernel The kernel 1196 */ Is_in_x_range_2(Curved_kernel_via_analysis_2 * kernel)1197 Is_in_x_range_2(Curved_kernel_via_analysis_2 *kernel) : 1198 Base(kernel) { 1199 } 1200 1201 /*!\brief 1202 * Check whether a given point lies within the curve's x-range 1203 * 1204 * \param cv The arc 1205 * \param p the point 1206 * \return \c true if p lies in arc's x-range; \c false otherwise. 1207 */ operator()1208 bool operator()(const Arc_2& cv, const Point_2& p) const { 1209 return cv.is_in_x_range(p); 1210 } 1211 }; 1212 1213 /*!\brief 1214 * Tests two objects, whether they are equal 1215 */ 1216 template < class CurvedKernelViaAnalysis_2 > 1217 class Equal_2 : public 1218 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 1219 1220 public: 1221 //! this instance' first template parameter 1222 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1223 1224 //! the base type 1225 typedef 1226 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1227 Base; 1228 1229 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1230 1231 //! the result type 1232 typedef bool result_type; 1233 1234 //! the arity of the functor 1235 1236 /*!\brief 1237 * Standard constructor 1238 * 1239 * \param kernel The kernel 1240 */ Equal_2(Curved_kernel_via_analysis_2 * kernel)1241 Equal_2(Curved_kernel_via_analysis_2 *kernel) : 1242 Base(kernel) { 1243 } 1244 1245 /*!\brief 1246 * Check if the two points are the same 1247 * 1248 * \param p1 The first point. 1249 * \param p2 The second point. 1250 * \return \c true if the two point are the same; \c false otherwise. 1251 */ operator()1252 result_type operator()(const Point_2& p1, const Point_2& p2) const { 1253 return (Curved_kernel_via_analysis_2::instance(). 1254 compare_xy_2_object()(p1, p2) == 1255 CGAL::EQUAL); 1256 } 1257 1258 /*!\brief 1259 * Check if the two arcs are the same 1260 * 1261 * \param cv1 The first arc 1262 * \param cv2 The second arc 1263 * \return \c true if the two curves are the same; \c false otherwise. 1264 */ operator()1265 result_type operator()(const Arc_2& cv1, const Arc_2& cv2) const { 1266 1267 if (cv1.is_identical(cv2)) { 1268 return true; 1269 } 1270 // only one of the arcs is vertical => not equal 1271 if (cv1.is_vertical() != cv2.is_vertical()) { 1272 return false; 1273 } 1274 1275 Arc_2::simplify(cv1,cv2); 1276 // distinct supporting curves implies inequality, provided the 1277 // coprimality condition is satisfied 1278 if (!cv1.curve().is_identical(cv2.curve())) { 1279 return false; 1280 } 1281 1282 // here either both or none of the arcs are vertical, check for arcnos 1283 // equality 1284 if (!cv1.is_vertical() && cv1.arcno() != cv2.arcno()) { 1285 return false; 1286 } 1287 // otherwise compare respective curve ends: supporting curves and 1288 // arcnos are equal => the curve ends belong to the same arc 1289 return ((cv1._same_arc_compare_xy(cv1._minpoint(), cv2._minpoint()) == 1290 CGAL::EQUAL && 1291 cv1._same_arc_compare_xy(cv1._maxpoint(), cv2._maxpoint()) == 1292 CGAL::EQUAL)); 1293 } 1294 1295 }; 1296 1297 1298 /*!\brief 1299 * Functor that checks whether two arcs overlap 1300 */ 1301 template < class CurvedKernelViaAnalysis_2 > 1302 class Do_overlap_2 : public 1303 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 1304 1305 public: 1306 //! this instance' first template parameter 1307 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1308 1309 //! the base type 1310 typedef 1311 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1312 Base; 1313 1314 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1315 1316 //! the result type 1317 typedef bool result_type; 1318 1319 //! the arity of the functor 1320 1321 /*!\brief 1322 * Standard constructor 1323 * 1324 * \param kernel The kernel 1325 */ Do_overlap_2(Curved_kernel_via_analysis_2 * kernel)1326 Do_overlap_2(Curved_kernel_via_analysis_2 *kernel) : 1327 Base(kernel) { 1328 } 1329 1330 /*!\brief 1331 * Check whether two given arcs overlap, i.e., they have infinitely 1332 * many intersection points 1333 * 1334 * \param cv1 The first arc 1335 * \param cv2 The second arc 1336 * \return \c true if the curves overlap; \c false otherwise 1337 */ operator()1338 bool operator()(const Arc_2& cv1, const Arc_2& cv2) const { 1339 1340 CERR("\ndo_overlap\n"); 1341 if (cv1.is_identical(cv2)) { 1342 return true; 1343 } 1344 1345 Arc_2::simplify(cv1, cv2); 1346 // arcs with coprime support do not overlap 1347 if (!cv1.curve().is_identical(cv2.curve())) { 1348 return false; 1349 } 1350 1351 if (cv1.is_vertical() != cv2.is_vertical()) { 1352 return false; // only one arc is vertical => can't overlap 1353 } 1354 if (cv1.is_vertical()) { // both arcs are vertical 1355 // check for x-coordinates equality 1356 if (Curved_kernel_via_analysis_2::instance(). 1357 kernel().compare_1_object()( 1358 cv1._minpoint().x(), 1359 cv2._minpoint().x()) != CGAL::EQUAL) { 1360 return false; 1361 } 1362 // compare y-coordinates of min curve ends 1363 switch(cv1._same_arc_compare_xy( 1364 cv1._minpoint(), cv2._minpoint(), true) 1365 ) { 1366 case CGAL::EQUAL: // this->source == cv2->source => overlap ! 1367 return true; 1368 case CGAL::SMALLER: // this->source < cv2->source 1369 // check whether this->target > cv2->source 1370 return (cv1._same_arc_compare_xy( 1371 cv1._maxpoint(), cv2._minpoint(), 1372 true) == CGAL::LARGER); 1373 case CGAL::LARGER: // this->source > cv2->source 1374 // check whether this->source < cv2->target 1375 return (cv1._same_arc_compare_xy( 1376 cv1._minpoint(), cv2._maxpoint(), 1377 true) == CGAL::SMALLER); 1378 } 1379 } 1380 // processing non-vertical arcs 1381 if (cv1.arcno() != cv2.arcno()) { 1382 return false; 1383 } 1384 /* At this point, we have two non-vertical arcs supported by the same 1385 * curve with equal arc numbers in their interior. They do overlap if 1386 * their x-ranges overlap. Compare only x-coordinates */ 1387 switch (cv1._same_arc_compare_xy( 1388 cv1._minpoint(), cv2._minpoint(), false, true) 1389 ) { 1390 case CGAL::EQUAL: // this->source == cv2->source => overlap ! 1391 return true; 1392 case CGAL::SMALLER: // this->source < cv2->source 1393 // check whether this->target > cv2->source 1394 return (cv1._same_arc_compare_xy( 1395 cv1._maxpoint(), cv2._minpoint(), false, 1396 true) == CGAL::LARGER); 1397 case CGAL::LARGER: // this->source > cv2->source 1398 // check whether this->source < cv2->target 1399 return (cv1._same_arc_compare_xy( 1400 cv1._minpoint(), cv2._maxpoint(), false, 1401 true) == CGAL::SMALLER); 1402 } 1403 CGAL_error_msg("bogus comparison result"); 1404 return false; 1405 } 1406 }; 1407 1408 1409 /*!\brief 1410 * Functor that computes the intersections of two arcs 1411 */ 1412 template < class CurvedKernelViaAnalysis_2 > 1413 class Intersect_2 : 1414 public Curved_kernel_via_analysis_2_functor_base<CurvedKernelViaAnalysis_2> 1415 { 1416 public: 1417 //! this instance' first template parameter 1418 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1419 1420 //! the base type 1421 typedef 1422 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1423 Base; 1424 1425 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1426 1427 typedef unsigned int Multiplicity; 1428 typedef std::pair<Point_2, Multiplicity> Intersection_point; 1429 typedef boost::variant<Intersection_point, Arc_2> Intersection_result; 1430 1431 //! the result type 1432 typedef CGAL::cpp98::iterator<std::output_iterator_tag, Intersection_result> 1433 result_type; 1434 1435 //! the arity of the functor 1436 1437 /*!\brief 1438 * Standard constructor 1439 * 1440 * \param kernel The kernel 1441 */ Intersect_2(Curved_kernel_via_analysis_2 * kernel)1442 Intersect_2(Curved_kernel_via_analysis_2 *kernel) : 1443 Base(kernel) { 1444 } 1445 1446 // TODO add operators for non-x-monotone arcs + curves (i.e., all combis) 1447 1448 /*!\brief 1449 * Find all intersections of the two given arcs and insert them to the 1450 * output iterator. 1451 * 1452 * Type of output iterator is \c CGAL::Object 1453 * containing either an \c Arc_2 object (overlap) or a \c 1454 * std::pair< Point_2, unsigned int >, where the unsigned int denotes 1455 * the multiplicity of the zero-dimensional intersection (0 if unknown) 1456 * 1457 * \param cv1 The first arc 1458 * \param cv2 The second arc 1459 * \param oi The output iterator. 1460 * \return The past-the-end iterator. 1461 */ 1462 template < class OutputIterator > operator()1463 OutputIterator operator()(const Arc_2& cv1, const Arc_2& cv2, 1464 OutputIterator oi) const { 1465 CERR("\nintersect; cv1: " << cv1 1466 << ";\n cv2:" << cv2 << ""); 1467 1468 // if arcs overlap, just store their common part, otherwise compute 1469 // point-wise intersections 1470 std::vector<Arc_2> arcs; 1471 if (cv1._trim_if_overlapped(cv2, std::back_inserter(arcs))) { 1472 for (const auto& item : arcs) *oi++ = Intersection_result(item); 1473 return oi; 1474 } 1475 // process non-ov erlapping case 1476 std::vector<Intersection_point> vec; 1477 Arc_2::_intersection_points(cv1, cv2, std::back_inserter(vec)); 1478 for (const auto& item : vec) *oi++ = Intersection_result(item); 1479 return oi; 1480 } 1481 1482 }; 1483 1484 1485 /*!\brief 1486 * Functors that trims an arc 1487 */ 1488 template < class CurvedKernelViaAnalysis_2 > 1489 class Trim_2 : public 1490 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 1491 1492 public: 1493 //! this instance' first template parameter 1494 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1495 1496 //! the base type 1497 typedef 1498 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1499 Base; 1500 1501 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1502 1503 //! the result type 1504 typedef Arc_2 result_type; 1505 1506 //! the arity of the functor 1507 1508 /*!\brief 1509 * Standard constructor 1510 * 1511 * \param kernel The kernel 1512 */ Trim_2(Curved_kernel_via_analysis_2 * kernel)1513 Trim_2(Curved_kernel_via_analysis_2 *kernel) : 1514 Base(kernel) { 1515 } 1516 1517 /*!\brief 1518 * Returns a trimmed version of an arc 1519 * 1520 * \param cv The arc 1521 * \param p the new first endpoint 1522 * \param q the new second endpoint 1523 * \return The trimmed arc 1524 * 1525 * \pre p != q 1526 * \pre both points must be interior and must lie on \c cv 1527 */ operator()1528 Arc_2 operator()(const Arc_2& cv, const Point_2& p, const Point_2& q) { 1529 1530 CERR("trim\n"); 1531 1532 CGAL_precondition(p.location() == CGAL::ARR_INTERIOR); 1533 CGAL_precondition(q.location() == CGAL::ARR_INTERIOR); 1534 1535 CGAL_precondition(!Base::_ckva()->equal_2_object()(p, q)); 1536 CGAL_precondition(cv.compare_y_at_x(p) == CGAL::EQUAL); 1537 CGAL_precondition(cv.compare_y_at_x(q) == CGAL::EQUAL); 1538 1539 return cv._trim(p, q); 1540 } 1541 }; 1542 1543 1544 /*!\brief 1545 * Functor that splits a arc at an interior point 1546 */ 1547 template < class CurvedKernelViaAnalysis_2 > 1548 class Split_2 : public 1549 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 1550 1551 public: 1552 //! this instance' first template parameter 1553 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1554 1555 //! the base type 1556 typedef 1557 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1558 Base; 1559 1560 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1561 1562 //! the result type 1563 typedef void result_type; 1564 1565 //! the arity of the functor 1566 1567 /*!\brief 1568 * Standard constructor 1569 * 1570 * \param kernel The kernel 1571 */ Split_2(Curved_kernel_via_analysis_2 * kernel)1572 Split_2(Curved_kernel_via_analysis_2 *kernel) : 1573 Base(kernel) { 1574 } 1575 1576 /*!\brief 1577 * Split a given arc at a given point into two sub-arcs 1578 * 1579 * \param cv The arc to split 1580 * \param p The split point 1581 * \param c1 Output: The left resulting subcurve (p is its right endpoint) 1582 * \param c2 Output: The right resulting subcurve (p is its left endpoint) 1583 * 1584 * \pre p lies on cv but is not one of its end-points. 1585 */ operator()1586 void operator()(const Arc_2& cv, const Point_2 & p, 1587 Arc_2& c1, Arc_2& c2) const { 1588 1589 CGAL_precondition(cv.compare_y_at_x(p) == CGAL::EQUAL); 1590 // check that p is not an end-point of the arc 1591 CGAL_precondition(cv._same_arc_compare_xy(cv._minpoint(), p) != CGAL::EQUAL); 1592 CGAL_precondition(cv._same_arc_compare_xy(cv._maxpoint(), p) != CGAL::EQUAL); 1593 1594 CERR("\nsplit\n"); 1595 c1 = cv._replace_endpoints( 1596 cv._minpoint(), p, -1, (cv.is_vertical() ? -1 : cv.arcno()) 1597 ).first; 1598 c2 = cv._replace_endpoints( 1599 p, cv._maxpoint(), (cv.is_vertical() ? -1 : cv.arcno()), -1 1600 ).first; 1601 } 1602 }; 1603 1604 /*!\brief 1605 * Functor that computes whether two arcs are mergeable 1606 */ 1607 template < class CurvedKernelViaAnalysis_2 > 1608 class Are_mergeable_2 : public 1609 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 1610 1611 public: 1612 //! this instance' first template parameter 1613 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1614 1615 //! the base type 1616 typedef 1617 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1618 Base; 1619 1620 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1621 1622 //! the result type 1623 typedef bool result_type; 1624 1625 //! the arity of the functor 1626 1627 /*!\brief 1628 * Standard constructor 1629 * 1630 * \param kernel The kernel 1631 */ Are_mergeable_2(Curved_kernel_via_analysis_2 * kernel)1632 Are_mergeable_2(Curved_kernel_via_analysis_2 *kernel) : 1633 Base(kernel) { 1634 } 1635 1636 /*!\brief 1637 * Check whether two given arcs are mergeable 1638 * 1639 * \param cv1 The first arc 1640 * \param cv2 The second arc 1641 * \return \c true if the two arcs are mergeable, i.e., they are supported 1642 * by the same curve and share a common endpoint; \c false otherwise. 1643 */ operator()1644 bool operator()(const Arc_2& cv1, const Arc_2& cv2) const { 1645 1646 CERR("\nare_mergeable\n"); 1647 1648 if (cv1.do_overlap(cv2)) {// if arcs overlap they are not mergeable 1649 return false; // this also call simplify 1650 } 1651 1652 // touch in at most one point now and supporting curves are simplified 1653 // both arcs must be either vertical or not 1654 if (!cv1.curve().is_identical(cv2.curve()) || 1655 cv1.is_vertical() != cv2.is_vertical()) { 1656 return false; 1657 } 1658 // if both arcs are non-vertical => they must have equal arcnos 1659 // to be mergeable 1660 if (!cv1.is_vertical() && cv1.arcno() != cv2.arcno()) { 1661 return false; 1662 } 1663 // for non-vertical arcs arc numbers are equal => can use same_arc_cmp 1664 bool max_min = 1665 (cv1._same_arc_compare_xy(cv1._maxpoint(), cv2._minpoint()) == 1666 CGAL::EQUAL), 1667 min_max = false; 1668 if (!max_min) { // both cases cannot happen simultaneously 1669 min_max = 1670 (cv1._same_arc_compare_xy(cv1._minpoint(), cv2._maxpoint()) == 1671 CGAL::EQUAL); 1672 if (!min_max) { // arcs have no common end-point => not mergeable 1673 return false; 1674 } 1675 } 1676 // check that the common point is not an event point 1677 if (cv1.is_vertical()) { // both arcs are vertical 1678 Point_2 common = (max_min ? cv1._maxpoint() : cv1._minpoint()); 1679 // a common end must be a finite point 1680 CGAL_precondition(cv1.is_interior(common.location())); 1681 // check that there are no other non-vertical branches coming 1682 // through this point 1683 1684 Curve_analysis_2 ca_2(cv1.curve()); 1685 typename Curve_analysis_2::Status_line_1 cv_line = 1686 ca_2.status_line_for_x(common.x()); 1687 CGAL_assertion(cv_line.is_event()); // ?? 1688 1689 // we are not allowed to use number_of_incident_branches() 1690 // since the common point might be supported by different curve, 1691 // and therefore its arcno might be not valid for *this arc 1692 for (int k = 0; k < cv_line.number_of_events(); k++) { 1693 // use a temporary object for comparison predicate 1694 typename Point_2::Coordinate_2 tmp(common.x(), cv1.curve(), k); 1695 if (Curved_kernel_via_analysis_2::instance(). 1696 kernel().compare_xy_2_object()( 1697 common.xy(), tmp) == 1698 CGAL::EQUAL) { 1699 return false; 1700 } 1701 } 1702 } else if (cv1.interval_id() != cv2.interval_id()) { 1703 return false; // non-vertical case 1704 } 1705 1706 return true; 1707 } 1708 }; 1709 1710 /*!\brief 1711 * Functor that merges two arcs 1712 */ 1713 template < class CurvedKernelViaAnalysis_2 > 1714 class Merge_2 : public 1715 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 1716 1717 public: 1718 //! this instance' first template parameter 1719 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1720 1721 //! the base type 1722 typedef 1723 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1724 Base; 1725 1726 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1727 1728 //! the result type 1729 typedef void result_type; 1730 1731 //! the arity of the functor 1732 1733 /*!\brief 1734 * Standard constructor 1735 * 1736 * \param kernel The kernel 1737 */ Merge_2(Curved_kernel_via_analysis_2 * kernel)1738 Merge_2(Curved_kernel_via_analysis_2 *kernel) : 1739 Base(kernel) { 1740 } 1741 1742 /*!\brief 1743 * Merges two given arcs into a single one 1744 * 1745 * \param cv1 The first arc 1746 * \param cv2 The second arc 1747 * \param c Output: The resulting arc 1748 * 1749 * \pre The two arcs are mergeable, that is they are supported by the 1750 * same curve and share a common endpoint. 1751 */ operator()1752 void operator()(const Arc_2& cv1, const Arc_2& cv2, Arc_2& c) const { 1753 1754 CERR("merge\n"); 1755 CGAL_precondition(cv1.are_mergeable(cv2)); 1756 Arc_2::simplify(cv1, cv2); 1757 1758 Point_2 src, tgt; 1759 int arcno_s = -1, arcno_t = -1; 1760 bool replace_src; // true if cv2 < *this otherwise *this arc < cv2 arc 1761 // arcs are mergeable => they have one common finite end-point 1762 replace_src = 1763 (cv1._same_arc_compare_xy(cv1._minpoint(), cv2._maxpoint()) == 1764 CGAL::EQUAL); 1765 src = (replace_src ? cv2._minpoint() : cv1._minpoint()); 1766 tgt = (replace_src ? cv1._maxpoint() : cv2._maxpoint()); 1767 1768 if (!cv1.is_vertical()) { 1769 arcno_s = (replace_src ? cv2.arcno(CGAL::ARR_MIN_END) : 1770 cv1.arcno(CGAL::ARR_MIN_END)); 1771 arcno_t = (replace_src ? cv1.arcno(CGAL::ARR_MAX_END) : 1772 cv2.arcno(CGAL::ARR_MAX_END)); 1773 } 1774 Arc_2 arc = cv1._replace_endpoints(src, tgt, arcno_s, arcno_t).first; 1775 // arc.set_boundaries_after_merge(*this, s); - no need to, since 1776 // boundaries are stored in Point_2 type and will be copied implicitly 1777 1778 c = arc; 1779 } 1780 }; 1781 1782 1783 /*!\brief 1784 * Functor that computes whether a point lies on a supporting curve 1785 */ 1786 template < class CurvedKernelViaAnalysis_2 > 1787 class Is_on_2 : public 1788 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 1789 1790 public: 1791 //! this instance' first template parameter 1792 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1793 1794 //! the base type 1795 typedef 1796 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1797 Base; 1798 1799 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1800 1801 //! the result type 1802 typedef bool result_type; 1803 1804 //! the arity of the functor 1805 1806 /*!\brief 1807 * Standard constructor 1808 * 1809 * \param kernel The kernel 1810 */ Is_on_2(Curved_kernel_via_analysis_2 * kernel)1811 Is_on_2(Curved_kernel_via_analysis_2 *kernel) : 1812 Base(kernel) { 1813 } 1814 1815 /*!\brief 1816 * Checks whether \c p lies on \c c 1817 * 1818 * \param p The point to test 1819 * \param c The curve 1820 * \return \c true if the \c p lies on \c c, \c false otherwise 1821 */ operator()1822 result_type operator()(const Point_2& p, const Curve_analysis_2& c) const { 1823 result_type res = 1824 (Curved_kernel_via_analysis_2::instance(). 1825 kernel().sign_at_2_object()(c, p.xy()) 1826 == CGAL::ZERO); 1827 return res; 1828 } 1829 1830 /*!\brief 1831 * Checks whether \c p lies on \c cv 1832 * 1833 * \param p The point to test 1834 * \param c The curve arc 1835 * \return \c true if the \c p lies on \c cv, \c false otherwise 1836 */ operator()1837 result_type operator()(const Point_2& p, const Arc_2& cv) const { 1838 // fix by Michael Hemmer: 1839 if(cv.is_in_x_range(p.x())){ 1840 return cv.compare_y_at_x(p) == CGAL::EQUAL; 1841 } 1842 return false; 1843 1844 // This is the old code that seems to interpret the arc as open 1845 // In particular, it returns false for vertical arcs. 1846 // (Michael Hemmer) 1847 // bool is_left, is_right; 1848 // result_type res = 1849 // (cv.is_in_x_range(p.x(),&is_left,&is_right)) && 1850 // !(is_left) && 1851 // !(is_right) && 1852 // (cv.compare_y_at_x(p) == CGAL::EQUAL); 1853 // return res; 1854 } 1855 1856 }; 1857 1858 1859 /*!\brief 1860 * Functor that decomposes curve into x-monotone arcs and isolated points 1861 */ 1862 template <class CurvedKernelViaAnalysis_2> 1863 class Make_x_monotone_2 : public 1864 Curved_kernel_via_analysis_2_functor_base<CurvedKernelViaAnalysis_2> { 1865 1866 public: 1867 //! this instance' first template parameter 1868 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1869 1870 //! the base type 1871 typedef 1872 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2> 1873 Base; 1874 1875 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1876 1877 //! the result type 1878 typedef CGAL::cpp98::iterator< std::output_iterator_tag, CGAL::Object> 1879 result_type; 1880 1881 //! the arity of the functor 1882 1883 /*!\brief 1884 * Standard constructor 1885 * 1886 * \param kernel The kernel 1887 */ Make_x_monotone_2(Curved_kernel_via_analysis_2 * kernel)1888 Make_x_monotone_2(Curved_kernel_via_analysis_2* kernel) : 1889 Base(kernel) 1890 {} 1891 1892 /*!\brief 1893 * Decomposes a given arc into list of x-monotone arcs 1894 * (subcurves) and insert them to the output iterator. Since \c Arc_2 1895 * is by definition x-monotone, an input arc is passed to the 1896 * output iterator directly. 1897 * 1898 * \param cv The arc 1899 * \param oi The output iterator, whose value-type is Object 1900 * The returned objects are all wrappers Arc_2 objects 1901 * \return The past-the-end iterator 1902 */ 1903 template <class OutputIterator> operator()1904 OutputIterator operator()(const Arc_2& cv, OutputIterator oi) const 1905 { 1906 typedef typename Curved_kernel_via_analysis_2::Point_2 Point_2; 1907 typedef typename Curved_kernel_via_analysis_2::Arc_2 Arc_2; 1908 typedef boost::variant<Point_2, Arc_2> Make_x_monotone_result; 1909 *oi++ = Make_x_monotone_result(cv); 1910 return oi; 1911 } 1912 1913 /*!\brief 1914 * Decomposes a given curve into list of x-monotone arcs 1915 * (subcurves) and isolated points and insert them to the output iterator. 1916 * 1917 * \param cv The curve 1918 * \param oi The output iterator, whose value-type is Object. 1919 * The returned objects either wrapper Arc_2 or Point_2 objects 1920 * \return The past-the-end iterator 1921 */ 1922 template <class OutputIterator> operator()1923 OutputIterator operator()(const Curve_analysis_2& cv, OutputIterator oi) 1924 const 1925 { 1926 CGAL::internal::Make_x_monotone_2< Curved_kernel_via_analysis_2 > 1927 make_x_monotone(Base::_ckva()); 1928 1929 return make_x_monotone(cv, oi); 1930 } 1931 1932 /*!\brief 1933 * Splits an input object \c obj into x-monotone arcs and isolated points 1934 * 1935 * \param obj the polymorph input object: can represet \c Point_2, 1936 * \c Arc_2, \c Non_x_monotone_arc_2 or \c Curve_analysis_2 1937 * \param oi Output iterator that stores CGAL::Object, which either 1938 * encapsulates \c Point_2 or \c Arc_2 1939 * \return Past-the-end iterator of \c oi 1940 */ 1941 template <class OutputIterator> operator()1942 OutputIterator operator()(CGAL::Object obj, OutputIterator oi) 1943 { 1944 typedef typename Curved_kernel_via_analysis_2::Point_2 Point_2; 1945 typedef typename Curved_kernel_via_analysis_2::Arc_2 Arc_2; 1946 typedef typename Curved_kernel_via_analysis_2::Non_x_monotone_arc_2 1947 Non_x_monotone_arc_2; 1948 typedef boost::variant<Point_2, Arc_2> 1949 Make_x_monotone_result; 1950 1951 Curve_analysis_2 curve; 1952 Point_2 p; 1953 Arc_2 xcv; 1954 Non_x_monotone_arc_2 nxarc; 1955 1956 if (CGAL::assign(curve, obj)) oi = (*this)(curve, oi); 1957 else if (CGAL::assign(nxarc, obj)) 1958 std::cerr << "AU BACKE" << std::endl; 1959 //oi = std::transform(nxarc.begin(), nxarc.end(), oi, 1960 // std::ptr_fun(CGAL::make_object<Arc_2>)); 1961 else if (CGAL::assign(xcv, obj)) *oi++ = Make_x_monotone_result(xcv); 1962 else if (CGAL::assign(p, obj)) *oi++ = Make_x_monotone_result(p); 1963 else CGAL_error(); 1964 return oi; 1965 } 1966 }; 1967 1968 1969 // left-right 1970 1971 /*!\brief 1972 * Functor computing parameter space in x for arc 1973 */ 1974 template < class CurvedKernelViaAnalysis_2 > 1975 class Parameter_space_in_x_2 : public 1976 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 1977 1978 public: 1979 //! this instance' first template parameter 1980 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 1981 1982 //! the base type 1983 typedef 1984 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 1985 Base; 1986 1987 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 1988 1989 //! the result type 1990 typedef CGAL::Arr_parameter_space result_type; 1991 1992 //! the arity of the functor 1993 1994 /*!\brief 1995 * Standard constructor 1996 * 1997 * \param kernel The kernel 1998 */ Parameter_space_in_x_2(Curved_kernel_via_analysis_2 * kernel)1999 Parameter_space_in_x_2(Curved_kernel_via_analysis_2 *kernel) : 2000 Base(kernel) { 2001 } 2002 2003 /*! Obtains the parameter space in x at the end of an arc. 2004 * 2005 * \param cv The arc 2006 * \param ce the arc end indicator: 2007 * ARR_MIN_END - the minimal end of cv 2008 * ARR_MAX_END - the maximal end of cv 2009 * \return the parameter space at the \c ce end of \c cv 2010 * ARR_LEFT_BOUNDARY - the arc approaches the left boundary of the 2011 * parameter space 2012 * ARR_INTERIOR - the arc does not approach a boundary of the 2013 * parameter space 2014 * ARR_RIGHT_BOUNDARY - the arc approaches the right boundary of the 2015 * parameter space 2016 */ operator()2017 result_type operator()(const Arc_2& cv, CGAL::Arr_curve_end ce) const { 2018 2019 CGAL::Arr_parameter_space loc = cv.location(ce); 2020 if(loc == CGAL::ARR_LEFT_BOUNDARY || loc == CGAL::ARR_RIGHT_BOUNDARY) 2021 return loc; 2022 return CGAL::ARR_INTERIOR; 2023 } 2024 operator()2025 result_type operator()(const Point_2& pt) const { 2026 return pt.location(); 2027 } 2028 2029 }; 2030 2031 /*!\brief 2032 * Functor that compares ends of arcs near left or right boundary 2033 */ 2034 template < class CurvedKernelViaAnalysis_2 > 2035 class Compare_y_near_boundary_2 : public 2036 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 2037 2038 public: 2039 //! this instance' first template parameter 2040 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 2041 2042 //! the base type 2043 typedef 2044 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 2045 Base; 2046 2047 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 2048 2049 //! the result type 2050 typedef CGAL::Comparison_result result_type; 2051 2052 //! the arity of the functor 2053 2054 /*!\brief 2055 * Standard constructor 2056 * 2057 * \param kernel The kernel 2058 */ Compare_y_near_boundary_2(Curved_kernel_via_analysis_2 * kernel)2059 Compare_y_near_boundary_2(Curved_kernel_via_analysis_2 *kernel) : 2060 Base(kernel) { 2061 } 2062 2063 /*!\brief 2064 * Compare the y-coordinates of 2 arcs at their ends near the left 2065 * or right boundary of the parameter space 2066 * 2067 * \param cv1 the first arc. 2068 * \param cv2 the second arc. 2069 * \param ce the arc end indicator. 2070 * \return CGAL::SMALLER is y(cv1,ce) < y(cv2,ce2) near left/right boundary 2071 * CGAL::EQUAL is y(cv1,ce) = y(cv2,ce2) near left/right boundary, 2072 * i.e., they overlap 2073 * \return CGAL::LARGER is y(cv1,ce) > y(cv2,ce2) near left/right boundary 2074 * 2075 * \pre the ce ends of the arcs cv1 and cv2 lie either on the left 2076 * boundary or on the right boundary of the parameter space. 2077 */ operator()2078 result_type operator()(const Arc_2& cv1, const Arc_2& cv2, 2079 CGAL::Arr_curve_end ce) const { 2080 2081 CERR("\ncompare_y_near_boundary; cv1: " << cv1 << "; cv2: " << 2082 cv2 << "; end: " << ce << "\n"); 2083 2084 2085 CGAL::Comparison_result res = CGAL::EQUAL; 2086 2087 CGAL::Arr_parameter_space loc1 = cv1.location(ce); 2088 CGAL_precondition(cv1.is_on_left_right(loc1)); 2089 CGAL_precondition(loc1 == cv2.location(ce)); 2090 // comparing ids is the same as calling is_identical() ?? 2091 if (cv1.id() == cv2.id()) { 2092 CERR("result: " << res << "\n"); // EQUAL 2093 return res; 2094 } 2095 2096 // both points lie on the left-right-identification, i.e., equalx 2097 // TODO this interface is NOT official 2098 CGAL::Object obj1 = 2099 cv1.curve().asymptotic_value_of_arc(loc1, cv1.arcno()); 2100 CGAL::Object obj2 = 2101 cv2.curve().asymptotic_value_of_arc(loc1, cv2.arcno()); 2102 2103 typename Point_2::Curved_kernel_via_analysis_2::Curve_kernel_2:: 2104 Algebraic_real_1 y1, y2; 2105 CGAL::Arr_parameter_space ps1, ps2; 2106 2107 if (CGAL::assign(ps1, obj1)) { 2108 if (CGAL::assign(ps2, obj2)) { 2109 res = CGAL::EQUAL; 2110 } else { 2111 CGAL_assertion(CGAL::assign(y2, obj2)); 2112 res = (ps1 == CGAL::ARR_BOTTOM_BOUNDARY ? 2113 CGAL::SMALLER : CGAL::LARGER); 2114 } 2115 } else { 2116 CGAL_assertion_code(bool check = ) 2117 CGAL::assign(y1, obj1); 2118 CGAL_assertion(check); 2119 if (CGAL::assign(ps2, obj2)) { 2120 res = (ps2 == CGAL::ARR_TOP_BOUNDARY ? 2121 CGAL::SMALLER : CGAL::LARGER); 2122 } else { 2123 CGAL_assertion_code(bool check = ) 2124 CGAL::assign(y2, obj2); 2125 CGAL_assertion(check); 2126 2127 // Remark: Is filtered 2128 res = Base::_ckva()->kernel().compare_1_object()(y1, y2); 2129 } 2130 } 2131 2132 if (res != EQUAL) { 2133 CERR("result: " << res << "\n"); 2134 return res; 2135 } 2136 2137 CGAL_precondition(cv1.is_on_left_right(loc1)); 2138 CGAL_precondition(loc1 == cv2.location(ce)); 2139 // comparing ids is the same as calling is_identical() ?? 2140 if (cv1.id() == cv2.id()) { 2141 CGAL::Comparison_result res = CGAL::EQUAL; 2142 CERR("result: " << res << "\n"); 2143 return res; 2144 } 2145 2146 // in this setting same handling as for +/-oo ? 2147 res = cv1._compare_arc_numbers(cv2, loc1); 2148 CERR("result: " << res << "\n"); 2149 return res; 2150 } 2151 }; 2152 2153 // bottom-top 2154 2155 template < class CurvedKernelViaAnalysis_2 > 2156 class Parameter_space_in_y_2 : public 2157 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 2158 2159 public: 2160 //! this instance' first template parameter 2161 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 2162 2163 //! the base type 2164 typedef 2165 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 2166 Base; 2167 2168 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 2169 2170 //! the result type 2171 typedef CGAL::Arr_parameter_space result_type; 2172 2173 //! the arity of the functor 2174 2175 /*!\brief 2176 * Standard constructor 2177 * 2178 * \param kernel The kernel 2179 */ Parameter_space_in_y_2(Curved_kernel_via_analysis_2 * kernel)2180 Parameter_space_in_y_2(Curved_kernel_via_analysis_2 *kernel) : 2181 Base(kernel) { 2182 } 2183 2184 /*! Obtains the parameter space in y at the end of an arc. 2185 * 2186 * \param cv The arc 2187 * \param ce the arc end indicator: 2188 * ARR_MIN_END - the minimal end of cv 2189 * ARR_MAX_END - the maximal end of cv 2190 * \return the parameter space at the \c ce end of \c cv 2191 * ARR_BOTTOM_BOUNDARY- the arc approaches the bottom boundary of the 2192 * parameter space 2193 * ARR_INTERIOR - the arc does not approach a boundary of the 2194 * parameter space 2195 * ARR_TOP_BOUNDARY - the arc approaches the top boundary of the 2196 * parameter space 2197 */ operator()2198 result_type operator()(const Arc_2& cv, CGAL::Arr_curve_end ce) const { 2199 2200 CGAL::Arr_parameter_space loc = cv.location(ce); 2201 if(loc == CGAL::ARR_BOTTOM_BOUNDARY || loc == CGAL::ARR_TOP_BOUNDARY) 2202 return loc; 2203 return CGAL::ARR_INTERIOR; 2204 } 2205 operator()2206 result_type operator()(const Point_2& pt) const { 2207 return pt.location(); 2208 } 2209 2210 }; 2211 2212 2213 /*!\brief 2214 * Functor that compares x-limits at the top or bottom boundary 2215 */ 2216 template < class CurvedKernelViaAnalysis_2 > 2217 class Compare_x_at_limit_2 : public 2218 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 2219 2220 public: 2221 //! this instance' first template parameter 2222 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 2223 2224 //! the base type 2225 typedef 2226 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 2227 Base; 2228 2229 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 2230 2231 //! the result type 2232 typedef CGAL::Comparison_result result_type; 2233 2234 //! the arity of the functor 2235 Compare_x_at_limit_2(Curved_kernel_via_analysis_2 * kernel)2236 Compare_x_at_limit_2(Curved_kernel_via_analysis_2 *kernel) : 2237 Base(kernel) { 2238 } 2239 2240 /*!\brief Compare the x-limit of a vertical with the x-limit of 2241 * an arc end near the boundary at bottom or top boundary 2242 * 2243 * \param p the point direction. 2244 * \param cv the arc, the endpoint of which is compared. 2245 * \param ce the arc-end indicator - 2246 * ARR_MIN_END - the minimal end of cv or 2247 * ARR_MAX_END - the maximal end of cv. 2248 * \return the comparison result: 2249 * SMALLER - x(p) \< x(cv, ce); 2250 * EQUAL - x(p) = x(cv, ce); 2251 * LARGER - x(p) > x(cv, ce). 2252 * 2253 * \pre p lies in the interior of the parameter space. 2254 * \pre the ce end of the line cv lies on a boundary. 2255 */ operator()2256 result_type operator()(const Point_2& p, const Arc_2& cv, 2257 CGAL::Arr_curve_end ce) const { 2258 2259 2260 CERR("\ncompare_x_at_limit: p: " << p << "\n cv: " << 2261 cv << "; curve_end: " << ce << "\n"); 2262 2263 // this curve end has boundary only in y 2264 CGAL_precondition(cv.is_on_bottom_top(cv.location(ce))); 2265 if (cv.is_singular()) // the curve end goes to contraction => x-order 2266 return CGAL::EQUAL; // doesn't matter 2267 2268 CGAL::Comparison_result res = 2269 Curved_kernel_via_analysis_2::instance(). 2270 kernel().compare_1_object()( 2271 p.x(), cv.curve_end_x(ce) 2272 ); 2273 CERR("result: " << res << "\n"); 2274 return res; 2275 } 2276 2277 /*! Compare the x-limits of 2 arcs ends near the top or bottom 2278 * boundary of the parameter space 2279 * \param cv1 the first arc. 2280 * \param ce1 the first arc end indicator - 2281 * ARR_MIN_END - the minimal end of cv1 or 2282 * ARR_MAX_END - the maximal end of cv1. 2283 * \param cv2 the second arc. 2284 * \param ce2 the second arc end indicator - 2285 * ARR_MIN_END - the minimal end of cv2 or 2286 * ARR_MAX_END - the maximal end of cv2. 2287 * \return the second comparison result: 2288 * SMALLER - x(cv1, ce1) \< x(cv2, ce2); 2289 * EQUAL - x(cv1, ce1) = x(cv2, ce2); 2290 * LARGER - x(cv1, ce1) > x(cv2, ce2). 2291 * 2292 * \pre the ce1 end of the arc cv1 lies on a boundary. 2293 * \pre the ce2 end of the arc cv2 lies on a boundary. 2294 */ operator()2295 result_type operator()(const Arc_2& cv1, CGAL::Arr_curve_end ce1, 2296 const Arc_2& cv2, CGAL::Arr_curve_end ce2) const { 2297 2298 CERR("\ncompare_x_at_limit: cv1: " << cv1 << "\n cv2: " << 2299 cv2 << "; end1: " << ce1 << "; end2: " << ce2 << "\n"); 2300 /*CGAL::Arr_boundary_type bnd1 = boundary(end1), 2301 bnd2 = cv2.boundary(ce2);*/ 2302 CGAL_precondition_code(CGAL::Arr_parameter_space loc1 = cv1.location(ce1)); 2303 CGAL_precondition_code(CGAL::Arr_parameter_space loc2 = cv2.location(ce2)); 2304 CGAL_precondition(cv1.is_on_bottom_top(loc1)); 2305 CGAL_precondition(cv1.is_on_bottom_top(loc2)); 2306 2307 if (cv1.is_singular() != cv1.is_singular()) { 2308 // only one curve end lies at singularity (another at +/-oo) 2309 CGAL_error_msg("SINGULARITY + INF comparison is not yet \ 2310 implemented"); 2311 } 2312 2313 CGAL::Comparison_result res = Curved_kernel_via_analysis_2::instance(). 2314 kernel().compare_1_object()( 2315 cv1.curve_end_x(ce1), 2316 cv2.curve_end_x(ce2) 2317 ); 2318 CERR("result: " << res << "\n"); 2319 return res; 2320 } 2321 }; 2322 2323 2324 /*!\brief 2325 * Functor that compares x-coordinates near the top or bottom boundary 2326 */ 2327 template < class CurvedKernelViaAnalysis_2 > 2328 class Compare_x_near_limit_2 : public 2329 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 2330 2331 public: 2332 //! this instance' first template parameter 2333 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 2334 2335 //! the base type 2336 typedef 2337 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 2338 Base; 2339 2340 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 2341 2342 //! the result type 2343 typedef CGAL::Comparison_result result_type; 2344 2345 //! the arity of the functor 2346 Compare_x_near_limit_2(Curved_kernel_via_analysis_2 * kernel)2347 Compare_x_near_limit_2(Curved_kernel_via_analysis_2 *kernel) : 2348 Base(kernel) { 2349 } 2350 2351 /*! Compare the x-coordinates of 2 arcs ends near the top or bottom 2352 * boundary of the parameter space 2353 * \param cv1 the first arc. 2354 * \param cv2 the second arc. 2355 * \param ce the arc end indicator - 2356 * ARR_MIN_END - the minimal end of curves or 2357 * ARR_MAX_END - the maximal end of curves. 2358 * \return the second comparison result: 2359 * SMALLER - x(cv1, ce) \< x(cv2, ce); 2360 * EQUAL - x(cv1, ce) = x(cv2, ce); 2361 * LARGER - x(cv1, ce) > x(cv2, ce). 2362 * 2363 * \pre the ce1 end of the arc cv1 lies on a boundary. 2364 * \pre the ce2 end of the arc cv2 lies on a boundary. 2365 * \pre both curve ends are on the same boundary 2366 */ operator()2367 result_type operator()(const Arc_2& cv1, const Arc_2& cv2, 2368 CGAL::Arr_curve_end ce) const { 2369 2370 CERR("\ncompare_x_near_limit: cv1: " << cv1 << "\n cv2: " << 2371 cv2 << "; ce: " << ce << "\n"); 2372 2373 CGAL::Arr_parameter_space loc1 = cv1.location(ce); 2374 CGAL_precondition_code(CGAL::Arr_parameter_space loc2 = 2375 cv2.location(ce)); 2376 CGAL_precondition(cv1.is_on_bottom_top(loc1)); 2377 CGAL_precondition(cv1.is_on_bottom_top(loc2)); 2378 CGAL_precondition(cv1.compare_x_at_limit(ce, cv2, ce) == CGAL::EQUAL); 2379 2380 CGAL_precondition(loc1 == loc2); 2381 2382 Coordinate_1 x0(cv1.curve_end_x(ce)); 2383 CGAL::Comparison_result res = cv1._compare_arc_numbers( 2384 cv2, CGAL::ARR_INTERIOR, x0, 2385 (ce == CGAL::ARR_MIN_END ? 2386 CGAL::POSITIVE : CGAL::NEGATIVE) 2387 ); 2388 if ((ce == CGAL::ARR_MAX_END && 2389 loc1 == CGAL::ARR_TOP_BOUNDARY) || 2390 (ce == CGAL::ARR_MIN_END && 2391 loc1 == CGAL::ARR_BOTTOM_BOUNDARY)) { 2392 res = opposite(res); 2393 } 2394 CERR("result: " << res << "\n"); 2395 return res; 2396 } 2397 }; 2398 2399 2400 /*!\brief 2401 * Functor to construct a point on a curve 2402 */ 2403 template < class CurvedKernelViaAnalysis_2 > 2404 class Compare_endpoints_xy_2 : public 2405 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 2406 2407 public: 2408 //! this instance' first template parameter 2409 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 2410 2411 //! the base type 2412 typedef 2413 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 2414 Base; 2415 2416 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 2417 2418 //! the result type 2419 typedef CGAL::Comparison_result result_type; 2420 2421 /*!\brief 2422 * Standard constructor 2423 * 2424 * \param kernel The kernel 2425 */ Compare_endpoints_xy_2(Curved_kernel_via_analysis_2 * kernel)2426 Compare_endpoints_xy_2(Curved_kernel_via_analysis_2 *kernel) : 2427 Base(kernel) { 2428 } 2429 2430 /*!\brief 2431 * Compares endpoints of arc lexicographically 2432 * 2433 * \param arc the arc 2434 * \return The order of endpoints 2435 */ operator()2436 CGAL::Comparison_result operator()(const Arc_2& xcv) { 2437 if (xcv.is_left_to_right()) { 2438 return (CGAL::SMALLER); 2439 } else { 2440 return (CGAL::LARGER); 2441 } 2442 return CGAL::EQUAL; 2443 } 2444 }; 2445 2446 2447 /*!\brief 2448 * Functor to construct a point on a curve 2449 */ 2450 template < class CurvedKernelViaAnalysis_2 > 2451 class Construct_opposite_2 : public 2452 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 2453 2454 public: 2455 //! this instance' first template parameter 2456 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 2457 2458 //! the base type 2459 typedef 2460 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 2461 Base; 2462 2463 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 2464 2465 //! the result type 2466 typedef Arc_2 result_type; 2467 2468 /*!\brief 2469 * Standard constructor 2470 * 2471 * \param kernel The kernel 2472 */ Construct_opposite_2(Curved_kernel_via_analysis_2 * kernel)2473 Construct_opposite_2(Curved_kernel_via_analysis_2 *kernel) : 2474 Base(kernel) { 2475 } 2476 2477 /*!\brief 2478 * Construct an arc of opposite direction 2479 * 2480 * \param arc the arc to be reversed 2481 * \return The reversed arc 2482 */ operator()2483 Arc_2 operator()(const Arc_2& xcv) { 2484 return xcv.flip(); 2485 } 2486 }; 2487 2488 2489 2490 /*!\brief 2491 * Functor that computes the x-extreme points of a curve 2492 */ 2493 template < class CurvedKernelViaAnalysis_2 > 2494 class X_extreme_points_2 : public 2495 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 2496 2497 public: 2498 //! this instance' first template parameter 2499 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 2500 2501 //! the base type 2502 typedef 2503 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 2504 Base; 2505 2506 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 2507 2508 typedef typename Curve_analysis_2::Coordinate_2 Coordinate_2; 2509 2510 //! the result type 2511 typedef CGAL::cpp98::iterator< std::output_iterator_tag, Coordinate_2 > 2512 result_type; 2513 2514 //! the arity of the functor 2515 2516 /*!\brief 2517 * Standard constructor 2518 * 2519 * \param kernel The kernel 2520 */ X_extreme_points_2(Curved_kernel_via_analysis_2 * kernel)2521 X_extreme_points_2(Curved_kernel_via_analysis_2 *kernel) : 2522 Base(kernel) { 2523 } 2524 2525 /*!\brief 2526 */ 2527 template < class OutputIterator > operator()2528 OutputIterator operator()(const Curve_analysis_2& ca, 2529 OutputIterator oi) const { 2530 2531 typedef typename Curve_analysis_2::Status_line_1 Status_line_1; 2532 2533 int events = ca.number_of_status_lines_with_event(); 2534 2535 for ( int i = 0; i < events; i++ ) { 2536 2537 Status_line_1 status_line = ca.status_line_at_event(i); 2538 2539 int lifts = status_line.number_of_events(); 2540 2541 for( int j = 0; j < lifts; j++ ) { 2542 2543 std::pair<int, int> arcs = 2544 status_line.number_of_incident_branches(j); 2545 2546 if (arcs.first == 0 || arcs.second == 0) 2547 *oi++ = status_line.algebraic_real_2(j); 2548 } 2549 } 2550 return oi; 2551 } 2552 2553 }; 2554 2555 /*!\brief 2556 * Functor that computes the y-extreme points of a curve 2557 */ 2558 template < class CurvedKernelViaAnalysis_2 > 2559 class Y_extreme_points_2 : public 2560 Curved_kernel_via_analysis_2_functor_base< CurvedKernelViaAnalysis_2 > { 2561 2562 public: 2563 //! this instance' first template parameter 2564 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 2565 2566 //! the base type 2567 typedef 2568 Curved_kernel_via_analysis_2_functor_base< Curved_kernel_via_analysis_2 > 2569 Base; 2570 2571 CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 2572 2573 typedef typename Curve_analysis_2::Coordinate_2 Coordinate_2; 2574 2575 //! the result type 2576 typedef CGAL::cpp98::iterator< std::output_iterator_tag, Coordinate_2 > 2577 result_type; 2578 2579 //! the arity of the functor 2580 2581 /*!\brief 2582 * Standard constructor 2583 * 2584 * \param kernel The kernel 2585 */ Y_extreme_points_2(Curved_kernel_via_analysis_2 * kernel)2586 Y_extreme_points_2(Curved_kernel_via_analysis_2 *kernel) : 2587 Base(kernel) { 2588 } 2589 2590 /*!\brief 2591 */ 2592 template < class OutputIterator > operator()2593 OutputIterator operator()(const Curve_analysis_2& ca, 2594 OutputIterator oi) const { 2595 2596 typedef typename Curve_analysis_2::Status_line_1 Status_line_1; 2597 2598 typename Base::Curve_kernel_2 curve_kernel = Base::_ckva()->kernel(); 2599 2600 Curve_analysis_2 ca_yx 2601 = curve_kernel.swap_x_and_y_2_object() (ca); 2602 2603 std::vector<Coordinate_2> y_critical_points; 2604 2605 Base::_ckva()->x_extreme_points_2_object()(ca_yx, 2606 std::back_inserter(y_critical_points)); 2607 2608 for( typename std::vector<Coordinate_2>::iterator it 2609 = y_critical_points.begin(); 2610 it != y_critical_points.end(); 2611 it++ ) { 2612 2613 Coordinate_1 curr_x = curve_kernel.get_y_2_object()( *it ); 2614 2615 Status_line_1 status_line = ca.status_line_at_exact_x(curr_x); 2616 2617 int lifts = status_line.number_of_events(); 2618 2619 for( int i = 0; i < lifts; i++ ) { 2620 Coordinate_2 lift_xy = status_line.algebraic_real_2(i); 2621 2622 bool y_coordinate_found; 2623 2624 while(true) { 2625 2626 if( curve_kernel.upper_boundary_y_2_object() (lift_xy) < 2627 curve_kernel.lower_boundary_x_2_object() (*it) ) { 2628 y_coordinate_found = false; 2629 break; 2630 } 2631 if( curve_kernel.upper_boundary_y_2_object() (lift_xy) >= 2632 curve_kernel.upper_boundary_x_2_object() (*it) ) { 2633 y_coordinate_found = true; 2634 break; 2635 } 2636 2637 curve_kernel.refine_x_2_object() (*it); 2638 } 2639 2640 if(y_coordinate_found) { 2641 *oi++ = Coordinate_2(curr_x, ca, i); 2642 break; 2643 } 2644 } 2645 } 2646 return oi; 2647 } 2648 2649 }; 2650 2651 2652 #undef CGAL_CKvA_2_GRAB_BASE_FUNCTOR_TYPES 2653 2654 } // namespace Curved_kernel_via_analysis_2_Functors 2655 2656 /*!\brief 2657 * Collects the main set of functors of a curved kernel 2658 */ 2659 template < class CurvedKernelViaAnalysis_2, class Dummy = void> 2660 class Curved_kernel_via_analysis_2_functors { 2661 2662 public: 2663 //!\name Public types 2664 //!@{ 2665 2666 //! this instance's first template parameter 2667 typedef CurvedKernelViaAnalysis_2 Curved_kernel_via_analysis_2; 2668 //!@} 2669 // typedef Curved_kernel_via_analysis_2_functors< 2670 // CurvedKernelViaAnalysis_2 > Functor_base; 2671 2672 // declares curved kernel functors, for each functor defines a member function 2673 // returning an instance of this functor 2674 #define CGAL_CKvA_2_functor_pred(Y, Z) \ 2675 typedef \ 2676 Curved_kernel_via_analysis_2_Functors::Y< Curved_kernel_via_analysis_2 \ 2677 > Y; \ 2678 Y Z() const { return Y(&Curved_kernel_via_analysis_2::instance()); } 2679 2680 #define CGAL_CKvA_2_functor_cons(Y, Z) CGAL_CKvA_2_functor_pred(Y, Z) 2681 2682 CGAL_CKvA_2_functor_pred(Compare_x_2, compare_x_2_object); 2683 CGAL_CKvA_2_functor_pred(Compare_xy_2, compare_xy_2_object); 2684 CGAL_CKvA_2_functor_pred(Is_vertical_2, is_vertical_2_object); 2685 2686 CGAL_CKvA_2_functor_cons(Construct_min_vertex_2, 2687 construct_min_vertex_2_object); 2688 CGAL_CKvA_2_functor_cons(Construct_max_vertex_2, 2689 construct_max_vertex_2_object); 2690 CGAL_CKvA_2_functor_cons(Construct_interior_vertex_2, 2691 construct_interior_vertex_2_object); 2692 2693 CGAL_CKvA_2_functor_pred(Compare_y_at_x_2, compare_y_at_x_2_object); 2694 CGAL_CKvA_2_functor_pred(Compare_y_at_x_left_2, 2695 compare_y_at_x_left_2_object); 2696 CGAL_CKvA_2_functor_pred(Compare_y_at_x_right_2, 2697 compare_y_at_x_right_2_object); 2698 CGAL_CKvA_2_functor_pred(Equal_2, equal_2_object); 2699 CGAL_CKvA_2_functor_pred(Is_in_x_range_2, is_in_x_range_2_object); 2700 CGAL_CKvA_2_functor_pred(Do_overlap_2, do_overlap_2_object); 2701 CGAL_CKvA_2_functor_cons(Intersect_2, intersect_2_object); 2702 CGAL_CKvA_2_functor_cons(Trim_2, trim_2_object); 2703 CGAL_CKvA_2_functor_cons(Split_2, split_2_object); 2704 CGAL_CKvA_2_functor_pred(Are_mergeable_2, are_mergeable_2_object); 2705 CGAL_CKvA_2_functor_cons(Merge_2, merge_2_object); 2706 2707 2708 CGAL_CKvA_2_functor_pred(Is_on_2, is_on_2_object); 2709 CGAL_CKvA_2_functor_cons(Make_x_monotone_2, make_x_monotone_2_object); 2710 2711 // left-right 2712 CGAL_CKvA_2_functor_pred(Parameter_space_in_x_2, 2713 parameter_space_in_x_2_object); 2714 CGAL_CKvA_2_functor_pred(Compare_y_near_boundary_2, 2715 compare_y_near_boundary_2_object); 2716 2717 // bottom-top 2718 CGAL_CKvA_2_functor_pred(Parameter_space_in_y_2, 2719 parameter_space_in_y_2_object); 2720 CGAL_CKvA_2_functor_pred(Compare_x_at_limit_2, 2721 compare_x_at_limit_2_object); 2722 CGAL_CKvA_2_functor_pred(Compare_x_near_limit_2, 2723 compare_x_near_limit_2_object); 2724 2725 CGAL_CKvA_2_functor_cons(X_extreme_points_2, x_extreme_points_2_object); 2726 CGAL_CKvA_2_functor_cons(Y_extreme_points_2, y_extreme_points_2_object); 2727 2728 CGAL_CKvA_2_functor_cons(Construct_point_2, 2729 construct_point_2_object); 2730 2731 CGAL_CKvA_2_functor_cons(Construct_point_on_arc_2, 2732 construct_point_on_arc_2_object); 2733 2734 CGAL_CKvA_2_functor_cons(Construct_arc_2, 2735 construct_arc_2_object); 2736 2737 CGAL_CKvA_2_functor_pred(Compare_endpoints_xy_2, 2738 compare_endpoints_xy_2_object); 2739 2740 CGAL_CKvA_2_functor_cons(Construct_opposite_2, 2741 construct_opposite_2_object); 2742 2743 #undef CGAL_CKvA_2_functor_pred 2744 #undef CGAL_CKvA_2_functor_cons 2745 2746 }; // Curved_kernel_via_analysis_2_functors 2747 2748 } // namespace internal 2749 2750 } //namespace CGAL 2751 2752 #endif // CGAL_CURVED_KERNEL_VIA_ANALYSIS_2_FUNCTORS_H 2753 // EOF 2754