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/partition_y_monotone_2.h $
7 // $Id: partition_y_monotone_2.h 5a36ff8 2020-12-04T08:02:26+00:00 Giles Bathgate
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 // Implementaion of the algorithm from pp 49--55 of "Computational Geometry
15 // Algorithms and Applications" by de Berg, van Kreveld, Overmars, and
16 // Schwarzkopf for producing a partitioning of a polygon into y-monotone
17 // pieces.
18 //
19 // NOTE: e_i = (v_i, v_{i+1})
20 //
21 // TREE:
22 // "Therefore we store the edges of P intersecting the sweep line in the
23 // leaves of a dynamic binary search tree T. The left-to-right order of
24 // the leaves of T corresponds to the left-to-right order of the edges.
25 // Because we are only interested in edges to the left of split and merge
26 // vertices we only need to store edges in T that have the interior of P
27 // to their right. With each edge in T we store its helper."
28 //
29 //
30
31 #ifndef CGAL_PARTITION_Y_MONOTONE_H
32 #define CGAL_PARTITION_Y_MONOTONE_H
33
34 #include <CGAL/license/Partition_2.h>
35
36
37 #include <CGAL/Partition_2/Indirect_not_less_yx_2.h>
38 #include <CGAL/Partition_2/Indirect_edge_compare.h>
39 #include <CGAL/Partition_2/Partitioned_polygon_2.h>
40 #include <CGAL/ch_selected_extreme_points_2.h>
41 #include <CGAL/IO/Tee_for_output_iterator.h>
42 #include <CGAL/Partition_2/partition_assertions.h>
43 #include <CGAL/partition_is_valid_2.h>
44 #include <CGAL/Partition_traits_2.h>
45 #include <map>
46
47 namespace CGAL {
48
49 enum Partition_y_mono_vertex_type {PARTITION_Y_MONO_START_VERTEX,
50 PARTITION_Y_MONO_SPLIT_VERTEX,
51 PARTITION_Y_MONO_REGULAR_VERTEX,
52 PARTITION_Y_MONO_COLLINEAR_VERTEX,
53 PARTITION_Y_MONO_MERGE_VERTEX,
54 PARTITION_Y_MONO_END_VERTEX};
55
56
57 //
58 // assumes CCW orientation of vertices
59 //
60 template <class BidirectionalCirculator, class Traits>
partition_y_mono_vertex_type(BidirectionalCirculator c,const Traits & traits)61 Partition_y_mono_vertex_type partition_y_mono_vertex_type(
62 BidirectionalCirculator c,
63 const Traits& traits)
64 {
65 typedef typename Traits::Point_2 Point_2;
66 BidirectionalCirculator previous = c;
67 previous--;
68 BidirectionalCirculator next = c;
69 next++;
70 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
71 std::cout << "partition_y_mono__vertex_type: previous " << *previous
72 << " c " << *c << " next " << *next << std::endl;
73 #endif
74 typename Traits::Compare_y_2 compare_y_2 = traits.compare_y_2_object();
75
76 if (compare_y_2(Point_2(*previous), Point_2(*c)) == EQUAL &&
77 compare_y_2(Point_2(*next), Point_2(*c)) == EQUAL)
78 return PARTITION_Y_MONO_COLLINEAR_VERTEX;
79
80 typename Traits::Less_yx_2 less_yx = traits.less_yx_2_object();
81 typename Traits::Left_turn_2 left_turn = traits.left_turn_2_object();
82
83 if(less_yx(Point_2(*previous), Point_2(*c)))
84 {
85 if(less_yx(Point_2(*next), Point_2(*c))) // previous and next both less_yx
86 if(left_turn(Point_2(*previous), Point_2(*c), Point_2(*next))) // interior angle less than pi
87 return PARTITION_Y_MONO_START_VERTEX;
88 else // interior angle greater than pi
89 return PARTITION_Y_MONO_SPLIT_VERTEX;
90 else // previous less_yx and next not
91 return PARTITION_Y_MONO_REGULAR_VERTEX;
92 }
93 else
94 {
95 if(less_yx(Point_2(*c), Point_2(*next))) // previous and next both not less_yx
96 if(left_turn(Point_2(*previous), Point_2(*c), Point_2(*next))) // interior angle less than pi
97 return PARTITION_Y_MONO_END_VERTEX;
98 else // interior angle greater than pi
99 return PARTITION_Y_MONO_MERGE_VERTEX;
100 else // next less_yx and previous not
101 return PARTITION_Y_MONO_REGULAR_VERTEX;
102 }
103 }
104
105 template <class Tree>
partition_y_mono_print_tree(Tree tree)106 void partition_y_mono_print_tree(Tree tree)
107 {
108 typedef typename Tree::iterator iterator;
109
110 iterator it = tree.begin();
111 for (; it != tree.end(); it++) {
112 std::cout << "edge node " << *(*it).first << " helper " << *(*it).second
113 << std::endl;
114 }
115 std::cout << std::endl;
116 }
117
118 template <class BidirectionalCirculator, class Tree>
partition_y_mono_handle_start_vertex(BidirectionalCirculator c,Tree & tree)119 void partition_y_mono_handle_start_vertex(BidirectionalCirculator c,
120 Tree& tree)
121 {
122 typedef typename Tree::value_type ValuePair;
123
124 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
125 std::cout << *c << " is a start vertex " << std::endl;
126 #endif
127 tree.insert(ValuePair(c, c));
128 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
129 std::cout << "partition_handle_start_vertex: after insert tree is "
130 << std::endl;
131 partition_y_mono_print_tree(tree);
132 #endif
133 // insert e_i (edge from *c to *++c) into "tree" with helper(e_i) = v_i
134 }
135
136 template <class BidirectionalCirculator, class Tree,
137 class Partition_Poly, class Traits>
partition_y_mono_handle_end_vertex(BidirectionalCirculator c,Tree & tree,Partition_Poly & partition_poly,const Traits & traits)138 void partition_y_mono_handle_end_vertex(BidirectionalCirculator c, Tree& tree,
139 Partition_Poly& partition_poly,
140 const Traits& traits )
141 {
142
143 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
144 std::cout << *c << " is an end vertex " << std::endl;
145 #endif
146
147 typedef typename Tree::iterator tree_iterator;
148 tree_iterator it;
149 BidirectionalCirculator previous = c;
150 previous--;
151
152 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
153 std::cout << "partition_y_mono_handle_end_vertex: previous " << *previous
154 << std::endl;
155 #endif
156 it = tree.find(previous);
157 CGAL_assertion (it != tree.end());
158
159 if (partition_y_mono_vertex_type((*it).second, traits) ==
160 PARTITION_Y_MONO_MERGE_VERTEX)
161 {
162 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
163 std::cout << "partition_y_mono_handle_end_vertex: diagonal "
164 << *(*it).second << " to " << *c << std::endl;
165 #endif
166 partition_poly.insert_diagonal(c, (*it).second);
167 }
168 tree.erase(it);
169 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
170 std::cout << "partition_y_mono_handle_end_vertex: after erase tree is "
171 << std::endl;
172 partition_y_mono_print_tree(tree);
173 #endif
174 // if helper(e_{i-1}) is a merge vertex
175 // insert diagonal connecting v_i to helper(e_{i-1})
176 // delete e_{i-1} from tree
177 }
178
179 template<class BidirectionalCirculator, class Iterator, class Tree>
180 inline
partition_y_mono_edge_directly_left(BidirectionalCirculator c,Tree & tree,Iterator & it)181 void partition_y_mono_edge_directly_left(BidirectionalCirculator c, Tree& tree,
182 Iterator& it)
183 {
184 it = tree.lower_bound(c); // edge directly to the left of v_i since the
185 // items in the tree are sorted from right to
186 // left
187 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
188 if (it != tree.end())
189 std::cout << "partition_y_mono_edge_directly_left: lower_bound edge node: "
190 << *((*it).first) << " helper " << *((*it).second) << std::endl;
191 #endif
192 }
193
194 template <class BidirectionalCirculator, class Tree, class Partition_Poly>
partition_y_mono_handle_split_vertex(BidirectionalCirculator c,Tree & tree,Partition_Poly & partition_poly)195 void partition_y_mono_handle_split_vertex(BidirectionalCirculator c,
196 Tree& tree,
197 Partition_Poly& partition_poly)
198 {
199 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
200 std::cout << *c << " is a split vertex " << std::endl;
201 #endif
202
203 typedef typename Tree::iterator tree_iterator;
204 typedef typename Tree::value_type ValuePair;
205 tree_iterator it;
206 partition_y_mono_edge_directly_left(c, tree, it);
207 if (it != tree.end())
208 {
209 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
210 std::cout << "partition_y_mono_handle_split_vertex: diagonal "
211 << *(*it).second << " to " << *c << std::endl;
212 #endif
213 partition_poly.insert_diagonal(c, (*it).second);
214 BidirectionalCirculator ej = (*it).first;
215 tree.erase(it);
216 tree.insert(ValuePair(ej, c));
217 }
218 tree.insert(ValuePair(c, c));
219 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
220 std::cout << "partition_y_mono_handle_split_vertex: "
221 << "after erase and inserts tree is" << std::endl;
222 partition_y_mono_print_tree(tree);
223 #endif
224 // 1. find the edge e_j in tree directly to the left of v_i
225 // 2. insert the diagonal connecting v_i to helper(e_j)
226 // 3. helper(e_j) = v_i
227 // 4. Insert e_i in tree and set helper(e_i) to v_i
228 }
229
230 template <class BidirectionalCirculator, class Tree,
231 class Partition_Poly, class Traits>
partition_y_mono_handle_merge_vertex(BidirectionalCirculator c,Tree & tree,Partition_Poly & partition_poly,const Traits & traits)232 void partition_y_mono_handle_merge_vertex(BidirectionalCirculator c,
233 Tree& tree,
234 Partition_Poly& partition_poly,
235 const Traits& traits)
236 {
237 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
238 std::cout << *c << " is a merge vertex " << std::endl;
239 #endif
240
241 typedef typename Tree::iterator tree_iterator;
242 typedef typename Tree::value_type ValuePair;
243 BidirectionalCirculator prev = c;
244 prev--;
245 tree_iterator it = tree.find(prev);
246 CGAL_assertion (it != tree.end());
247
248 if (partition_y_mono_vertex_type((*it).second,traits) ==
249 PARTITION_Y_MONO_MERGE_VERTEX)
250 {
251 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
252 std::cout << "partition_y_mono_handle_merge_vertex 1: diagonal "
253 << *(*it).second << " to " << *c << std::endl;
254 #endif
255 partition_poly.insert_diagonal(c, (*it).second);
256 }
257 tree.erase(it);
258
259 partition_y_mono_edge_directly_left(c, tree, it);
260 if (it != tree.end())
261 {
262 if (partition_y_mono_vertex_type((*it).second,traits) ==
263 PARTITION_Y_MONO_MERGE_VERTEX)
264 {
265 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
266 std::cout << "partition_y_mono_handle_merge_vertex 2: diagonal "
267 << *(*it).second << " to " << *c << std::endl;
268 #endif
269 partition_poly.insert_diagonal(c, (*it).second);
270 }
271 BidirectionalCirculator ej = (*it).first;
272 tree.erase(it);
273 tree.insert(ValuePair(ej,c));
274 }
275 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
276 std::cout << "partition_y_mono_handle_merge_vertex: after erase(s) tree is "
277 << std::endl;
278 partition_y_mono_print_tree(tree);
279 #endif
280 // 1. if helper(e_{i-1}) is a merge vertex
281 // insert the diagonal connecting v_i to helper(e_{i-1})
282 // 2. delete e_{i-1} from tree
283 // 3. find the edge e_j in tree directly to the left of v_i
284 // 4. if helper(e_j) is a merge vertex
285 // insert diagonal connecting v_i to helper(e_j) in polygon
286 // 5. helper(e_j) = v_i
287 }
288
289 template <class BidirectionalCirculator, class Traits>
partition_y_mono_interior_to_right(BidirectionalCirculator c,const Traits & traits)290 bool partition_y_mono_interior_to_right(BidirectionalCirculator c,
291 const Traits& traits)
292 {
293 typedef typename Traits::Point_2 Point_2;
294 typename Traits::Compare_y_2 compare_y_2 = traits.compare_y_2_object();
295
296 BidirectionalCirculator previous = c; previous--;
297
298 Comparison_result cmp_y = compare_y_2(Point_2(*previous), Point_2(*c));
299 if (cmp_y == LARGER) return true;
300
301 BidirectionalCirculator next = c; next++;
302
303 if (cmp_y == EQUAL && compare_y_2(Point_2(*next), Point_2(*c)) == SMALLER) return true;
304
305 return false;
306 }
307
308 template <class BidirectionalCirculator, class Tree, class Partition_Poly,
309 class Traits>
partition_y_mono_handle_regular_vertex(BidirectionalCirculator c,Tree & tree,Partition_Poly & partition_poly,const Traits & traits)310 void partition_y_mono_handle_regular_vertex(BidirectionalCirculator c,
311 Tree& tree,
312 Partition_Poly& partition_poly,
313 const Traits& traits )
314 {
315 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
316 std::cout << *c << " is a regular vertex " << std::endl;
317 #endif
318 typedef typename Tree::iterator tree_iterator;
319 typedef typename Tree::value_type ValuePair;
320 tree_iterator it;
321
322 BidirectionalCirculator previous = c;
323 previous--;
324
325 if (partition_y_mono_interior_to_right(c, traits))
326 {
327 it = tree.find(previous);
328 CGAL_assertion( it != tree.end() );
329
330 if (partition_y_mono_vertex_type((*it).second, traits) ==
331 PARTITION_Y_MONO_MERGE_VERTEX)
332 {
333 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
334 std::cout << "partition_y_mono_handle_regular_vertex 1: diagonal "
335 << *(*it).second << " to " << *c << std::endl;
336 #endif
337 partition_poly.insert_diagonal(c, (*it).second);
338 }
339 tree.erase(it);
340 tree.insert(ValuePair(c,c));
341 }
342 else
343 {
344 partition_y_mono_edge_directly_left(c, tree, it);
345 CGAL_assertion (it != tree.end());
346
347 if (partition_y_mono_vertex_type((*it).second, traits) ==
348 PARTITION_Y_MONO_MERGE_VERTEX)
349 {
350 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
351 std::cout << "partition_y_mono_handle_regular_vertex 2: diagonal "
352 << *c << " to " << *(*it).second << std::endl;
353 #endif
354 partition_poly.insert_diagonal(c, (*it).second);
355 }
356 BidirectionalCirculator ej = (*it).first;
357 tree.erase(it);
358 tree.insert(ValuePair(ej,c));
359 }
360 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
361 std::cout << "partition_y_mono_handle_regular_vertex: "
362 << "after erase and insert tree is" << std::endl;
363 partition_y_mono_print_tree(tree);
364 #endif
365 // if interior of polygon lies to the right of v_i
366 // if helper(e_{i-1}) is a merge vertex
367 // insert diagonal connecting v_i to helper(e_{i-1}) in polygon
368 // delete e_{i-1} from tree
369 // insert e_i in tree and set helper(e_i) to v_i
370 // else
371 // find the edge e_j in tree directly left of v_i
372 // if helper(e_j) is a merge vertex
373 // insert diagonal connecting v_i to helper(e_j) in D
374 // helper(e_j) = v_i
375 }
376
377 template <class BidirectionalCirculator, class Tree>
partition_y_mono_handle_collinear_vertex(BidirectionalCirculator c,Tree & tree)378 void partition_y_mono_handle_collinear_vertex(BidirectionalCirculator c,
379 Tree& tree)
380 {
381 typedef typename Tree::iterator tree_iterator;
382 typedef typename Tree::value_type ValuePair;
383 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
384 std::cout << *c << " is a collinear vertex " << std::endl;
385 #endif
386
387 tree_iterator it;
388
389 BidirectionalCirculator previous = c;
390 previous--;
391 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
392 std::cout << *previous << " is the previous vertex " << std::endl;
393 #endif
394
395 it = tree.find(previous);
396 if ( it != tree.end() )
397 {
398 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
399 std::cout << "partition_y_mono_handle_collinear_vertex : removing "
400 << *(*it).first << std::endl;
401 #endif
402 tree.erase(it);
403 }
404 tree.insert(ValuePair(c,c));
405 }
406
407
408 template <class InputIterator, class OutputIterator, class Traits>
partition_y_monotone_2(InputIterator first,InputIterator beyond,OutputIterator result,const Traits & traits)409 OutputIterator partition_y_monotone_2(InputIterator first,
410 InputIterator beyond,
411 OutputIterator result,
412 const Traits& traits)
413 {
414 if (first == beyond) return result;
415
416 typedef Partitioned_polygon_2< Traits > P_Polygon_2;
417 typedef typename P_Polygon_2::iterator I;
418 typedef Circulator_from_iterator<I> Circulator;
419
420 #if defined(CGAL_PARTITION_NO_POSTCONDITIONS) || \
421 defined(CGAL_NO_POSTCONDITIONS)
422 OutputIterator res(result);
423 #else
424 typedef typename Traits::Polygon_2 Polygon_2;
425 Tee_for_output_iterator<OutputIterator, Polygon_2> res(result);
426 #endif // no postcondition
427
428 P_Polygon_2 polygon(first, beyond, traits);
429 CGAL_partition_precondition(
430 orientation_2(polygon.begin(), polygon.end(), traits) == COUNTERCLOCKWISE);
431
432 Circulator circ(polygon.begin(), polygon.end()), done = circ;
433 std::vector<Circulator> circulators;
434 CGAL_For_all(circ, done){
435 circulators.push_back(circ);
436 }
437 std::sort(circulators.begin(), circulators.end(), Indirect_not_less_yx_2<Traits>(traits));
438
439 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
440 std::cout << "Initial vertex list: "<< circulators << std::endl;
441 for(std::vector<Circulator>::const_iterator it = circulators.begin();
442 it != circulators.end();
443 it++){
444 std::cout << **it << " " ;
445 }
446 std::cout << std::endl;
447 #endif
448
449 typedef Indirect_edge_compare<Circulator, Traits> Cmp;
450 typedef std::map<Circulator, Circulator, Cmp> Tree;
451 Cmp cmp(traits);
452 Tree tree(cmp);
453
454 typename std::vector<Circulator>::iterator it = circulators.begin();
455 for (; it != circulators.end(); it++) {
456 switch (partition_y_mono_vertex_type(*it, traits))
457 {
458 case PARTITION_Y_MONO_START_VERTEX:
459 partition_y_mono_handle_start_vertex(*it, tree);
460 break;
461 case PARTITION_Y_MONO_SPLIT_VERTEX:
462 partition_y_mono_handle_split_vertex(*it, tree, polygon);
463 break;
464 case PARTITION_Y_MONO_END_VERTEX:
465 partition_y_mono_handle_end_vertex(*it, tree, polygon, traits);
466 break;
467 case PARTITION_Y_MONO_MERGE_VERTEX:
468 partition_y_mono_handle_merge_vertex(*it, tree, polygon, traits);
469 break;
470 case PARTITION_Y_MONO_REGULAR_VERTEX:
471 partition_y_mono_handle_regular_vertex(*it, tree, polygon, traits);
472 break;
473 case PARTITION_Y_MONO_COLLINEAR_VERTEX:
474 partition_y_mono_handle_collinear_vertex(*it, tree);
475 break;
476 }
477 }
478 #ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
479 I v_it;
480 for (v_it = polygon.begin(); v_it != polygon.end(); v_it++)
481 {
482 (*v_it).print_diagonals();
483 }
484 #endif
485 polygon.partition(res, 0);
486
487 CGAL_partition_postcondition(
488 y_monotone_partition_is_valid_2(polygon.begin(), polygon.end(),
489 res.output_so_far_begin(),
490 res.output_so_far_end(), traits));
491
492 #if defined(CGAL_PARTITION_NO_POSTCONDITIONS) || \
493 defined(CGAL_NO_POSTCONDITIONS)
494 return res;
495 #else
496 return res.to_output_iterator();
497 #endif // no postconditions
498 }
499
500 template <class InputIterator, class OutputIterator>
501 inline
partition_y_monotone_2(InputIterator first,InputIterator beyond,OutputIterator result)502 OutputIterator partition_y_monotone_2(InputIterator first,
503 InputIterator beyond,
504 OutputIterator result)
505 {
506 typedef typename std::iterator_traits<InputIterator>::value_type Point_2;
507 typedef typename Kernel_traits<Point_2>::Kernel K;
508 return partition_y_monotone_2(first, beyond, result,
509 Partition_traits_2<K>());
510 }
511
512 }
513
514 #endif // CGAL_PARTITION_Y_MONOTONE_H
515