1 // Copyright (c) 2001
2 // Utrecht University (The Netherlands),
3 // ETH Zurich (Switzerland),
4 // INRIA Sophia-Antipolis (France),
5 // Max-Planck-Institute Saarbruecken (Germany),
6 // and Tel-Aviv University (Israel). All rights reserved.
7 //
8 // This file is part of CGAL (www.cgal.org)
9 //
10 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Polygon/include/CGAL/Polygon_2/Polygon_2_simplicity.h $
11 // $Id: Polygon_2_simplicity.h 6b4ba80 2021-03-31T15:58:09+02:00 Mael Rouxel-Labbé
12 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
13 //
14 //
15 // Author(s) : Geert-Jan Giezeman <geert@cs.uu.nl>
16
17 #ifndef CGAL_POLYGON_2_SIMPLICITY_H
18 #define CGAL_POLYGON_2_SIMPLICITY_H
19
20 #include <CGAL/disable_warnings.h>
21
22 #include <CGAL/enum.h>
23 #include <CGAL/Polygon_2/polygon_assertions.h>
24 #include <set>
25 #include <vector>
26 #include <algorithm>
27
28 /*
29 A polygon is called simple of no edges intersect each other, except
30 consecutive edges, which intersect in their common vertex.
31 The test for simplicity is implemented by means of a sweep line algorithm.
32 The vertical line is swept from left to right. The edges of the polygon that
33 are crossed by the sweep line are stored in a tree from bottom to top.
34
35 We discern three types of events:
36 - insertion events. When both edges of a polygon vertex extend to the right
37 we need to insert both edges in the tree. We need to search with the vertex
38 to find out between which edges the new edges are to be inserted.
39 - deletion events. When both edges extend to the left of the vertex we need
40 to remove both edges from the tree. We have to check that the vertex lies
41 between the edges above and below the removed edges.
42 - replacement event. In the other case we need to replace the edge that
43 extends to the left by the edge that extends to the right. We need to check
44 that the vertex lies between the edges above and below the current edge.
45
46 We represent the tree by a std::set. This is not a perfect fit for the
47 operations described above. In particular, the fact that we search with a
48 VERTEX, while the set contains EDGES, is not directly supported. The
49 insertion of edges is also complicated by the fact that we need to insert
50 two edges starting at the same vertex. The order in which they are inserted
51 in the tree does matter, because the edges go in separate directions.
52 Because of this the set needs a special associated comparison function.
53 Every edge has a flag 'is_in_tree', which is true for the edges in the tree
54 but false for the edges when they are inserted. The comparison function
55 treats the latter type of edge as a vertex. Another flag, is_left_to_right,
56 tells which of the two vertices to take. The problem of the coinciding
57 vertices is solved by the convention that the highest edges is always
58 inserted first. The comparison function uses this fact.
59
60 Vertex indices of the polygon play a double role. The number v can be used to
61 identify vertex v or the edge from vertex v to vertex v+1.
62
63 */
64
65 namespace CGAL {
66
67 namespace i_polygon {
68 // namespace CGAL::i_polygon is used for internal functions
69
70 typedef std::vector<int>::size_type Index_t;
71
72 struct Vertex_index {
Vertex_indexVertex_index73 Vertex_index() {}
Vertex_indexVertex_index74 explicit Vertex_index(Index_t i): m_i(i) {}
as_intVertex_index75 Index_t as_int() const {return m_i;}
76 Vertex_index operator++() {++m_i; return *this; }
77 bool operator==(const Vertex_index& other) const { return (m_i == other.m_i); }
78
79 private:
80 Index_t m_i;
81 };
82
83 struct Vertex_order {
Vertex_orderVertex_order84 explicit Vertex_order(Index_t i): m_i(i) {}
as_intVertex_order85 Index_t as_int() {return m_i;}
86 private:
87 Index_t m_i;
88 };
89
90 template <class ForwardIterator, class PolygonTraits>
91 class Vertex_data ;
92
93 template <class VertexData>
94 class Less_segments {
95 typedef VertexData Vertex_data;
96 Vertex_data *m_vertex_data;
97 bool less_than_in_tree(Vertex_index i, Vertex_index j) const;
98 public:
Less_segments(Vertex_data * vertex_data)99 Less_segments(Vertex_data *vertex_data) : m_vertex_data(vertex_data) {}
100 bool operator()(Vertex_index i, Vertex_index j) const;
101 };
102
103 // The data in Edge_data is attached to an edge when it is (about to be)
104 // inserted in the tree.
105 // Although conceptually this data belongs in the tree, it is stored with
106 // the vertices in the Vertex_data structure.
107
108 template <class LessSegments>
109 struct Edge_data {
110 typedef std::set<Vertex_index, LessSegments> Tree;
Edge_dataEdge_data111 Edge_data() : is_in_tree(false) {}
Edge_dataEdge_data112 Edge_data(typename Tree::iterator it) : tree_it(it), is_in_tree(false) {}
113 typename Tree::iterator tree_it; // The iterator of the edge in the tree.
114 // Needed for cross reference. If edge j
115 // is in the tree: *edges[j].tree_it == j
116 bool is_in_tree :1; // Must be set -after- inserting the edge
117 // in the tree. Plays a role in the
118 // comparison function of the tree.
119 bool is_left_to_right :1; // Direction of edge from vertex v to v+1
120 };
121
122 template <class ForwardIterator, class PolygonTraits>
123 class Vertex_data_base {
124 public:
125 typedef typename PolygonTraits::Point_2 Point_2;
126
127 // ForwardIterator points_start;
128 std::vector<ForwardIterator> iterators;
129 std::vector<Vertex_order> m_order_of;
130 std::vector<Vertex_index> m_idx_at_rank;
131 std::vector<Vertex_index>::size_type m_size;
132 typename PolygonTraits::Orientation_2 orientation_2;
133 typename PolygonTraits::Less_xy_2 less_xy_2;
134 bool is_simple_result;
135
136 Vertex_data_base(ForwardIterator begin, ForwardIterator end,
137 const PolygonTraits& pgnt);
138
ordered_left_to_right(Vertex_index v1,Vertex_index v2)139 bool ordered_left_to_right(Vertex_index v1, Vertex_index v2)
140 { return m_order_of[v1.as_int()].as_int() <
141 m_order_of[v2.as_int()].as_int();}
index_at_rank(Vertex_order vo)142 Vertex_index index_at_rank(Vertex_order vo) const
143 { return m_idx_at_rank[vo.as_int()];}
next(Vertex_index k)144 Vertex_index next(Vertex_index k) const
145 { ++k; return k.as_int() == m_size ? Vertex_index(0) : k;}
prev(Vertex_index k)146 Vertex_index prev(Vertex_index k) const
147 { return k.as_int() == 0
148 ? Vertex_index(m_size-1)
149 : Vertex_index(k.as_int()-1);
150 }
point(Vertex_index i)151 Point_2 point(Vertex_index i)
152 { return *iterators[i.as_int()];}
153 // { return points_start[i.as_int()];}
154 };
155
156 template <class ForwardIterator, class PolygonTraits>
157 class Vertex_data : public Vertex_data_base<ForwardIterator, PolygonTraits> {
158 public:
159 typedef Less_segments<Vertex_data> Less_segs;
160 typedef std::set<Vertex_index, Less_segs> Tree;
161 typedef Vertex_data_base<ForwardIterator, PolygonTraits> Base_class;
162
163 using Base_class::ordered_left_to_right;
164 using Base_class::next;
165 using Base_class::prev;
166 using Base_class::index_at_rank;
167 using Base_class::point;
168
169 std::vector<Edge_data<Less_segs> > edges;
170
171 Vertex_data(ForwardIterator begin, ForwardIterator end,
172 const PolygonTraits& pgnt);
173
174 void init(Tree *tree);
175 void left_and_right_index(Vertex_index &left, Vertex_index &right,
176 Vertex_index edge);
left_index(Vertex_index edge)177 Vertex_index left_index(Vertex_index edge)
178 { return edges[edge.as_int()].is_left_to_right ? edge : next(edge); }
179
180 void sweep(Tree *tree);
181 bool insertion_event(Tree *tree,
182 Vertex_index i, Vertex_index j, Vertex_index k);
183 bool replacement_event(Tree *tree,
184 Vertex_index cur, Vertex_index to_insert);
185 bool deletion_event(Tree *tree, Vertex_index i, Vertex_index j);
186 bool on_right_side(Vertex_index vt, Vertex_index edge, bool above);
187 };
188
189 template <class VertexData>
190 class Less_vertex_data {
191 VertexData *m_vertex_data;
192 public:
Less_vertex_data(VertexData * vd)193 Less_vertex_data(VertexData *vd)
194 : m_vertex_data(vd) {}
195 bool operator()(Vertex_index i, Vertex_index j) const;
196 };
197
198 } // end of namespace i_polygon
199
200 // ----- implementation of i_polygon functions. -----
201
202 namespace i_polygon {
203 template <class VertexData>
204 bool Less_segments<VertexData>::
operator()205 operator()(Vertex_index i, Vertex_index j) const
206 {
207 if (i.as_int() == j.as_int()) {
208 // Some STL implementations may call comparator(x, x)
209 // to verify irreflexivity. Don't violate less_than_in_tree's
210 // preconditions in such an environment.
211 return false;
212 } else if (m_vertex_data->edges[j.as_int()].is_in_tree) {
213 return less_than_in_tree(i,j);
214 } else {
215 return !less_than_in_tree(j,i);
216 }
217 }
218
219 template <class VertexData>
220 bool Less_segments<VertexData>::
less_than_in_tree(Vertex_index new_edge,Vertex_index tree_edge)221 less_than_in_tree(Vertex_index new_edge, Vertex_index tree_edge) const
222 {
223 CGAL_polygon_precondition(
224 m_vertex_data->edges[tree_edge.as_int()].is_in_tree);
225 CGAL_polygon_precondition(
226 !m_vertex_data->edges[new_edge.as_int()].is_in_tree);
227 Vertex_index left, mid, right;
228 m_vertex_data->left_and_right_index(left, right, tree_edge);
229 mid = m_vertex_data->left_index(new_edge);
230 if (mid.as_int() == left.as_int()) {
231 return true;
232 }
233 switch (m_vertex_data->orientation_2( m_vertex_data->point(left),
234 m_vertex_data->point(mid), m_vertex_data->point(right))) {
235 case LEFT_TURN: return true;
236 case RIGHT_TURN: return false;
237 case COLLINEAR: break;
238 }
239 m_vertex_data->is_simple_result = false;
240 return true;
241 }
242
243 template <class VertexData>
244 bool Less_vertex_data<VertexData>::
operator()245 operator()(Vertex_index i, Vertex_index j) const
246 {
247 return m_vertex_data->less_xy_2(
248 m_vertex_data->point(i), m_vertex_data->point(j));
249 }
250
251 template <class ForwardIterator, class PolygonTraits>
252 Vertex_data_base<ForwardIterator, PolygonTraits>::
Vertex_data_base(ForwardIterator begin,ForwardIterator end,const PolygonTraits & pgn_traits)253 Vertex_data_base(ForwardIterator begin, ForwardIterator end,
254 const PolygonTraits& pgn_traits)
255 : orientation_2(pgn_traits.orientation_2_object()),
256 less_xy_2(pgn_traits.less_xy_2_object())
257 {
258 m_size = std::distance(begin, end);
259 is_simple_result = true;
260 m_idx_at_rank.reserve(m_size);
261 iterators.reserve(m_size);
262 m_order_of.insert(m_order_of.end(), m_size, Vertex_order(0));
263 for (Index_t i = 0; i< m_size; ++i, ++begin) {
264 m_idx_at_rank.push_back(Vertex_index(i));
265 iterators.push_back(begin);
266 }
267 std::sort(m_idx_at_rank.begin(), m_idx_at_rank.end(),
268 Less_vertex_data<Vertex_data_base>(this));
269 for (Index_t j = 0; j < m_size; ++j) {
270 Vertex_order vo(j);
271 m_order_of[index_at_rank(vo).as_int()] = vo;
272 }
273 }
274
275 template <class ForwardIterator, class PolygonTraits>
276 void Vertex_data<ForwardIterator, PolygonTraits>::
left_and_right_index(Vertex_index & left,Vertex_index & right,Vertex_index edge)277 left_and_right_index(Vertex_index &left, Vertex_index &right,
278 Vertex_index edge)
279 {
280 if (edges[edge.as_int()].is_left_to_right) {
281 left = edge; right = next(edge);
282 } else {
283 right = edge; left = next(edge);
284 }
285 }
286
287 template <class ForwardIterator, class PolygonTraits>
288 Vertex_data<ForwardIterator, PolygonTraits>::
Vertex_data(ForwardIterator begin,ForwardIterator end,const PolygonTraits & pgn_traits)289 Vertex_data(ForwardIterator begin, ForwardIterator end,
290 const PolygonTraits& pgn_traits)
291 : Base_class(begin, end, pgn_traits) {}
292
293 template <class ForwardIterator, class PolygonTraits>
init(Tree * tree)294 void Vertex_data<ForwardIterator, PolygonTraits>::init(Tree *tree)
295 {
296 // The initialization cannot be done in the constructor,
297 // otherwise we copy singular valued iterators.
298 edges.insert(edges.end(), this->m_size, Edge_data<Less_segs>(tree->end()));
299 }
300
301
302 template <class ForwardIterator, class PolygonTraits>
303 bool Vertex_data<ForwardIterator, PolygonTraits>::
insertion_event(Tree * tree,Vertex_index prev_vt,Vertex_index mid_vt,Vertex_index next_vt)304 insertion_event(Tree *tree, Vertex_index prev_vt,
305 Vertex_index mid_vt, Vertex_index next_vt)
306 {
307 // check which endpoint is above the other
308 bool left_turn;
309 switch(this->orientation_2(point(prev_vt), point(mid_vt), point(next_vt))) {
310 case LEFT_TURN: left_turn = true; break;
311 case RIGHT_TURN: left_turn = false; break;
312 default: return false;
313
314 }
315 Edge_data<Less_segs>
316 &td_prev = edges[prev_vt.as_int()],
317 &td_mid = edges[mid_vt.as_int()];
318 td_prev.is_in_tree = false;
319 td_prev.is_left_to_right = false;
320 td_mid.is_in_tree = false;
321 td_mid.is_left_to_right = true;
322 // insert the highest chain first
323 std::pair<typename Tree::iterator, bool> result;
324 if (left_turn) {
325 result = tree->insert(prev_vt);
326 // CGAL_polygon_assertion(result.second)
327 td_prev.tree_it = result.first;
328 td_prev.is_in_tree = true;
329 result = tree->insert(mid_vt);
330 // CGAL_polygon_assertion(result.second)
331 td_mid.tree_it = result.first;
332 td_mid.is_in_tree = true;
333 } else {
334 result = tree->insert(mid_vt);
335 // CGAL_polygon_assertion(result.second)
336 td_mid.tree_it = result.first;
337 td_mid.is_in_tree = true;
338 result = tree->insert(prev_vt);
339 // CGAL_polygon_assertion(result.second)
340 td_prev.tree_it = result.first;
341 td_prev.is_in_tree = true;
342 }
343 return true;
344 }
345
346 template <class ForwardIterator, class PolygonTraits>
347 bool Vertex_data<ForwardIterator, PolygonTraits>::
on_right_side(Vertex_index vt,Vertex_index edge_id,bool above)348 on_right_side(Vertex_index vt, Vertex_index edge_id, bool above)
349 {
350 Orientation turn =
351 this->orientation_2(point(edge_id), point(vt), point(next(edge_id)));
352 bool left_turn = edges[edge_id.as_int()].is_left_to_right ? above : !above;
353 if (left_turn) {
354 if (turn != RIGHT_TURN) {
355 return false;
356 }
357 } else {
358 if (turn != LEFT_TURN) {
359 return false;
360 }
361 }
362 return true;
363 }
364
365 template <class ForwardIterator, class PolygonTraits>
366 bool Vertex_data<ForwardIterator, PolygonTraits>::
replacement_event(Tree * tree,Vertex_index cur_edge,Vertex_index next_edge)367 replacement_event(Tree *tree, Vertex_index cur_edge, Vertex_index next_edge)
368 {
369 // check if continuation point is on the right side of neighbor segments
370 typedef typename Tree::iterator It;
371 Edge_data<Less_segs> &td = edges[cur_edge.as_int()];
372 CGAL_polygon_assertion(td.is_in_tree);
373 It cur_seg = td.tree_it;
374 Vertex_index cur_vt = (td.is_left_to_right) ? next_edge : cur_edge;
375 if (cur_seg != tree->begin()) {
376 It seg_below = cur_seg;
377 --seg_below;
378 if (!on_right_side(cur_vt, *seg_below, true)) {
379 return false;
380 }
381 }
382 It seg_above = cur_seg;
383 ++ seg_above;
384 if (seg_above != tree->end()) {
385 if (!on_right_side(cur_vt, *seg_above, false)) {
386 return false;
387 }
388 }
389 // replace the segment
390 Edge_data<Less_segs> &new_td =
391 edges[next_edge.as_int()];
392 new_td.is_left_to_right = td.is_left_to_right;
393 new_td.is_in_tree = false;
394 tree->erase(cur_seg);
395 td.is_in_tree = false;
396 new_td.tree_it = tree->insert(seg_above, next_edge);
397 new_td.is_in_tree = true;
398 return true;
399 }
400
401 template <class ForwardIterator, class PolygonTraits>
402 bool Vertex_data<ForwardIterator, PolygonTraits>::
deletion_event(Tree * tree,Vertex_index prev_vt,Vertex_index mid_vt)403 deletion_event(Tree *tree, Vertex_index prev_vt, Vertex_index mid_vt)
404 {
405 // check if continuation point is on the right side of neighbor segments
406 typedef typename Tree::iterator It;
407 Edge_data<Less_segs>
408 &td_prev = edges[prev_vt.as_int()],
409 &td_mid = edges[mid_vt.as_int()];
410 It prev_seg = td_prev.tree_it, mid_seg = td_mid.tree_it;
411 Vertex_index cur_vt = (td_prev.is_left_to_right) ? mid_vt : prev_vt;
412 It seg_above = prev_seg;
413 ++seg_above;
414 if (seg_above == mid_seg) {
415 ++seg_above;
416 } else {
417 // mid_seg was not above prev_seg, so prev_seg should be above mid_seg
418 // We check this to see if the edges are really neighbors in the tree.
419 It prev_seg_copy = mid_seg;
420 ++prev_seg_copy;
421 if (prev_seg_copy != prev_seg)
422 return false;
423 }
424 // remove the segments
425 tree->erase(prev_seg);
426 td_prev.is_in_tree = false;
427 tree->erase(mid_seg);
428 td_mid.is_in_tree = false;
429 // Check if the vertex that is removed lies between the two tree edges.
430 if (seg_above != tree->end()) {
431 if (!on_right_side(cur_vt, *seg_above, false))
432 return false;
433 }
434 if (seg_above != tree->begin()) {
435 --seg_above; // which turns it in seg_below
436 if (!on_right_side(cur_vt, *seg_above, true))
437 return false;
438 }
439 return true;
440 }
441
442 template <class ForwardIterator, class PolygonTraits>
443 void Vertex_data<ForwardIterator, PolygonTraits>::
sweep(Tree * tree)444 sweep(Tree *tree)
445 {
446 if (this->m_size < 3)
447 return;
448 bool succes = true;
449 for (Index_t i=0; i< this->m_size; ++i) {
450 Vertex_index cur = index_at_rank(Vertex_order(i));
451 Vertex_index prev_vt = prev(cur), next_vt = next(cur);
452 if (ordered_left_to_right(cur, next_vt)) {
453 if (ordered_left_to_right(cur, prev_vt))
454 succes = insertion_event(tree, prev_vt, cur, next_vt);
455 else
456 succes = replacement_event(tree, prev_vt, cur);
457 } else {
458 if (ordered_left_to_right(cur, prev_vt))
459 succes = replacement_event(tree, cur, prev_vt);
460 else
461 succes = deletion_event(tree, prev_vt, cur);
462 }
463 if (!succes)
464 break;
465 }
466 if (!succes)
467 this->is_simple_result = false;
468 }
469 }
470 // ----- End of implementation of i_polygon functions. -----
471
472
473 template <class Iterator, class PolygonTraits>
is_simple_polygon(Iterator points_begin,Iterator points_end,const PolygonTraits & polygon_traits)474 bool is_simple_polygon(Iterator points_begin, Iterator points_end,
475 const PolygonTraits& polygon_traits)
476 {
477 typedef Iterator ForwardIterator;
478 typedef i_polygon::Vertex_data<ForwardIterator, PolygonTraits> Vertex_data;
479 typedef std::set<i_polygon::Vertex_index,
480 i_polygon::Less_segments<Vertex_data> > Tree;
481
482 // A temporary fix as the sweep in some cases doesn't discover vertices with degree > 2
483 // Todo: fix the sweep code
484 std::vector<typename PolygonTraits::Point_2> points(points_begin,points_end);
485 std::sort(points.begin(), points.end(), polygon_traits.less_xy_2_object());
486
487 typename std::vector<typename PolygonTraits::Point_2>::iterator
488 succ(points.begin()) , it(succ++);
489 for(;succ != points.end(); ++it,++succ){
490 if(*it == *succ){
491 return false;
492 }
493 }
494 // end of fix
495 Vertex_data vertex_data(points_begin, points_end, polygon_traits);
496 Tree tree(&vertex_data);
497 vertex_data.init(&tree);
498 vertex_data.sweep(&tree);
499 return vertex_data.is_simple_result;
500 }
501
502 } // end of namespace CGAL
503
504 #include <CGAL/enable_warnings.h>
505
506 #endif
507