1 // Copyright (c) 2003,2004 INRIA Sophia-Antipolis (France). 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/Apollonius_graph_2/include/CGAL/Apollonius_graph_hierarchy_2.h $ 7 // $Id: Apollonius_graph_hierarchy_2.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Menelaos Karavelas <mkaravel@iacm.forth.gr> 12 13 #ifndef CGAL_APOLLONIUS_GRAPH_HIERARCHY_2_H 14 #define CGAL_APOLLONIUS_GRAPH_HIERARCHY_2_H 15 16 #include <CGAL/license/Apollonius_graph_2.h> 17 18 19 #include <map> 20 21 #include <boost/random/linear_congruential.hpp> 22 #include <boost/random/geometric_distribution.hpp> 23 #include <boost/random/variate_generator.hpp> 24 25 #include <CGAL/Apollonius_graph_2.h> 26 #include <CGAL/Triangulation_data_structure_2.h> 27 #include <CGAL/Apollonius_graph_vertex_base_2.h> 28 #include <CGAL/Triangulation_face_base_2.h> 29 #include <CGAL/Apollonius_graph_hierarchy_vertex_base_2.h> 30 31 #include <CGAL/Apollonius_graph_2/Traits_wrapper_2.h> 32 33 namespace CGAL { 34 35 36 // parameterization of the hierarchy 37 const unsigned int ag_hierarchy_2__ratio = 30; 38 const unsigned int ag_hierarchy_2__minsize = 20; 39 const unsigned int ag_hierarchy_2__maxlevel = 5; 40 // maximal number of points is 30^5 = 24 millions ! 41 42 template < class Gt, 43 class Agds = Triangulation_data_structure_2< 44 Apollonius_graph_hierarchy_vertex_base_2< 45 Apollonius_graph_vertex_base_2<Gt,true> >, 46 Triangulation_face_base_2<Gt> >, 47 class LTag = Tag_false > 48 class Apollonius_graph_hierarchy_2 49 : public Apollonius_graph_2< Gt, Agds, LTag > 50 { 51 private: 52 typedef Apollonius_graph_2<Gt,Agds,LTag> Apollonius_graph_base; 53 typedef Apollonius_graph_base Ag_base; 54 55 public: 56 typedef Gt Geom_traits; 57 typedef typename Gt::Site_2 Site_2; 58 typedef typename Gt::Point_2 Point_2; 59 60 typedef typename Ag_base::Vertex_handle Vertex_handle; 61 typedef typename Ag_base::Face_handle Face_handle; 62 typedef typename Ag_base::Edge Edge; 63 64 typedef typename Ag_base::Face_circulator Face_circulator; 65 typedef typename Ag_base::Edge_circulator Edge_circulator; 66 typedef typename Ag_base::Vertex_circulator Vertex_circulator; 67 68 typedef typename Ag_base::All_faces_iterator All_faces_iterator; 69 typedef typename Ag_base::Finite_faces_iterator Finite_faces_iterator; 70 71 typedef typename Ag_base::All_vertices_iterator All_vertices_iterator; 72 typedef typename Ag_base::Finite_vertices_iterator 73 Finite_vertices_iterator; 74 75 typedef typename Ag_base::All_edges_iterator All_edges_iterator; 76 typedef typename Ag_base::Finite_edges_iterator Finite_edges_iterator; 77 78 typedef typename Ag_base::Sites_iterator Sites_iterator; 79 typedef typename Ag_base::Visible_sites_iterator Visible_sites_iterator; 80 typedef typename Ag_base::Hidden_sites_iterator Hidden_sites_iterator; 81 82 typedef typename Ag_base::size_type size_type; 83 84 using Ag_base::insert_first; 85 using Ag_base::insert_second; 86 using Ag_base::insert_third; 87 using Ag_base::is_hidden; 88 using Ag_base::incircle; 89 using Ag_base::edge_interior; 90 using Ag_base::insert_degree_2; 91 using Ag_base::initialize_conflict_region; 92 using Ag_base::expand_conflict_region; 93 using Ag_base::retriangulate_conflict_region; 94 using Ag_base::is_infinite; 95 96 public: 97 // CREATION 98 //--------- 99 Apollonius_graph_hierarchy_2 100 (const Geom_traits& gt = Geom_traits()); 101 102 template<class Input_iterator> 103 Apollonius_graph_hierarchy_2(Input_iterator first, 104 Input_iterator beyond, 105 const Geom_traits& gt = Geom_traits()) Apollonius_graph_base(gt)106 : Apollonius_graph_base(gt) 107 { 108 init_hierarchy(gt); 109 insert(first, beyond); 110 } 111 112 Apollonius_graph_hierarchy_2 113 (const Apollonius_graph_hierarchy_2& agh); 114 115 Apollonius_graph_hierarchy_2& 116 operator=(const Apollonius_graph_hierarchy_2& agh); 117 118 ~Apollonius_graph_hierarchy_2(); 119 120 protected: 121 // used to initialize the hierarchy at construction time 122 void init_hierarchy(const Geom_traits& gt); 123 124 public: 125 // INSERTION 126 //---------- 127 template < class Input_iterator > insert(Input_iterator first,Input_iterator beyond)128 size_type insert(Input_iterator first, Input_iterator beyond) 129 { 130 // copy the sites to a local container 131 typename Apollonius_graph_base::Site_list wp_list; 132 // Site_list wp_list; 133 for (Input_iterator it = first; it != beyond; ++it) { 134 wp_list.push_back(*it); 135 } 136 137 // sort by decreasing weight 138 typename Apollonius_graph_base::Site_less_than_comparator 139 less_than(this->geom_traits()); 140 std::sort(wp_list.begin(), wp_list.end(), less_than); 141 142 // now insert 143 typename Apollonius_graph_base::Site_list_iterator lit; 144 for (lit = wp_list.begin(); lit != wp_list.end(); ++lit) { 145 insert(*lit); 146 } 147 148 149 // store how many sites where in the range 150 std::size_t num = wp_list.size(); 151 152 // clear the local container 153 wp_list.clear(); 154 155 // return the number of sites in range 156 return num; 157 } 158 159 Vertex_handle insert(const Site_2& p); insert(const Site_2 & p,Vertex_handle vnear)160 Vertex_handle insert(const Site_2& p, 161 Vertex_handle vnear) { 162 // the following statement has been added in order to avoid 163 // a g++3.2.1_FreeBSD-RELEASE warning 164 vnear = Vertex_handle(); 165 return insert(p); 166 } 167 168 public: 169 // REMOVAL 170 //-------- 171 void remove(Vertex_handle v); 172 173 public: 174 // NEAREST NEIGHBOR LOCATION 175 //-------------------------- 176 public: 177 Vertex_handle nearest_neighbor(const Point_2& p) const; nearest_neighbor(const Point_2 & p,Vertex_handle)178 inline Vertex_handle nearest_neighbor(const Point_2& p, 179 Vertex_handle /* vnear */) const { 180 return nearest_neighbor(p); 181 } 182 183 public: 184 // VALIDITY CHECK 185 //--------------- 186 bool is_valid(bool verbose = false, int level = 1) const; 187 188 public: 189 // MISCELLANEOUS 190 //-------------- 191 void clear(); 192 void swap(Apollonius_graph_hierarchy_2& agh); 193 194 // I/O 195 //---- 196 void file_input(std::istream& is); 197 void file_output(std::ostream& os) const; 198 199 private: 200 // private methods 201 void 202 nearest_neighbor(const Point_2& p, 203 Vertex_handle vnear[ag_hierarchy_2__maxlevel]) const; 204 205 int random_level(); 206 207 void copy(const Apollonius_graph_hierarchy_2 &agh); 208 209 private: 210 // class variables 211 // here is the stack of graphs which form the hierarchy 212 Apollonius_graph_base* hierarchy[ag_hierarchy_2__maxlevel]; 213 boost::rand48 random; // random generator 214 215 public: 216 template<class OutputItFaces, class OutputItBoundaryEdges, 217 class OutputItHiddenVertices> 218 boost::tuples::tuple<OutputItFaces, OutputItBoundaryEdges, 219 OutputItHiddenVertices> 220 get_conflicts_and_boundary_and_hidden_vertices(const Site_2& p, 221 OutputItFaces fit, 222 OutputItBoundaryEdges eit, 223 OutputItHiddenVertices vit, 224 Vertex_handle start = 225 Vertex_handle()) const 226 { 227 Vertex_handle vnearest = nearest_neighbor(p.point(), start); 228 return this->get_all(p, fit, eit, vit, vnearest, false); 229 } 230 231 template<class OutputItFaces, class OutputItBoundaryEdges> 232 std::pair<OutputItFaces, OutputItBoundaryEdges> 233 get_conflicts_and_boundary(const Site_2& p, 234 OutputItFaces fit, 235 OutputItBoundaryEdges eit, 236 Vertex_handle start = 237 Vertex_handle()) const { 238 boost::tuples::tuple<OutputItFaces,OutputItBoundaryEdges,Emptyset_iterator> 239 tup = 240 get_conflicts_and_boundary_and_hidden_vertices(p, 241 fit, 242 eit, 243 Emptyset_iterator(), 244 start); 245 return std::make_pair( boost::tuples::get<0>(tup), 246 boost::tuples::get<1>(tup) ); 247 } 248 249 250 template<class OutputItBoundaryEdges, class OutputItHiddenVertices> 251 std::pair<OutputItBoundaryEdges, OutputItHiddenVertices> 252 get_boundary_of_conflicts_and_hidden_vertices(const Site_2& p, 253 OutputItBoundaryEdges eit, 254 OutputItHiddenVertices vit, 255 Vertex_handle start = 256 Vertex_handle()) const { 257 boost::tuples::tuple<Emptyset_iterator,OutputItBoundaryEdges, 258 OutputItHiddenVertices> 259 tup = 260 get_conflicts_and_boundary_and_hidden_vertices(p, 261 Emptyset_iterator(), 262 eit, 263 vit, 264 start); 265 return std::make_pair( boost::tuples::get<1>(tup), 266 boost::tuples::get<2>(tup) ); 267 } 268 269 270 template<class OutputItFaces, class OutputItHiddenVertices> 271 std::pair<OutputItFaces, OutputItHiddenVertices> 272 get_conflicts_and_hidden_vertices(const Site_2& p, 273 OutputItFaces fit, 274 OutputItHiddenVertices vit, 275 Vertex_handle start = 276 Vertex_handle()) const { 277 boost::tuples::tuple<OutputItFaces,Emptyset_iterator, 278 OutputItHiddenVertices> 279 tup = 280 get_conflicts_and_boundary_and_hidden_vertices(p, 281 fit, 282 Emptyset_iterator(), 283 vit, 284 start); 285 return std::make_pair( boost::tuples::get<0>(tup), 286 boost::tuples::get<2>(tup) ); 287 } 288 289 template<class OutputItFaces> 290 OutputItFaces get_conflicts(const Site_2& p, 291 OutputItFaces fit, 292 Vertex_handle start = Vertex_handle()) const { 293 boost::tuples::tuple<OutputItFaces,Emptyset_iterator,Emptyset_iterator> 294 tup = 295 get_conflicts_and_boundary_and_hidden_vertices(p, 296 fit, 297 Emptyset_iterator(), 298 Emptyset_iterator(), 299 start); 300 return boost::tuples::get<0>(tup); 301 } 302 303 template<class OutputItBoundaryEdges> 304 OutputItBoundaryEdges 305 get_boundary_of_conflicts(const Site_2& p, 306 OutputItBoundaryEdges eit, 307 Vertex_handle start = Vertex_handle()) const { 308 boost::tuples::tuple<Emptyset_iterator,OutputItBoundaryEdges, 309 Emptyset_iterator> 310 tup = 311 get_conflicts_and_boundary_and_hidden_vertices(p, 312 Emptyset_iterator(), 313 eit, 314 Emptyset_iterator(), 315 start); 316 return boost::tuples::get<1>(tup); 317 } 318 319 template<class OutputItHiddenVertices> 320 OutputItHiddenVertices 321 get_hidden_vertices(const Site_2& p, 322 OutputItHiddenVertices vit, 323 Vertex_handle start = Vertex_handle()) const { 324 boost::tuples::tuple<Emptyset_iterator,Emptyset_iterator, 325 OutputItHiddenVertices> 326 tup = 327 get_conflicts_and_boundary_and_hidden_vertices(p, 328 Emptyset_iterator(), 329 Emptyset_iterator(), 330 vit, 331 start); 332 return boost::tuples::get<2>(tup); 333 } 334 }; 335 336 337 template<class Gt, class Agds, class LTag> 338 std::ostream& operator<<(std::ostream& os, 339 const Apollonius_graph_hierarchy_2<Gt,Agds,LTag>& agh) 340 { 341 agh.file_output(os); 342 return os; 343 } 344 345 template<class Gt, class Agds, class LTag> 346 std::istream& operator>>(std::istream& is, 347 Apollonius_graph_hierarchy_2<Gt,Agds,LTag>& agh) 348 { 349 agh.file_input(is); 350 return is; 351 } 352 353 } //namespace CGAL 354 355 356 #include <CGAL/Apollonius_graph_2/Apollonius_graph_hierarchy_2_impl.h> 357 358 359 #endif // CGAL_APOLLONIUS_GRAPH_HIERARCHY_2_H 360