1 // Copyright (c) 2000 Max-Planck-Institute Saarbruecken (Germany). 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/Partition_2/include/CGAL/Partition_2/Vertex_visibility_graph_2.h $ 7 // $Id: Vertex_visibility_graph_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) : Susan Hert <hert@mpi-sb.mpg.de> 12 13 /* 14 Provides an implementation of the algorithm of Overmars and Welzl 15 for computing the visibility graph of a set of non-intersecting 16 line segments in the plane. 17 18 @inproceedings{ow-nmcvg-88 19 , author = "M. H. Overmars and Emo Welzl" 20 , title = "New methods for computing visibility graphs" 21 , booktitle = "Proc. 4th Annu. ACM Sympos. Comput. Geom." 22 , year = 1988 23 , pages = "164--171" 24 } 25 26 The running time is $O(n^2)$ with linear space requirements. 27 28 The algorithm implemented uses a sweep-line technique to construct the 29 visibility graph. The sweep data structure is a rotation tree, implemented 30 in the class CGAL::Rotation_tree_2. 31 32 A direction vector $d$ is swept from $-\pi/2$ to $\pi/2$, 33 and the sweep data structure, and whenever the direction of this vector 34 coincides with the slope of an edge in the rotation tree, the tree $G$ 35 is updated and edges of the visibility graph are reported. To accomplish 36 the updates, it is necessary to keep track of all the leaves that are 37 leftmost children of their parents. In particular, one needs to know the 38 rightmost of these leftmost children. 39 40 Two data structures are needed for the implementation of the algorithm: 41 the sweep data structure $G$, and a stack $S$ that contains all the 42 leaves in $G$ that are the leftmost children of their parents. 43 44 TODO: 45 --is_valid function is not complete 46 --??? would a list of list of sorted vertices be a better representation? 47 48 */ 49 50 #ifndef CGAL_VERTEX_VISIBILITY_GRAPH_2_H 51 #define CGAL_VERTEX_VISIBILITY_GRAPH_2_H 52 53 #include <CGAL/license/Partition_2.h> 54 55 #include <CGAL/Partition_2/Rotation_tree_2.h> 56 #include <CGAL/Partition_2/Indirect_less_xy_2.h> 57 #include <CGAL/Partition_2/Iterator_list.h> 58 #include <CGAL/Partition_2/Turn_reverser.h> 59 #include <CGAL/Partition_2/Point_pair_less_xy_2.h> 60 #include <CGAL/Partition_2/Segment_less_yx_2.h> 61 #include <cmath> 62 #include <list> 63 #include <stack> 64 #include <vector> 65 #include <set> 66 #include <map> 67 #include <iostream> 68 69 namespace CGAL { 70 71 template <class Traits> 72 class Vertex_visibility_graph_2 73 { 74 private: 75 typedef Vertex_visibility_graph_2<Traits> Self; 76 typedef typename Traits::Point_2 Point_2; 77 typedef typename Traits::Left_turn_2 Left_turn_2; 78 typedef typename Traits::Less_xy_2 Less_xy_2; 79 typedef typename Traits::Orientation_2 Orientation_2; 80 typedef typename Traits::Collinear_are_ordered_along_line_2 81 Collinear_are_ordered_along_line_2; 82 typedef typename Traits::Are_strictly_ordered_along_line_2 83 Are_strictly_ordered_along_line_2; 84 typedef CGAL::Segment_less_yx_2<Traits> Segment_less_yx_2; 85 86 typedef Rotation_tree_2<Traits> Tree; 87 typedef typename Tree::iterator Tree_iterator; 88 89 typedef std::list< Point_2 > Polygon; 90 typedef typename Polygon::const_iterator Polygon_const_iterator; 91 typedef typename Polygon::iterator Polygon_iterator; 92 93 // the edge set is simply a set of point pairs. 94 typedef std::pair<Point_2, Point_2> Point_pair; 95 typedef Point_pair_less_xy_2<Traits> Point_pair_compare; 96 typedef std::set< Point_pair, Point_pair_compare > Edge_set; 97 98 // this map associates with each point (vertex), the iterator in the 99 // original list that it originated from and its current visibility 100 // point iterator. 101 typedef std::pair<Polygon_const_iterator, Polygon_const_iterator> 102 Iterator_pair; 103 typedef std::map<Point_2, Iterator_pair, Less_xy_2> Vertex_map; 104 typedef typename Vertex_map::iterator Vertex_map_iterator; 105 106 public: 107 typedef typename Edge_set::iterator iterator; 108 typedef typename Edge_set::const_iterator const_iterator; 109 Vertex_visibility_graph_2()110 Vertex_visibility_graph_2() {} 111 112 // 113 // first and beyond should be iterators over vertices of a polygon 114 // 115 template <class ForwardIterator> Vertex_visibility_graph_2(ForwardIterator first,ForwardIterator beyond,const Traits & traits)116 Vertex_visibility_graph_2(ForwardIterator first, ForwardIterator beyond, const Traits& traits): 117 left_turn_2(traits.left_turn_2_object()), 118 orientation_2(traits.orientation_2_object()), 119 collinear_ordered_2(traits.collinear_are_ordered_along_line_2_object()), 120 are_strictly_ordered_along_line_2( 121 traits.are_strictly_ordered_along_line_2_object()), 122 less_xy_2(traits.less_xy_2_object()), 123 edges(Point_pair_compare(traits)) 124 { 125 build(first, beyond, traits); 126 } 127 128 // Pre: ccw order of points; no repeated points 129 template <class ForwardIterator> build(ForwardIterator first,ForwardIterator beyond,const Traits & traits)130 void build(ForwardIterator first, ForwardIterator beyond, const Traits& traits) 131 { 132 Polygon polygon(first,beyond); 133 Tree tree(polygon.begin(), polygon.end(),traits); 134 135 Vertex_map vertex_map(less_xy_2); 136 initialize_vertex_map(polygon, vertex_map, traits); 137 138 // NOTE: use the std::list as the basis here because otherwise the basis 139 // is a deque, which is buggy under MSVC++ 140 std::stack<Tree_iterator, std::list<Tree_iterator> > stack; 141 // push on p_0, the rightmost point 142 stack.push(tree.rightmost_point_ref()); 143 144 Tree_iterator p, p_r, q; 145 Tree_iterator z; 146 147 while (!stack.empty()) 148 { 149 p = stack.top(); 150 #ifdef CGAL_VISIBILITY_GRAPH_DEBUG 151 if (p != tree.end()) 152 std::cout << "p = " << *p << std::endl; 153 else 154 std::cout << "p == nullptr" << std::endl; 155 #endif 156 stack.pop(); 157 p_r = tree.right_sibling(p); 158 #ifdef CGAL_VISIBILITY_GRAPH_DEBUG 159 if (p_r != tree.end()) 160 std::cout << "p_r = " << *p_r << std::endl; 161 else 162 std::cout << "p_r == nullptr" << std::endl; 163 #endif 164 q = tree.parent(p); 165 #ifdef CGAL_VISIBILITY_GRAPH_DEBUG 166 if (q != tree.end()) 167 std::cout << "q = " << *q << std::endl; 168 else 169 std::cout << "q == nullptr" << std::endl; 170 #endif 171 if (!tree.parent_is_p_minus_infinity(p)) 172 { 173 #ifdef CGAL_VISIBILITY_GRAPH_DEBUG 174 std::cout << "q is not p_minus_infinity" << std::endl; 175 #endif 176 handle(p,q,polygon,vertex_map); 177 } 178 z = tree.left_sibling(q); 179 #ifdef CGAL_VISIBILITY_GRAPH_DEBUG 180 if (z != tree.end()) 181 std::cout << "z = " << *z << std::endl; 182 else 183 std::cout << "z == nullptr" << std::endl; 184 std::cout << "erasing " << *p << " from tree " << std::endl; 185 #endif 186 tree.erase(p); 187 if ((z == tree.end()) || !left_turn_to_parent(p,z,tree)) 188 { 189 #ifdef CGAL_VISIBILITY_GRAPH_DEBUG 190 std::cout << "making " << *p << " the left sibling of " << *q 191 << std::endl; 192 #endif 193 tree.set_left_sibling(p,q); 194 } 195 else 196 { 197 // NOTE: no need to check here if z is p_infinity since you are 198 // moving DOWN the tree instead of up and p_infinity is at the root 199 Turn_reverser<Point_2, Left_turn_2> right_turn(left_turn_2); 200 201 while ((tree.rightmost_child(z) != tree.end()) && 202 !right_turn(*p,*tree.rightmost_child(z),*z)) 203 { 204 z = tree.rightmost_child(z); 205 #ifdef CGAL_VISIBILITY_GRAPH_DEBUG 206 std::cout << " z = " << *z << std::endl; 207 #endif 208 } 209 tree.set_rightmost_child(p,z); 210 if (!stack.empty() && z == stack.top()) 211 { 212 #ifdef CGAL_VISIBILITY_GRAPH_DEBUG 213 std::cout << "popping " << *z << " from top of stack " 214 << std::endl; 215 #endif 216 z = stack.top(); 217 stack.pop(); 218 } 219 } 220 #ifdef CGAL_VISIBILITY_GRAPH_DEBUG 221 std::cout << " p is now " << *p << std::endl; 222 #endif 223 if (tree.left_sibling(p) == tree.end() && 224 !tree.parent_is_p_infinity(p)) 225 { 226 #ifdef CGAL_VISIBILITY_GRAPH_DEBUG 227 std::cout << "pushing " << *p << std::endl; 228 #endif 229 stack.push(p); 230 } 231 if (p_r != tree.end()) stack.push(p_r); 232 } 233 // print_edge_set(edges); 234 } 235 236 clear()237 void clear() 238 { 239 edges.clear(); 240 } 241 begin()242 iterator begin() 243 { 244 return edges.begin(); 245 } 246 begin()247 const_iterator begin() const 248 { 249 return edges.begin(); 250 } 251 end()252 const_iterator end() const 253 { 254 return edges.end(); 255 } 256 end()257 iterator end() 258 { 259 return edges.end(); 260 } 261 insert_edge(const Point_pair & edge)262 void insert_edge(const Point_pair& edge) 263 { 264 if (less_xy_2(edge.first,edge.second)) 265 edges.insert(edge); 266 else 267 edges.insert(Point_pair(edge.second, edge.first)); 268 } 269 is_an_edge(const Point_pair & edge)270 bool is_an_edge(const Point_pair& edge) 271 { 272 if (less_xy_2(edge.first,edge.second)) 273 return edges.find(edge) != edges.end(); 274 else 275 return edges.find(Point_pair(edge.second, edge.first)) != edges.end(); 276 } 277 278 #if 0 279 // ??? need to finish this ??? 280 template <class ForwardIterator> 281 bool is_valid(ForwardIterator first, ForwardIterator beyond) 282 { 283 std::vector<Point_2> vertices(first, beyond); 284 bool edge_there[vertices.size()]; 285 286 // for each edge in the graph determine if it is either an edge of the 287 // polygon or, if not, if it intersects the polygon in the interior of 288 // the edge. 289 for (iterator e_it = edges.begin(); e_it != edges.end(); e_it++) 290 { 291 Segment_2 s = construct_segment_2((*e_it).first, (*e_it).second); 292 if (is_an_edge(*e_it)) 293 edge_there[edge_num] = true; 294 else if (do_intersect_in_interior(s, first, beyond)) 295 return false; 296 } 297 // check if all the edges of the polygon are present 298 // 299 // ??? how do you check if there are missing edges ??? 300 } 301 #endif 302 303 304 private: 305 print_vertex_map(const Vertex_map & vertex_map,const Polygon & polygon)306 void print_vertex_map(const Vertex_map& vertex_map, 307 const Polygon& polygon) 308 { 309 typedef typename Vertex_map::const_iterator const_iterator; 310 311 for (const_iterator it = vertex_map.begin(); it != vertex_map.end();it++) 312 { 313 if ((*it).second.second != polygon.end()) 314 std::cout << (*it).first << " sees " << *((*it).second.second) 315 << std::endl; 316 } 317 } 318 319 template<class E> print_edge_set(const E & edges)320 void print_edge_set(const E& edges) 321 { 322 typedef typename E::iterator iterator; 323 for (iterator it = edges.begin(); it != edges.end(); it++) 324 { 325 std::cout << (*it).first << " " << (*it).second << std::endl; 326 } 327 } 328 329 // want to determine, for each vertex p of the polygon, the line segment 330 // immediately below it. For vertical edges, the segment below is not the 331 // one that begins at the other endpoint of the edge. 332 void initialize_vertex_map(const Polygon& polygon, 333 Vertex_map& vertex_map, 334 const Traits& traits); 335 336 // determines if one makes a left turn going from p to q to q's parent. 337 // if q's parent is p_infinity, then a left turn is made when p's x value 338 // is less than q's x value or the x values are the same and p's y value is 339 // less than q's. 340 // if p, q, and q's parent are collinear, then one makes a "left turn" 341 // if q is between p and q's parent (since this means that p can't see 342 // q's parent and thus should not become a child of that node) 343 bool left_turn_to_parent(Tree_iterator p, Tree_iterator q, Tree& tree); 344 345 346 // returns true if q is the vertex after p is_next_to(const Polygon & polygon,Polygon_const_iterator p,Polygon_const_iterator q)347 bool is_next_to(const Polygon& polygon, Polygon_const_iterator p, 348 Polygon_const_iterator q) const 349 { 350 Polygon_const_iterator next = p; next++; 351 if (next == polygon.end()) next = polygon.begin(); 352 return (q == next); 353 } 354 355 // returns true if q is the vertex before or after p are_adjacent(const Polygon & polygon,Polygon_const_iterator p,Polygon_const_iterator q)356 bool are_adjacent(const Polygon& polygon, Polygon_const_iterator p, 357 Polygon_const_iterator q) const 358 { 359 Polygon_const_iterator next = p; next++; 360 if (next == polygon.end()) next = polygon.begin(); 361 if (q == next) return true; 362 next = q; next++; 363 if (next == polygon.end()) next = polygon.begin(); 364 if (p == next) return true; 365 return false; 366 } 367 368 // returns true if the diagonal from p to q cuts the interior angle at p 369 bool diagonal_in_interior(const Polygon& polygon, 370 Polygon_const_iterator p, 371 Polygon_const_iterator q); 372 373 374 // returns true if the looker can see the point_to_see 375 bool point_is_visible(const Polygon& polygon, 376 Polygon_const_iterator point_to_see, 377 Vertex_map_iterator looker); 378 379 void update_visibility(Vertex_map_iterator p_it, 380 Vertex_map_iterator q_it, 381 const Polygon& polygon, int are_adjacent); 382 383 void update_collinear_visibility(Vertex_map_iterator p_it, 384 Vertex_map_iterator q_it, 385 const Polygon& polygon); 386 387 // The segment between points p and q is a potential visibility edge 388 // This function determines if the edge should be added or not (based 389 // on p's current visibility point) and updates p's visibility point 390 // where appropriate 391 void handle(Tree_iterator p, Tree_iterator q, const Polygon& polygon, 392 Vertex_map& vertex_map); 393 394 private: 395 Left_turn_2 left_turn_2; 396 Orientation_2 orientation_2; 397 Collinear_are_ordered_along_line_2 collinear_ordered_2; 398 Are_strictly_ordered_along_line_2 are_strictly_ordered_along_line_2; 399 Less_xy_2 less_xy_2; 400 Edge_set edges; 401 }; 402 403 } 404 405 #include <CGAL/Partition_2/Vertex_visibility_graph_2_impl.h> 406 407 #endif // CGAL_VERTEX_VISIBILITY_GRAPH_2_H 408