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