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