1 // Copyright (c) 2005  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/Boolean_set_operations_2/include/CGAL/Boolean_set_operations_2/Gps_agg_op_visitor.h $
7 // $Id: Gps_agg_op_visitor.h 254d60f 2019-10-19T15:23:19+02:00 Sébastien Loriot
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 //                 Ron Wein        <wein@post.tau.ac.il>
13 
14 #ifndef CGAL_BSO_2_GSP_AGG_OP_VISITOR_H
15 #define CGAL_BSO_2_GSP_AGG_OP_VISITOR_H
16 
17 #include <CGAL/license/Boolean_set_operations_2.h>
18 
19 #include <CGAL/Unique_hash_map.h>
20 #include <CGAL/Surface_sweep_2/Arr_construction_ss_visitor.h>
21 #include <CGAL/Arr_tags.h>
22 #include <CGAL/Arr_topology_traits/Arr_bounded_planar_construction_helper.h>
23 #include <CGAL/Arr_topology_traits/Arr_unb_planar_construction_helper.h>
24 #include <CGAL/Default.h>
25 
26 namespace CGAL {
27 
28 template <typename Helper_, typename Arrangement_, typename Visitor_ = Default>
29 class Gps_agg_op_base_visitor :
30   public Arr_construction_ss_visitor<
31     Helper_,
32     typename Default::Get<Visitor_, Gps_agg_op_base_visitor<Helper_,
33                                                             Arrangement_,
34                                                             Visitor_> >::type>
35 {
36 public:
37   typedef Helper_                                       Helper;
38   typedef Arrangement_                                  Arrangement_2;
39 
40   typedef typename Helper::Geometry_traits_2            Geometry_traits_2;
41   typedef typename Helper::Event                        Event;
42   typedef typename Helper::Subcurve                     Subcurve;
43 
44 private:
45   typedef Geometry_traits_2                             Gt2;
46   typedef Arrangement_2                                 Arr;
47 
48   typedef Gps_agg_op_base_visitor<Helper, Arr, Visitor_>
49                                                         Self;
50   typedef typename Default::Get<Visitor_, Self>::type   Visitor;
51   typedef Arr_construction_ss_visitor<Helper, Visitor>  Base;
52 
53 public:
54   typedef typename Arr::Halfedge_handle                 Halfedge_handle;
55   typedef typename Arr::Vertex_handle                   Vertex_handle;
56   typedef typename Gt2::X_monotone_curve_2              X_monotone_curve_2;
57   typedef typename Gt2::Point_2                         Point_2;
58 
59   typedef Unique_hash_map<Halfedge_handle, unsigned int>
60                                                         Edges_hash;
61 
62 protected:
63   Edges_hash* m_edges_hash; // maps halfedges to their BC (coundary counter)
64 
65 public:
Gps_agg_op_base_visitor(Arr * arr,Edges_hash * hash)66   Gps_agg_op_base_visitor(Arr* arr, Edges_hash* hash) :
67     Base(arr),
68     m_edges_hash(hash)
69   {}
70 
71   // TODO (IMPORTANT): unbounded helper might be not fully supported
72   // TODO add mpl-warning
73 
insert_in_face_interior(const X_monotone_curve_2 & cv,Subcurve * sc)74   virtual Halfedge_handle insert_in_face_interior(const X_monotone_curve_2& cv,
75                                                   Subcurve* sc)
76   {
77     Halfedge_handle he = Base::insert_in_face_interior(cv, sc);
78     insert_edge_to_hash(he, cv);
79     return he;
80   }
81 
insert_at_vertices(const X_monotone_curve_2 & cv,Halfedge_handle hhandle,Halfedge_handle prev,Subcurve * sc,bool & new_face_created)82   virtual Halfedge_handle insert_at_vertices(const X_monotone_curve_2& cv,
83                                              Halfedge_handle hhandle,
84                                              Halfedge_handle prev,
85                                              Subcurve* sc,
86                                              bool& new_face_created)
87   {
88     Halfedge_handle res_he =
89       Base::insert_at_vertices(cv, hhandle, prev, sc, new_face_created);
90     insert_edge_to_hash(res_he, cv);
91     return res_he;
92   }
93 
insert_from_right_vertex(const X_monotone_curve_2 & cv,Halfedge_handle he,Subcurve * sc)94   virtual Halfedge_handle insert_from_right_vertex(const X_monotone_curve_2& cv,
95                                                    Halfedge_handle he,
96                                                    Subcurve* sc)
97   {
98     Halfedge_handle res_he = Base::insert_from_right_vertex(cv, he, sc);
99     insert_edge_to_hash(res_he, cv);
100     return res_he;
101   }
102 
insert_from_left_vertex(const X_monotone_curve_2 & cv,Halfedge_handle he,Subcurve * sc)103   virtual Halfedge_handle insert_from_left_vertex(const X_monotone_curve_2& cv,
104                                                   Halfedge_handle he,
105                                                   Subcurve* sc)
106   {
107     Halfedge_handle res_he = Base::insert_from_left_vertex(cv, he, sc);
108     insert_edge_to_hash(res_he, cv);
109     return res_he;
110   }
111 
112 private:
insert_edge_to_hash(Halfedge_handle he,const X_monotone_curve_2 & cv)113   void insert_edge_to_hash(Halfedge_handle he, const X_monotone_curve_2& cv)
114   {
115     const Comparison_result he_dir =
116       ((Arr_halfedge_direction)he->direction() == ARR_LEFT_TO_RIGHT) ?
117       SMALLER : LARGER;
118 
119     const Comparison_result cv_dir =
120       this->m_arr_access.arrangement().geometry_traits()->
121             compare_endpoints_xy_2_object()(cv);
122 
123     if (he_dir == cv_dir) {
124       (*m_edges_hash)[he] = cv.data().bc();
125       (*m_edges_hash)[he->twin()] = cv.data().twin_bc();
126     }
127     else {
128       (*m_edges_hash)[he] = cv.data().twin_bc();
129       (*m_edges_hash)[he->twin()] = cv.data().bc();
130     }
131   }
132 };
133 
134 template <typename Helper_, typename Arrangement_, typename Visitor_ = Default>
135 class Gps_agg_op_visitor :
136   public Gps_agg_op_base_visitor<Helper_, Arrangement_,
137                                  Gps_agg_op_visitor<Helper_, Arrangement_,
138                                                     Visitor_> >
139 {
140 public:
141   typedef Helper_                                       Helper;
142   typedef Arrangement_                                  Arrangement_2;
143 
144   typedef typename Helper::Geometry_traits_2            Geometry_traits_2;
145   typedef typename Helper::Event                        Event;
146   typedef typename Helper::Subcurve                     Subcurve;
147 
148 private:
149   typedef Geometry_traits_2                             Gt2;
150   typedef Arrangement_2                                 Arr;
151 
152   typedef Gps_agg_op_visitor<Helper, Arr, Visitor_>     Self;
153   typedef typename Default::Get<Visitor_, Self>::type   Visitor;
154   typedef Gps_agg_op_base_visitor<Helper, Arr, Visitor> Base;
155 
156 public:
157   typedef typename Base::Halfedge_handle                Halfedge_handle;
158   typedef typename Base::Vertex_handle                  Vertex_handle;
159   typedef typename Gt2::X_monotone_curve_2              X_monotone_curve_2;
160   typedef typename Gt2::Point_2                         Point_2;
161 
162 protected:
163   unsigned int m_event_count;                   // The number of events so far.
164   std::vector<Vertex_handle>* m_vertices_vec;   // The vertices, sorted in
165                                                 // ascending order.
166 
167 public:
Gps_agg_op_visitor(Arr * arr,typename Base::Edges_hash * hash,std::vector<Vertex_handle> * vertices_vec)168   Gps_agg_op_visitor(Arr* arr, typename Base::Edges_hash* hash,
169                      std::vector<Vertex_handle>* vertices_vec) :
170     Base(arr, hash),
171     m_event_count(0),
172     m_vertices_vec(vertices_vec)
173   {}
174 
before_handle_event(Event * event)175   void before_handle_event(Event* event)
176   {
177     event->set_index(m_event_count);
178     m_event_count++;
179   }
180 
181   virtual Halfedge_handle
insert_in_face_interior(const X_monotone_curve_2 & cv,Subcurve * sc)182   insert_in_face_interior(const X_monotone_curve_2& cv, Subcurve* sc)
183   {
184     Halfedge_handle res_he = Base::insert_in_face_interior(cv, sc);
185 
186     // We now have a halfedge whose source vertex is associated with the
187     // last event and whose target vertex is associated with the current event:
188     Event* curr_event = this->current_event();
189     Event* last_event = (sc)->last_event();
190 
191     CGAL_assertion((Arr_halfedge_direction)res_he->direction() ==
192                     ARR_LEFT_TO_RIGHT);
193     _insert_vertex(curr_event, res_he->target());
194     _insert_vertex(last_event, res_he->source());
195 
196     return res_he;
197   }
198 
insert_from_right_vertex(const X_monotone_curve_2 & cv,Halfedge_handle he,Subcurve * sc)199   virtual Halfedge_handle insert_from_right_vertex(const X_monotone_curve_2& cv,
200                                                    Halfedge_handle he,
201                                                    Subcurve* sc)
202   {
203     Halfedge_handle res_he = Base::insert_from_right_vertex(cv, he, sc);
204 
205     // We now have a halfedge whose target vertex is associated with the
206     // last event (we have already dealt with its source vertex).
207     Event* last_event = (sc)->last_event();
208     CGAL_assertion((Arr_halfedge_direction)res_he->direction() ==
209                     ARR_RIGHT_TO_LEFT);
210     _insert_vertex(last_event, res_he->target());
211     return res_he;
212   }
213 
insert_from_left_vertex(const X_monotone_curve_2 & cv,Halfedge_handle he,Subcurve * sc)214   virtual Halfedge_handle insert_from_left_vertex(const X_monotone_curve_2& cv,
215                                                   Halfedge_handle he,
216                                                   Subcurve* sc)
217   {
218     Halfedge_handle  res_he = Base::insert_from_left_vertex(cv, he, sc);
219 
220     // We now have a halfedge whose target vertex is associated with the
221     // current event(we have already dealt with its source vertex).
222     Event* curr_event = this->current_event();
223 
224     CGAL_assertion((Arr_halfedge_direction)res_he->direction() ==
225                     ARR_LEFT_TO_RIGHT);
226     _insert_vertex (curr_event, res_he->target());
227     return res_he;
228   }
229 
230 private:
_insert_vertex(const Event * event,Vertex_handle v)231   void _insert_vertex(const Event* event, Vertex_handle v)
232   {
233     const unsigned int index = event->index();
234     if (index >= m_vertices_vec->size()) m_vertices_vec->resize(2 * (index + 1));
235     (*m_vertices_vec)[index] = v;
236   }
237 
238 };
239 
240 } // namespace CGAL
241 
242 #endif
243