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_on_surface_base_2_impl.h $
7 // $Id: Gps_on_surface_base_2_impl.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) : Baruch Zukerman <baruchzu@post.tau.ac.il>
12 // Efi Fogel <efif@post.tau.ac.il>
13 // Ophir Setter <ophir.setter@cs.tau.ac.il>
14 // Guy Zucker <guyzucke@post.tau.ac.il>
15
16 #ifndef CGAL_GPS_ON_SURFACE_BASE_2_IMPL_H
17 #define CGAL_GPS_ON_SURFACE_BASE_2_IMPL_H
18
19 #include <CGAL/license/Boolean_set_operations_2.h>
20
21
22 #include <CGAL/iterator.h>
23 #include <CGAL/function_objects.h>
24 #include <CGAL/circulator.h>
25 #include <CGAL/Boolean_set_operations_2/Gps_bfs_scanner.h>
26 #include <CGAL/Arr_accessor.h>
27
28 #include <queue>
29 #include <list>
30
31 namespace CGAL {
32
33 template <class Traits_, class TopTraits_, class ValidationPolicy>
34 void Gps_on_surface_base_2<Traits_, TopTraits_,ValidationPolicy>::
construct_polygon(Ccb_halfedge_const_circulator ccb,Polygon_2 & pgn,const Traits_ * tr)35 construct_polygon(Ccb_halfedge_const_circulator ccb, Polygon_2 & pgn,
36 const Traits_* tr)
37 {
38 typedef CGAL::Ccb_curve_iterator<Arrangement_on_surface_2>
39 Ccb_curve_iterator;
40 Ccb_curve_iterator begin(ccb, false);
41 Ccb_curve_iterator end(ccb, true);
42
43 tr->construct_polygon_2_object()(begin, end, pgn);
44 }
45
46 // The comments below was written after trying to understand what the visitors
47 // do. There was no comment by the author of this class.
48 // This class is used afterwards to extract polygons from the representing
49 // arrangement.
50 // This scanner is not the same as the Gps_bfs_scanner. In this file, the
51 // Gps_bfs_scanner is used with Init_faces_visitor to init the faces of the
52 // representing arrangement.
53 // It seems that Gps_bfs_scanner is used for a regular bfs scan on the faces
54 // of the arrangements, with comparison to Arr_bfs_scanner that cares about
55 // inner ccbs and outer ccbs (it treats them differently).
56 // If this is the case, we should unite Gps_bfs_scanner with the regular
57 // adaptation of arrangement to boost graph.
58 template <class Arrangement, class OutputIterator>
59 class Arr_bfs_scanner
60 {
61 public:
62 typedef typename Arrangement::Geometry_traits_2 Gps_traits;
63 typedef typename Arrangement::Topology_traits Gps_top_traits;
64 typedef typename Gps_traits::Polygon_2 Polygon_2;
65 typedef typename Gps_traits::Polygon_with_holes_2 Polygon_with_holes_2;
66 typedef typename Arrangement::Ccb_halfedge_const_circulator
67 Ccb_halfedge_const_circulator;
68 typedef typename Arrangement::Face_const_iterator Face_const_iterator;
69 typedef typename Arrangement::Halfedge_const_iterator Halfedge_const_iterator;
70 typedef typename Arrangement::Outer_ccb_const_iterator
71 Outer_ccb_const_iterator;
72 typedef typename Arrangement::Inner_ccb_const_iterator
73 Inner_ccb_const_iterator;
74
75
76 protected:
77 const Gps_traits* m_traits;
78 std::queue<Face_const_iterator> m_holes_q;
79 std::list<Polygon_2> m_pgn_holes;
80 OutputIterator m_oi;
81
82 public:
83 /*! Constructor */
Arr_bfs_scanner(const Gps_traits * tr,OutputIterator oi)84 Arr_bfs_scanner(const Gps_traits* tr, OutputIterator oi) :
85 m_traits(tr),
86 m_oi(oi)
87 {}
88
scan(Arrangement & arr)89 void scan(Arrangement& arr)
90 {
91 Face_const_iterator ubf;
92 for (ubf = arr.faces_begin(); ubf != arr.faces_end(); ++ubf)
93 {
94 if (ubf->number_of_outer_ccbs() != 0)
95 continue;
96 if (ubf->visited())
97 continue;
98
99 Inner_ccb_const_iterator holes_it;
100 if (!ubf->contained())
101 {
102 ubf->set_visited(true);
103 for (holes_it = ubf->inner_ccbs_begin();
104 holes_it != ubf->inner_ccbs_end(); ++holes_it)
105 {
106 scan_ccb (*holes_it);
107 }
108 }
109 else
110 {
111 // ubf is contained -> unbounded polygon !!
112 scan_contained_ubf(ubf);
113
114 }
115
116 while(!m_holes_q.empty())
117 {
118 Face_const_iterator top_f = m_holes_q.front();
119 m_holes_q.pop();
120 top_f->set_visited(true);
121 for (holes_it = top_f->inner_ccbs_begin();
122 holes_it != top_f->inner_ccbs_end(); ++holes_it)
123 {
124 scan_ccb(*holes_it);
125 }
126
127 //scan_uncontained_face(top_f->outer_ccb());
128 }
129 }
130
131 Face_const_iterator fit;
132 for (fit = arr.faces_begin(); fit != arr.faces_end(); ++fit)
133 {
134 fit->set_visited(false);
135 }
136 }
137
output_iterator()138 OutputIterator output_iterator() const
139 {
140 return m_oi;
141 }
142
scan_ccb(Ccb_halfedge_const_circulator ccb)143 void scan_ccb(Ccb_halfedge_const_circulator ccb)
144 {
145
146 Polygon_2 pgn_boundary;
147 Gps_on_surface_base_2<Gps_traits, Gps_top_traits>::
148 construct_polygon(ccb, pgn_boundary, m_traits);
149
150 Ccb_halfedge_const_circulator ccb_end = ccb;
151 do
152 {
153 Halfedge_const_iterator he = ccb;
154 if (!he->twin()->face()->visited())
155 all_incident_faces(he->twin()->face());
156 ++ccb;
157 }
158 while(ccb != ccb_end);
159 Polygon_with_holes_2 pgn =
160 m_traits->construct_polygon_with_holes_2_object()(pgn_boundary,
161 m_pgn_holes.begin(),
162 m_pgn_holes.end());
163 /*Polygon_with_holes_2 pgn(pgn_boundary,
164 m_pgn_holes.begin(),
165 m_pgn_holes.end());*/
166 *m_oi = pgn;
167 ++m_oi;
168 m_pgn_holes.clear();
169 }
170
scan_contained_ubf(Face_const_iterator ubf)171 void scan_contained_ubf(Face_const_iterator ubf)
172 {
173 CGAL_assertion(ubf->number_of_outer_ccbs() == 0 && ubf->contained());
174 // ubf is contained -> unbounded polygon !!
175 all_incident_faces(ubf);
176 Polygon_2 boundary;
177 Polygon_with_holes_2 pgn =
178 m_traits->construct_polygon_with_holes_2_object()(boundary,
179 m_pgn_holes.begin(),
180 m_pgn_holes.end());
181 /*Polygon_with_holes_2 pgn(boundary,
182 m_pgn_holes.begin(),
183 m_pgn_holes.end());*/
184 *m_oi = pgn;
185 ++m_oi;
186 m_pgn_holes.clear();
187 }
188
189
all_incident_faces(Face_const_iterator f)190 void all_incident_faces(Face_const_iterator f)
191 {
192 CGAL_assertion(!f->visited());
193 f->set_visited(true);
194 if (f->number_of_outer_ccbs() != 0)
195 {
196 if (!f->contained())
197 {
198 for (Outer_ccb_const_iterator oci = f->outer_ccbs_begin();
199 oci != f->outer_ccbs_end(); ++oci)
200 {
201 m_pgn_holes.push_back(Polygon_2());
202 Gps_on_surface_base_2<Gps_traits, Gps_top_traits>::
203 construct_polygon(*oci, m_pgn_holes.back(), m_traits);
204 }
205
206 m_holes_q.push(f);
207 }
208
209
210 for (Outer_ccb_const_iterator oci = f->outer_ccbs_begin();
211 oci != f->outer_ccbs_end(); ++oci)
212 {
213 Ccb_halfedge_const_circulator ccb_end = *oci;
214 Ccb_halfedge_const_circulator ccb_circ = ccb_end;
215 do
216 {
217 //get the current halfedge on the face boundary
218 Halfedge_const_iterator he = ccb_circ;
219 Face_const_iterator new_f = he->twin()->face();
220 if (!new_f->visited())
221 {
222 all_incident_faces(new_f);
223 }
224 ++ccb_circ;
225 }
226 while(ccb_circ != ccb_end);
227 }
228 }
229
230 if (f->contained())
231 {
232 Inner_ccb_const_iterator hit;
233 for(hit = f->inner_ccbs_begin(); hit != f->inner_ccbs_end(); ++hit)
234 {
235 Ccb_halfedge_const_circulator ccb_of_hole = *hit;
236 Halfedge_const_iterator he = ccb_of_hole;
237 if (is_single_face(ccb_of_hole))
238 {
239 CGAL_assertion(!he->twin()->face()->contained());
240
241 m_pgn_holes.push_back(Polygon_2());
242 Gps_on_surface_base_2<Gps_traits, Gps_top_traits>::
243 construct_polygon(he->twin()->face()->outer_ccb(),
244 m_pgn_holes.back(), m_traits);
245 m_holes_q.push(he->twin()->face());
246 }
247 else
248 {
249 Ccb_halfedge_const_circulator ccb_end = ccb_of_hole;
250 do
251 {
252 Halfedge_const_iterator he = ccb_of_hole;
253 if (!he->twin()->face()->visited())
254 all_incident_faces(he->twin()->face());
255 ++ccb_of_hole;
256 }
257 while(ccb_of_hole != ccb_end);
258 }
259 }
260 }
261 }
262
is_single_face(Ccb_halfedge_const_circulator ccb)263 bool is_single_face(Ccb_halfedge_const_circulator ccb)
264 {
265 Ccb_halfedge_const_circulator ccb_end = ccb;
266 Ccb_halfedge_const_circulator ccb_circ = ccb_end;
267 Halfedge_const_iterator he = ccb;
268 Face_const_iterator curr_f = he->twin()->face();
269 do
270 {
271 //get the current halfedge on the face boundary
272 Halfedge_const_iterator he = ccb_circ;
273 if (he->twin()->face() != curr_f)
274 return false;
275 if (he->twin()->target()->degree() != 2)
276 return false;
277 ++ccb_circ;
278 }
279 while(ccb_circ != ccb_end);
280 return true;
281 }
282 };
283
284
285 template <class Arrangement>
286 class Init_faces_visitor
287 {
288 typedef typename Arrangement::Face_iterator Face_iterator;
289 typedef typename Arrangement::Halfedge_iterator Halfedge_iterator;
290
291 public:
292
293 //! discovered_face
294 /*! discovered_face is called by Gps_bfs_scanner when it reveals a new face
295 during a BFS scan. It is important to say that I have a strong suspition
296 that this place is the reason why discovered_face was once called
297 "flip_face" (WTF?)
298 \param old_f The face that was already revealed
299 \param new_f The face that we have just now revealed
300 */
discovered_face(Face_iterator old_f,Face_iterator new_f,Halfedge_iterator)301 void discovered_face(Face_iterator old_f,
302 Face_iterator new_f,
303 Halfedge_iterator /*he*/)
304 {
305 new_f->set_contained(!old_f->contained());
306 }
307 };
308
309 //! _insert
310 /*! The function inserts a polygon into an arrangement, assuming that the
311 polygon is contained in one face of the arrangement.
312 \param pgn The polygon to be inserted to the arrangement. pgn must be
313 completely disjoint from the arrangement
314 \param arr The arrangement to insert the polygon to.
315 */
316 template <class Traits_, class TopTraits_, class ValidationPolicy>
317 void Gps_on_surface_base_2<Traits_, TopTraits_,ValidationPolicy>::
_insert(const Polygon_2 & pgn,Arrangement_on_surface_2 & arr)318 _insert(const Polygon_2& pgn, Arrangement_on_surface_2 & arr)
319 {
320 typedef Arr_accessor<Arrangement_on_surface_2> Arr_accessor;
321
322 Arr_accessor accessor(arr);
323 Compare_endpoints_xy_2 cmp_ends = m_traits->compare_endpoints_xy_2_object();
324
325 std::pair<Curve_const_iterator, Curve_const_iterator> itr_pair =
326 m_traits->construct_curves_2_object()(pgn);
327
328 if (itr_pair.first == itr_pair.second)
329 return;
330
331 Curve_const_iterator curr = itr_pair.first;
332 Curve_const_iterator end = itr_pair.second;
333
334 const Arr_parameter_space ps_x =
335 m_traits_adaptor.parameter_space_in_x_2_object()(*curr, ARR_MIN_END);
336 const Arr_parameter_space ps_y =
337 m_traits_adaptor.parameter_space_in_y_2_object()(*curr, ARR_MIN_END);
338
339 Object obj_f;
340 if ((ps_x == ARR_INTERIOR) && (ps_y == ARR_INTERIOR))
341 {
342 Point_location pl(arr);
343 obj_f = pl.locate(m_traits->construct_min_vertex_2_object()(*curr));
344 }
345 else
346 {
347 obj_f = accessor.locate_curve_end(*curr, ARR_MIN_END, ps_x, ps_y);
348 }
349
350 Face_const_handle const_f;
351 // face should not be contained as the pgn is completly disjoint of the
352 // arrangement.
353 CGAL_assertion(CGAL::assign(const_f, obj_f) && !const_f->contained());
354 CGAL::assign(const_f, obj_f);
355 Face_iterator f = arr.non_const_handle(const_f);
356
357 Halfedge_handle first_he =
358 arr.insert_in_face_interior(*curr, f);
359 //first_he is directed from left to right (see insert_in_face_interior)
360
361 Halfedge_handle curr_he;
362 if (cmp_ends(*curr) == CGAL::SMALLER)
363 {
364 // curr curve and first_he have the same direction
365 curr_he = first_he;
366 first_he = first_he->twin();
367 }
368 else
369 {
370 // curr curve and first_he have opposite directions
371 CGAL_assertion(cmp_ends(*curr) == CGAL::LARGER);
372 curr_he = first_he->twin();
373 }
374
375 Curve_const_iterator temp = curr;
376 ++temp;
377 if (temp == end) // a polygon with circular arcs may have only
378 // two edges (full circle for example)
379 {
380 /*Halfedge_handle he =
381 arr.insert_at_vertices(*temp, curr_he, first_he);*/
382 bool new_face_created = false;
383 bool dummy_swapped_predecessors = false;
384 Halfedge_handle he = accessor.insert_at_vertices_ex (curr_he,
385 *temp, (cmp_ends(*temp) == CGAL::SMALLER ? ARR_LEFT_TO_RIGHT : ARR_RIGHT_TO_LEFT),
386 first_he->next(),
387 new_face_created,
388 dummy_swapped_predecessors);
389 // TODO EBEB 2012-08-06 do we have to care if order has been swapped,
390 // or do we have to disallow swapping?
391
392 CGAL_assertion(new_face_created);
393 CGAL_assertion((he->face() != he->twin()->face()));
394
395 he->face()->set_contained(true);
396 return;
397 }
398
399 //The polygon has 3 or more edges
400 Curve_const_iterator last = end;
401 --last;
402 for(++curr ; curr != last; ++curr)
403 {
404 const X_monotone_curve_2& curr_cv = *curr;
405 if (cmp_ends(curr_cv) == CGAL::SMALLER)
406 curr_he = arr.insert_from_left_vertex(curr_cv, curr_he);
407 else
408 {
409 CGAL_assertion(cmp_ends(curr_cv) == CGAL::LARGER);
410 curr_he = arr.insert_from_right_vertex(curr_cv, curr_he);
411 }
412 }
413
414 const X_monotone_curve_2& last_cv = *last;
415 /*Halfedge_handle last_he =
416 arr.insert_at_vertices(last_cv, curr_he, first_he); */
417 bool new_face_created = false;
418 bool dummy_swapped_predecessors = false;
419 Halfedge_handle last_he =
420 accessor.insert_at_vertices_ex (curr_he,
421 last_cv, ( cmp_ends(last_cv) == CGAL::SMALLER ? ARR_LEFT_TO_RIGHT : ARR_RIGHT_TO_LEFT),
422 first_he->next(),
423 new_face_created,
424 dummy_swapped_predecessors);
425 // TODO EBEB 2012-08-06 do we have to care if order has been swapped,
426 // or do we have to disallow swapping?
427
428 CGAL_assertion(new_face_created);
429 CGAL_assertion((last_he->face() != last_he->twin()->face()));
430
431 last_he->face()->set_contained(true);
432 }
433
434
435 template <class Traits_, class TopTraits_, class ValidationPolicy>
436 template<class PolygonIter >
437 void Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
insert(PolygonIter p_begin,PolygonIter p_end)438 insert(PolygonIter p_begin, PolygonIter p_end)
439 {
440 typename std::iterator_traits<PolygonIter>::value_type pgn;
441 //check validity of all polygons
442 for(PolygonIter pitr = p_begin; pitr != p_end; ++pitr)
443 {
444 ValidationPolicy::is_valid(*pitr, *m_traits);
445 }
446
447 _insert(p_begin, p_end, pgn);
448 }
449
450 template <class Traits_, class TopTraits_, class ValidationPolicy>
451 template<class PolygonIter, class PolygonWithHolesIter>
452 void Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
insert(PolygonIter p_begin,PolygonIter p_end,PolygonWithHolesIter pwh_begin,PolygonWithHolesIter pwh_end)453 insert(PolygonIter p_begin, PolygonIter p_end,
454 PolygonWithHolesIter pwh_begin, PolygonWithHolesIter pwh_end)
455 {
456 typedef std::list<X_monotone_curve_2> XCurveList;
457 typedef Init_faces_visitor<Arrangement_on_surface_2> My_visitor;
458 typedef Gps_bfs_scanner<Arrangement_on_surface_2, My_visitor> Arr_bfs_scanner;
459
460 XCurveList xcurve_list;
461
462 for( ; p_begin != p_end; ++p_begin)
463 {
464 ValidationPolicy::is_valid(*p_begin, *m_traits);
465 _construct_curves(*p_begin, std::back_inserter(xcurve_list));
466 }
467
468 bool is_unbounded = false;
469 for( ; pwh_begin != pwh_end; ++pwh_begin)
470 {
471 ValidationPolicy::is_valid(*pwh_begin, *m_traits);
472 is_unbounded = (is_unbounded || m_traits->construct_is_unbounded_object()(*pwh_begin));
473 // is_unbounded = (is_unbounded || pwh_begin->is_unbounded());
474 _construct_curves(*pwh_begin, std::back_inserter(xcurve_list));
475 }
476 insert_non_intersecting_curves(*m_arr, xcurve_list.begin(), xcurve_list.end());
477
478 if (is_unbounded)
479 {
480 for (Face_iterator fit = m_arr->faces_begin();
481 fit != m_arr->faces_end(); ++fit)
482 {
483 if (fit->number_of_outer_ccbs() == 0)
484 fit->set_contained(true);
485 }
486 }
487
488 My_visitor v;
489 Arr_bfs_scanner scanner(v);
490 scanner.scan(*m_arr);
491 _reset_faces(m_arr);
492 }
493
494 //insert a range of simple polygons to the arrangement
495 template <class Traits_, class TopTraits_, class ValidationPolicy>
496 template<class PolygonIter>
497 void Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
_insert(PolygonIter p_begin,PolygonIter p_end,Polygon_2 &)498 _insert(PolygonIter p_begin, PolygonIter p_end, Polygon_2 & /*pgn*/)
499 {
500 for(PolygonIter pitr = p_begin; pitr != p_end; ++pitr)
501 {
502 this->_insert(*pitr, *m_arr);
503 }
504 }
505
506 template <class Traits_, class TopTraits_, class ValidationPolicy>
507 template<class PolygonIter>
508 void Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
_insert(PolygonIter p_begin,PolygonIter p_end,Polygon_with_holes_2 &)509 _insert(PolygonIter p_begin, PolygonIter p_end, Polygon_with_holes_2 & /*pgn*/)
510 {
511 typedef std::list<X_monotone_curve_2> XCurveList;
512 typedef Init_faces_visitor<Arrangement_on_surface_2> My_visitor;
513 typedef Gps_bfs_scanner<Arrangement_on_surface_2, My_visitor> Arr_bfs_scanner;
514
515 XCurveList xcurve_list;
516 bool is_unbounded = false;
517 for( ; p_begin != p_end; ++p_begin)
518 {
519 // is_unbounded = (is_unbounded || p_begin->is_unbounded());
520 is_unbounded = (is_unbounded || m_traits->construct_is_unbounded_object()(*p_begin));
521 _construct_curves(*p_begin, std::back_inserter(xcurve_list));
522
523 }
524 insert_non_intersecting_curves(*m_arr, xcurve_list.begin(), xcurve_list.end());
525
526 if (is_unbounded)
527 {
528 for (Face_iterator fit = m_arr->faces_begin();
529 fit != m_arr->faces_end(); ++fit)
530 {
531 if (fit->number_of_outer_ccbs() == 0)
532 fit->set_contained(true);
533 }
534 }
535
536 My_visitor v;
537 Arr_bfs_scanner scanner(v);
538 scanner.scan(*m_arr);
539 _reset_faces(m_arr);
540 }
541
542 //insert non-sipmle poloygons with holes (non incident edges may have
543 // common vertex, but they dont intersect at their interior
544 template <class Traits_, class TopTraits_, class ValidationPolicy>
545 void Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
_insert(const Polygon_with_holes_2 & pgn,Arrangement_on_surface_2 & arr)546 _insert(const Polygon_with_holes_2 & pgn, Arrangement_on_surface_2 & arr)
547 {
548 // inner function not exposed to user - no validation
549 // ValidationPolicy::is_valid(pgn, *m_traits);
550
551 typedef std::list<X_monotone_curve_2> XCurveList;
552 typedef Init_faces_visitor<Arrangement_on_surface_2> My_visitor;
553 typedef Gps_bfs_scanner<Arrangement_on_surface_2, My_visitor> Arr_bfs_scanner;
554
555 XCurveList xcurve_list;
556 _construct_curves(pgn, std::back_inserter(xcurve_list));
557 insert_non_intersecting_curves(arr, xcurve_list.begin(), xcurve_list.end());
558
559 //if (pgn.is_unbounded())
560 if (m_traits->construct_is_unbounded_object()(pgn))
561 {
562 for (Face_iterator fit = arr.faces_begin();
563 fit != arr.faces_end(); ++fit)
564 {
565 if (fit->number_of_outer_ccbs() == 0)
566 fit->set_contained(true);
567 }
568 }
569
570 My_visitor v;
571 Arr_bfs_scanner scanner(v);
572 scanner.scan(arr);
573 _reset_faces(&arr);
574 }
575
576 template <class Traits_, class TopTraits_, class ValidationPolicy>
577 template <class OutputIterator>
578 void
579 Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
_construct_curves(const Polygon_2 & pgn,OutputIterator oi)580 _construct_curves(const Polygon_2 & pgn, OutputIterator oi)
581 {
582 std::pair<Curve_const_iterator, Curve_const_iterator> itr_pair =
583 m_traits->construct_curves_2_object()(pgn);
584 std::copy (itr_pair.first, itr_pair.second, oi);
585 }
586
587 template <class Traits_, class TopTraits_, class ValidationPolicy>
588 template <class OutputIterator>
589 void Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
_construct_curves(const Polygon_with_holes_2 & pgn,OutputIterator oi)590 _construct_curves(const Polygon_with_holes_2 & pgn, OutputIterator oi)
591 {
592 //if (!pgn.is_unbounded())
593 if (!m_traits->construct_is_unbounded_object()(pgn))
594 {
595 const Polygon_2& pgn_boundary =
596 m_traits->construct_outer_boundary_object()(pgn);
597 std::pair<Curve_const_iterator, Curve_const_iterator> itr_pair =
598 m_traits->construct_curves_2_object()(pgn_boundary);
599 std::copy (itr_pair.first, itr_pair.second, oi);
600 }
601 std::pair<GP_Holes_const_iterator, GP_Holes_const_iterator> hpair =
602 m_traits->construct_holes_object()(pgn);
603 GP_Holes_const_iterator hit;
604 for (hit = hpair.first; hit != hpair.second; ++hit)
605 {
606 const Polygon_2& pgn_hole = *hit;
607 std::pair<Curve_const_iterator, Curve_const_iterator> itr_pair =
608 m_traits->construct_curves_2_object()(pgn_hole);
609 std::copy (itr_pair.first, itr_pair.second, oi);
610 }
611 }
612
613 template <class Traits_, class TopTraits_, class ValidationPolicy>
614 template <class OutputIterator>
615 OutputIterator
616 Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
polygons_with_holes(OutputIterator out)617 polygons_with_holes(OutputIterator out) const
618 {
619 typedef Arr_bfs_scanner<Arrangement_on_surface_2, OutputIterator> Arr_bfs_scanner;
620 Arr_bfs_scanner scanner(this->m_traits, out);
621 scanner.scan(*(this->m_arr));
622 return (scanner.output_iterator());
623 }
624
625
626 template <class Traits_, class TopTraits_, class ValidationPolicy>
627 typename Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::Size
628 Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
number_of_polygons_with_holes()629 number_of_polygons_with_holes() const
630 {
631
632 typedef Arr_bfs_scanner<Arrangement_on_surface_2, Counting_output_iterator>
633 Arr_bfs_scanner;
634 //counting_output_operator CTOR reqires a parameter
635 std::size_t cc = 0;
636 Arr_bfs_scanner scanner(this->m_traits, Counting_output_iterator(&cc));
637 scanner.scan(*(this->m_arr));
638 return (scanner.output_iterator().current_counter());
639 }
640
641
642 template <class Traits_, class TopTraits_, class ValidationPolicy>
643 bool Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
locate(const Point_2 & q,Polygon_with_holes_2 & pgn)644 locate(const Point_2& q, Polygon_with_holes_2& pgn) const
645 {
646 Point_location pl(*m_arr);
647
648 Object obj = pl.locate(q);
649 Face_const_iterator f;
650 if (CGAL::assign(f, obj))
651 {
652 if (!f->contained())
653 return false;
654 }
655 else
656 {
657 Halfedge_const_handle he;
658 if (CGAL::assign(he, obj))
659 {
660 if (he->face()->contained())
661 f = he->face();
662 else
663 {
664 CGAL_assertion(he->twin()->face()->contained());
665 f = he->twin()->face();
666 }
667 }
668 else
669 {
670 Vertex_const_handle v;
671 CGAL_assertion(CGAL::assign(v, obj));
672 CGAL::assign(v, obj);
673 Halfedge_around_vertex_const_circulator hav = v->incident_halfedges();
674 Halfedge_const_handle he = hav;
675 if (he->face()->contained())
676 f = he->face();
677 else
678 {
679 CGAL_assertion(he->twin()->face()->contained());
680 f = he->twin()->face();
681 }
682 }
683 }
684
685 typedef Oneset_iterator<Polygon_with_holes_2> OutputItr;
686 typedef Arr_bfs_scanner<Arrangement_on_surface_2, OutputItr> Arr_bfs_scanner;
687
688 OutputItr oi (pgn);
689 Arr_bfs_scanner scanner(this->m_traits, oi);
690
691
692 Ccb_halfedge_const_circulator ccb_of_pgn = get_boundary_of_polygon(f);
693 this->_reset_faces();
694 if (ccb_of_pgn == Ccb_halfedge_const_circulator())
695 {
696 // the polygon has no boundary
697
698 // f is unbounded
699 for (Face_iterator fit = m_arr->faces_begin(); fit != m_arr->faces_end();
700 ++fit)
701 {
702 if (fit->number_of_outer_ccbs() == 0)
703 scanner.scan_contained_ubf(fit);
704 }
705 }
706 else
707 {
708 Halfedge_const_handle he_of_pgn = ccb_of_pgn;
709 this->_reset_faces();
710 he_of_pgn->face()->set_visited(true);
711 scanner.scan_ccb(ccb_of_pgn);
712 }
713
714 this->_reset_faces();
715 return true;
716 }
717
718 template <class Traits_, class TopTraits_, class ValidationPolicy>
719 typename Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::Ccb_halfedge_const_circulator
720 Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
get_boundary_of_polygon(Face_const_iterator f)721 get_boundary_of_polygon(Face_const_iterator f) const
722 {
723 CGAL_assertion(!f->visited());
724 f->set_visited(true);
725
726 if (f->number_of_outer_ccbs() == 0) // (f->is_unbounded())
727 {
728 return Ccb_halfedge_const_circulator();
729 }
730
731 // We assume that a polygon has only one outer_ccb. This code does not handle
732 // the case where there are more than 1 outer ccbs. If this is the case, we
733 // need to devise a method to convert the outer ccbs to inner ccbs so we
734 // will have only one outer ccb.
735 if (f->number_of_outer_ccbs() > 1)
736 CGAL_error_msg("Not implemented yet.");
737
738 // Some compilers (VC 9) do not like that we directly access the ccb_circ. So we have
739 // to pass through the iterator.
740 Outer_ccb_const_iterator oci_temp = f->outer_ccbs_begin();
741 Ccb_halfedge_const_circulator ccb_end = *oci_temp;
742 Ccb_halfedge_const_circulator ccb_circ = ccb_end;
743 do
744 {
745 //get the current halfedge on the face boundary
746 Halfedge_const_iterator he = ccb_circ;
747 Face_const_iterator new_f = he->twin()->face();
748 if (!new_f->visited())
749 {
750 if (is_hole_of_face(new_f, he) && !new_f->contained())
751 return (he->twin());
752 return (get_boundary_of_polygon(new_f));
753 }
754 ++ccb_circ;
755 }
756 while(ccb_circ != ccb_end);
757 CGAL_error();
758 return Ccb_halfedge_const_circulator();
759
760 }
761
762 template <class Traits_, class TopTraits_, class ValidationPolicy>
763 bool Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
is_hole_of_face(Face_const_handle f,Halfedge_const_handle he)764 is_hole_of_face(Face_const_handle f, Halfedge_const_handle he) const
765 {
766 Inner_ccb_const_iterator holes_it;
767 for (holes_it = f->inner_ccbs_begin();
768 holes_it != f->inner_ccbs_end(); ++holes_it)
769 {
770 Ccb_halfedge_const_circulator ccb = *holes_it;
771 Ccb_halfedge_const_circulator ccb_end = ccb;
772 do
773 {
774 Halfedge_const_handle he_inside_hole = ccb;
775 he_inside_hole = he_inside_hole->twin();
776 if (he == he_inside_hole)
777 return true;
778
779 ++ccb;
780 }
781 while(ccb != ccb_end);
782 }
783
784 return false;
785 }
786
787 } // namespace CGAL
788
789 #endif // CGAL_GPS_UTILS_H
790