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/Surface_sweep_2/Arr_insertion_traits_2.h $ 7 // $Id: Arr_insertion_traits_2.h 4158542 2020-04-01T12:31:51+03:00 Efi Fogel 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Baruch Zukerman <baruchzu@post.tau.ac.il> 12 // Efi Fogel <efif@post.tau.ac.il> 13 14 #ifndef CGAL_ARR_INSERTION_TRAITS_2_H 15 #define CGAL_ARR_INSERTION_TRAITS_2_H 16 17 #include <CGAL/license/Arrangement_on_surface_2.h> 18 19 /*! \file 20 * 21 * Defintion of the Arr_insertion_traits_2<Traits,Arrangement> class. 22 */ 23 24 #include <CGAL/Surface_sweep_2/Arr_basic_insertion_traits_2.h> 25 26 namespace CGAL { 27 28 /*! \class Arr_insertion_traits_2 29 * 30 * A meta-traits class that stores a halfedge handle with every x-monotone 31 * curve, and a vertex handle with each point. This information is used to 32 * speed up the aggregated insertion process. 33 */ 34 template <typename GeometryTraits_2, typename Arrangement_2_> 35 class Arr_insertion_traits_2 : 36 public Arr_basic_insertion_traits_2<GeometryTraits_2, Arrangement_2_> 37 { 38 public: 39 typedef GeometryTraits_2 Geometry_traits_2; 40 typedef Arrangement_2_ Arrangement_2; 41 42 private: 43 typedef Geometry_traits_2 Gt2; 44 typedef Arrangement_2 Arr2; 45 typedef Arr_basic_insertion_traits_2<Gt2, Arr2> Base; 46 47 public: 48 typedef typename Gt2::Intersect_2 Base_intersect_2; 49 typedef typename Gt2::Split_2 Base_split_2; 50 typedef typename Base::Base_x_monotone_curve_2 Base_x_monotone_curve_2; 51 typedef typename Base::X_monotone_curve_2 X_monotone_curve_2; 52 typedef typename Base::Halfedge_handle Halfedge_handle; 53 typedef typename Base::Base_point_2 Base_point_2; 54 typedef typename Base::Point_2 Point_2; 55 typedef typename Base::Multiplicity Multiplicity; 56 57 typedef typename Base::Has_left_category Has_left_category; 58 typedef typename Base::Has_do_intersect_category Has_do_intersect_category; 59 60 // should be ok, as basic_insertion (=Base) completes incomplete tags 61 typedef typename Base::Left_side_category Left_side_category; 62 typedef typename Base::Bottom_side_category Bottom_side_category; 63 typedef typename Base::Top_side_category Top_side_category; 64 typedef typename Base::Right_side_category Right_side_category; 65 66 /* Insertion is implemented as sweep-line visitor. The sweep-line algorithm 67 * never performs merging of curves. Therefore, AreMergeable_2 and 68 * Merge_2 are not needed either. 69 */ 70 typedef Tag_false Has_merge_category; 71 72 public: 73 /*! Constructor with a traits class. */ Arr_insertion_traits_2(const Gt2 & tr)74 Arr_insertion_traits_2(const Gt2& tr) : Base(tr) {} 75 76 /*! A functor that compares compares the y-coordinates of two x-monotone 77 * curves immediately to the right of their intersection point. 78 */ 79 class Intersect_2 { 80 protected: 81 //! The base operators. 82 Base_intersect_2 m_base_intersect; 83 84 /*! Constructor. 85 * The constructor is declared private to allow only the functor 86 * obtaining function, which is a member of the nesting class, 87 * constructing it. 88 */ Intersect_2(const Base_intersect_2 & base)89 Intersect_2(const Base_intersect_2& base) : m_base_intersect (base) {} 90 91 //! Allow its functor obtaining function calling the private constructor. 92 friend class Arr_insertion_traits_2<Gt2, Arrangement_2>; 93 94 public: 95 template<typename OutputIterator> operator()96 OutputIterator operator()(const X_monotone_curve_2& cv1, 97 const X_monotone_curve_2& cv2, 98 OutputIterator oi) 99 { 100 typedef std::pair<Point_2, Multiplicity> Intersection_point; 101 typedef boost::variant<Intersection_point, X_monotone_curve_2> 102 Intersection_result; 103 typedef boost::variant<Intersection_point, Base_x_monotone_curve_2> 104 Intersection_base_result; 105 106 Halfedge_handle invalid_he; 107 108 if ((cv1.halfedge_handle() != invalid_he) && 109 (cv2.halfedge_handle() != invalid_he) && 110 (cv1.halfedge_handle() != cv2.halfedge_handle())) 111 { 112 // The curves are interior-disjoint as both of them are already in 113 // the arrangement. 114 return oi; 115 } 116 117 std::vector<Intersection_base_result> xections; 118 m_base_intersect(cv1.base(), cv2.base(), std::back_inserter(xections)); 119 // convert objects that are associated with Base_x_monotone_curve_2 to 120 // X_monotone_curve_2 121 for (const auto& xection : xections) { 122 const Intersection_point* 123 p_p = boost::get<Intersection_point>(&xection); 124 if (p_p != nullptr) { 125 *oi++ = Intersection_result(xection); 126 continue; 127 } 128 const Base_x_monotone_curve_2* base_cv_p = 129 boost::get<Base_x_monotone_curve_2>(&xection); 130 CGAL_assertion(base_cv_p); 131 132 // Add halfedge handles to the resulting curve. 133 Halfedge_handle he; 134 if (cv1.halfedge_handle() != invalid_he) he = cv1.halfedge_handle(); 135 else if (cv2.halfedge_handle() != invalid_he) 136 he = cv2.halfedge_handle(); 137 X_monotone_curve_2 cv(*base_cv_p, he); 138 cv.set_overlapping(); 139 *oi++ = Intersection_result(cv); 140 } 141 xections.clear(); 142 return oi; 143 } 144 }; 145 146 /*! Obtain a Intersect_2 function object */ intersect_2_object()147 Intersect_2 intersect_2_object () const 148 { return (Intersect_2(this->m_base_traits->intersect_2_object())); } 149 150 /*! A functor that splits an arc at a point. */ 151 class Split_2 { 152 protected: 153 //! The base operator. 154 Base_split_2 m_base_split; 155 156 /*! Constructor. 157 * The constructor is declared private to allow only the functor 158 * obtaining function, which is a member of the nesting class, 159 * constructing it. 160 */ Split_2(const Base_split_2 & base)161 Split_2(const Base_split_2& base) : m_base_split (base) {} 162 163 //! Allow its functor obtaining function calling the private constructor. 164 friend class Arr_insertion_traits_2<Gt2, Arrangement_2>; 165 166 public: operator()167 void operator()(const X_monotone_curve_2& cv, const Point_2 & p, 168 X_monotone_curve_2& c1, X_monotone_curve_2& c2) 169 { 170 m_base_split(cv.base(), p.base(), c1.base(), c2.base()); 171 c1.set_halfedge_handle(cv.halfedge_handle()); 172 c2.set_halfedge_handle(cv.halfedge_handle()); 173 } 174 }; 175 176 /*! Obtain a Split_2 function object */ split_2_object()177 Split_2 split_2_object() const 178 { return (Split_2(this->m_base_traits->split_2_object())); } 179 }; 180 181 } // namespace CGAL 182 183 #endif 184