1 // Copyright (c) 2006,2007,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_non_caching_segment_traits_2.h $ 7 // $Id: Arr_non_caching_segment_traits_2.h 436ba5f 2020-06-30T21:23:16+03:00 Efi Fogel 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 // (base on old version by: Iddo Hanniel) 13 14 #ifndef CGAL_ARR_NON_CACHING_SEGMENT_TRAITS_H 15 #define CGAL_ARR_NON_CACHING_SEGMENT_TRAITS_H 16 17 #include <CGAL/license/Arrangement_on_surface_2.h> 18 19 #include <CGAL/disable_warnings.h> 20 21 /*! \file The non-caching segment traits-class for the arrangement package. 22 * This traits class handles general segments. It is a model of the 23 * ArrangementTraits_2 concept, a refinement of the ArrangementBasicTraits_2 24 * concept. The class is templated by a kernel and inherits from the 25 * Arr_non_caching_segment_basic_traits_2 class instanciated with the kernel - 26 * a model of the ArrangementBasicTraits_2 concept. It defined a few additional 27 * functors required by the concept it models. 28 */ 29 30 #include <boost/variant.hpp> 31 32 #include <CGAL/Exact_predicates_exact_constructions_kernel.h> 33 #include <CGAL/tags.h> 34 #include <CGAL/Arr_tags.h> 35 #include <CGAL/Arr_non_caching_segment_basic_traits_2.h> 36 #include <CGAL/intersections.h> 37 38 namespace CGAL { 39 40 /*! \class 41 * A model of the ArrangementTraits_2 concept that handles general 42 * line segments. 43 */ 44 template <typename Kernel_T = Exact_predicates_exact_constructions_kernel> 45 class Arr_non_caching_segment_traits_2 : 46 public Arr_non_caching_segment_basic_traits_2<Kernel_T> 47 { 48 public: 49 typedef Kernel_T Kernel; 50 51 typedef Arr_non_caching_segment_basic_traits_2<Kernel> Base; 52 typedef typename Base::Segment_assertions Segment_assertions; 53 typedef typename Base::Has_exact_division Has_exact_division; 54 55 /*! Default constructor */ Arr_non_caching_segment_traits_2()56 Arr_non_caching_segment_traits_2() : Base() {} 57 58 /// \name Types and functors inherited from the base 59 //@{ 60 61 // Traits types: 62 typedef typename Base::Has_left_category Has_left_category; 63 typedef typename Base::Has_do_intersect_category Has_do_intersect_category; 64 65 typedef typename Base::Left_side_category Left_side_category; 66 typedef typename Base::Bottom_side_category Bottom_side_category; 67 typedef typename Base::Top_side_category Top_side_category; 68 typedef typename Base::Right_side_category Right_side_category; 69 70 typedef typename Base::Point_2 Point_2; 71 typedef typename Base::X_monotone_curve_2 X_monotone_curve_2; 72 typedef typename Base::Multiplicity Multiplicity; 73 74 /*! Compare the x-coordinates of two points */ 75 typedef typename Base::Compare_x_2 Compare_x_2; 76 77 /*! Compare two points lexigoraphically; by x, then by y */ 78 typedef typename Base::Compare_xy_2 Compare_xy_2; 79 80 /*! Obtain the left endpoint of a given segment */ 81 typedef typename Base::Construct_min_vertex_2 Construct_min_vertex_2; 82 83 /*! Obtain the right endpoint of a given segment */ 84 typedef typename Base::Construct_max_vertex_2 Construct_max_vertex_2; 85 86 /*! Check whether a given segment is vertical */ 87 typedef typename Base::Is_vertical_2 Is_vertical_2; 88 89 /*! Return the location of a given point with respect to an input segment */ 90 typedef typename Base::Compare_y_at_x_2 Compare_y_at_x_2; 91 92 /*! Check if two segments or if two points are identical */ 93 typedef typename Base::Equal_2 Equal_2; 94 95 /*! Compare the y value of two segments immediately to the left of their 96 * intersection point 97 */ 98 typedef typename Base::Compare_y_at_x_left_2 Compare_y_at_x_left_2; 99 100 /*! Compare the y value of two segments immediately to the right of their 101 * intersection point 102 */ 103 typedef typename Base::Compare_y_at_x_right_2 Compare_y_at_x_right_2; 104 105 //@} 106 107 /// \name Types and functors introduced here (based on the kernel) 108 //@{ 109 110 // Categories: 111 typedef Tag_true Has_merge_category; 112 113 // Traits types: 114 typedef X_monotone_curve_2 Curve_2; 115 116 /*! \class Make_x_monotone_2 117 * A functor for subdividing a curve into x-monotone curves. 118 */ 119 class Make_x_monotone_2 { 120 public: 121 /*! Subdivide a given curve into x-monotone subcurves and insert them into 122 * a given output iterator. As segments are always x_monotone, only one 123 * x-monotone curve is inserted into the output iterator. 124 * \param cv the segment. 125 * \param oi the output iterator for the result. Its dereference type is a 126 * variant that wraps a \c Point_2 or an \c X_monotone_curve_2 127 * objects. 128 * \return the past-the-end iterator. 129 */ 130 template <typename OutputIterator> operator()131 OutputIterator operator()(const Curve_2& cv, OutputIterator oi) const 132 { 133 // Wrap the segment with a variant. 134 typedef boost::variant<Point_2, X_monotone_curve_2> 135 Make_x_monotone_result; 136 *oi++ = Make_x_monotone_result(cv); 137 return oi; 138 } 139 }; 140 141 /*! Obtain a Make_x_monotone_2 functor object. */ make_x_monotone_2_object()142 Make_x_monotone_2 make_x_monotone_2_object() const 143 { return Make_x_monotone_2(); } 144 145 /*! \class 146 * A functor for splitting a segment into two segements. 147 */ 148 class Split_2 { 149 typedef Arr_non_caching_segment_traits_2<Kernel_T> Self; 150 151 public: 152 /*! Split a given x-monotone curve at a given point into two sub-curves. 153 * \param cv The curve to split 154 * \param p The split point. 155 * \param c1 Output: The left resulting subcurve (p is its right endpoint). 156 * \param c2 Output: The right resulting subcurve (p is its left endpoint). 157 * \pre p lies on cv but is not one of its end-points. 158 */ operator()159 void operator()(const X_monotone_curve_2& cv, const Point_2& p, 160 X_monotone_curve_2& c1, X_monotone_curve_2& c2) const 161 { 162 Base base; 163 164 // Make sure that p lies on the interior of the curve. 165 CGAL_precondition_code(auto compare_xy = base.compare_xy_2_object()); 166 167 Construct_min_vertex_2 min_vertex = base.construct_min_vertex_2_object(); 168 Construct_max_vertex_2 max_vertex = base.construct_max_vertex_2_object(); 169 170 const Point_2& left = min_vertex(cv); 171 const Point_2& right = max_vertex(cv); 172 CGAL_precondition 173 (Segment_assertions::_assert_is_point_on(p, cv, Has_exact_division()) && 174 compare_xy(left, p) == SMALLER && 175 compare_xy(right, p) == LARGER); 176 177 typename Base::Construct_segment_2 construct_segment = 178 base.construct_segment_2_object(); 179 180 Self self; 181 if (self.compare_endpoints_xy_2_object()(cv) == SMALLER) { 182 c1 = construct_segment(left, p); 183 c2 = construct_segment(p, right); 184 } 185 else { 186 c1 = construct_segment(p, left); 187 c2 = construct_segment(right, p); 188 } 189 } 190 }; 191 192 /*! Obtain a Split_2 functor object. */ split_2_object()193 Split_2 split_2_object() const { return Split_2(); } 194 195 /*! \class 196 * A functor for computing intersections. 197 */ 198 class Intersect_2 { 199 protected: 200 typedef Arr_non_caching_segment_traits_2<Kernel> Traits; 201 202 /*! The traits (in case it has state) */ 203 const Traits& m_traits; 204 205 /*! Constructor 206 * \param traits the traits (in case it has state) 207 */ Intersect_2(const Traits & traits)208 Intersect_2(const Traits& traits) : m_traits(traits) {} 209 210 friend class Arr_non_caching_segment_traits_2<Kernel>; 211 212 public: 213 /*! Find the intersections of the two given segments and insert them into 214 * the given output iterator. As two segments may itersect only once, only 215 * a single intersection will be contained in the iterator. 216 * \param cv1 The first curve. 217 * \param cv2 The second curve. 218 * \param oi The output iterator. 219 * \return The past-the-end iterator. 220 */ 221 template <typename OutputIterator> operator()222 OutputIterator operator()(const X_monotone_curve_2& cv1, 223 const X_monotone_curve_2& cv2, 224 OutputIterator oi) const 225 { 226 typedef std::pair<Point_2, Multiplicity> Intersection_point; 227 typedef boost::variant<Intersection_point, X_monotone_curve_2> 228 Intersection_result; 229 230 const Kernel& kernel = m_traits; 231 auto res = kernel.intersect_2_object()(cv1, cv2); 232 233 // There is no intersection: 234 if (! res) return oi; 235 236 // Chack if the intersection is a point: 237 const Point_2* p_p = boost::get<Point_2>(&*res); 238 if (p_p != nullptr) { 239 // Create a pair representing the point with its multiplicity, 240 // which is always 1 for line segments for all practical purposes. 241 // If the two segments intersect at their endpoints, then the 242 // multiplicity is undefined, but we deliberately ignore it for 243 // efficieny reasons. 244 *oi++ = Intersection_result(Intersection_point(*p_p, 1)); 245 return oi; 246 } 247 248 // The intersection is a segment. 249 const X_monotone_curve_2* cv_p = boost::get<X_monotone_curve_2>(&*res); 250 CGAL_assertion(cv_p != nullptr); 251 252 Comparison_result cmp1 = m_traits.compare_endpoints_xy_2_object()(cv1); 253 Comparison_result cmp2 = m_traits.compare_endpoints_xy_2_object()(cv2); 254 255 if (cmp1 == cmp2) { 256 // cv1 and cv2 have the same directions, maintain this direction 257 // in the overlap segment 258 if (m_traits.compare_endpoints_xy_2_object()(*cv_p) != cmp1) { 259 auto ctr_opposite = kernel.construct_opposite_segment_2_object(); 260 *oi++ = Intersection_result(ctr_opposite(*cv_p)); 261 return oi; 262 } 263 } 264 *oi++ = Intersection_result(*cv_p); 265 return oi; 266 } 267 }; 268 269 /*! Obtain an Intersect_2 functor object. */ intersect_2_object()270 Intersect_2 intersect_2_object() const { return Intersect_2(*this); } 271 272 /*! \class 273 * A functor for testing whether two segments are mergeable. 274 */ 275 class Are_mergeable_2 { 276 protected: 277 typedef Arr_non_caching_segment_traits_2<Kernel> Traits; 278 279 /*! The traits (in case it has state) */ 280 const Traits* m_traits; 281 282 /*! Constructor 283 * \param traits the traits (in case it has state) 284 */ Are_mergeable_2(const Traits * traits)285 Are_mergeable_2(const Traits* traits) : m_traits(traits) {} 286 287 friend class Arr_non_caching_segment_traits_2<Kernel>; 288 289 public: 290 /*! Check whether it is possible to merge two given x-monotone curves. 291 * \param cv1 The first curve. 292 * \param cv2 The second curve. 293 * \return (true) if the two curves are mergeable, that is, if they are 294 * supported by the same line; (false) otherwise. 295 * \pre cv1 and cv2 share a common endpoint. 296 */ operator()297 bool operator()(const X_monotone_curve_2& cv1, 298 const X_monotone_curve_2& cv2) const 299 { 300 const Base* base = m_traits; 301 Equal_2 equal = base->equal_2_object(); 302 Construct_min_vertex_2 min_vertex = base->construct_min_vertex_2_object(); 303 Construct_max_vertex_2 max_vertex = base->construct_max_vertex_2_object(); 304 if (! equal(max_vertex(cv1), min_vertex(cv2)) && 305 ! equal(max_vertex(cv2), min_vertex(cv1))) 306 return false; 307 308 // Check if the two curves have the same supporting line. 309 return (base->compare_slope_2_object()(cv1, cv2) == EQUAL); 310 } 311 }; 312 313 /*! Obtain an Are_mergeable_2 functor object */ are_mergeable_2_object()314 Are_mergeable_2 are_mergeable_2_object() const 315 { return Are_mergeable_2(this); } 316 317 /*! \class Merge_2 318 * A functor that merges two x-monotone arcs into one. 319 */ 320 class Merge_2 { 321 protected: 322 typedef Arr_non_caching_segment_traits_2<Kernel> Traits; 323 324 /*! The traits (in case it has state) */ 325 const Traits* m_traits; 326 327 /*! Constructor 328 * \param traits the traits (in case it has state) 329 */ Merge_2(const Traits * traits)330 Merge_2(const Traits* traits) : m_traits(traits) {} 331 332 friend class Arr_non_caching_segment_traits_2<Kernel>; 333 334 public: 335 /*! Merge two given segments into a single segment. 336 * \param cv1 The first curve. 337 * \param cv2 The second curve. 338 * \param c Output: The merged curve. 339 * \pre The two curves are mergeable. 340 */ operator()341 void operator()(const X_monotone_curve_2& cv1, 342 const X_monotone_curve_2& cv2, 343 X_monotone_curve_2& c) const 344 { 345 CGAL_precondition(m_traits->are_mergeable_2_object()(cv2, cv1)); 346 347 const Base* base = m_traits; 348 Equal_2 equal = base->equal_2_object(); 349 Construct_min_vertex_2 min_vertex = base->construct_min_vertex_2_object(); 350 Construct_max_vertex_2 max_vertex = base->construct_max_vertex_2_object(); 351 352 // Check which curve extends to the right of the other. 353 const Point_2& left1 = min_vertex(cv1); 354 const Point_2& right1 = max_vertex(cv1); 355 const Point_2& left2 = min_vertex(cv2); 356 const Point_2& right2 = max_vertex(cv2); 357 358 if (equal(right1, left2)) { 359 // cv2 extends cv1 to the right. 360 c = base->construct_segment_2_object()(left1, right2); 361 return; 362 } 363 // cv1 extends cv2 to the right. 364 CGAL_precondition(equal(right2, left1)); 365 366 c = base->construct_segment_2_object()(left2, right1); 367 } 368 }; 369 370 /*! Obtain a Merge_2 functor object */ merge_2_object()371 Merge_2 merge_2_object() const { return Merge_2(this); } 372 //@} 373 374 //! \name Functor definitions for the Boolean set-operations. 375 //@{ 376 typedef typename Kernel::Construct_opposite_segment_2 Construct_opposite_2; 377 378 /*! Obtain a Construct_opposite_2 functor object */ construct_opposite_2_object()379 Construct_opposite_2 construct_opposite_2_object() const 380 { return Construct_opposite_2(); } 381 382 class Compare_endpoints_xy_2 { 383 public: 384 /*! 385 * Compare the two endpoints of a given curve lexigoraphically. 386 * \param cv The curve. 387 * \return SMALLER if cv is directed from left to right and LARGER 388 * otherwise. 389 */ operator()390 Comparison_result operator()(const X_monotone_curve_2& cv) const 391 { 392 typedef typename Kernel::Construct_vertex_2 Construct_vertex_2; 393 394 Kernel k; 395 Base b; 396 Construct_vertex_2 ctr_v = k.construct_vertex_2_object(); 397 Compare_xy_2 cmp_xy = b.compare_xy_2_object(); 398 return(cmp_xy(ctr_v(cv,0), ctr_v(cv,1))); 399 } 400 }; 401 402 /*! Obtain a Compare_endpoints_xy_2 functor object */ compare_endpoints_xy_2_object()403 Compare_endpoints_xy_2 compare_endpoints_xy_2_object() const 404 { return Compare_endpoints_xy_2(); } 405 //@} 406 }; 407 408 } //namespace CGAL 409 410 #include <CGAL/enable_warnings.h> 411 412 #endif 413