1 // Copyright (c) 2003,2004,2005,2006,2007,2008,2009,2010,2011 INRIA Sophia-Antipolis (France). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org). 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Arrangement_on_surface_2/include/CGAL/Arr_circular_line_arc_traits_2.h $ 7 // $Id: Arr_circular_line_arc_traits_2.h af94033 2021-01-07T16:39:03+01:00 Dmitry Anisimov 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // Author(s) : Monique Teillaud, Sylvain Pion, Julien Hazebrouck 11 12 // Partially supported by the IST Programme of the EU as a Shared-cost 13 // RTD (FET Open) Project under Contract No IST-2000-26473 14 // (ECG - Effective Computational Geometry for Curves and Surfaces) 15 // and a STREP (FET Open) Project under Contract No IST-006413 16 // (ACS -- Algorithms for Complex Shapes) 17 18 #ifndef CGAL_CIRCULAR_KERNEL_VARIANT_TRAITS_2_H 19 #define CGAL_CIRCULAR_KERNEL_VARIANT_TRAITS_2_H 20 21 #include <CGAL/license/Arrangement_on_surface_2.h> 22 23 #include <CGAL/disable_warnings.h> 24 25 /*! \file 26 * This file was developed at Inria, France, and copied over to the 27 * Arrangement_2 package, which it is now part of. It contains a traits 28 * class for the arrangement package that handles circular and linear curves. 29 * It is based on the circular kernel. 30 * 31 * \todo Fix the circular-kernel make-x-monotone functor to use modern variant 32 * instead of the legacy CGAL::Object. Then, eliminate the special 33 * implementation here and directly use the kernel functor instead. 34 */ 35 36 #include <vector> 37 38 #include <boost/variant.hpp> 39 40 #include <CGAL/basic.h> 41 #include <CGAL/Arr_tags.h> 42 43 namespace CGAL { 44 namespace VariantFunctors{ 45 46 // Takes an iterator range of Object(Line/Circular_arc/Point), 47 // returns a variant of Line, Circular_arc, and Point_2. 48 template <class CK, class Arc1, class Arc2, class OutputIterator> 49 OutputIterator object_to_object_variant(const std::vector<CGAL::Object> & res1,OutputIterator res2)50 object_to_object_variant(const std::vector<CGAL::Object>& res1, 51 OutputIterator res2) 52 { 53 typedef typename CK::Circular_arc_point_2 Point_2; 54 typedef boost::variant<Arc1, Arc2> X_monotone_curve_2; 55 typedef boost::variant<Point_2, X_monotone_curve_2> 56 Make_x_monotone_result; 57 58 for (auto it = res1.begin(); it != res1.end(); ++it) { 59 if (const Arc1* arc = CGAL::object_cast<Arc1>(&*it)) { 60 boost::variant<Arc1, Arc2> v = *arc; 61 *res2++ = Make_x_monotone_result(v); 62 } 63 else if (const Arc2* line = CGAL::object_cast<Arc2>(&*it)) { 64 boost::variant<Arc1, Arc2> v = *line; 65 *res2++ = Make_x_monotone_result(v); 66 } 67 else if (const Point_2* p = CGAL::object_cast<Point_2>(&*it)) { 68 *res2++ = Make_x_monotone_result(*p); 69 } 70 else CGAL_error(); 71 } 72 return res2; 73 } 74 75 template <class CircularKernel, class Arc1, class Arc2> 76 class Compare_y_to_right_2 77 { 78 public: 79 typedef CGAL::Comparison_result result_type; 80 typedef typename CircularKernel::Circular_arc_point_2 81 Circular_arc_point_2; 82 83 result_type operator()84 operator()(const boost::variant< Arc1, Arc2 > &a1, 85 const boost::variant< Arc1, Arc2 > &a2, 86 const Circular_arc_point_2 &p) const 87 { 88 if ( const Arc1* arc1 = boost::get<Arc1>( &a1 ) ){ 89 if ( const Arc1* arc2 = boost::get<Arc1>( &a2 ) ){ 90 return CircularKernel() 91 .compare_y_to_right_2_object()(*arc1, *arc2, p); 92 } 93 else { 94 const Arc2* arc2e = boost::get<Arc2>( &a2 ); 95 return CircularKernel() 96 .compare_y_to_right_2_object()(*arc1, *arc2e, p); 97 } 98 } 99 const Arc2* arc1 = boost::get<Arc2>( &a1 ); 100 if ( const Arc1* arc2 = boost::get<Arc1>( &a2 ) ){ 101 return CircularKernel() 102 .compare_y_to_right_2_object()(*arc1, *arc2, p); 103 } 104 const Arc2* arc2e = boost::get<Arc2>( &a2 ); 105 return CircularKernel() 106 .compare_y_to_right_2_object()(*arc1, *arc2e, p); 107 } 108 }; 109 110 111 template <class CircularKernel> 112 class Variant_Equal_2 113 : public boost::static_visitor<bool> 114 { 115 public : 116 117 template < typename T > 118 bool operator()119 operator()(const T &a0, const T &a1) const 120 { 121 return CircularKernel().equal_2_object()(a0,a1); 122 } 123 124 template < typename T1, typename T2 > 125 bool operator()126 operator()(const T1 &, const T2 &) const 127 { 128 return false; 129 } 130 }; 131 132 133 134 template <class CircularKernel, class Arc1, class Arc2> 135 class Equal_2 136 : public CircularKernel::Equal_2 137 { 138 public: 139 typedef boost::variant< Arc1, Arc2 > Curve_2; 140 typedef bool result_type; 141 using CircularKernel::Equal_2::operator(); 142 typedef typename CircularKernel::Circular_arc_point_2 143 Circular_arc_point_2; 144 typedef typename CircularKernel::Line_arc_2 Line_arc_2; 145 typedef typename CircularKernel::Circular_arc_2 Circular_arc_2; 146 typedef typename CircularKernel::Equal_2 CK_Equal_2; 147 148 result_type operator()149 operator() (const Circular_arc_point_2 &p0, 150 const Circular_arc_point_2 &p1) const 151 { return CK_Equal_2()(p0, p1); } 152 153 result_type operator()154 operator() (const Circular_arc_2 &a0, const Circular_arc_2 &a1) const 155 { return CK_Equal_2()(a0, a1); } 156 157 result_type operator()158 operator() (const Line_arc_2 &a0, const Line_arc_2 &a1) const 159 { return CK_Equal_2()(a0, a1); } 160 161 result_type operator()162 operator() ( const Line_arc_2 &/*a0*/, const Circular_arc_2 &/*a1*/) const 163 { return false; } 164 165 result_type operator()166 operator() ( const Circular_arc_2 &/*a0*/, const Line_arc_2 &/*a1*/) const 167 { return false; } 168 169 result_type operator()170 operator()(const Curve_2 &a0, const Curve_2 &a1) const 171 { 172 return boost::apply_visitor 173 ( Variant_Equal_2<CircularKernel>(), a0, a1 ); 174 } 175 176 }; 177 178 179 180 181 template <class CircularKernel, class Arc1, class Arc2> 182 class Compare_y_at_x_2 183 { 184 public: 185 typedef typename CircularKernel::Circular_arc_point_2 186 Circular_arc_point_2; 187 typedef CGAL::Comparison_result result_type; 188 189 result_type operator()190 operator() (const Circular_arc_point_2 &p, 191 const boost::variant< Arc1, Arc2 > &A1) const 192 { 193 if ( const Arc1* arc1 = boost::get<Arc1>( &A1 ) ){ 194 return CircularKernel().compare_y_at_x_2_object()(p, *arc1); 195 } 196 else { 197 const Arc2* arc2 = boost::get<Arc2>( &A1 ); 198 return CircularKernel().compare_y_at_x_2_object()(p, *arc2); 199 } 200 } 201 }; 202 203 template <class CircularKernel> 204 class Variant_Do_overlap_2 : public boost::static_visitor<bool> 205 { 206 public: 207 template < typename T > 208 bool operator()209 operator()(const T &a0, const T &a1) const 210 { 211 return CircularKernel().do_overlap_2_object()(a0, a1); 212 } 213 214 template < typename T1, typename T2 > 215 bool operator()216 operator()(const T1 &, const T2 &) const 217 { 218 return false; 219 } 220 }; 221 222 223 template <class CircularKernel, class Arc1, class Arc2> 224 class Do_overlap_2 225 { 226 public: 227 typedef typename CircularKernel::Circular_arc_point_2 228 Circular_arc_point_2; 229 typedef bool result_type; 230 231 result_type operator()232 operator()(const boost::variant< Arc1, Arc2 > &A0, 233 const boost::variant< Arc1, Arc2 > &A1) const 234 { 235 return boost::apply_visitor 236 ( Variant_Do_overlap_2<CircularKernel>(), A0, A1 ); 237 } 238 }; 239 240 241 //! A functor for subdividing curves into x-monotone curves. 242 template <class CircularKernel, class Arc1, class Arc2> 243 class Make_x_monotone_2 244 { 245 public: 246 typedef typename CircularKernel::Circular_arc_point_2 247 Circular_arc_point_2; 248 249 template < class OutputIterator,class Not_X_Monotone > 250 OutputIterator operator()251 operator()(const boost::variant<Arc1, Arc2, Not_X_Monotone> &A, 252 OutputIterator res) const 253 { 254 if ( const Arc1* arc1 = boost::get<Arc1>( &A ) ) { 255 std::vector<CGAL::Object> container; 256 CircularKernel(). 257 make_x_monotone_2_object()(*arc1,std::back_inserter(container)); 258 return object_to_object_variant<CircularKernel, Arc1, Arc2> 259 (container, res); 260 } 261 else { 262 const Arc2* arc2 = boost::get<Arc2>( &A ); 263 std::vector<CGAL::Object> container; 264 CircularKernel(). 265 make_x_monotone_2_object()(*arc2,std::back_inserter(container)); 266 return object_to_object_variant<CircularKernel, Arc1, Arc2> 267 (container, res); 268 } 269 } 270 }; 271 272 template <class CircularKernel, class Arc1, class Arc2> 273 class Intersect_2 274 { 275 public: 276 typedef typename CircularKernel::Circular_arc_point_2 277 Circular_arc_point_2; 278 279 template < class OutputIterator > 280 OutputIterator operator()281 operator()(const boost::variant< Arc1, Arc2 > &c1, 282 const boost::variant< Arc1, Arc2 > &c2, 283 OutputIterator oi) const 284 { 285 if ( const Arc1* arc1 = boost::get<Arc1>( &c1 ) ){ 286 if ( const Arc1* arc2 = boost::get<Arc1>( &c2 ) ){ 287 return CircularKernel().intersect_2_object()(*arc1, *arc2, oi); 288 } 289 const Arc2* arc2 = boost::get<Arc2>( &c2 ); 290 return CircularKernel().intersect_2_object()(*arc1, *arc2, oi); 291 } 292 293 const Arc2* arc1e = boost::get<Arc2>( &c1 ); 294 if ( const Arc1* arc2 = boost::get<Arc1>( &c2 ) ){ 295 return CircularKernel().intersect_2_object()(*arc1e, *arc2, oi); 296 } 297 const Arc2* arc2 = boost::get<Arc2>( &c2 ); 298 return CircularKernel().intersect_2_object()(*arc1e, *arc2, oi); 299 } 300 301 }; 302 303 template <class CircularKernel, class Arc1, class Arc2> 304 class Split_2 305 { 306 307 public: 308 typedef typename CircularKernel::Circular_arc_point_2 309 Circular_arc_point_2; 310 typedef void result_type; 311 result_type operator()312 operator()(const boost::variant< Arc1, Arc2 > &A, 313 const Circular_arc_point_2 &p, 314 boost::variant< Arc1, Arc2 > &ca1, 315 boost::variant< Arc1, Arc2 > &ca2) const 316 { 317 // TODO : optimize by extracting the references from the variants ? 318 if ( const Arc1* arc1 = boost::get<Arc1>( &A ) ){ 319 Arc1 carc1; 320 Arc1 carc2; 321 CircularKernel().split_2_object()(*arc1, p, carc1, carc2); 322 ca1 = carc1; 323 ca2 = carc2; 324 return ; 325 326 } 327 else{ 328 const Arc2* arc2 = boost::get<Arc2>( &A ); 329 Arc2 cline1; 330 Arc2 cline2; 331 CircularKernel().split_2_object()(*arc2, p, cline1, cline2); 332 ca1 = cline1; 333 ca2 = cline2; 334 return ; 335 336 } 337 } 338 }; 339 340 341 template <class CircularKernel> 342 class Variant_Construct_min_vertex_2 343 : public boost::static_visitor 344 <const typename CircularKernel::Circular_arc_point_2&> 345 { 346 typedef typename CircularKernel::Circular_arc_point_2 347 Circular_arc_point_2; 348 349 public : 350 351 typedef Circular_arc_point_2 result_type; 352 //typedef const result_type& qualified_result_type; 353 354 template < typename T > 355 //typename boost::remove_reference<qualified_result_type>::type 356 Circular_arc_point_2 operator()357 operator()(const T &a) const 358 { 359 //CGAL_kernel_precondition(CircularKernel().compare_xy_2_object()(a.left(), a.right())==CGAL::SMALLER); 360 return CircularKernel().construct_circular_min_vertex_2_object()(a); 361 } 362 }; 363 364 template <class CircularKernel, class Arc1, class Arc2> 365 class Construct_min_vertex_2//: public Has_qrt 366 { 367 typedef typename CircularKernel::Circular_arc_point_2 Point_2; 368 public: 369 370 typedef Point_2 result_type; 371 //typedef const result_type& qualified_result_type; 372 373 //typename boost::remove_reference<qualified_result_type>::type 374 result_type operator()375 operator() (const boost::variant< Arc1, Arc2 > & cv) const 376 { 377 return boost::apply_visitor 378 ( Variant_Construct_min_vertex_2<CircularKernel>(), cv ); 379 } 380 }; 381 382 383 384 385 386 template <class CircularKernel> 387 class Variant_Construct_max_vertex_2 388 : public boost::static_visitor<const typename 389 CircularKernel::Circular_arc_point_2&> 390 { 391 typedef typename CircularKernel::Circular_arc_point_2 392 Circular_arc_point_2; 393 394 public : 395 396 typedef Circular_arc_point_2 result_type; 397 //typedef const result_type& qualified_result_type; 398 399 template < typename T > 400 //typename boost::remove_reference<qualified_result_type>::type 401 Circular_arc_point_2 operator()402 operator()(const T &a) const 403 { 404 //CGAL_kernel_precondition(CircularKernel().compare_xy_2_object()(a.left(), a.right())==CGAL::SMALLER); 405 return (CircularKernel().construct_circular_max_vertex_2_object()(a)); 406 } 407 }; 408 409 410 template <class CircularKernel, class Arc1, class Arc2> 411 class Construct_max_vertex_2//: public Has_qrt 412 { 413 typedef typename CircularKernel::Circular_arc_point_2 Point_2; 414 public: 415 /*! 416 * Get the right endpoint of the x-monotone curve (segment). 417 * \param cv The curve. 418 * \return The right endpoint. 419 */ 420 typedef Point_2 result_type; 421 //typedef const result_type& qualified_result_type; 422 423 //typename boost::remove_reference<qualified_result_type>::type 424 result_type operator()425 operator() (const boost::variant< Arc1, Arc2 > & cv) const 426 { 427 return boost::apply_visitor 428 ( Variant_Construct_max_vertex_2<CircularKernel>(), cv ); 429 } 430 }; 431 432 template <class CircularKernel> 433 class Variant_Is_vertical_2 434 : public boost::static_visitor<bool> 435 { 436 public : 437 438 template < typename T > 439 bool operator()440 operator()(const T &a) const 441 { 442 return CircularKernel().is_vertical_2_object()(a); 443 } 444 }; 445 446 template <class CircularKernel, class Arc1, class Arc2> 447 class Is_vertical_2 448 { 449 public: 450 typedef bool result_type; 451 operator()452 bool operator() (const boost::variant< Arc1, Arc2 >& cv) const 453 { 454 return boost::apply_visitor 455 ( Variant_Is_vertical_2<CircularKernel>(), cv ); 456 } 457 }; 458 459 } 460 461 462 // a empty class used to have different types between Curve_2 and X_monotone_curve_2 463 // in Arr_circular_line_arc_traits_2. 464 namespace internal_Argt_traits{ 465 struct Not_X_Monotone{}; 466 inline std::ostream& operator << (std::ostream& os, const Not_X_Monotone&) 467 {return os;} 468 } 469 470 /// Traits class for CGAL::Arrangement_2 (and similar) based on a CircularKernel. 471 472 template < typename CircularKernel> 473 class Arr_circular_line_arc_traits_2 { 474 475 typedef Arr_circular_line_arc_traits_2< CircularKernel > Self; 476 477 typedef typename CircularKernel::Line_arc_2 Arc1; 478 typedef typename CircularKernel::Circular_arc_2 Arc2; 479 480 public: 481 482 typedef CircularKernel Kernel; 483 typedef typename CircularKernel::Circular_arc_point_2 484 Circular_arc_point_2; 485 486 typedef typename CircularKernel::Circular_arc_point_2 Point; 487 typedef typename CircularKernel::Circular_arc_point_2 Point_2; 488 489 typedef unsigned int Multiplicity; 490 491 typedef CGAL::Tag_false Has_left_category; 492 typedef CGAL::Tag_false Has_merge_category; 493 typedef CGAL::Tag_false Has_do_intersect_category; 494 495 typedef Arr_oblivious_side_tag Left_side_category; 496 typedef Arr_oblivious_side_tag Bottom_side_category; 497 typedef Arr_oblivious_side_tag Top_side_category; 498 typedef Arr_oblivious_side_tag Right_side_category; 499 500 typedef internal_Argt_traits::Not_X_Monotone Not_X_Monotone; 501 502 typedef boost::variant< Arc1, Arc2, Not_X_Monotone > Curve_2; 503 typedef boost::variant< Arc1, Arc2 > X_monotone_curve_2; 504 505 private: 506 CircularKernel ck; 507 public: 508 509 Arr_circular_line_arc_traits_2(const CircularKernel &k = CircularKernel()) ck(k)510 : ck(k) {} 511 512 typedef typename CircularKernel::Compare_x_2 Compare_x_2; 513 typedef typename CircularKernel::Compare_xy_2 Compare_xy_2; 514 typedef typename 515 VariantFunctors::Construct_min_vertex_2<CircularKernel, Arc1, Arc2> 516 Construct_min_vertex_2; 517 typedef 518 VariantFunctors::Construct_max_vertex_2<CircularKernel, Arc1, Arc2> 519 Construct_max_vertex_2; 520 typedef VariantFunctors::Is_vertical_2<CircularKernel, Arc1, Arc2> 521 Is_vertical_2; 522 typedef VariantFunctors::Compare_y_at_x_2<CircularKernel, Arc1, Arc2> 523 Compare_y_at_x_2; 524 typedef VariantFunctors::Compare_y_to_right_2<CircularKernel, Arc1, Arc2> 525 Compare_y_at_x_right_2; 526 typedef VariantFunctors::Equal_2<CircularKernel, Arc1, Arc2> 527 Equal_2; 528 typedef VariantFunctors::Make_x_monotone_2<CircularKernel, Arc1, Arc2> 529 Make_x_monotone_2; 530 typedef VariantFunctors::Split_2<CircularKernel, Arc1, Arc2> 531 Split_2; 532 typedef VariantFunctors::Intersect_2<CircularKernel, Arc1, Arc2> 533 Intersect_2; 534 535 compare_x_2_object()536 Compare_x_2 compare_x_2_object() const 537 { return ck.compare_x_2_object(); } 538 compare_xy_2_object()539 Compare_xy_2 compare_xy_2_object() const 540 { return ck.compare_xy_2_object(); } 541 compare_y_at_x_2_object()542 Compare_y_at_x_2 compare_y_at_x_2_object() const 543 { return Compare_y_at_x_2(); } 544 compare_y_at_x_right_2_object()545 Compare_y_at_x_right_2 compare_y_at_x_right_2_object() const 546 { return Compare_y_at_x_right_2(); } 547 equal_2_object()548 Equal_2 equal_2_object() const 549 { return Equal_2(); } 550 make_x_monotone_2_object()551 Make_x_monotone_2 make_x_monotone_2_object() const 552 { return Make_x_monotone_2(); } 553 split_2_object()554 Split_2 split_2_object() const 555 { return Split_2(); } 556 intersect_2_object()557 Intersect_2 intersect_2_object() const 558 { return Intersect_2(); } 559 construct_min_vertex_2_object()560 Construct_min_vertex_2 construct_min_vertex_2_object() const 561 { return Construct_min_vertex_2(); } 562 construct_max_vertex_2_object()563 Construct_max_vertex_2 construct_max_vertex_2_object() const 564 { return Construct_max_vertex_2(); } 565 is_vertical_2_object()566 Is_vertical_2 is_vertical_2_object() const 567 { return Is_vertical_2();} 568 569 570 }; 571 572 } // namespace CGAL 573 574 #include <CGAL/enable_warnings.h> 575 576 #endif // CGAL_CIRCULAR_KERNEL_VARIANT_TRAITS_H 577