1 // Copyright (c) 2006,2007,2008,2009,2010,2011 Tel-Aviv University(Israel). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org). 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Arrangement_on_surface_2/include/CGAL/Arr_polycurve_traits_2.h $ 7 // $Id: Arr_polycurve_traits_2.h 3b70343 2020-11-16T16:19:43+01:00 Maxime Gimeno 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // Author(s): Efi Fogel <efif@post.tau.ac.il> 11 // Ron Wein <wein@post.tau.ac.il> 12 // Dror Atariah <dror.atariah@fu-berlin.de> 13 // Waqar Khan <wkhan@mpi-inf.mpg.de> 14 15 #ifndef CGAL_ARR_POLYCURVE_TRAITS_2_H 16 #define CGAL_ARR_POLYCURVE_TRAITS_2_H 17 18 #include <CGAL/license/Arrangement_on_surface_2.h> 19 20 #include <CGAL/disable_warnings.h> 21 22 /*! \file 23 * The traits-class for the general piece-wise (polycurve) type of curves of the 24 * arrangement package. 25 */ 26 27 #include <iterator> 28 29 #include <boost/variant.hpp> 30 #include <boost/type_traits/is_same.hpp> 31 #include <boost/utility/enable_if.hpp> 32 33 #include <CGAL/basic.h> 34 #include <CGAL/tags.h> 35 #include <CGAL/Arr_segment_traits_2.h> 36 #include <CGAL/Arr_polycurve_basic_traits_2.h> 37 #include <CGAL/Arr_geometry_traits/Polycurve_2.h> 38 #include <CGAL/Arr_tags.h> 39 #include <CGAL/Arr_enums.h> 40 41 namespace CGAL { 42 43 template <typename SubcurveTraits_2 = Arr_segment_traits_2<> > 44 class Arr_polycurve_traits_2 : 45 public Arr_polycurve_basic_traits_2<SubcurveTraits_2> 46 { 47 public: 48 typedef SubcurveTraits_2 Subcurve_traits_2; 49 50 private: 51 typedef Arr_polycurve_basic_traits_2<Subcurve_traits_2> Base; 52 53 public: 54 /// \name Types inherited from the polycurve basic traits class. 55 //@{ 56 typedef typename Base::Has_left_category Has_left_category; 57 typedef typename Base::Has_do_intersect_category 58 Has_do_intersect_category; 59 60 typedef typename Base::Left_side_category Left_side_category; 61 typedef typename Base::Bottom_side_category Bottom_side_category; 62 typedef typename Base::Top_side_category Top_side_category; 63 typedef typename Base::Right_side_category Right_side_category; 64 65 typedef typename Base::Are_all_sides_oblivious_tag 66 Are_all_sides_oblivious_tag; 67 68 typedef typename Base::X_monotone_subcurve_2 X_monotone_subcurve_2; 69 typedef typename Base::Size Size; 70 typedef typename Base::size_type size_type; 71 72 typedef typename Base::Point_2 Point_2; 73 typedef typename Base::X_monotone_curve_2 X_monotone_curve_2; 74 75 typedef typename Base::Compare_x_2 Compare_x_2; 76 typedef typename Base::Compare_xy_2 Compare_xy_2; 77 typedef typename Base::Construct_min_vertex_2 Construct_min_vertex_2; 78 typedef typename Base::Construct_max_vertex_2 Construct_max_vertex_2; 79 typedef typename Base::Is_vertical_2 Is_vertical_2; 80 typedef typename Base::Compare_y_at_x_2 Compare_y_at_x_2; 81 typedef typename Base::Compare_y_at_x_left_2 Compare_y_at_x_left_2; 82 typedef typename Base::Compare_y_at_x_right_2 Compare_y_at_x_right_2; 83 typedef typename Base::Equal_2 Equal_2; 84 typedef typename Base::Compare_endpoints_xy_2 Compare_endpoints_xy_2; 85 typedef typename Base::Construct_opposite_2 Construct_opposite_2; 86 typedef typename Base::Approximate_2 Approximate_2; 87 typedef typename Base::Construct_x_monotone_curve_2 88 Construct_x_monotone_curve_2; 89 typedef typename Base::Parameter_space_in_x_2 Parameter_space_in_x_2; 90 typedef typename Base::Parameter_space_in_y_2 Parameter_space_in_y_2; 91 typedef typename Base::Compare_x_on_boundary_2 Compare_x_on_boundary_2; 92 typedef typename Base::Compare_x_at_limit_2 Compare_x_at_limit_2; 93 typedef typename Base::Compare_x_near_boundary_2 Compare_x_near_boundary_2; 94 typedef typename Base::Compare_x_near_limit_2 Compare_x_near_limit_2; 95 typedef typename Base::Compare_y_on_boundary_2 Compare_y_on_boundary_2; 96 typedef typename Base::Compare_y_near_boundary_2 Compare_y_near_boundary_2; 97 typedef typename Base::Is_on_y_identification_2 Is_on_y_identification_2; 98 typedef typename Base::Is_on_x_identification_2 Is_on_x_identification_2; 99 100 typedef typename Base::Trim_2 Trim_2; 101 102 //@} 103 104 /// \name Types and functors inherited from the subcurve geometry traits. 105 //@{ 106 107 typedef typename Subcurve_traits_2::Has_merge_category Has_merge_category; 108 typedef typename Subcurve_traits_2::Multiplicity Multiplicity; 109 typedef typename Subcurve_traits_2::Curve_2 Subcurve_2; 110 111 //@} 112 113 // Backward compatibility: 114 typedef Subcurve_2 Segment_2; 115 116 private: 117 typedef Arr_polycurve_traits_2<Subcurve_traits_2> Self; 118 119 public: 120 /*! Default constructor */ Arr_polycurve_traits_2()121 Arr_polycurve_traits_2() : Base() {} 122 123 /*! Constructor with given subcurve traits 124 * \param seg_traits an already existing subcurve tarits which is passed will 125 * be used by the class. 126 */ Arr_polycurve_traits_2(const Subcurve_traits_2 * geom_traits)127 Arr_polycurve_traits_2(const Subcurve_traits_2* geom_traits) : 128 Base(geom_traits) 129 {} 130 131 /*! A polycurve represents a general continuous piecewise-linear 132 * curve, without degenerated subcurves. 133 */ 134 typedef internal::Polycurve_2<Subcurve_2, Point_2> Curve_2; 135 136 /// \name Basic predicate functors(based on the subcurve traits). 137 //@{ 138 139 /*! \class 140 * A functor that obtains the number of points of a polycurve. 141 */ 142 class Number_of_points_2 : public Base::Number_of_points_2 { 143 public: operator()144 size_type operator()(const Curve_2& cv) const 145 { 146 size_type num_seg = cv.number_of_subcurves(); 147 return (num_seg == 0) ? 0 : num_seg + 1; 148 } 149 }; 150 151 /*! Obtain a number_of_points_2 functor object. */ number_of_points_2_object()152 Number_of_points_2 number_of_points_2_object() const 153 { return Number_of_points_2(); } 154 155 ///@} 156 157 /// \name Construction functors(based on the subcurve traits). 158 //@{ 159 160 #ifndef DOXYGEN_RUNNING 161 class Push_back_2; 162 #endif 163 164 //! A functor for subdividing curves into x-monotone curves. 165 class Make_x_monotone_2 { 166 protected: 167 typedef Arr_polycurve_traits_2<Subcurve_traits_2> Polycurve_traits_2; 168 /*! The traits (in case it has state) */ 169 const Polycurve_traits_2& m_poly_traits; 170 171 public: 172 /*! Constructor. */ Make_x_monotone_2(const Polycurve_traits_2 & traits)173 Make_x_monotone_2(const Polycurve_traits_2& traits) : 174 m_poly_traits(traits) 175 {} 176 177 /*! Subdivide a given curve into x-monotone sub-curves and insert them into 178 * a given output iterator. 179 * 180 * \pre if `cv` is not empty then it must be continuous and well-oriented. 181 * \param cv the curve. 182 * \param oi an output iterator for the result. Its value type is a variant 183 * that wraps Point_2 or an X_monotone_curve_2 objects. 184 * \return the past-the-end iterator. 185 */ 186 private: 187 template <typename OutputIterator> operator_impl(const Curve_2 & cv,OutputIterator oi,Arr_all_sides_oblivious_tag)188 OutputIterator operator_impl(const Curve_2& cv, OutputIterator oi, 189 Arr_all_sides_oblivious_tag) const 190 { 191 typedef boost::variant<Point_2, X_monotone_subcurve_2> 192 Make_x_monotone_subresult; 193 typedef boost::variant<Point_2, X_monotone_curve_2> 194 Make_x_monotone_result; 195 196 // If the polycurve is empty, return. 197 if (cv.number_of_subcurves() == 0) return oi; 198 199 auto ctr_x_curve = m_poly_traits.construct_x_monotone_curve_2_object(); 200 201 auto make_seg_x_monotone = 202 m_poly_traits.subcurve_traits_2()->make_x_monotone_2_object(); 203 204 auto cmp_seg_endpts = 205 m_poly_traits.subcurve_traits_2()->compare_endpoints_xy_2_object(); 206 207 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 208 auto ctr_seg_opposite = 209 m_poly_traits.subcurve_traits_2()->construct_opposite_2_object(); 210 #endif 211 212 // Convert the input polycurve to a sequence of variant objects, such 213 // that each object wraps an x-monotone subcurve. 214 std::vector<Make_x_monotone_subresult> x_seg_objects; 215 for (auto its = cv.subcurves_begin(); its != cv.subcurves_end(); ++its) 216 make_seg_x_monotone(*its, std::back_inserter(x_seg_objects)); 217 auto it = x_seg_objects.begin(); 218 const auto* x_seg_p = boost::get<X_monotone_subcurve_2>(&(*it)); 219 #if ! defined (CGAL_NO_ASSERTIONS) 220 CGAL_assertion(x_seg_p != nullptr); 221 #endif 222 223 // If the polycurve consists of a single x-monotone subcurve, return. 224 if (x_seg_objects.size() == 1) { 225 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 226 if (cmp_seg_endpts(x_seg) == LARGER) 227 *oi++ = Make_x_monotone_result(ctr_x_curve(ctr_seg_opposite(*x_seg_p))); else *oi++ = Make_x_monotone_result(ctr_x_curve(*x_seg_p)); 228 #else 229 *oi++ = Make_x_monotone_result(ctr_x_curve(*x_seg_p)); 230 #endif 231 x_seg_objects.clear(); 232 return oi; 233 } 234 235 CGAL_precondition_code 236 ( 237 // To be used in order to verify continuity and well-orientedness 238 // of the input curve cv. 239 auto min_seg_v = 240 m_poly_traits.subcurve_traits_2()->construct_min_vertex_2_object(); 241 auto max_seg_v = 242 m_poly_traits.subcurve_traits_2()->construct_max_vertex_2_object(); 243 auto equal = m_poly_traits.subcurve_traits_2()->equal_2_object(); 244 Point_2 last_target = (cmp_seg_endpts(*x_seg_p) == SMALLER) ? 245 max_seg_v(*x_seg_p) : min_seg_v(*x_seg_p); 246 Point_2 next_src; 247 ); 248 249 // The polycurve consists of at least 2 x-monotone subcurves: 250 Push_back_2 push_back = m_poly_traits.push_back_2_object(); 251 auto is_seg_vertical = 252 m_poly_traits.subcurve_traits_2()->is_vertical_2_object(); 253 254 bool is_start_vertical = is_seg_vertical(*x_seg_p); 255 Comparison_result start_dir = cmp_seg_endpts(*x_seg_p); 256 257 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 258 Push_front_2 push_front = m_poly_traits.push_front_2_object(); 259 X_monotone_curve_2 x_polycurve = (cmp_seg_endpts(x_seg) == LARGER) ? 260 ctr_x_curve(ctr_seg_opposite(*x_seg_p)) : ctr_x_curve(*x_seg_p); 261 #else 262 X_monotone_curve_2 x_polycurve = ctr_x_curve(*x_seg_p); 263 #endif 264 265 for (++it; it != x_seg_objects.end(); ++it) { 266 const auto* x_seg_p = boost::get<X_monotone_subcurve_2>(&(*it)); 267 #if ! defined (CGAL_NO_ASSERTIONS) 268 CGAL_assertion(x_seg_p != nullptr); 269 #endif 270 271 // Test that cv is continuous and well-oriented. 272 CGAL_precondition_code 273 ( 274 next_src = (cmp_seg_endpts(*x_seg_p) == SMALLER) ? 275 min_seg_v(*x_seg_p) : max_seg_v(*x_seg_p); 276 ); 277 CGAL_precondition_msg 278 ( 279 equal(last_target, next_src), 280 "cv must form a continuous and well oriented curve." 281 ); 282 CGAL_precondition_code 283 ( 284 last_target = (cmp_seg_endpts(*x_seg_p) == SMALLER) ? 285 max_seg_v(*x_seg_p) : min_seg_v(*x_seg_p); 286 ); 287 288 if ((cmp_seg_endpts(*x_seg_p) != start_dir) || 289 (is_seg_vertical(*x_seg_p) != is_start_vertical)) 290 { 291 // Construct an x-monotone curve from the sub-range which was found 292 *oi++ = Make_x_monotone_result(x_polycurve); 293 is_start_vertical = is_seg_vertical(*x_seg_p); 294 start_dir = cmp_seg_endpts(*x_seg_p); 295 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 296 x_polycurve = (cmp_seg_endpts(*x_seg_p) == LARGER) ? 297 ctr_x_curve(ctr_seg_opposite(*x_seg_p)) : ctr_x_curve(*x_seg_p); 298 #else 299 x_polycurve = ctr_x_curve(*x_seg_p); 300 #endif 301 } 302 else { 303 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 304 if (cmp_seg_endpts(*x_seg_p) == LARGER) 305 push_front(x_polycurve, ctr_seg_opposite(*x_seg_p)); 306 else 307 push_back(x_polycurve, *x_seg_p); 308 #else 309 push_back(x_polycurve, *x_seg_p); 310 #endif 311 } 312 313 } // for loop 314 if (x_polycurve.number_of_subcurves() != 0) 315 *oi++ = Make_x_monotone_result(x_polycurve); 316 x_seg_objects.clear(); 317 return oi; 318 } 319 320 template <typename OutputIterator> operator_impl(const Curve_2 & cv,OutputIterator oi,Arr_not_all_sides_oblivious_tag)321 OutputIterator operator_impl(const Curve_2& cv, OutputIterator oi, 322 Arr_not_all_sides_oblivious_tag) const 323 { 324 typedef boost::variant<Point_2, X_monotone_subcurve_2> 325 Make_x_monotone_subresult; 326 typedef boost::variant<Point_2, X_monotone_curve_2> 327 Make_x_monotone_result; 328 329 // If the polycurve is empty, return. 330 if (cv.number_of_subcurves() == 0) return oi; 331 332 auto ctr_x_curve = m_poly_traits.construct_x_monotone_curve_2_object(); 333 334 auto make_seg_x_monotone = 335 m_poly_traits.subcurve_traits_2()->make_x_monotone_2_object(); 336 337 auto cmp_seg_endpts = 338 m_poly_traits.subcurve_traits_2()->compare_endpoints_xy_2_object(); 339 340 auto ps_x = 341 m_poly_traits.subcurve_traits_2()->parameter_space_in_x_2_object(); 342 auto ps_y = 343 m_poly_traits.subcurve_traits_2()->parameter_space_in_y_2_object(); 344 345 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 346 typename Subcurve_traits_2::Construct_opposite_2 ctr_seg_opposite = 347 m_poly_traits.subcurve_traits_2()->construct_opposite_2_object(); 348 #endif 349 350 // Convert the input polycurve to a sequence of objects, such that 351 // each object wraps an x-monotone subcurve. 352 std::vector<Make_x_monotone_subresult> x_seg_objects; 353 for (auto its = cv.subcurves_begin(); its != cv.subcurves_end(); ++its) 354 make_seg_x_monotone(*its, std::back_inserter(x_seg_objects)); 355 auto it = x_seg_objects.begin(); 356 const auto* x_seg_p = boost::get<X_monotone_subcurve_2>(&(*it)); 357 #if ! defined (CGAL_NO_ASSERTIONS) 358 CGAL_assertion(x_seg_p != nullptr); 359 #endif 360 361 // If the polycurve consists of a single x-monotone subcurve, return. 362 if (x_seg_objects.size() == 1) { 363 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 364 if (cmp_seg_endpts(x_seg) == LARGER) 365 *oi++ = Make_x_monotone_result(ctr_x_curve(ctr_seg_opposite(*x_seg_p))); else *oi++ = Make_x_monotone_result(ctr_x_curve(*x_seg_p)); 366 #else 367 *oi++ = Make_x_monotone_result(ctr_x_curve(*x_seg_p)); 368 #endif 369 x_seg_objects.clear(); 370 return oi; 371 } 372 373 CGAL_precondition_code 374 ( 375 // To be used in order to verify continuity and well-orientedness 376 // of the input curve cv. 377 auto min_seg_v = 378 m_poly_traits.subcurve_traits_2()->construct_min_vertex_2_object(); 379 auto max_seg_v = 380 m_poly_traits.subcurve_traits_2()->construct_max_vertex_2_object(); 381 auto equal = m_poly_traits.subcurve_traits_2()->equal_2_object(); 382 Point_2 last_target = (cmp_seg_endpts(*x_seg_p) == SMALLER) ? 383 max_seg_v(*x_seg_p) : min_seg_v(*x_seg_p); 384 Point_2 next_src; 385 ); 386 387 // The polycurve consists of at least 2 x-monotone subcurves: 388 Push_back_2 push_back = m_poly_traits.push_back_2_object(); 389 auto is_seg_vertical = 390 m_poly_traits.subcurve_traits_2()->is_vertical_2_object(); 391 392 bool is_start_vertical = is_seg_vertical(*x_seg_p); 393 Comparison_result start_dir = cmp_seg_endpts(*x_seg_p); 394 395 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 396 Push_front_2 push_front = m_poly_traits.push_front_2_object(); 397 X_monotone_curve_2 x_polycurve = (cmp_seg_endpts(x_seg) == LARGER) ? 398 ctr_x_curve(ctr_seg_opposite(*x_seg_p)) : ctr_x_curve(*x_seg_p); 399 #else 400 X_monotone_curve_2 x_polycurve = ctr_x_curve(*x_seg_p); 401 #endif 402 403 for (++it; it != x_seg_objects.end(); ++it) { 404 const auto* x_seg_p = boost::get<X_monotone_subcurve_2>(&(*it)); 405 #if ! defined (CGAL_NO_ASSERTIONS) 406 CGAL_assertion(x_seg_p != nullptr); 407 #endif 408 409 // Test that cv is continuous and well-oriented. 410 CGAL_precondition_code 411 ( 412 next_src = (cmp_seg_endpts(*x_seg_p) == SMALLER) ? 413 min_seg_v(*x_seg_p) : max_seg_v(*x_seg_p); 414 ); 415 CGAL_precondition_msg 416 ( 417 equal(last_target, next_src), 418 "cv must form a continuous and well oriented curve." 419 ); 420 CGAL_precondition_code 421 ( 422 last_target = (cmp_seg_endpts(*x_seg_p) == SMALLER) ? 423 max_seg_v(*x_seg_p) : min_seg_v(*x_seg_p); 424 ); 425 426 Arr_curve_end polycurve_target = 427 (cmp_seg_endpts(x_polycurve[0]) == SMALLER) ? 428 ARR_MAX_END : ARR_MIN_END; 429 Arr_curve_end seg_source = (cmp_seg_endpts(*x_seg_p) == SMALLER) ? 430 ARR_MIN_END : ARR_MAX_END; 431 auto num_segs = x_polycurve.number_of_subcurves(); 432 433 if ((cmp_seg_endpts(*x_seg_p) != start_dir) || 434 (is_seg_vertical(*x_seg_p) != is_start_vertical)) 435 { 436 // Construct an x-monotone curve from the sub-range which was found 437 *oi++ = Make_x_monotone_result(x_polycurve); 438 is_start_vertical = is_seg_vertical(*x_seg_p); 439 start_dir = cmp_seg_endpts(*x_seg_p); 440 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 441 x_polycurve (cmp_seg_endpts(*x_seg_p) == LARGER) ? 442 ctr_x_curve(ctr_seg_opposite(*x_seg_p)) : ctr_x_curve(*x_seg_p); 443 #else 444 x_polycurve = ctr_x_curve(*x_seg_p); 445 #endif 446 } 447 else if (ps_x(x_polycurve[num_segs-1], polycurve_target) != 448 ARR_INTERIOR || 449 (ps_x(*x_seg_p, seg_source) != ARR_INTERIOR)) 450 { 451 *oi++ = Make_x_monotone_result(x_polycurve); 452 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 453 x_polycurve = (cmp_seg_endpts(*x_seg_p) == LARGER) ? 454 ctr_seg_opposite(*x_seg_p) : ctr_x_curve(*x_seg_p); 455 #endif 456 x_polycurve = ctr_x_curve(*x_seg_p); 457 } 458 459 else { 460 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 461 if (cmp_seg_endpts(*x_seg_p) == LARGER) 462 push_front(x_polycurve, ctr_seg_opposite(*x_seg_p)); 463 else 464 push_back(x_polycurve, *x_seg_p); 465 #else 466 push_back(x_polycurve, *x_seg_p); 467 #endif 468 } 469 } // for loop 470 if (x_polycurve.number_of_subcurves() != 0) 471 *oi++ = Make_x_monotone_result(x_polycurve); 472 x_seg_objects.clear(); 473 return oi; 474 } 475 476 public: 477 template <typename OutputIterator> operator()478 OutputIterator operator()(const Curve_2& cv, OutputIterator oi) const 479 { return operator_impl(cv, oi, Are_all_sides_oblivious_tag()); } 480 }; 481 482 /*! Obtain a Make_x_monotone_2 functor object. */ make_x_monotone_2_object()483 Make_x_monotone_2 make_x_monotone_2_object() const 484 { return Make_x_monotone_2(*this); } 485 486 /* Functor to augment a polycurve by either adding a vertex or a subcurve 487 * at the back. 488 * TODO: Test all the operator()'s. (Don't forget vertical cases!) 489 */ 490 class Push_back_2 : public Base::Push_back_2 { 491 protected: 492 typedef Arr_polycurve_traits_2<Subcurve_traits_2> Polycurve_traits_2; 493 494 public: 495 /*! Constructor. */ Push_back_2(const Polycurve_traits_2 & traits)496 Push_back_2(const Polycurve_traits_2& traits) : Base::Push_back_2(traits) {} 497 498 // Normally, the moment the compiler finds a name, it stops looking. In 499 // other words, the compiler first finds the operator() in the current 500 // class and stops looking, never finding the one in the base class. 501 // Explicitly bring the base operator() into scope, unnecesitating the 502 // code below. 503 using Base::Push_back_2::operator(); 504 505 // /*! Append a subcurve to an existing x-monotone polycurve at the back. 506 // */ 507 // void operator()(X_monotone_curve_2& xcv, 508 // const X_monotone_subcurve_2& seg) 509 // const 510 // { Base::Push_back_2::operator()(xcv, seg); } 511 512 /* Append a subcurve to an existing polycurve at the back. 513 * If the polycurve is empty, the subcurve will be its only subcurve. 514 */ operator()515 void operator()(Curve_2& cv, const Subcurve_2& seg) const 516 { cv.push_back(seg); } 517 }; 518 519 /*! Obtain a Push_back_2 functor object. */ push_back_2_object()520 Push_back_2 push_back_2_object() const { return Push_back_2(*this); } 521 522 /* Functor to augment a polycurve by either adding a vertex or a subcurve 523 * at the front. 524 * TODO: Test all the operator()'s. (Don't forget vertical cases!) 525 */ 526 class Push_front_2 : public Base::Push_front_2 { 527 protected: 528 typedef Arr_polycurve_traits_2<Subcurve_traits_2> Polycurve_traits_2; 529 530 public: 531 /*! Constructor. */ Push_front_2(const Polycurve_traits_2 & traits)532 Push_front_2(const Polycurve_traits_2& traits) : 533 Base::Push_front_2(traits) 534 {} 535 536 // Normally, the moment the compiler finds a name, it stops looking. In 537 // other words, the compiler first finds the operator() in the current 538 // class and stops looking, never finding the one in the base class. 539 // Explicitly bring the base operator() into scope, unnecesitating the 540 // code below. 541 using Base::Push_front_2::operator(); 542 543 // /*! Append a subcurve to an existing x-monotone polycurve at the front. 544 // */ 545 // void operator()(X_monotone_curve_2& xcv, 546 // const X_monotone_subcurve_2& seg) 547 // const 548 // { Base::Push_front_2::operator()(xcv, seg); } 549 550 /* Append a subcurve to an existing polycurve at the front. */ operator()551 void operator()(Curve_2& cv, const Subcurve_2& seg) const 552 { cv.push_front(seg); } 553 }; 554 555 /*! Obtain a Push_front_2 functor object. */ push_front_2_object()556 Push_front_2 push_front_2_object() const { return Push_front_2(*this); } 557 558 class Split_2 { 559 protected: 560 typedef Arr_polycurve_traits_2<Subcurve_traits_2> Polycurve_traits_2; 561 /*! The polycurve traits (in case it has state) */ 562 const Polycurve_traits_2& m_poly_traits; 563 564 public: 565 /*! Constructor. */ Split_2(const Polycurve_traits_2 & traits)566 Split_2(const Polycurve_traits_2& traits) : m_poly_traits(traits) {} 567 568 public: 569 /*! Split a given x-monotone curve at a given point into two sub-curves. 570 * \param cv The curve to split 571 * \param p The split point. 572 * \param c1 Output: The left resulting subcurve(p is its right endpoint). 573 * \param c2 Output: The right resulting subcurve(p is its left endpoint). 574 * \pre p lies on cv but is not one of its end-points. 575 */ operator()576 void operator()(const X_monotone_curve_2& xcv, const Point_2& p, 577 X_monotone_curve_2& xcv1, X_monotone_curve_2& xcv2) const 578 { 579 const Subcurve_traits_2* geom_traits = m_poly_traits.subcurve_traits_2(); 580 auto min_vertex = geom_traits->construct_min_vertex_2_object(); 581 auto max_vertex = geom_traits->construct_max_vertex_2_object(); 582 auto equal = geom_traits->equal_2_object(); 583 auto cmp_seg_endpts = geom_traits->compare_endpoints_xy_2_object(); 584 585 // Make sure the split point is not one of the curve endpoints. 586 CGAL_precondition((! equal(m_poly_traits. 587 construct_min_vertex_2_object()(xcv), p))); 588 CGAL_precondition((! equal(m_poly_traits. 589 construct_max_vertex_2_object()(xcv), p))); 590 591 CGAL_precondition_msg(xcv.number_of_subcurves() > 0, 592 "Cannot split a polycurve of length zero."); 593 594 Comparison_result dir = cmp_seg_endpts(xcv[0]); 595 596 // Locate the subcurve on the polycurve xcv that contains p. 597 std::size_t i = m_poly_traits.locate(xcv, p); 598 599 CGAL_precondition(i != Polycurve_traits_2::INVALID_INDEX); 600 601 // Clear the output curves. 602 xcv1.clear(); 603 xcv2.clear(); 604 605 // Push all subcurves labeled(0, 1, ... , i-1) into xcv1. 606 for (std::size_t j = 0; j < i; ++j) xcv1.push_back(xcv[j]); 607 608 if (dir == SMALLER){ 609 // Check whether the split point is xcv[i]'s source or target. 610 if (equal(max_vertex(xcv[i]), p)) { 611 // The entire i'th subcurve belongs to xcv1: 612 xcv1.push_back(xcv[i]); 613 } 614 else if (equal(min_vertex(xcv[i]), p)) { 615 // The entire i'th subcurves belongs to xcv2: 616 xcv2.push_back(xcv[i]); 617 } 618 else { 619 // The i'th subcurve should be split: The left part(seg1) 620 // goes to xcv1, and the right part(seg2) goes to xcv2. 621 X_monotone_subcurve_2 seg1, seg2; 622 m_poly_traits.subcurve_traits_2()->split_2_object()(xcv[i], p, 623 seg1, seg2); 624 625 xcv1.push_back(seg1); 626 xcv2.push_back(seg2); 627 } 628 } 629 else { 630 if (equal(min_vertex(xcv[i]), p)) { 631 xcv1.push_back(xcv[i]); 632 } 633 else if (equal(max_vertex(xcv[i]), p)) { 634 xcv2.push_back(xcv[i]); 635 } 636 else { 637 X_monotone_subcurve_2 seg1, seg2; 638 m_poly_traits.subcurve_traits_2()-> 639 split_2_object()(xcv[i], p, seg1, seg2); 640 641 if (cmp_seg_endpts(seg2) == LARGER){ 642 xcv1.push_back(seg2); 643 } 644 else { 645 // seg2 has to be reversed 646 seg2 = m_poly_traits.subcurve_traits_2()-> 647 construct_opposite_2_object()(seg2); 648 xcv1.push_back(seg2); 649 } 650 651 if (cmp_seg_endpts(seg1) == LARGER){ 652 xcv2.push_back(seg1); 653 } 654 else { 655 // seg2 has to be reversed 656 seg1 = m_poly_traits.subcurve_traits_2()-> 657 construct_opposite_2_object()(seg1); 658 xcv1.push_back(seg1); 659 } 660 } 661 } 662 663 // Push all subcurves labeled(i+1, i+2, ... , n-1) into xcv1. 664 std::size_t n = xcv.number_of_subcurves(); 665 666 for (std::size_t j = i+1; j < n; ++j) xcv2.push_back(xcv[j]); 667 668 if (dir != SMALLER) std::swap(xcv1, xcv2); 669 } 670 }; 671 672 /*! Obtain a Split_2 functor object. */ split_2_object()673 Split_2 split_2_object() const { return Split_2(*this); } 674 675 class Intersect_2 { 676 protected: 677 typedef Arr_polycurve_traits_2<Subcurve_traits_2> Polycurve_traits_2; 678 /*! The polycurve traits (in case it has state) */ 679 const Polycurve_traits_2& m_poly_traits; 680 681 public: 682 /*! Constructor. */ Intersect_2(const Polycurve_traits_2 & traits)683 Intersect_2(const Polycurve_traits_2& traits) : m_poly_traits(traits) {} 684 685 /*! Find the intersections of the two given curves and insert them into the 686 * given output iterator. As two subcurves may itersect only once, only a 687 * single intersection will be contained in the iterator. 688 * Note: If the intersection yields an overlap then it will be oriented 689 * from left-to-right. 690 * \param cv1 The first curve. 691 * \param cv2 The second curve. 692 * \param oi The output iterator. 693 * \return The past-the-end iterator. 694 */ 695 template <typename OutputIterator> 696 OutputIterator operator()697 operator()(const X_monotone_curve_2& cv1, 698 const X_monotone_curve_2& cv2, 699 OutputIterator oi) const 700 { 701 typedef std::pair<Point_2, Multiplicity> Intersection_point; 702 typedef boost::variant<Intersection_point, X_monotone_subcurve_2> 703 Intersection_base_result; 704 typedef boost::variant<Intersection_point, X_monotone_curve_2> 705 Intersection_result; 706 707 const Subcurve_traits_2* geom_traits = m_poly_traits.subcurve_traits_2(); 708 auto cmp_y_at_x = m_poly_traits.compare_y_at_x_2_object(); 709 auto equal = geom_traits->equal_2_object(); 710 auto min_vertex = geom_traits->construct_min_vertex_2_object(); 711 auto max_vertex = geom_traits->construct_max_vertex_2_object(); 712 auto intersect = geom_traits->intersect_2_object(); 713 auto cmp_seg_endpts = geom_traits->compare_endpoints_xy_2_object(); 714 auto construct_opposite = geom_traits->construct_opposite_2_object(); 715 716 Comparison_result dir1 = cmp_seg_endpts(cv1[0]); 717 Comparison_result dir2 = cmp_seg_endpts(cv2[0]); 718 719 std::vector<X_monotone_subcurve_2> ocv; // Used to represent overlaps. 720 const bool invert_ocv = ((dir1 == LARGER) && (dir2 == LARGER)); 721 const bool consistent = (dir1 == dir2); 722 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 723 CGAL_assertion(consistent); 724 #endif 725 726 const std::size_t n1 = cv1.number_of_subcurves(); 727 const std::size_t n2 = cv2.number_of_subcurves(); 728 729 std::size_t i1 = (dir1 == SMALLER) ? 0 : n1-1; 730 std::size_t i2 = (dir2 == SMALLER) ? 0 : n2-1; 731 732 auto compare_xy = m_poly_traits.compare_xy_2_object(); 733 Comparison_result left_res = 734 compare_xy(cv1[i1], ARR_MIN_END, cv2[i2], ARR_MIN_END); 735 736 if (left_res == SMALLER) { 737 // cv1's left endpoint is to the left of cv2's left endpoint: 738 // Locate the index i1 of the subcurve in cv1 which contains cv2's 739 // left endpoint. 740 i1 = m_poly_traits.locate_impl(cv1, cv2[i2], ARR_MIN_END, 741 Are_all_sides_oblivious_tag()); 742 if (i1 == Polycurve_traits_2::INVALID_INDEX) return oi; 743 744 if (equal(max_vertex(cv1[i1]), min_vertex(cv2[i2]))) { 745 if (((dir1 == SMALLER) && (i1 == n1-1)) || 746 ((dir1 == LARGER) && (i1 == 0))){ 747 // cv1's right endpoint equals cv2's left endpoint 748 // Thus we can return this single(!) intersection point 749 Intersection_point p(max_vertex(cv1[i1]), 0); 750 *oi++ = Intersection_result(p); 751 return oi; 752 } 753 dir1 == SMALLER ? 754 ++i1 : 755 (i1 != 0) ? --i1 : (std::size_t) Polycurve_traits_2::INVALID_INDEX; 756 left_res = EQUAL; 757 } 758 } 759 else if (left_res == LARGER) { 760 // cv1's left endpoint is to the right of cv2's left endpoint: 761 // Locate the index i2 of the subcurve in cv2 which contains cv1's 762 // left endpoint. 763 i2 = m_poly_traits.locate_impl(cv2, cv1[i1], ARR_MIN_END, 764 Are_all_sides_oblivious_tag()); 765 if (i2 == Polycurve_traits_2::INVALID_INDEX) return oi; 766 767 if (equal(max_vertex(cv2[i2]), min_vertex(cv1[i1]))) { 768 if (((dir2 == SMALLER) && (i2 == n2-1)) || 769 ((dir2 == LARGER) && (i2 == 0))){ 770 // cv2's right endpoint equals cv1's left endpoint 771 // Thus we can return this single(!) intersection point 772 Intersection_point p(max_vertex(cv2[i2]), 0); 773 *oi++ = Intersection_result(p); 774 return oi; 775 } 776 777 dir2 == SMALLER ? 778 ++i2 : 779 (i2 != 0) ? --i2 : (std::size_t) Polycurve_traits_2::INVALID_INDEX; 780 left_res = EQUAL; 781 } 782 } 783 784 // Check if the left endpoint lies on the other polycurve. 785 bool left_coincides = (left_res == EQUAL); 786 bool left_overlap = false; 787 788 if (left_res == SMALLER) 789 left_coincides = (cmp_y_at_x(cv2[i2], ARR_MIN_END, cv1[i1]) == EQUAL); 790 else if (left_res == LARGER) 791 left_coincides = (cmp_y_at_x(cv1[i1], ARR_MIN_END, cv2[i2]) == EQUAL); 792 793 // The main loop: Go simultaneously over both polycurves. 794 Comparison_result right_res = left_res; 795 bool right_coincides = left_coincides; 796 bool right_overlap = false; 797 798 while (((dir1 == SMALLER) && (dir2 == SMALLER) && 799 (i1 < n1) && (i2 < n2)) || 800 ((dir1 != SMALLER) && (dir2 == SMALLER) && 801 (i1 != Polycurve_traits_2::INVALID_INDEX) && (i2 < n2)) || 802 ((dir1 == SMALLER) && (dir2 != SMALLER) && (i1 < n1) && 803 (i2 != Polycurve_traits_2::INVALID_INDEX)) || 804 ((dir1 != SMALLER) && (dir2 != SMALLER) && 805 (i1 != Polycurve_traits_2::INVALID_INDEX) && 806 (i2 != Polycurve_traits_2::INVALID_INDEX))) 807 { 808 right_res = compare_xy(cv1[i1], ARR_MAX_END, cv2[i2], ARR_MAX_END); 809 810 right_coincides = (right_res == EQUAL); 811 if (right_res == SMALLER) 812 right_coincides = 813 (cmp_y_at_x(cv1[i1], ARR_MAX_END, cv2[i2]) == EQUAL); 814 else if (right_res == LARGER) 815 right_coincides = 816 (cmp_y_at_x(cv2[i2], ARR_MAX_END, cv1[i1]) == EQUAL); 817 818 right_overlap = false; 819 820 //! EF: the following code is abit suspicious. It may erroneously 821 // assume that the subcurves cannot overlap more than once. 822 if (! right_coincides && ! left_coincides) { 823 // Non of the endpoints of the current subcurve of one polycurve 824 // coincides with the curent subcurve of the other polycurve: 825 // Output the intersection if exists. 826 std::vector<Intersection_base_result> xections; 827 intersect(cv1[i1], cv2[i2], std::back_inserter(xections)); 828 for (const auto& xection : xections) { 829 const X_monotone_subcurve_2* subcv_p = 830 boost::get<X_monotone_subcurve_2>(&xection); 831 if (subcv_p != nullptr) { 832 ocv.push_back(*subcv_p); 833 oi = output_ocv (ocv, invert_ocv, oi); 834 continue; 835 } 836 837 const Intersection_point* p_p = 838 boost::get<Intersection_point>(&xection); 839 if (p_p != nullptr) *oi++ = Intersection_result(*p_p); 840 } 841 } 842 else if (right_coincides && left_coincides) { 843 // An overlap exists between the current subcurves of the 844 // polycurves: Output the overlapping subcurve. 845 right_overlap = true; 846 847 std::vector<Intersection_base_result> sub_xections; 848 intersect(cv1[i1], cv2[i2], std::back_inserter(sub_xections)); 849 850 for (const auto& item : sub_xections) { 851 const X_monotone_subcurve_2* x_seg = 852 boost::get<X_monotone_subcurve_2>(&item); 853 if (x_seg != nullptr) { 854 X_monotone_subcurve_2 seg = *x_seg; 855 // We maintain the variant that if the input curves have opposite 856 // directions (! consistent), the overalpping curves are directed 857 // left=>right. This, however, is not guaranteed for the 858 // subcurves. Therefore, we need to enforce it. That is, we make 859 // sure the subcurves are also directed left=>right in this case. 860 if (! consistent && (cmp_seg_endpts(seg) == LARGER)) 861 seg = construct_opposite(seg); 862 #ifdef CGAL_ALWAYS_LEFT_TO_RIGHT 863 CGAL_assertion(cmp_seg_endpts(seg) == SMALLER); 864 #endif 865 ocv.push_back(seg); 866 } 867 868 const Intersection_point* p_ptr = 869 boost::get<Intersection_point>(&item); 870 if (p_ptr != nullptr) { 871 // Any point that is not equal to the max_vertex of the 872 // subcurve should be inserted into oi. 873 // The max_vertex of the current subcurve (if intersecting) 874 // will be taken care of as the min_vertex of in the next 875 // iteration. 876 if (! equal(p_ptr->first, max_vertex(cv1[i1]))) 877 *oi++ = Intersection_result(*p_ptr); 878 } 879 } 880 } 881 882 else if (left_coincides && ! right_coincides) { 883 // std::cout << "Left is coinciding but right is not." << std::endl; 884 // The left point of the current subcurve of one polycurve 885 // coincides with the current subcurve of the other polycurve. 886 if (left_overlap) { 887 // An overlap occurred at the previous iteration: 888 // Output the overlapping polycurve. 889 CGAL_assertion(ocv.size() > 0); 890 oi = output_ocv (ocv, invert_ocv, oi); 891 } 892 else { 893 // The left point of the current subcurve of one 894 // polycurve coincides with the current subcurve of the 895 // other polycurve, and no overlap occurred at the 896 // previous iteration: Output the intersection 897 // point. The derivative of at least one of the 898 // polycurves is not defined at this point, so we give 899 // it multiplicity 0. 900 if (left_res == SMALLER) { 901 Intersection_point p(min_vertex(cv2[i2]), 0); 902 *oi++ = Intersection_result(p); 903 } 904 else { 905 Intersection_point p(min_vertex(cv1[i1]), 0); 906 *oi++ = Intersection_result(p); 907 } 908 } 909 } 910 911 // Proceed forward. 912 if (right_res != SMALLER) { 913 if (dir2 == SMALLER) ++i2; 914 else { 915 if (i2 == 0) i2 = Polycurve_traits_2::INVALID_INDEX; 916 else --i2; 917 } 918 } 919 if (right_res != LARGER) { 920 if (dir1 == SMALLER) 921 ++i1; 922 else { 923 if (i1 == 0) i1 = Polycurve_traits_2::INVALID_INDEX; 924 else --i1; 925 } 926 } 927 left_res = (right_res == SMALLER) ? LARGER : 928 (right_res == LARGER) ? SMALLER : EQUAL; 929 930 left_coincides = right_coincides; 931 left_overlap = right_overlap; 932 } // END of while loop 933 934 // Output the remaining overlapping polycurve, if necessary. 935 if (ocv.size() > 0) { 936 oi = output_ocv (ocv, invert_ocv, oi); 937 } 938 else if (right_coincides) { 939 typedef std::pair<Point_2,Multiplicity> return_point; 940 return_point ip; 941 if (right_res == SMALLER) { 942 ip = (dir1 == SMALLER) ? 943 return_point(max_vertex(cv1[i1-1]), 0) : 944 (i1 != Polycurve_traits_2::INVALID_INDEX) ? 945 return_point(max_vertex(cv1[i1+1]), 0) : 946 return_point(max_vertex(cv1[0]), 0); 947 *oi++ = Intersection_result(ip); 948 } 949 else if (right_res == LARGER) { 950 ip = (dir2 == SMALLER) ? 951 return_point(max_vertex(cv2[i2-1]), 0) : 952 (i2 != Polycurve_traits_2::INVALID_INDEX) ? 953 return_point(max_vertex(cv2[i2+1]), 0) : 954 return_point(max_vertex(cv2[0]), 0); 955 *oi++ = Intersection_result(ip); 956 } 957 else if (((i1 > 0) && (dir1 == SMALLER)) || 958 ((i1 < n1) && (dir1 != SMALLER)) || 959 ((i1 == Polycurve_traits_2::INVALID_INDEX) && 960 (dir1 != SMALLER))) 961 { 962 ip = (dir1 == SMALLER) ? 963 return_point(max_vertex(cv1[i1-1]), 0) : 964 (i1 != Polycurve_traits_2::INVALID_INDEX) ? 965 return_point(max_vertex(cv1[i1+1]), 0) : 966 return_point(max_vertex(cv1[0]), 0); 967 *oi++ = Intersection_result(ip); 968 } 969 else { 970 CGAL_assertion_msg((dir2 == SMALLER && i2 > 0) || 971 (dir2 != SMALLER && i2 < n2) || 972 (dir2 != SMALLER && 973 ((i1 == Polycurve_traits_2::INVALID_INDEX) || 974 (i2 == Polycurve_traits_2::INVALID_INDEX))), 975 "Wrong index for xcv2 in Intersect_2 of " 976 "polycurves."); 977 ip = (dir2 == SMALLER) ? 978 return_point(max_vertex(cv2[i2-1]), 0) : 979 (i2 != Polycurve_traits_2::INVALID_INDEX) ? 980 return_point(max_vertex(cv2[i2+1]), 0) : 981 return_point(max_vertex(cv2[0]), 0); 982 *oi++ = Intersection_result(ip); 983 } 984 } 985 986 return oi; 987 } 988 989 private: 990 991 template <typename OutputIterator> output_ocv(std::vector<X_monotone_subcurve_2> & ocv,bool invert_ocv,OutputIterator oi)992 inline OutputIterator output_ocv 993 (std::vector<X_monotone_subcurve_2>& ocv, bool invert_ocv, OutputIterator oi) const 994 { 995 typedef std::pair<Point_2, Multiplicity> Intersection_point; 996 typedef boost::variant<Intersection_point, X_monotone_curve_2> 997 Intersection_result; 998 X_monotone_curve_2 curve; 999 if (invert_ocv) 1000 std::reverse (ocv.begin(), ocv.end()); 1001 for (X_monotone_subcurve_2& sc : ocv) 1002 curve.push_back (sc); 1003 *(oi ++) = Intersection_result(curve); 1004 1005 ocv.clear(); 1006 1007 return oi; 1008 } 1009 }; 1010 1011 /*! Obtain an Intersect_2 functor object. */ intersect_2_object()1012 Intersect_2 intersect_2_object() const 1013 { return Intersect_2(*this); } 1014 1015 class Are_mergeable_2 { 1016 protected: 1017 typedef Arr_polycurve_traits_2<Subcurve_traits_2> Polycurve_traits_2; 1018 /*! The polycurve traits (in case it has state) */ 1019 const Polycurve_traits_2& m_poly_traits; 1020 1021 public: 1022 /*! Constructor. */ Are_mergeable_2(const Polycurve_traits_2 & traits)1023 Are_mergeable_2(const Polycurve_traits_2& traits) : 1024 m_poly_traits(traits) 1025 {} 1026 1027 /*! Check whether it is possible to merge two given x-monotone curves. 1028 * \param cv1 The first curve. 1029 * \param cv2 The second curve. 1030 * \return(true) if the two curves are mergeable, that is, they share a 1031 * common endpoint and the same orientation;(false) otherwise. 1032 */ operator()1033 bool operator()(const X_monotone_curve_2& cv1, 1034 const X_monotone_curve_2& cv2) const 1035 { 1036 const Subcurve_traits_2* geom_traits = m_poly_traits.subcurve_traits_2(); 1037 Construct_min_vertex_2 min_vertex = 1038 m_poly_traits.construct_min_vertex_2_object(); 1039 Construct_max_vertex_2 max_vertex = 1040 m_poly_traits.construct_max_vertex_2_object(); 1041 typename Subcurve_traits_2::Equal_2 equal = 1042 geom_traits->equal_2_object(); 1043 typename Subcurve_traits_2::Is_vertical_2 is_seg_vertical = 1044 geom_traits->is_vertical_2_object(); 1045 1046 Comparison_result dir1 = 1047 m_poly_traits.compare_endpoints_xy_2_object()(cv1); 1048 Comparison_result dir2 = 1049 m_poly_traits.compare_endpoints_xy_2_object()(cv2); 1050 1051 if (dir1 != dir2) 1052 return false; 1053 1054 bool ver1 = is_seg_vertical(cv1[0]); 1055 bool ver2 = is_seg_vertical(cv2[0]); 1056 1057 return (((// Both are directed from left-to-right 1058 (dir1 == SMALLER) && 1059 ((equal(max_vertex(cv1),min_vertex(cv2))) || 1060 (equal(max_vertex(cv2),min_vertex(cv1))))) || 1061 (// Both are directed from right-to-left 1062 (dir1 == LARGER) && 1063 ((equal(min_vertex(cv1),max_vertex(cv2))) || 1064 (equal(max_vertex(cv1),min_vertex(cv2)))) 1065 )) && 1066 (// Either both should be vertical or both should 1067 // be NOT vertical. 1068 (ver1 && ver2) || (!ver1 && !ver2))); 1069 } 1070 }; 1071 1072 /*! Obtain an Are_mergeable_2 functor object. */ are_mergeable_2_object()1073 Are_mergeable_2 are_mergeable_2_object() const 1074 { return Are_mergeable_2(*this); } 1075 1076 /*! \class Merge_2 1077 * A functor that merges two x-monotone curves into one. 1078 */ 1079 /* Roadmap: Allow merging of overlapping polycurves. This means also 1080 * changing the subcurve traits class. 1081 */ 1082 class Merge_2 { 1083 protected: 1084 typedef Arr_polycurve_traits_2<Subcurve_traits_2> Geometry_traits; 1085 /*! The traits (in case it has state) */ 1086 const Geometry_traits& m_poly_traits; 1087 1088 public: 1089 /*! Constructor 1090 * \param traits the traits (in case it has state) 1091 */ Merge_2(const Geometry_traits & traits)1092 Merge_2(const Geometry_traits& traits) : m_poly_traits(traits) {} 1093 1094 /*! Merge two given x-monotone curves into a single curve(segment). 1095 * \param cv1 The first curve. 1096 * \param cv2 The second curve. 1097 * \param c Output: The merged curve. 1098 * \pre The two curves are mergeable. 1099 */ operator()1100 void operator()(const X_monotone_curve_2& cv1, 1101 const X_monotone_curve_2& cv2, 1102 X_monotone_curve_2& c) const 1103 { 1104 CGAL_precondition(m_poly_traits.are_mergeable_2_object()(cv1, cv2)); 1105 1106 Construct_min_vertex_2 get_min_v = 1107 m_poly_traits.construct_min_vertex_2_object(); 1108 Construct_max_vertex_2 get_max_v = 1109 m_poly_traits.construct_max_vertex_2_object(); 1110 Compare_endpoints_xy_2 cmp_seg_endpts = 1111 m_poly_traits.compare_endpoints_xy_2_object(); 1112 Equal_2 equal = m_poly_traits.equal_2_object(); 1113 1114 c.clear(); 1115 if (// Either both are left-to-right and cv2 is to the right of cv1 1116 ((cmp_seg_endpts(cv1)==SMALLER) && 1117 (equal(get_max_v(cv1),get_min_v(cv2)))) || 1118 // or both are right-to-left and cv2 is to the left of cv1 1119 ((cmp_seg_endpts(cv1)==LARGER) && 1120 (equal(get_min_v(cv1), get_max_v(cv2))))) 1121 { 1122 const std::size_t n1 = cv1.number_of_subcurves(); 1123 const std::size_t n2 = cv2.number_of_subcurves(); 1124 std::size_t i; 1125 1126 // cv2 extends cv1 to the right: 1127 for (i = 0; i < n1 - 1; ++i) c.push_back(cv1[i]); 1128 1129 // Try to merge the to contiguous line subcurves: 1130 if (m_poly_traits.subcurve_traits_2()-> 1131 are_mergeable_2_object()(cv1[n1 - 1], cv2[0])) 1132 { 1133 X_monotone_subcurve_2 seg; 1134 m_poly_traits.subcurve_traits_2()-> 1135 merge_2_object()(cv1[n1 - 1], cv2[0], seg); 1136 c.push_back(seg); 1137 } 1138 else { 1139 c.push_back(cv1[n1 - 1]); 1140 c.push_back(cv2[0]); 1141 } 1142 1143 for (i = 1; i < n2; ++i) c.push_back(cv2[i]); 1144 } 1145 else 1146 return this->operator()(cv2,cv1,c); 1147 } 1148 }; 1149 1150 /*! Obtain a Merge_2 functor object. */ merge_2_object()1151 Merge_2 merge_2_object() const { return Merge_2(*this); } 1152 ///@} 1153 1154 /*! \class 1155 * A functor that constructs a (general) polycurve. 1156 */ 1157 class Construct_curve_2 { 1158 protected: 1159 typedef Arr_polycurve_traits_2<Subcurve_traits_2> Polycurve_traits_2; 1160 /*! The polycurve traits (in case it has state) */ 1161 const Polycurve_traits_2& m_poly_traits; 1162 1163 public: 1164 /*! Constructor. */ Construct_curve_2(const Polycurve_traits_2 & traits)1165 Construct_curve_2(const Polycurve_traits_2& traits) : 1166 m_poly_traits(traits) 1167 {} 1168 1169 /*! Obtain a polycurve that consists of one given subcurve. */ operator()1170 Curve_2 operator()(const Subcurve_2& seg) const { return Curve_2(seg); } 1171 1172 /* Construct a well-oriented polycurve from a range of either 1173 * `SubcurveTraits::Point_2` or `SubcurveTraits::Subcurve_2`. 1174 */ 1175 template <typename ForwardIterator> operator()1176 Curve_2 operator()(ForwardIterator begin, ForwardIterator end) const 1177 { 1178 typedef typename std::iterator_traits<ForwardIterator>::value_type VT; 1179 typedef typename boost::is_same<VT, Point_2>::type Is_point; 1180 // Dispatch the range to the appropriate implementation. 1181 return constructor_impl(begin, end, Is_point()); 1182 } 1183 1184 /*! Construction of a polycurve from a range of points. 1185 * \pre The range contains at least two points 1186 * \pre Consecutive points are disjoint. 1187 * \return Well-oriented polycurve connecting the given 1188 * points. The order of the vertices is determined by 1189 * their order in the range. Furthermore, the 1190 * orientation of the polycurve is induced by their 1191 * order. 1192 */ 1193 template <typename ForwardIterator> constructor_impl(ForwardIterator,ForwardIterator,boost::true_type)1194 Curve_2 constructor_impl(ForwardIterator /* begin */, 1195 ForwardIterator /* end */, 1196 boost::true_type) const 1197 { CGAL_error_msg("Cannot construct a polycurve from a range of points!"); } 1198 1199 /*! Construction implementation from a range of subcurves. 1200 * Note that the subcurves in the range are NOT necessarily x-monotone, 1201 * thus it is impossible to test (even in precondition) whether the input 1202 * forms a continuous and well oriented polycurve. 1203 * \pre Range should contain at least one subcurve. 1204 */ 1205 template <typename ForwardIterator> constructor_impl(ForwardIterator begin,ForwardIterator end,boost::false_type)1206 Curve_2 constructor_impl(ForwardIterator begin, ForwardIterator end, 1207 boost::false_type) const 1208 { 1209 // Range has to contain at least one subcurve 1210 CGAL_precondition(begin != end); 1211 return Curve_2(begin, end); 1212 } 1213 }; 1214 1215 /*! Obtain a Construct_curve_2 functor object. */ construct_curve_2_object()1216 Construct_curve_2 construct_curve_2_object() const 1217 { return Construct_curve_2(*this); } 1218 }; 1219 1220 } //namespace CGAL 1221 1222 #include <CGAL/enable_warnings.h> 1223 1224 #endif 1225