1 // Copyright (c) 2005,2006,2007,2008,2009,2010,2011,2012,2013 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/Arrangement_on_surface_2/include/CGAL/Arrangement_2/Arrangement_on_surface_2_impl.h $
7 // $Id: Arrangement_on_surface_2_impl.h dc36cee 2021-03-10T11:53:16+01:00 Laurent Rineau
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 // Author(s): Ron Wein <wein@post.tau.ac.il>
11 // Efi Fogel <efif@post.tau.ac.il>
12 // Eric Berberich <eric.berberich@cgal.org>
13 // (based on old version by: Iddo Hanniel,
14 // Eyal Flato,
15 // Oren Nechushtan,
16 // Ester Ezra,
17 // Shai Hirsch,
18 // and Eugene Lipovetsky)
19
20 #ifndef CGAL_ARRANGEMENT_ON_SURFACE_2_IMPL_H
21 #define CGAL_ARRANGEMENT_ON_SURFACE_2_IMPL_H
22
23 #include <CGAL/license/Arrangement_on_surface_2.h>
24
25 #ifndef CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
26 #define CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE 0
27 #endif
28
29 /*! \file
30 * Member-function definitions for the Arrangement_2<GeomTraits, TopTraits>
31 * class-template.
32 */
33
34 #include <boost/variant.hpp>
35
36 #include <CGAL/function_objects.h>
37 #include <CGAL/use.h>
38
39 namespace CGAL {
40
41 //-----------------------------------------------------------------------------
42 // Default constructor.
43 //
44 template <typename GeomTraits, typename TopTraits>
Arrangement_on_surface_2()45 Arrangement_on_surface_2<GeomTraits, TopTraits>::Arrangement_on_surface_2() :
46 m_topol_traits()
47 {
48 typedef has_Left_side_category<GeomTraits> Cond_left;
49 typedef internal::Validate_left_side_category<GeomTraits, Cond_left::value>
50 Validate_left_side_category;
51 void (Validate_left_side_category::*pleft)(void) =
52 &Validate_left_side_category::template missing__Left_side_category<int>;
53 (void)pleft;
54
55 typedef has_Bottom_side_category<GeomTraits> Cond_bottom;
56 typedef internal::Validate_bottom_side_category<GeomTraits,
57 Cond_bottom::value>
58 Validate_bottom_side_category;
59 void (Validate_bottom_side_category::*pbottom)(void) =
60 &Validate_bottom_side_category::template missing__Bottom_side_category<int>;
61 (void)pbottom;
62
63 typedef has_Top_side_category<GeomTraits> Cond_top;
64 typedef internal::Validate_top_side_category<GeomTraits, Cond_top::value>
65 Validate_top_side_category;
66 void (Validate_top_side_category::*ptop)(void) =
67 &Validate_top_side_category::template missing__Top_side_category<int>;
68 (void)ptop;
69
70 typedef has_Right_side_category<GeomTraits> Cond_right;
71 typedef internal::Validate_right_side_category<GeomTraits, Cond_right::value>
72 Validate_right_side_category;
73 void (Validate_right_side_category::*pright)(void) =
74 &Validate_right_side_category::template missing__Right_side_category<int>;
75 (void)pright;
76
77 // Initialize the DCEL structure to represent an empty arrangement.
78 m_topol_traits.init_dcel();
79
80 // Allocate the traits.
81 m_geom_traits = new Traits_adaptor_2;
82 m_own_traits = true;
83 }
84
85 //-----------------------------------------------------------------------------
86 // Copy constructor.
87 //
88 template <typename GeomTraits, typename TopTraits>
89 Arrangement_on_surface_2<GeomTraits, TopTraits>::
Arrangement_on_surface_2(const Self & arr)90 Arrangement_on_surface_2(const Self& arr) :
91 m_geom_traits(nullptr),
92 m_own_traits(false)
93 {
94 assign(arr);
95 }
96
97 //-----------------------------------------------------------------------------
98 // Constructor given a traits object.
99 //
100 template <typename GeomTraits, typename TopTraits>
101 Arrangement_on_surface_2<GeomTraits, TopTraits>::
Arrangement_on_surface_2(const Geometry_traits_2 * geom_traits)102 Arrangement_on_surface_2(const Geometry_traits_2* geom_traits) :
103 m_topol_traits(geom_traits)
104 {
105 typedef has_Left_side_category<GeomTraits> Cond_left;
106 typedef internal::Validate_left_side_category<GeomTraits, Cond_left::value>
107 Validate_left_side_category;
108 void (Validate_left_side_category::*pleft)(void) =
109 &Validate_left_side_category::template missing__Left_side_category<int>;
110 (void)pleft;
111
112 typedef has_Bottom_side_category<GeomTraits> Cond_bottom;
113 typedef internal::Validate_bottom_side_category<GeomTraits,
114 Cond_bottom::value>
115 Validate_bottom_side_category;
116 void (Validate_bottom_side_category::*pbottom)(void) =
117 &Validate_bottom_side_category::template missing__Bottom_side_category<int>;
118 (void)pbottom;
119
120 typedef has_Top_side_category<GeomTraits> Cond_top;
121 typedef internal::Validate_top_side_category<GeomTraits, Cond_top::value>
122 Validate_top_side_category;
123 void (Validate_top_side_category::*ptop)(void) =
124 &Validate_top_side_category::template missing__Top_side_category<int>;
125 (void)ptop;
126
127 typedef has_Right_side_category<GeomTraits> Cond_right;
128 typedef internal::Validate_right_side_category<GeomTraits, Cond_right::value>
129 Validate_right_side_category;
130 void (Validate_right_side_category::*pright)(void) =
131 &Validate_right_side_category::template missing__Right_side_category<int>;
132 (void)pright;
133
134 // Initialize the DCEL structure to represent an empty arrangement.
135 m_topol_traits.init_dcel();
136
137 // Set the traits.
138 m_geom_traits = static_cast<const Traits_adaptor_2*>(geom_traits);
139 m_own_traits = false;
140 }
141
142 //-----------------------------------------------------------------------------
143 // Assignment operator.
144 //
145 template <typename GeomTraits, typename TopTraits>
146 Arrangement_on_surface_2<GeomTraits, TopTraits>&
147 Arrangement_on_surface_2<GeomTraits, TopTraits>::operator=(const Self& arr)
148 {
149 if (this == &arr) return (*this); // handle self-assignment
150 assign(arr);
151 return (*this);
152 }
153
154 //-----------------------------------------------------------------------------
155 // Assign an arrangement.
156 //
157 template <typename GeomTraits, typename TopTraits>
assign(const Self & arr)158 void Arrangement_on_surface_2<GeomTraits, TopTraits>::assign(const Self& arr)
159 {
160 // Clear the current contents of the arrangement.
161 clear();
162
163 // Notify the observers that an assignment is to take place.
164 _notify_before_assign(arr);
165
166 // Assign the topology-traits object.
167 m_topol_traits.assign(arr.m_topol_traits);
168
169 // Go over the vertices and create duplicates of the stored points.
170 Point_2* dup_p;
171 DVertex* p_v;
172
173 typename Dcel::Vertex_iterator vit;
174 for (vit = _dcel().vertices_begin(); vit != _dcel().vertices_end(); ++vit) {
175 p_v = &(*vit);
176
177 if (! p_v->has_null_point()) {
178 // Create the duplicate point and store it in the points container.
179 dup_p = _new_point(p_v->point());
180
181 // Associate the vertex with the duplicated point.
182 p_v->set_point(dup_p);
183 }
184 }
185
186 // Go over the edge and create duplicates of the stored curves.
187 typename Dcel::Edge_iterator eit;
188 for (eit = _dcel().edges_begin(); eit != _dcel().edges_end(); ++eit) {
189 DHalfedge* p_e = &(*eit);
190
191 if (! p_e->has_null_curve()) {
192 // Create the duplicate curve and store it in the curves container.
193 X_monotone_curve_2* dup_cv = _new_curve(p_e->curve());
194
195 // Associate the halfedge (and its twin) with the duplicated curve.
196 p_e->set_curve(dup_cv);
197 }
198 }
199
200 // Take care of the traits object.
201 if (m_own_traits && (m_geom_traits != nullptr)) {
202 delete m_geom_traits;
203 m_geom_traits = nullptr;
204 }
205
206 m_geom_traits = (arr.m_own_traits) ? new Traits_adaptor_2 : arr.m_geom_traits;
207 m_own_traits = arr.m_own_traits;
208
209 // Notify the observers that the assignment has been performed.
210 _notify_after_assign();
211 }
212
213 //-----------------------------------------------------------------------------
214 // Destructor.
215 //
216 template <typename GeomTraits, typename TopTraits>
~Arrangement_on_surface_2()217 Arrangement_on_surface_2<GeomTraits, TopTraits>::~Arrangement_on_surface_2()
218 {
219 // Free all stored points.
220 typename Dcel::Vertex_iterator vit;
221 for (vit = _dcel().vertices_begin(); vit != _dcel().vertices_end(); ++vit)
222 if (! vit->has_null_point())
223 _delete_point(vit->point());
224
225 // Free all stores curves.
226 typename Dcel::Edge_iterator eit;
227 for (eit = _dcel().edges_begin(); eit != _dcel().edges_end(); ++eit)
228 if (! eit->has_null_curve())
229 _delete_curve(eit->curve());
230
231 // Free the traits object, if necessary.
232 if (m_own_traits && (m_geom_traits != nullptr)) {
233 delete m_geom_traits;
234 m_geom_traits = nullptr;
235 }
236
237 // Detach all observers still attached to the arrangement.
238 Observers_iterator iter = m_observers.begin();
239 Observers_iterator next;
240 Observers_iterator end = m_observers.end();
241
242 while (iter != end) {
243 next = iter;
244 ++next;
245 (*iter)->detach();
246 iter = next;
247 }
248 }
249
250 //-----------------------------------------------------------------------------
251 // Clear the arrangement.
252 //
253 template <typename GeomTraits, typename TopTraits>
clear()254 void Arrangement_on_surface_2<GeomTraits, TopTraits>::clear()
255 {
256 // Notify the observers that we are about to clear the arragement.
257 _notify_before_clear();
258
259 // Free all stored points.
260 typename Dcel::Vertex_iterator vit;
261 for (vit = _dcel().vertices_begin(); vit != _dcel().vertices_end(); ++vit)
262 if (! vit->has_null_point()) _delete_point(vit->point());
263
264 // Free all stores curves.
265 typename Dcel::Edge_iterator eit;
266 for (eit = _dcel().edges_begin(); eit != _dcel().edges_end(); ++eit)
267 if (! eit->has_null_curve()) _delete_curve(eit->curve());
268
269 // Clear the DCEL and construct an empty arrangement.
270 _dcel().delete_all();
271 m_topol_traits.init_dcel();
272
273 // Notify the observers that we have just cleared the arragement.
274 _notify_after_clear();
275 }
276
277 //-----------------------------------------------------------------------------
278 // Insert a point as an isolated vertex in the interior of a given face.
279 //
280 template <typename GeomTraits, typename TopTraits>
281 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Vertex_handle
282 Arrangement_on_surface_2<GeomTraits, TopTraits>::
insert_in_face_interior(const Point_2 & p,Face_handle f)283 insert_in_face_interior(const Point_2& p, Face_handle f)
284 {
285 DFace* p_f = _face(f);
286
287 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
288 std::cout << "Aos_2: insert_in_face_interior (interface)" << std::endl;
289 std::cout << "pt : " << p << std::endl;
290 std::cout << "face : " << &(*f) << std::endl;
291 #endif
292
293 // Create a new vertex associated with the given point.
294 // We assume the point has no boundary conditions.
295 DVertex* v = _create_vertex(p);
296 Vertex_handle vh(v);
297
298 // Insert v as an isolated vertex inside the given face.
299 _insert_isolated_vertex(p_f, v);
300
301 // Return a handle to the new isolated vertex.
302 return vh;
303 }
304
305 //-----------------------------------------------------------------------------
306 // Insert an x-monotone curve into the arrangement as a new hole (inner
307 // component) inside the given face.
308 //
309 template <typename GeomTraits, typename TopTraits>
310 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
311 Arrangement_on_surface_2<GeomTraits, TopTraits>::
insert_in_face_interior(const X_monotone_curve_2 & cv,Face_handle f)312 insert_in_face_interior(const X_monotone_curve_2& cv, Face_handle f)
313 {
314 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
315 std::cout << "Aos_2: insert_in_face_interior (interface)" << std::endl;
316 std::cout << "cv : " << cv << std::endl;
317 std::cout << "face : " << &(*f) << std::endl;
318 #endif
319
320 DFace* p_f = _face(f);
321
322 // Check if cv's left end has boundary conditions, and obtain a vertex v1
323 // that corresponds to this end.
324 const Arr_parameter_space ps_x1 =
325 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MIN_END);
326 const Arr_parameter_space ps_y1 =
327 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MIN_END);
328 DHalfedge* fict_prev1 = nullptr;
329
330 DVertex* v1 = ((ps_x1 == ARR_INTERIOR) && (ps_y1 == ARR_INTERIOR)) ?
331 // The curve has a valid left endpoint: Create a new vertex associated
332 // with the curve's left endpoint.
333 _create_vertex(m_geom_traits->construct_min_vertex_2_object()(cv)) :
334 // Locate the DCEL features that will be used for inserting the curve's
335 // left end.
336 _place_and_set_curve_end(p_f, cv, ARR_MIN_END, ps_x1, ps_y1, &fict_prev1);
337
338 // Check if cv's right end has boundary conditions, and obtain a vertex v2
339 // that corresponds to this end.
340 const Arr_parameter_space ps_x2 =
341 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END);
342 const Arr_parameter_space ps_y2 =
343 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END);
344 DHalfedge* fict_prev2 = nullptr;
345
346 DVertex* v2 = ((ps_x2 == ARR_INTERIOR) && (ps_y2 == ARR_INTERIOR)) ?
347 // The curve has a valid right endpoint: Create a new vertex associated
348 // with the curve's right endpoint.
349 _create_vertex(m_geom_traits->construct_max_vertex_2_object()(cv)) :
350 // Locate the DCEL features that will be used for inserting the curve's
351 // right end.
352 _place_and_set_curve_end(p_f, cv, ARR_MAX_END, ps_x2, ps_y2, &fict_prev2);
353
354 // Create the edge connecting the two vertices (note we know v1 is
355 // lexicographically smaller than v2).
356 DHalfedge* new_he;
357
358 if ((fict_prev1 == nullptr) && (fict_prev2 == nullptr))
359 // Both vertices represent valid points.
360 new_he = _insert_in_face_interior(p_f, cv, ARR_LEFT_TO_RIGHT, v1, v2);
361 else if ((fict_prev1 == nullptr) && (fict_prev2 != nullptr)) {
362 // v1 represents a valid point and v2 is inserted using its predecessor.
363 new_he = _insert_from_vertex(fict_prev2, cv, ARR_RIGHT_TO_LEFT, v1);
364 new_he = new_he->opposite();
365 }
366 else if ((fict_prev1 != nullptr) && (fict_prev2 == nullptr))
367 // v1 is inserted using its predecessor and v2 represents a valid point.
368 new_he = _insert_from_vertex(fict_prev1, cv, ARR_LEFT_TO_RIGHT, v2);
369 else {
370 // Both vertices are inserted using their predecessor halfedges.
371
372 // Comment:
373 // In case the inserted curve has two vertical asymptotes at the top
374 // it happens that fict_prev1 is split by the max end and becomes the
375 // prev edge, which is fict_prev2. Since both pointers are equal they
376 // both point to the max end. Thus, we advance fict_prev1 by one
377 // such that it points to the min end again.
378 // Note that this only happens at the top. At the bottom everything
379 // goes fine since the insertion order is reverted with respect to the
380 // orientation of the edges.
381 //
382 // In the other function such a fix is not needed, as at most one
383 // curve-end reaches the boundary. It is also not possible to delay
384 // it to _insert_at_vertices, as that expects the two predecessor
385 // halfedges as input. An early detecting is also not possible
386 // (i.e.~in _place_and_set_curve_end), as that needs to know to be
387 // called from here!
388 if (fict_prev1 == fict_prev2) fict_prev1 = fict_prev1->next();
389
390 // Note that in this case we may create a new face.
391 bool new_face_created = false;
392 bool check_swapped_predecessors = false;
393 new_he = _insert_at_vertices(fict_prev1, cv, ARR_LEFT_TO_RIGHT,
394 fict_prev2->next(), new_face_created,
395 check_swapped_predecessors);
396 // Comment EBEB 2012-10-21: Swapping does not take place as there is no local minumum so far
397 CGAL_assertion(!check_swapped_predecessors);
398 // usually one would expect to have an new_he (and its twin) lying on the
399 // same _inner_ CCB ...
400
401 if (new_face_created) {
402 // ... but in case that a new face got created new_he should lie on an
403 // outer CCB
404 CGAL_assertion(new_he->is_on_outer_ccb());
405 // Note! new_he is not needed to define the new outer CCB of the new face
406 // Here, it can be the outer ccb of the old face, as there is also not
407 // swapping taking place!
408
409 // In case a new face has been created (pointed by the new halfedge we
410 // obtained), we have to examine the holes and isolated vertices in the
411 // existing face (pointed by the twin halfedge) and move the relevant
412 // holes and isolated vertices into the new face.
413 _relocate_in_new_face(new_he);
414 }
415 }
416
417 // Return a handle to the new halfedge directed from left to right.
418 CGAL_postcondition(new_he->direction() == ARR_LEFT_TO_RIGHT);
419 return (Halfedge_handle(new_he));
420 }
421
422 //-----------------------------------------------------------------------------
423 // Insert an x-monotone curve into the arrangement, such that its left
424 // endpoint corresponds to a given arrangement vertex.
425 //
426 template <typename GeomTraits, typename TopTraits>
427 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
428 Arrangement_on_surface_2<GeomTraits, TopTraits>::
insert_from_left_vertex(const X_monotone_curve_2 & cv,Vertex_handle v,Face_handle f)429 insert_from_left_vertex(const X_monotone_curve_2& cv,
430 Vertex_handle v,
431 Face_handle f)
432 {
433 CGAL_precondition_code
434 (const bool at_obnd1 =
435 !m_geom_traits->is_closed_2_object()(cv, ARR_MIN_END));
436 CGAL_precondition_msg
437 ((! at_obnd1 &&
438 m_geom_traits->equal_2_object()
439 (v->point(),
440 m_geom_traits->construct_min_vertex_2_object()(cv))) ||
441 (at_obnd1 && v->is_at_open_boundary()),
442 "The input vertex should be the left curve end.");
443
444 // Check if cv's right end has boundary conditions. If not, create a vertex
445 // that corresponds to the right endpoint.
446 const Arr_parameter_space ps_x2 =
447 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END);
448 const Arr_parameter_space ps_y2 =
449 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END);
450 DVertex* v2 = nullptr;
451 DHalfedge* fict_prev2 = nullptr;
452
453 if ((ps_x2 == ARR_INTERIOR) && (ps_y2 == ARR_INTERIOR))
454 // The curve has a valid right endpoint: Create a new vertex associated
455 // with the curve's right endpoint.
456 v2 = _create_vertex(m_geom_traits->construct_max_vertex_2_object()(cv));
457
458 // Check if the given vertex, corresponding to the left curve end, has no
459 // incident edges.
460 if (v->degree() == 0) {
461 // The given vertex is an isolated one: We should in fact insert the curve
462 // in the interior of the face containing this vertex.
463 DVertex* v1 = _vertex(v);
464 DIso_vertex* iv = nullptr;
465 DFace* p_f = nullptr;
466
467 if (v->is_isolated()) {
468 // Obtain the face from the isolated vertex.
469 iv = v1->isolated_vertex();
470 p_f = iv->face();
471 }
472 else {
473 // In this case the face that contains v should be provided by the user.
474 CGAL_precondition(f != Face_handle());
475 p_f = _face(f);
476 }
477
478 // If the vertex that corresponds to cv's right end has boundary
479 // conditions, create it now.
480 if (v2 == nullptr)
481 // Locate the DCEL features that will be used for inserting the curve's
482 // right end.
483 v2 = _place_and_set_curve_end(p_f, cv, ARR_MAX_END, ps_x2, ps_y2,
484 &fict_prev2);
485
486 if (iv != nullptr) {
487 // Remove the isolated vertex v1, as it will not be isolated any more.
488 p_f->erase_isolated_vertex(iv);
489 _dcel().delete_isolated_vertex(iv);
490 }
491
492 // Create the edge connecting the two vertices (note that we know that
493 // v1 is smaller than v2).
494 DHalfedge* new_he;
495 if (fict_prev2 == nullptr)
496 new_he = _insert_in_face_interior(p_f, cv, ARR_LEFT_TO_RIGHT, v1, v2);
497 else {
498 new_he = _insert_from_vertex(fict_prev2, cv, ARR_RIGHT_TO_LEFT, v1);
499 new_he = new_he->opposite();
500 }
501
502 // Return a handle to the new halfedge directed from v1 to v2.
503 CGAL_postcondition(new_he->direction() == ARR_LEFT_TO_RIGHT);
504 return (Halfedge_handle(new_he));
505 }
506
507 // Go over the incident halfedges around v and find the halfedge after
508 // which the new curve should be inserted.
509 DHalfedge* prev1 = _locate_around_vertex(_vertex(v), cv, ARR_MIN_END);
510 CGAL_assertion_msg
511 (prev1 != nullptr,
512 "The inserted curve cannot be located in the arrangement.");
513
514 DFace* f1 = prev1->is_on_inner_ccb() ? prev1->inner_ccb()->face() :
515 prev1->outer_ccb()->face();
516
517 // If the vertex that corresponds to cv's right end has boundary conditions,
518 // create it now.
519 if (v2 == nullptr)
520 // Locate the DCEL features that will be used for inserting the curve's
521 // right end.
522 v2 =
523 _place_and_set_curve_end(f1, cv, ARR_MAX_END, ps_x2, ps_y2, &fict_prev2);
524
525 // Perform the insertion (note that we know that prev1->vertex is smaller
526 // than v2).
527 DHalfedge* new_he;
528
529 if (fict_prev2 == nullptr)
530 // Insert the halfedge given the predecessor halfedge of v1.
531 new_he = _insert_from_vertex(prev1, cv, ARR_LEFT_TO_RIGHT, v2);
532 else {
533 // Insert the halfedge given the two predecessor halfedges.
534 // Note that in this case we may create a new face.
535 bool new_face_created = false;
536 bool check_swapped_predecessors = false;
537 new_he = _insert_at_vertices(prev1, cv, ARR_LEFT_TO_RIGHT,
538 fict_prev2->next(),
539 new_face_created, check_swapped_predecessors);
540 // Comment EBEB 2012-10-21: Swapping does not take place as the insertion
541 // merges the CCB as an "interior" extension into an outer CCB of a face
542 // incident the parameter space's boundary.
543 CGAL_assertion(!check_swapped_predecessors);
544
545 if (new_face_created) {
546 CGAL_assertion(new_he->is_on_outer_ccb());
547 // Note! new_he is not needed to define the new outer CCB of the new face
548 // Here, it can be the outer ccb of the old face, as there is also not
549 // swapping taking place!
550
551 // In case a new face has been created (pointed by the new halfedge we
552 // obtained), we have to examine the holes and isolated vertices in the
553 // existing face (pointed by the twin halfedge) and move the relevant
554 // holes and isolated vertices into the new face.
555 _relocate_in_new_face(new_he);
556 }
557 }
558
559 // Return a handle to the halfedge directed toward the new vertex v2.
560 CGAL_postcondition(new_he->direction() == ARR_LEFT_TO_RIGHT);
561 return (Halfedge_handle(new_he));
562 }
563
564 //-----------------------------------------------------------------------------
565 // Insert an x-monotone curve into the arrangement, such that one its left
566 // endpoint corresponds to a given arrangement vertex, given the exact place
567 // for the curve in the circular list around this vertex.
568 //
569 template <typename GeomTraits, typename TopTraits>
570 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
571 Arrangement_on_surface_2<GeomTraits, TopTraits>::
insert_from_left_vertex(const X_monotone_curve_2 & cv,Halfedge_handle prev)572 insert_from_left_vertex(const X_monotone_curve_2& cv, Halfedge_handle prev)
573 {
574 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
575 std::cout << "Aos_2: insert_from_left_vertex (interface)" << std::endl;
576 std::cout << "cv : " << cv << std::endl;
577 if (!prev->is_fictitious()) {
578 std::cout << "prev : " << prev ->curve() << std::endl;
579 } else {
580 std::cout << "prev : fictitious" << std::endl;
581 }
582 std::cout << "dir : " << prev->direction() << std::endl;
583 #endif
584
585 CGAL_precondition_code
586 (const bool at_obnd1 =
587 !m_geom_traits->is_closed_2_object()(cv, ARR_MIN_END));
588 CGAL_precondition_msg
589 ((! at_obnd1 &&
590 m_geom_traits->equal_2_object()
591 (prev->target()->point(),
592 m_geom_traits->construct_min_vertex_2_object()(cv))) ||
593 (at_obnd1 && prev->target()->is_at_open_boundary()),
594 "The target of the input halfedge should be the left curve end.");
595
596 CGAL_precondition_msg
597 (at_obnd1 || _locate_around_vertex(_vertex(prev->target()),
598 cv, ARR_MIN_END) == _halfedge(prev),
599 "In the clockwise order of curves around the vertex, "
600 " cv must succeed the curve of prev.");
601
602 // Get the predecessor halfedge for the insertion of the left curve end.
603 DHalfedge* prev1 = _halfedge(prev);
604 DFace* f1 = _face(prev->face());
605
606 // Check if cv's right end has boundary conditions, and obtain a vertex
607 // that corresponds to this end.
608 const Arr_parameter_space ps_x2 =
609 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END);
610 const Arr_parameter_space ps_y2 =
611 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END);
612 DHalfedge* fict_prev2 = nullptr;
613
614 DVertex* v2 = ((ps_x2 == ARR_INTERIOR) && (ps_y2 == ARR_INTERIOR)) ?
615 // The curve has a valid right endpoint: Create a new vertex associated
616 // with the curve's right endpoint.
617 _create_vertex(m_geom_traits->construct_max_vertex_2_object()(cv)) :
618 // Locate the DCEL features that will be used for inserting the curve's
619 // right end.
620 _place_and_set_curve_end(f1, cv, ARR_MAX_END, ps_x2, ps_y2, &fict_prev2);
621
622 // Perform the insertion (note that we know that prev1->vertex is smaller
623 // than v2).
624 DHalfedge* new_he;
625
626 if (fict_prev2 == nullptr)
627 // Insert the halfedge given the predecessor halfedge of the left vertex.
628 new_he = _insert_from_vertex(prev1, cv, ARR_LEFT_TO_RIGHT, v2);
629 else {
630 // Insert the halfedge given the two predecessor halfedges.
631 // Note that in this case we may create a new face.
632 bool new_face_created = false;
633 bool check_swapped_predecessors = false;
634 new_he = _insert_at_vertices(prev1, cv, ARR_LEFT_TO_RIGHT,
635 fict_prev2->next(), new_face_created,
636 check_swapped_predecessors);
637 // Comment EBEB 2012-10-21: Swapping does not take place as the insertion
638 // merges the CCB as an "interior" extension into an outer CCB of a face
639 // incident the parameter space's boundary.
640 CGAL_assertion(!check_swapped_predecessors);
641
642 if (new_face_created) {
643 CGAL_assertion(new_he->is_on_outer_ccb());
644 // Note! new_he is not needed to define the new outer CCB of the new face
645 // Here, it can be the outer ccb of the old face, as there is also not
646 // swapping taking place!
647
648 // In case a new face has been created (pointed by the new halfedge we
649 // obtained), we have to examine the holes and isolated vertices in the
650 // existing face (pointed by the twin halfedge) and move the relevant
651 // holes and isolated vertices into the new face.
652 _relocate_in_new_face(new_he);
653 }
654 }
655
656 // Return a handle to the halfedge directed toward the new vertex v2.
657 CGAL_postcondition(new_he->direction() == ARR_LEFT_TO_RIGHT);
658 return (Halfedge_handle(new_he));
659 }
660
661 //-----------------------------------------------------------------------------
662 // Insert an x-monotone curve into the arrangement, such that its right
663 // endpoint corresponds to a given arrangement vertex.
664 //
665 template <typename GeomTraits, typename TopTraits>
666 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
667 Arrangement_on_surface_2<GeomTraits, TopTraits>::
insert_from_right_vertex(const X_monotone_curve_2 & cv,Vertex_handle v,Face_handle f)668 insert_from_right_vertex(const X_monotone_curve_2& cv,
669 Vertex_handle v, Face_handle f)
670 {
671 CGAL_precondition_code
672 (const bool at_obnd2 =
673 !m_geom_traits->is_closed_2_object()(cv, ARR_MAX_END));
674 CGAL_precondition_msg
675 ((! at_obnd2 &&
676 m_geom_traits->equal_2_object()
677 (v->point(),
678 m_geom_traits->construct_max_vertex_2_object()(cv))) ||
679 (at_obnd2 && v->is_at_open_boundary()),
680 "The input vertex should be the right curve end.");
681
682 // Check if cv's left end has boundary conditions. If not, create a vertex
683 // that corresponds to the left endpoint.
684 const Arr_parameter_space ps_x1 =
685 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MIN_END);
686 const Arr_parameter_space ps_y1 =
687 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MIN_END);
688 DVertex* v1 = nullptr;
689 DHalfedge* fict_prev1 = nullptr;
690
691 if ((ps_x1 == ARR_INTERIOR) && (ps_y1 == ARR_INTERIOR))
692 // The curve has a valid left endpoint: Create a new vertex associated
693 // with the curve's left endpoint.
694 v1 = _create_vertex(m_geom_traits->construct_min_vertex_2_object()(cv));
695
696 // Check if the given vertex, corresponding to the right curve end, has no
697 // incident edges.
698 if (v->degree() == 0) {
699 // The given vertex is an isolated one: We should in fact insert the curve
700 // in the interior of the face containing this vertex.
701 DVertex* v2 = _vertex(v);
702 DIso_vertex* iv = nullptr;
703 DFace* p_f = nullptr;
704
705 if (v->is_isolated()) {
706 // Obtain the face from the isolated vertex.
707 iv = v2->isolated_vertex();
708 p_f = iv->face();
709 }
710 else {
711 // In this case the face that contains v should be provided by the user.
712 CGAL_precondition(f != Face_handle());
713 p_f = _face(f);
714 }
715
716 // If the vertex that corresponds to cv's left end has boundary
717 // conditions, create it now.
718 if (v1 == nullptr)
719 // Locate the DCEL features that will be used for inserting the curve's
720 // left end.
721 v1 = _place_and_set_curve_end(p_f, cv, ARR_MIN_END, ps_x1, ps_y1,
722 &fict_prev1);
723
724 if (iv != nullptr) {
725 // Remove the isolated vertex v2, as it will not be isolated any more.
726 p_f->erase_isolated_vertex(iv);
727 _dcel().delete_isolated_vertex(iv);
728 }
729
730 // Create the edge connecting the two vertices (note that we know that
731 // v1 is smaller than v2).
732 DHalfedge* new_he = (fict_prev1 == nullptr) ?
733 _insert_in_face_interior(p_f, cv, ARR_LEFT_TO_RIGHT, v1, v2) :
734 _insert_from_vertex(fict_prev1, cv, ARR_LEFT_TO_RIGHT, v2);
735
736 // Return a handle to the new halfedge whose target is the new vertex v1.
737 CGAL_postcondition(new_he->opposite()->direction() == ARR_RIGHT_TO_LEFT);
738 return (Halfedge_handle(new_he->opposite()));
739 }
740
741 // Go over the incident halfedges around v and find the halfedge after
742 // which the new curve should be inserted.
743 DHalfedge* prev2 = _locate_around_vertex(_vertex(v), cv, ARR_MAX_END);
744 CGAL_assertion_msg
745 (prev2 != nullptr, "The inserted curve cannot be located in the arrangement.");
746
747 DFace* f2 = prev2->is_on_inner_ccb() ? prev2->inner_ccb()->face() :
748 prev2->outer_ccb()->face();
749
750 // If the vertex that corresponds to cv's left end has boundary conditions,
751 // create it now.
752 if (v1 == nullptr)
753 // Locate the DCEL features that will be used for inserting the curve's
754 // left end.
755 v1 =
756 _place_and_set_curve_end(f2, cv, ARR_MIN_END, ps_x1, ps_y1, &fict_prev1);
757
758 // Perform the insertion (note that we know that prev2->vertex is larger
759 // than v1).
760 DHalfedge* new_he;
761
762 if (fict_prev1 == nullptr)
763 // Insert the halfedge given the predecessor halfedge of v2.
764 new_he = _insert_from_vertex(prev2, cv, ARR_RIGHT_TO_LEFT, v1);
765 else {
766 // Insert the halfedge given the two predecessor halfedges.
767 // Note that in this case we may create a new face.
768 bool new_face_created = false;
769 bool check_swapped_predecessors = false;
770 new_he = _insert_at_vertices(prev2, cv, ARR_RIGHT_TO_LEFT,
771 fict_prev1->next(), new_face_created,
772 check_swapped_predecessors);
773 // Comment EBEB 2012-10-21: Swapping does not take place as the insertion
774 // merges the CCB as an "interior" extension into an outer CCB of a face
775 // incident the parameter space's boundary.
776 CGAL_assertion(!check_swapped_predecessors);
777
778 if (new_face_created) {
779 CGAL_assertion(new_he->is_on_outer_ccb());
780 // Note! new_he is not needed to define the new outer CCB of the new face
781 // Here, it can be the outer ccb of the old face, as there is also not
782 // swapping taking place!
783
784 // In case a new face has been created (pointed by the new halfedge we
785 // obtained), we have to examine the holes and isolated vertices in the
786 // existing face (pointed by the twin halfedge) and move the relevant
787 // holes and isolated vertices into the new face.
788 _relocate_in_new_face(new_he);
789 }
790
791 }
792
793 // Return a handle to the halfedge directed toward the new vertex v1.
794 CGAL_postcondition(new_he->direction() == ARR_RIGHT_TO_LEFT);
795 return (Halfedge_handle(new_he));
796 }
797
798 //-----------------------------------------------------------------------------
799 // Insert an x-monotone curve into the arrangement, such that its right
800 // endpoint corresponds to a given arrangement vertex, given the exact place
801 // for the curve in the circular list around this vertex.
802 //
803 template <typename GeomTraits, typename TopTraits>
804 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
805 Arrangement_on_surface_2<GeomTraits, TopTraits>::
insert_from_right_vertex(const X_monotone_curve_2 & cv,Halfedge_handle prev)806 insert_from_right_vertex(const X_monotone_curve_2& cv,
807 Halfedge_handle prev)
808 {
809 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
810 std::cout << "Aos_2: insert_from_right_vertex (interface)" << std::endl;
811 std::cout << "cv : " << cv << std::endl;
812 if (!prev->is_fictitious())
813 std::cout << "prev : " << prev ->curve() << std::endl;
814 else
815 std::cout << "prev : fictitious" << std::endl;
816 std::cout << "dir : " << prev->direction() << std::endl;
817 #endif
818
819 CGAL_precondition_code
820 (const bool at_obnd2 =
821 !m_geom_traits->is_closed_2_object()(cv, ARR_MAX_END));
822 CGAL_precondition_msg
823 ((! at_obnd2 &&
824 m_geom_traits->equal_2_object()
825 (prev->target()->point(),
826 m_geom_traits->construct_max_vertex_2_object()(cv))) ||
827 (at_obnd2 && prev->target()->is_at_open_boundary()),
828 "The input vertex should be the right curve end.");
829
830 CGAL_precondition_msg
831 (at_obnd2 ||
832 (_locate_around_vertex(_vertex(prev->target()), cv, ARR_MAX_END) ==
833 _halfedge(prev)),
834 "In the clockwise order of curves around the vertex, "
835 " cv must succeed the curve of prev.");
836
837 // Get the predecessor halfedge for the insertion of the right curve end.
838 DHalfedge* prev2 = _halfedge(prev);
839 DFace* f2 = _face(prev->face());
840
841 // Check if cv's left end has boundary conditions, and obtain a vertex v1
842 // that corresponds to this end.
843 const Arr_parameter_space ps_x1 =
844 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MIN_END);
845 const Arr_parameter_space ps_y1 =
846 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MIN_END);
847 DHalfedge* fict_prev1 = nullptr;
848
849 DVertex* v1 = ((ps_x1 == ARR_INTERIOR) && (ps_y1 == ARR_INTERIOR)) ?
850 // The curve has a valid left endpoint: Create a new vertex associated
851 // with the curve's left endpoint.
852 _create_vertex(m_geom_traits->construct_min_vertex_2_object()(cv)) :
853 // Locate the DCEL features that will be used for inserting the curve's
854 // left end.
855 _place_and_set_curve_end(f2, cv, ARR_MIN_END, ps_x1, ps_y1, &fict_prev1);
856
857 // Perform the insertion (note that we know that prev2->vertex is larger
858 // than v1).
859 DHalfedge* new_he;
860
861 if (fict_prev1 == nullptr)
862 // Insert the halfedge given the predecessor halfedge of the right vertex.
863 new_he = _insert_from_vertex(prev2, cv, ARR_RIGHT_TO_LEFT, v1);
864 else {
865 // Insert the halfedge given the two predecessor halfedges.
866 // Note that in this case we may create a new face.
867 bool new_face_created = false;
868 bool check_swapped_predecessors = false;
869 new_he = _insert_at_vertices(prev2, cv, ARR_RIGHT_TO_LEFT,
870 fict_prev1->next(), new_face_created,
871 check_swapped_predecessors);
872 // Comment EBEB 2012-10-21: Swapping does not take place as the insertion
873 // merges the CCB as an "interior" extension into an outer CCB of a face
874 // incident the parameter space's boundary.
875 CGAL_assertion(!check_swapped_predecessors);
876
877 if (new_face_created) {
878 CGAL_assertion(new_he->is_on_outer_ccb());
879 // Note! new_he is not needed to define the new outer CCB of the new face
880 // Here, it can be the outer ccb of the old face, as there is also not
881 // swapping taking place!
882
883 // In case a new face has been created (pointed by the new halfedge we
884 // obtained), we have to examine the holes and isolated vertices in the
885 // existing face (pointed by the twin halfedge) and move the relevant
886 // holes and isolated vertices into the new face.
887 _relocate_in_new_face(new_he);
888 }
889 }
890
891 // Return a handle to the halfedge directed toward the new vertex v1.
892 CGAL_postcondition(new_he->direction() == ARR_RIGHT_TO_LEFT);
893 return (Halfedge_handle(new_he));
894 }
895
896 //-----------------------------------------------------------------------------
897 // Insert an x-monotone curve into the arrangement, such that both its
898 // endpoints corresponds to a given arrangement vertex.
899 //
900 template <typename GeomTraits, typename TopTraits>
901 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
902 Arrangement_on_surface_2<GeomTraits, TopTraits>::
insert_at_vertices(const X_monotone_curve_2 & cv,Vertex_handle v1,Vertex_handle v2,Face_handle f)903 insert_at_vertices(const X_monotone_curve_2& cv,
904 Vertex_handle v1, Vertex_handle v2,
905 Face_handle f)
906 {
907 CGAL_USE(f);
908
909 // Determine which one of the given vertices matches the left end of the
910 // given curve.
911 const bool at_obnd1 = !m_geom_traits->is_closed_2_object()(cv, ARR_MIN_END);
912 const bool at_obnd2 = !m_geom_traits->is_closed_2_object()(cv, ARR_MAX_END);
913
914 Arr_curve_end ind1;
915 Arr_curve_end ind2;
916
917 if (! at_obnd1) {
918 CGAL_precondition_code(Vertex_handle v_right);
919
920 if (! v1->is_at_open_boundary() &&
921 m_geom_traits->equal_2_object()
922 (v1->point(),
923 m_geom_traits->construct_min_vertex_2_object()(cv)))
924 {
925 ind1 = ARR_MIN_END;
926 ind2 = ARR_MAX_END;
927 CGAL_precondition_code(v_right = v2);
928 }
929 else {
930 CGAL_precondition_msg
931 (! v2->is_at_open_boundary() &&
932 m_geom_traits->equal_2_object()
933 (v2->point(),
934 m_geom_traits->construct_min_vertex_2_object()(cv)),
935 "One of the input vertices should be the left curve end.");
936
937 ind1 = ARR_MAX_END;
938 ind2 = ARR_MIN_END;
939 CGAL_precondition_code(v_right = v1);
940 }
941
942 CGAL_precondition_msg
943 ((! at_obnd2 &&
944 m_geom_traits->equal_2_object()
945 (v_right->point(),
946 m_geom_traits->construct_max_vertex_2_object()(cv))) ||
947 (at_obnd2 && v_right->is_at_open_boundary()),
948 "One of the input vertices should be the right curve end.");
949 }
950 else {
951 if (! at_obnd2) {
952 CGAL_precondition_code(Vertex_handle v_left);
953
954 if (! v1->is_at_open_boundary() &&
955 m_geom_traits->equal_2_object()
956 (v1->point(),
957 m_geom_traits->construct_max_vertex_2_object()(cv)))
958 {
959 ind1 = ARR_MAX_END;
960 ind2 = ARR_MIN_END;
961 CGAL_precondition_code(v_left = v2);
962 }
963 else {
964 CGAL_precondition_msg
965 (! v2->is_at_open_boundary() &&
966 m_geom_traits->equal_2_object()
967 (v2->point(),
968 m_geom_traits->construct_max_vertex_2_object()(cv)),
969 "One of the input vertices should be the right curve end.");
970
971 ind1 = ARR_MIN_END;
972 ind2 = ARR_MAX_END;
973 CGAL_precondition_code(v_left = v1);
974 }
975
976 CGAL_precondition_msg
977 (at_obnd1 && v_left->is_at_open_boundary(),
978 "One of the input vertices should be the left curve end.");
979 }
980 else {
981 Arr_parameter_space ps_x1 =
982 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MIN_END);
983 Arr_parameter_space ps_y1 =
984 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MIN_END);
985
986 // Check which vertex should be associated with the minimal curve-end
987 // (so the other is associated with the maximal curve-end).
988 if (m_topol_traits.are_equal(_vertex(v1), cv, ARR_MIN_END, ps_x1, ps_y1))
989 {
990 CGAL_assertion
991 (m_topol_traits.are_equal
992 (_vertex(v2), cv, ARR_MAX_END,
993 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END),
994 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END)));
995
996 ind1 = ARR_MIN_END;
997 ind2 = ARR_MAX_END;
998 }
999 else {
1000 CGAL_assertion(m_topol_traits.are_equal
1001 (_vertex(v2), cv, ARR_MIN_END, ps_x1, ps_y1));
1002 CGAL_assertion
1003 (m_topol_traits.are_equal
1004 (_vertex(v1), cv, ARR_MAX_END,
1005 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END),
1006 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END)));
1007
1008 ind1 = ARR_MAX_END;
1009 ind2 = ARR_MIN_END;
1010 }
1011 }
1012 }
1013
1014 // Check whether one of the vertices has no incident halfedges.
1015 if (v1->degree() == 0) {
1016 // Get the face containing the isolated vertex v1.
1017 DVertex* p_v1 = _vertex(v1);
1018 DIso_vertex* iv1 = nullptr;
1019 DFace* f1 = nullptr;
1020
1021 if (p_v1->is_isolated()) {
1022 // Obtain the containing face from the isolated vertex record.
1023 iv1 = p_v1->isolated_vertex();
1024 f1 = iv1->face();
1025
1026 // Remove the isolated vertex v1, as it will not be isolated any more.
1027 f1->erase_isolated_vertex(iv1);
1028 _dcel().delete_isolated_vertex(iv1);
1029 }
1030
1031 // Check whether the other vertex also has no incident halfedges.
1032 if (v2->degree() == 0) {
1033 // Both end-vertices are isolated. Make sure they are contained inside
1034 // the same face.
1035 DVertex* p_v2 = _vertex(v2);
1036 DIso_vertex* iv2 = nullptr;
1037 DFace* f2 = nullptr;
1038
1039 if (p_v2->is_isolated()) {
1040 // Obtain the containing face from the isolated vertex record.
1041 iv2 = p_v2->isolated_vertex();
1042 f2 = iv2->face();
1043
1044 CGAL_assertion_msg
1045 ((f1 == nullptr) || (f1 == f2),
1046 "The two isolated vertices must be located inside the same face.");
1047
1048 // Remove the isolated vertex v2, as it will not be isolated any more.
1049 f2->erase_isolated_vertex(iv2);
1050 _dcel().delete_isolated_vertex(iv2);
1051 }
1052 else if (f1 == nullptr)
1053 // In this case the containing face must be given by the user.
1054 CGAL_precondition(f != Face_handle());
1055
1056 // Perform the insertion.
1057 Arr_halfedge_direction cv_dir =
1058 (ind1 == ARR_MIN_END) ? ARR_LEFT_TO_RIGHT : ARR_RIGHT_TO_LEFT;
1059 DHalfedge* new_he = _insert_in_face_interior(f1, cv, cv_dir, p_v1, p_v2);
1060
1061 return (Halfedge_handle(new_he));
1062 }
1063
1064 // Go over the incident halfedges around v2 and find the halfedge after
1065 // which the new curve should be inserted.
1066 DHalfedge* prev2 = _locate_around_vertex(_vertex(v2), cv, ind2);
1067 CGAL_assertion_msg
1068 (prev2 != nullptr,
1069 "The inserted curve cannot be located in the arrangement.");
1070
1071 CGAL_assertion_code
1072 (DFace* f2 = prev2->is_on_inner_ccb() ? prev2->inner_ccb()->face() :
1073 prev2->outer_ccb()->face());
1074
1075 CGAL_assertion_msg
1076 ((f1 == nullptr) || (f1 == f2),
1077 "The inserted curve should not intersect the existing arrangement.");
1078
1079 // Perform the insertion. Note that the returned halfedge is directed
1080 // toward v1 (and not toward v2), so we return its twin.
1081 Arr_halfedge_direction cv_dir =
1082 (ind2 == ARR_MIN_END) ? ARR_LEFT_TO_RIGHT : ARR_RIGHT_TO_LEFT;
1083 DHalfedge* new_he = _insert_from_vertex(prev2, cv, cv_dir, p_v1);
1084
1085 return (Halfedge_handle(new_he->opposite()));
1086 }
1087 else if (v2->degree() == 0) {
1088 // Get the face containing the isolated vertex v2.
1089 DVertex* p_v2 = _vertex(v2);
1090 DIso_vertex* iv2 = nullptr;
1091 DFace* f2 = nullptr;
1092
1093 if (v2->is_isolated()) {
1094 // Obtain the containing face from the isolated vertex record.
1095 iv2 = p_v2->isolated_vertex();
1096 f2 = iv2->face();
1097
1098 // Remove the isolated vertex v2, as it will not be isolated any more.
1099 f2->erase_isolated_vertex(iv2);
1100 _dcel().delete_isolated_vertex(iv2);
1101 }
1102
1103 // Go over the incident halfedges around v1 and find the halfedge after
1104 // which the new curve should be inserted.
1105 DHalfedge* prev1 = _locate_around_vertex(_vertex(v1), cv, ind1);
1106 CGAL_assertion_msg
1107 (prev1 != nullptr,
1108 "The inserted curve cannot be located in the arrangement.");
1109
1110 CGAL_assertion_code
1111 (DFace* f1 = prev1->is_on_inner_ccb() ? prev1->inner_ccb()->face() :
1112 prev1->outer_ccb()->face());
1113
1114 CGAL_assertion_msg
1115 ((f2 == nullptr) || (f2 == f1),
1116 "The inserted curve should not intersect the existing arrangement.");
1117
1118 // Perform the insertion.
1119 Arr_halfedge_direction cv_dir =
1120 (ind1 == ARR_MIN_END) ? ARR_LEFT_TO_RIGHT : ARR_RIGHT_TO_LEFT;
1121 DHalfedge* new_he = _insert_from_vertex(prev1, cv, cv_dir, p_v2);
1122
1123 return (Halfedge_handle(new_he));
1124 }
1125
1126 // Go over the incident halfedges around v1 and v2 and find the two
1127 // halfedges after which the new curve should be inserted, respectively.
1128 DHalfedge* prev1 = _locate_around_vertex(_vertex(v1), cv, ind1);
1129 DHalfedge* prev2 = _locate_around_vertex(_vertex(v2), cv, ind2);
1130
1131 CGAL_assertion_msg
1132 (((prev1 != nullptr) && (prev2 != nullptr)),
1133 "The inserted curve cannot be located in the arrangement.");
1134
1135 // Perform the insertion.
1136 return insert_at_vertices(cv, Halfedge_handle(prev1), Halfedge_handle(prev2));
1137 }
1138
1139 //-----------------------------------------------------------------------------
1140 // Insert an x-monotone curve into the arrangement, such that both its
1141 // endpoints correspond to given arrangement vertices, given the exact
1142 // place for the curve in one of the circular lists around a vertex.
1143 //
1144 template <typename GeomTraits, typename TopTraits>
1145 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
1146 Arrangement_on_surface_2<GeomTraits, TopTraits>::
insert_at_vertices(const X_monotone_curve_2 & cv,Halfedge_handle prev1,Vertex_handle v2)1147 insert_at_vertices(const X_monotone_curve_2& cv,
1148 Halfedge_handle prev1,
1149 Vertex_handle v2)
1150 {
1151 // Determine which one of the given vertices matches the left end of the
1152 // given curve.
1153 const bool at_obnd1 = !m_geom_traits->is_closed_2_object()(cv, ARR_MIN_END);
1154 const bool at_obnd2 = !m_geom_traits->is_closed_2_object()(cv, ARR_MAX_END);
1155
1156 Arr_curve_end ind2;
1157
1158 if (! at_obnd1) {
1159 CGAL_precondition_code(Vertex_handle v_right);
1160
1161 if (! prev1->target()->is_at_open_boundary() &&
1162 m_geom_traits->equal_2_object()
1163 (prev1->target()->point(),
1164 m_geom_traits->construct_min_vertex_2_object()(cv)))
1165 {
1166 ind2 = ARR_MAX_END;
1167 CGAL_precondition_code(v_right = v2);
1168 }
1169 else {
1170 CGAL_precondition_msg
1171 (! v2->is_at_open_boundary() &&
1172 m_geom_traits->equal_2_object()
1173 (v2->point(),
1174 m_geom_traits->construct_min_vertex_2_object()(cv)),
1175 "One of the input vertices should be the left curve end.");
1176
1177 ind2 = ARR_MIN_END;
1178 CGAL_precondition_code(v_right = prev1->target());
1179 }
1180
1181 CGAL_precondition_msg
1182 ((! at_obnd2 &&
1183 m_geom_traits->equal_2_object()
1184 (v_right->point(),
1185 m_geom_traits->construct_max_vertex_2_object()(cv))) ||
1186 (at_obnd2 && v_right->is_at_open_boundary()),
1187 "One of the input vertices should be the right curve end.");
1188 }
1189 else {
1190 if (! at_obnd2) {
1191 CGAL_precondition_code(Vertex_handle v_left);
1192
1193 if (! prev1->target()->is_at_open_boundary() &&
1194 m_geom_traits->equal_2_object()
1195 (prev1->target()->point(),
1196 m_geom_traits->construct_max_vertex_2_object()(cv)))
1197 {
1198 ind2 = ARR_MIN_END;
1199 CGAL_precondition_code(v_left = v2);
1200 }
1201 else {
1202 CGAL_precondition_msg
1203 (! v2->is_at_open_boundary() &&
1204 m_geom_traits->equal_2_object()
1205 (v2->point(),
1206 m_geom_traits->construct_max_vertex_2_object()(cv)),
1207 "One of the input vertices should be the right curve end.");
1208
1209 ind2 = ARR_MAX_END;
1210 CGAL_precondition_code(v_left = prev1->target());
1211 }
1212
1213 CGAL_precondition_msg
1214 (at_obnd1 && v_left->is_at_open_boundary(),
1215 "One of the input vertices should be the left curve end.");
1216 }
1217 else {
1218 Arr_parameter_space ps_x1 =
1219 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MIN_END);
1220 Arr_parameter_space ps_y1 =
1221 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MIN_END);
1222
1223 // Check which vertex should be associated with the minimal curve-end
1224 // (so the other is associated with the maximal curve-end).
1225 if (m_topol_traits.are_equal(_vertex(prev1->target()),
1226 cv, ARR_MIN_END, ps_x1, ps_y1))
1227 {
1228 CGAL_assertion
1229 (m_topol_traits.are_equal
1230 (_vertex(v2), cv, ARR_MAX_END,
1231 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END),
1232 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END)));
1233
1234 ind2 = ARR_MAX_END;
1235 }
1236 else {
1237 CGAL_assertion(m_topol_traits.are_equal
1238 (_vertex(v2), cv, ARR_MIN_END, ps_x1, ps_y1));
1239 CGAL_assertion
1240 (m_topol_traits.are_equal
1241 (_vertex(prev1->target()), cv, ARR_MAX_END,
1242 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END),
1243 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END)));
1244
1245 ind2 = ARR_MIN_END;
1246 }
1247 }
1248 }
1249
1250 // Check whether v2 is has no incident edges.
1251 if (v2->degree() == 0) {
1252 // Get the face containing the isolated vertex v2.
1253 DVertex* p_v2 = _vertex(v2);
1254 DIso_vertex* iv2 = nullptr;
1255 DFace* f2 = nullptr;
1256
1257 if (v2->is_isolated()) {
1258 iv2 = p_v2->isolated_vertex();
1259 f2 = iv2->face();
1260
1261 CGAL_assertion_msg
1262 (f2 == _face(prev1->face()),
1263 "The inserted curve should not intersect the existing arrangement.");
1264
1265 // Remove the isolated vertex v2, as it will not be isolated any more.
1266 f2->erase_isolated_vertex(iv2);
1267 _dcel().delete_isolated_vertex(iv2);
1268 }
1269
1270 // Perform the insertion.
1271 Arr_halfedge_direction cv_dir =
1272 (ind2 == ARR_MAX_END) ? ARR_LEFT_TO_RIGHT : ARR_RIGHT_TO_LEFT;
1273 DHalfedge* new_he = _insert_from_vertex(_halfedge(prev1), cv, cv_dir, p_v2);
1274
1275 return (Halfedge_handle(new_he));
1276 }
1277
1278 // Go over the incident halfedges around v2 and find the halfedge after
1279 // which the new curve should be inserted.
1280 DHalfedge* prev2 = _locate_around_vertex(_vertex(v2), cv, ind2);
1281 CGAL_assertion_msg
1282 (prev2 != nullptr, "The inserted curve cannot be located in the arrangement.");
1283
1284 // Perform the insertion.
1285 return (insert_at_vertices(cv, prev1, Halfedge_handle(prev2)));
1286 }
1287
1288 //-----------------------------------------------------------------------------
1289 // Insert an x-monotone curve into the arrangement, such that both its
1290 // endpoints correspond to given arrangement vertices, given the exact
1291 // place for the curve in both circular lists around these two vertices.
1292 //
1293 template <typename GeomTraits, typename TopTraits>
1294 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
1295 Arrangement_on_surface_2<GeomTraits, TopTraits>::
insert_at_vertices(const X_monotone_curve_2 & cv,Halfedge_handle prev1,Halfedge_handle prev2)1296 insert_at_vertices(const X_monotone_curve_2& cv,
1297 Halfedge_handle prev1,
1298 Halfedge_handle prev2)
1299 {
1300 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
1301 std::cout << "Aos_2: insert_at_vertices (interface)" << std::endl;
1302 std::cout << "cv : " << cv << std::endl;
1303 if (!prev1->is_fictitious())
1304 std::cout << "prev1: " << prev1->curve() << std::endl;
1305 else
1306 std::cout << "prev1: fictitious" << std::endl;
1307 std::cout << "dir1 : " << prev1->direction() << std::endl;
1308 if (!prev2->is_fictitious())
1309 std::cout << "prev2: " << prev2->curve() << std::endl;
1310 else
1311 std::cout << "prev2: fictitious" << std::endl;
1312 std::cout << "dir2 : " << prev2->direction() << std::endl;
1313 #endif
1314
1315 // Determine which one of the given vertices (the target vertices of the
1316 // given halfedges) matches the left end of the given curve.
1317 // Thus, we can determine the comparison result between prev1->target()
1318 // and prev2->target().
1319 const bool at_obnd1 = !m_geom_traits->is_closed_2_object()(cv, ARR_MIN_END);
1320 const bool at_obnd2 = !m_geom_traits->is_closed_2_object()(cv, ARR_MAX_END);
1321 Comparison_result res;
1322
1323 if (! at_obnd1) {
1324 CGAL_precondition_code(Vertex_handle v_right);
1325
1326 if (! prev1->target()->is_at_open_boundary() &&
1327 m_geom_traits->equal_2_object()
1328 (prev1->target()->point(),
1329 m_geom_traits->construct_min_vertex_2_object()(cv)))
1330 {
1331 res = SMALLER;
1332 CGAL_precondition_code(v_right = prev2->target());
1333 }
1334 else {
1335 CGAL_precondition_msg
1336 (! prev2->target()->is_at_open_boundary() &&
1337 m_geom_traits->equal_2_object()
1338 (prev2->target()->point(),
1339 m_geom_traits->construct_min_vertex_2_object()(cv)),
1340 "One of the input vertices should be the left curve end.");
1341
1342 res = LARGER;
1343 CGAL_precondition_code(v_right = prev1->target());
1344 }
1345
1346 CGAL_precondition_msg
1347 ((! at_obnd2 &&
1348 m_geom_traits->equal_2_object()
1349 (v_right->point(),
1350 m_geom_traits->construct_max_vertex_2_object()(cv))) ||
1351 (at_obnd2 && v_right->is_at_open_boundary()),
1352 "One of the input vertices should be the right curve end.");
1353 }
1354 else {
1355 if (! at_obnd2) {
1356 CGAL_precondition_code(Vertex_handle v_left);
1357
1358 if (! prev1->target()->is_at_open_boundary() &&
1359 m_geom_traits->equal_2_object()
1360 (prev1->target()->point(),
1361 m_geom_traits->construct_max_vertex_2_object()(cv)))
1362 {
1363 res = LARGER;
1364 CGAL_precondition_code(v_left = prev2->target());
1365 }
1366 else {
1367 CGAL_precondition_msg
1368 (! prev2->target()->is_at_open_boundary() &&
1369 m_geom_traits->equal_2_object()
1370 (prev2->target()->point(),
1371 m_geom_traits->construct_max_vertex_2_object()(cv)),
1372 "One of the input vertices should be the right curve end.");
1373
1374 res = SMALLER;
1375 CGAL_precondition_code(v_left = prev1->target());
1376 }
1377
1378 CGAL_precondition_msg
1379 (at_obnd1 && v_left->is_at_open_boundary(),
1380 "One of the input vertices should be the left curve end.");
1381 }
1382 else {
1383 Arr_parameter_space ps_x1 =
1384 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MIN_END);
1385 Arr_parameter_space ps_y1 =
1386 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MIN_END);
1387 // Check which vertex should be associated with the minimal curve-end
1388 // (so the other is associated with the maximal curve-end), and
1389 // determine the comparison result of the two vertices accordingly.
1390 if (m_topol_traits.are_equal(_vertex(prev1->target()),
1391 cv, ARR_MIN_END, ps_x1, ps_y1))
1392 {
1393 CGAL_assertion
1394 (m_topol_traits.are_equal
1395 (_vertex(prev2->target()), cv, ARR_MAX_END,
1396 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END),
1397 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END)));
1398
1399 res = SMALLER;
1400 }
1401 else {
1402 CGAL_assertion
1403 (m_topol_traits.are_equal
1404 (_vertex(prev2->target()), cv, ARR_MIN_END,
1405 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MIN_END),
1406 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MIN_END)));
1407 CGAL_assertion
1408 (m_topol_traits.are_equal
1409 (_vertex(prev1->target()), cv, ARR_MAX_END,
1410 m_geom_traits->parameter_space_in_x_2_object()(cv, ARR_MAX_END),
1411 m_geom_traits->parameter_space_in_y_2_object()(cv, ARR_MAX_END)));
1412
1413 res = LARGER;
1414 }
1415 }
1416 }
1417
1418 // Check if e1 and e2 are on the same connected component.
1419 DHalfedge* p_prev1 = _halfedge(prev1);
1420 DHalfedge* p_prev2 = _halfedge(prev2);
1421
1422 // Note that in this case we may create a new face.
1423 bool new_face_created = false;
1424 bool swapped_predecessors = false;
1425 DHalfedge* new_he =
1426 _insert_at_vertices(p_prev1, cv,
1427 (res == SMALLER ? ARR_LEFT_TO_RIGHT : ARR_RIGHT_TO_LEFT),
1428 p_prev2->next(), new_face_created,
1429 swapped_predecessors);
1430
1431 if (new_face_created)
1432 // Comment EBEB 2012-10-21: Here we allow swapping, as there might be
1433 // a local minima (or other needs), and thus new_he can lie on an inner CCB.
1434 // In fact we cannot expect new_he to lie on an inner or on an outer CCB.
1435
1436 // In case a new face has been created (pointed by the new halfedge we
1437 // obtained), we have to examine the holes and isolated vertices in the
1438 // existing face (pointed by the twin halfedge) and move the relevant
1439 // holes and isolated vertices into the new face.
1440 _relocate_in_new_face(new_he);
1441
1442 // Return a handle to the new halfedge directed from prev1's target to
1443 // prev2's target. Note that this may be the twin halfedge of the one
1444 // returned by _insert_at_vertices();
1445 if (swapped_predecessors) new_he = new_he->opposite();
1446
1447 return (Halfedge_handle(new_he));
1448 }
1449
1450 //-----------------------------------------------------------------------------
1451 // Replace the point associated with the given vertex.
1452 //
1453 template <typename GeomTraits, typename TopTraits>
1454 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Vertex_handle
1455 Arrangement_on_surface_2<GeomTraits, TopTraits>::
modify_vertex(Vertex_handle vh,const Point_2 & p)1456 modify_vertex(Vertex_handle vh, const Point_2& p)
1457 {
1458 CGAL_precondition_msg
1459 (! vh->is_at_open_boundary(),
1460 "The modified vertex must not lie on open boundary.");
1461 CGAL_precondition_msg(m_geom_traits->equal_2_object()(vh->point(), p),
1462 "The new point is different from the current one.");
1463
1464 // Modify the vertex.
1465 _modify_vertex(_vertex(vh), p);
1466
1467 // Return a handle to the modified vertex.
1468 return vh;
1469 }
1470
1471 //-----------------------------------------------------------------------------
1472 // Remove an isolated vertex from the interior of a given face.
1473 //
1474 template <typename GeomTraits, typename TopTraits>
1475 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Face_handle
1476 Arrangement_on_surface_2<GeomTraits, TopTraits>::
remove_isolated_vertex(Vertex_handle v)1477 remove_isolated_vertex(Vertex_handle v)
1478 {
1479 CGAL_precondition(v->is_isolated());
1480
1481 // Get the face containing v.
1482 DVertex* p_v = _vertex(v);
1483 DIso_vertex* iv = p_v->isolated_vertex();
1484 DFace* p_f = iv->face();
1485 Face_handle f = Face_handle(p_f);
1486
1487 // Notify the observers that we are abount to remove a vertex.
1488 _notify_before_remove_vertex(v);
1489
1490 // Remove the isolated vertex from the face that contains it.
1491 p_f->erase_isolated_vertex(iv);
1492 _dcel().delete_isolated_vertex(iv);
1493
1494 // Delete the vertex.
1495 _delete_point(p_v->point());
1496 _dcel().delete_vertex(p_v);
1497
1498 // Notify the observers that the vertex has been removed.
1499 _notify_after_remove_vertex();
1500
1501 // Return a handle for the face that used to contain the deleted vertex.
1502 return f;
1503 }
1504
1505 //-----------------------------------------------------------------------------
1506 // Replace the x-monotone curve associated with the given edge.
1507 //
1508 template <typename GeomTraits, typename TopTraits>
1509 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
1510 Arrangement_on_surface_2<GeomTraits, TopTraits>::
modify_edge(Halfedge_handle e,const X_monotone_curve_2 & cv)1511 modify_edge(Halfedge_handle e, const X_monotone_curve_2& cv)
1512 {
1513 CGAL_precondition_msg(! e->is_fictitious(),
1514 "The edge must be a valid one.");
1515 CGAL_precondition_msg(m_geom_traits->equal_2_object()(e->curve(), cv),
1516 "The new curve is different from the current one.");
1517
1518 // Modify the edge.
1519 _modify_edge(_halfedge(e), cv);
1520
1521 // Return a handle to the modified halfedge.
1522 return e;
1523 }
1524
1525 //-----------------------------------------------------------------------------
1526 // Split a given edge into two, and associate the given x-monotone
1527 // curves with the split edges.
1528 //
1529 template <typename GeomTraits, typename TopTraits>
1530 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
1531 Arrangement_on_surface_2<GeomTraits, TopTraits>::
split_edge(Halfedge_handle e,const X_monotone_curve_2 & cv1,const X_monotone_curve_2 & cv2)1532 split_edge(Halfedge_handle e,
1533 const X_monotone_curve_2& cv1, const X_monotone_curve_2& cv2)
1534 {
1535 CGAL_precondition_msg(! e->is_fictitious(), "The edge must be a valid one.");
1536
1537 // Get the split halfedge and its twin, its source and target.
1538 DHalfedge* he1 = _halfedge(e);
1539 DHalfedge* he2 = he1->opposite();
1540 DVertex* source = he2->vertex();
1541 CGAL_precondition_code(DVertex* target = he1->vertex());
1542
1543 // Determine the point where we split the halfedge. We also determine which
1544 // curve should be associated with he1 (and he2), which is the curve who
1545 // has an endpoint that equals e's source, and which should be associated
1546 // with the new pair of halfedges we are about to split (the one who has
1547 // an endpoint which equals e's target).
1548 if ((m_geom_traits->parameter_space_in_x_2_object()(cv1, ARR_MAX_END) ==
1549 ARR_INTERIOR) &&
1550 (m_geom_traits->parameter_space_in_y_2_object()(cv1, ARR_MAX_END) ==
1551 ARR_INTERIOR))
1552 {
1553 const Point_2 & cv1_right =
1554 m_geom_traits->construct_max_vertex_2_object()(cv1);
1555
1556 if ((m_geom_traits->parameter_space_in_x_2_object()(cv2, ARR_MIN_END) ==
1557 ARR_INTERIOR) &&
1558 (m_geom_traits->parameter_space_in_y_2_object()(cv2, ARR_MIN_END) ==
1559 ARR_INTERIOR) &&
1560 m_geom_traits->equal_2_object()(m_geom_traits->
1561 construct_min_vertex_2_object()(cv2),
1562 cv1_right))
1563 {
1564 // cv1's right endpoint and cv2's left endpoint are equal, so this should
1565 // be the split point. Now we check whether cv1 is incident to e's source
1566 // and cv2 to its target, or vice versa.
1567 if (_are_equal(source, cv1, ARR_MIN_END)) {
1568 CGAL_precondition_msg
1569 (_are_equal(target, cv2, ARR_MAX_END),
1570 "The subcurve endpoints must match e's end vertices.");
1571
1572 return (Halfedge_handle(_split_edge(he1, cv1_right, cv1, cv2)));
1573 }
1574
1575 CGAL_precondition_msg
1576 (_are_equal(source, cv2, ARR_MAX_END) &&
1577 _are_equal(target, cv1, ARR_MIN_END),
1578 "The subcurve endpoints must match e's end vertices.");
1579
1580 return (Halfedge_handle(_split_edge(he1, cv1_right, cv2, cv1)));
1581 }
1582 }
1583
1584 if ((m_geom_traits->parameter_space_in_x_2_object()(cv1, ARR_MIN_END) ==
1585 ARR_INTERIOR) &&
1586 (m_geom_traits->parameter_space_in_y_2_object()(cv1, ARR_MIN_END) ==
1587 ARR_INTERIOR))
1588 {
1589 const Point_2 & cv1_left =
1590 m_geom_traits->construct_min_vertex_2_object()(cv1);
1591
1592 if ((m_geom_traits->parameter_space_in_x_2_object()(cv2, ARR_MAX_END) ==
1593 ARR_INTERIOR) &&
1594 (m_geom_traits->parameter_space_in_y_2_object()(cv2, ARR_MAX_END) ==
1595 ARR_INTERIOR) &&
1596 m_geom_traits->equal_2_object()(m_geom_traits->
1597 construct_max_vertex_2_object()(cv2),
1598 cv1_left))
1599 {
1600 // cv1's left endpoint and cv2's right endpoint are equal, so this should
1601 // be the split point. Now we check whether cv1 is incident to e's source
1602 // and cv2 to its target, or vice versa.
1603 if (_are_equal(source, cv2, ARR_MIN_END)) {
1604 CGAL_precondition_msg
1605 (_are_equal(target, cv1, ARR_MAX_END),
1606 "The subcurve endpoints must match e's end vertices.");
1607
1608 return (Halfedge_handle(_split_edge(he1, cv1_left, cv2, cv1)));
1609 }
1610
1611 CGAL_precondition_msg
1612 (_are_equal(source, cv1, ARR_MAX_END) &&
1613 _are_equal(target, cv2, ARR_MIN_END),
1614 "The subcurve endpoints must match e's end vertices.");
1615
1616 return (Halfedge_handle(_split_edge(he1, cv1_left, cv1, cv2)));
1617 }
1618 }
1619
1620 CGAL_error_msg("The two subcurves must have a common endpoint.");
1621 return Halfedge_handle();
1622 }
1623
1624 //-----------------------------------------------------------------------------
1625 // Merge two edges to form a single edge, and associate the given x-monotone
1626 // curve with the merged edge.
1627 //
1628 template <typename GeomTraits, typename TopTraits>
1629 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle
1630 Arrangement_on_surface_2<GeomTraits, TopTraits>::
merge_edge(Halfedge_handle e1,Halfedge_handle e2,const X_monotone_curve_2 & cv)1631 merge_edge(Halfedge_handle e1, Halfedge_handle e2,
1632 const X_monotone_curve_2& cv)
1633 {
1634 CGAL_precondition_msg(! e1->is_fictitious() && ! e2->is_fictitious(),
1635 "The edges must be a valid.");
1636
1637 // Assign pointers to the existing halfedges, such that we have:
1638 //
1639 // he1 he3
1640 // -------> ------->
1641 // (.) (.)v (.)
1642 // <------- <-------
1643 // he2 he4
1644 //
1645 DHalfedge* _e1 = _halfedge(e1);
1646 DHalfedge* _e2 = _halfedge(e2);
1647 DHalfedge* he1 = nullptr;
1648 DHalfedge* he2 = nullptr;
1649 DHalfedge* he3 = nullptr;
1650 DHalfedge* he4 = nullptr;
1651
1652 if (_e1->vertex() == _e2->opposite()->vertex()) {
1653 he1 = _e1;
1654 he2 = he1->opposite();
1655 he3 = _e2;
1656 he4 = he3->opposite();
1657 }
1658 else if (_e1->opposite()->vertex() == _e2->opposite()->vertex()) {
1659 he2 = _e1;
1660 he1 = he2->opposite();
1661 he3 = _e2;
1662 he4 = he3->opposite();
1663 }
1664 else if (_e1->vertex() == _e2->vertex()) {
1665 he1 = _e1;
1666 he2 = he1->opposite();
1667 he4 = _e2;
1668 he3 = he4->opposite();
1669 }
1670 else if (_e1->opposite()->vertex() == _e2->vertex()) {
1671 he2 = _e1;
1672 he1 = he2->opposite();
1673 he4 = _e2;
1674 he3 = he4->opposite();
1675 }
1676 else {
1677 CGAL_precondition_msg(false,
1678 "The input edges do not share a common vertex.");
1679 return Halfedge_handle();
1680 }
1681
1682 // The vertex we are about to delete is now he1's target vertex.
1683 // Make sure that he1 and he4 are the only halfedges directed to v.
1684 DVertex* v = he1->vertex();
1685
1686 CGAL_precondition_msg
1687 (! v->has_null_point(),
1688 "The vertex removed by the merge must not lie on open boundary.");
1689 CGAL_precondition_msg
1690 (he1->next()->opposite() == he4 &&
1691 he4->next()->opposite() == he1,
1692 "The degree of the deleted vertex is greater than 2.");
1693
1694 // Make sure the curve ends match the end vertices of the merged edge.
1695 CGAL_precondition_msg
1696 ((_are_equal(he2->vertex(), cv, ARR_MIN_END) &&
1697 _are_equal(he3->vertex(), cv, ARR_MAX_END)) ||
1698 (_are_equal(he3->vertex(), cv, ARR_MIN_END) &&
1699 _are_equal(he2->vertex(), cv, ARR_MAX_END)),
1700 "The endpoints of the merged curve must match the end vertices.");
1701
1702 // Keep pointers to the components that contain two halfedges he3 and he2,
1703 // pointing at the end vertices of the merged halfedge.
1704 DInner_ccb* ic1 = (he3->is_on_inner_ccb()) ? he3->inner_ccb() : nullptr;
1705 DOuter_ccb* oc1 = (ic1 == nullptr) ? he3->outer_ccb() : nullptr;
1706
1707 DInner_ccb* ic2 = (he4->is_on_inner_ccb()) ? he4->inner_ccb() : nullptr;
1708 DOuter_ccb* oc2 = (ic2 == nullptr) ? he4->outer_ccb() : nullptr;
1709
1710 // Notify the observers that we are about to merge an edge.
1711 _notify_before_merge_edge(e1, e2, cv);
1712
1713 // As he1 and he2 will evetually represent the merged edge, while he3 and he4
1714 // will be deleted, check if the deleted halfedges are represantatives of a
1715 // the CCBs they belong to. If so, replace he3 by he1 and he4 by he2. Note
1716 // that as we just change the component representatives, we do not have to
1717 // notify the observers on the change.
1718 if (oc1 != nullptr && oc1->halfedge() == he3)
1719 oc1->set_halfedge(he1);
1720 else if (ic1 != nullptr && ic1->halfedge() == he3)
1721 ic1->set_halfedge(he1);
1722
1723 if (oc2 != nullptr && oc2->halfedge() == he4)
1724 oc2->set_halfedge(he2);
1725 else if (ic2 != nullptr && ic2->halfedge() == he4)
1726 ic2->set_halfedge(he2);
1727
1728 // If he3 is the incident halfedge to its target, replace it by he1.
1729 if (he3->vertex()->halfedge() == he3)
1730 he3->vertex()->set_halfedge(he1);
1731
1732 // Disconnect he3 and he4 from the edge list.
1733 if (he3->next() == he4) {
1734 // he3 and he4 form an "antenna", so he1 and he2 must be connected
1735 // together.
1736 he1->set_next(he2);
1737 }
1738 else {
1739 he1->set_next(he3->next());
1740 he4->prev()->set_next(he2);
1741 }
1742
1743 // Note that he1 (and its twin) is going to represent the merged edge while
1744 // he3 (and its twin) is going to be removed. We therefore associate the
1745 // merged curve with he1 and delete the curve associated with he3.
1746 he1->curve() = cv;
1747 _delete_curve(he3->curve());
1748
1749 // Set the properties of the merged edge.
1750 he1->set_vertex(he3->vertex());
1751
1752 // Notify the observers that we are about to delete a vertex.
1753 _notify_before_remove_vertex(Vertex_handle(v));
1754
1755 // Delete the point associated with the merged vertex.
1756 _delete_point(v->point());
1757
1758 // Delete the merged vertex.
1759 _dcel().delete_vertex(v);
1760
1761 // Notify the observers that the vertex has been deleted.
1762 _notify_after_remove_vertex();
1763
1764 // Delete the redundant halfedge pair.
1765 _dcel().delete_edge(he3);
1766
1767 // Create a handle for one of the merged halfedges.
1768 Halfedge_handle hh(he1);
1769
1770 // Notify the observers that the edge has been merge.
1771 _notify_after_merge_edge(hh);
1772
1773 // Return a handle for one of the merged halfedges.
1774 return hh;
1775 }
1776
1777 //-----------------------------------------------------------------------------
1778 // Remove an edge from the arrangement.
1779 //
1780 template <typename GeomTraits, typename TopTraits>
1781 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Face_handle
1782 Arrangement_on_surface_2<GeomTraits, TopTraits>::
remove_edge(Halfedge_handle e,bool remove_source,bool remove_target)1783 remove_edge(Halfedge_handle e, bool remove_source, bool remove_target)
1784 {
1785 // Comment EBEB 2012-08-06: this has become a simple forwarding function
1786 // the intelligence of whether to swap he with he->opposite()
1787 // has been moved to _remove_edge itself, as additional computed
1788 // data is reused there
1789
1790 CGAL_precondition_msg(! e->is_fictitious(),
1791 "The edge must be a valid one.");
1792
1793 DHalfedge* he1 = _halfedge(e);
1794 DFace* f = _remove_edge(he1, remove_source, remove_target);
1795 return Face_handle(f);
1796 }
1797
1798 //-----------------------------------------------------------------------------
1799 // Protected member functions (for internal use).
1800 //-----------------------------------------------------------------------------
1801
1802 //-----------------------------------------------------------------------------
1803 // Locate the place for the given curve around the given vertex.
1804 //
1805 template <typename GeomTraits, typename TopTraits>
1806 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::DHalfedge*
1807 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_locate_around_vertex(DVertex * v,const X_monotone_curve_2 & cv,Arr_curve_end ind)1808 _locate_around_vertex(DVertex* v,
1809 const X_monotone_curve_2& cv, Arr_curve_end ind) const
1810 {
1811 // Check if the given curve-end has boundary conditions.
1812 const Arr_parameter_space ps_x =
1813 m_geom_traits->parameter_space_in_x_2_object()(cv, ind);
1814 const Arr_parameter_space ps_y =
1815 m_geom_traits->parameter_space_in_y_2_object()(cv, ind);
1816
1817 if ((ps_x != ARR_INTERIOR) || (ps_y != ARR_INTERIOR))
1818 // Use the topology-traits class to locate the predecessor halfedge for
1819 // cv around the given vertex.
1820 return m_topol_traits.locate_around_boundary_vertex(v, cv, ind, ps_x, ps_y);
1821
1822 // In case of a non-boundary vertex, we look for the predecessor around v.
1823 // Get the first incident halfedge around v and the next halfedge.
1824 DHalfedge* first = v->halfedge();
1825 DHalfedge* curr = first;
1826
1827 if (curr == nullptr) return nullptr;
1828
1829 DHalfedge* next = curr->next()->opposite();
1830
1831 // In case there is only one halfedge incident to v, return this halfedge.
1832 if (curr == next) return curr;
1833
1834 // Otherwise, we traverse the halfedges around v until we find the pair
1835 // of adjacent halfedges between which we should insert cv.
1836 typename Traits_adaptor_2::Is_between_cw_2 is_between_cw =
1837 m_geom_traits->is_between_cw_2_object();
1838
1839 bool eq_curr, eq_next;
1840 while (! is_between_cw(cv, (ind == ARR_MIN_END),
1841 curr->curve(),
1842 (curr->direction() == ARR_RIGHT_TO_LEFT),
1843 next->curve(),
1844 (next->direction() == ARR_RIGHT_TO_LEFT),
1845 v->point(), eq_curr, eq_next))
1846 {
1847 // If cv equals one of the curves associated with the halfedges, it is
1848 // an illegal input curve, as it already exists in the arrangement.
1849 if (eq_curr || eq_next) return nullptr;
1850
1851 // Move to the next pair of incident halfedges.
1852 curr = next;
1853 next = curr->next()->opposite();
1854
1855 // If we completed a full traversal around v without locating the
1856 // place for cv, it follows that cv overlaps and existing curve.
1857 if (curr == first) return nullptr;
1858 }
1859
1860 // Return the halfedge we have located.
1861 return curr;
1862 }
1863
1864 //-----------------------------------------------------------------------------
1865 // Compute the distance (in halfedges) between two halfedges.
1866 //
1867 template <typename GeomTraits, typename TopTraits>
1868 unsigned int
1869 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_halfedge_distance(const DHalfedge * e1,const DHalfedge * e2)1870 _halfedge_distance(const DHalfedge* e1, const DHalfedge* e2) const
1871 {
1872 CGAL_precondition(e1 != e2);
1873 if (e1 == e2) return (0);
1874
1875 // Traverse the halfedge chain from e1 until reaching e2.
1876 const DHalfedge* curr = e1->next();
1877 unsigned int dist = 1;
1878
1879 while (curr != e2) {
1880 // If we have returned to e1, e2 is not reachable from e1.
1881 if (curr == e1) {
1882 CGAL_error();
1883 return (0);
1884 }
1885
1886 curr = curr->next();
1887 ++dist;
1888 }
1889
1890 // We have located e2 along the boundary of e1's component - return the
1891 // distance (number of halfedges) between e1 and e2.
1892 return (dist);
1893 }
1894
1895 //-----------------------------------------------------------------------------
1896 //Compare the length of the induced paths from e1 to e2 and from e2 to e1.
1897 // return SMALLER if e1 to e2 is shorter, EQUAL if paths lengths are equal,
1898 // o/w LARGER
1899 //
1900 template <typename GeomTraits, typename TopTraits>
1901 Comparison_result
1902 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_compare_induced_path_length(const DHalfedge * e1,const DHalfedge * e2)1903 _compare_induced_path_length(const DHalfedge* e1, const DHalfedge* e2) const
1904 {
1905 CGAL_precondition(e1 != e2);
1906 if (e1 == e2) return EQUAL;
1907
1908 // Traverse the halfedge chain from e1 until reaching e2.
1909 const DHalfedge* curr1 = e1->next();
1910 // Traverse the halfedge chain from e2 until reaching e1.
1911 const DHalfedge* curr2 = e2->next();
1912
1913 while ((curr1 != e2) && (curr2 != e1)) {
1914 // If we have returned to e1, e2 is not reachable from e1.
1915 if (curr1 == e1) {
1916 CGAL_error();
1917 return EQUAL;
1918 }
1919
1920 // If we have returned to e2, e1 is not reachable from e2.
1921 if (curr2 == e2) {
1922 CGAL_error();
1923 return EQUAL;
1924 }
1925
1926 curr1 = curr1->next();
1927 curr2 = curr2->next();
1928 }
1929
1930 // Return SMALLER if e1 to e2 is shorter than e2 to e1,
1931 // EQUAL if their lengths are equal, or LARGER if e2 to e1 is longer.
1932 Comparison_result res =
1933 (curr1 == e2) ? ((curr2 != e1) ? SMALLER : EQUAL) : LARGER;
1934
1935 CGAL_postcondition_code(int dist1 = _halfedge_distance(e1,e2));
1936 CGAL_postcondition_code(int dist2 = _halfedge_distance(e2,e1));
1937 CGAL_postcondition(((dist1 < dist2) && (res == SMALLER)) ||
1938 ((dist1 == dist2) && (res == EQUAL)) ||
1939 ((dist1 > dist2) && (res == LARGER)));
1940
1941 return res;
1942 }
1943
1944 //-----------------------------------------------------------------------------
1945 // Move a given outer CCB from one face to another.
1946 //
1947 template <typename GeomTraits, typename TopTraits>
1948 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_move_outer_ccb(DFace * from_face,DFace * to_face,DHalfedge * he)1949 _move_outer_ccb(DFace* from_face, DFace* to_face, DHalfedge* he)
1950 {
1951 // Get the DCEL record that represents the outer CCB.
1952 DOuter_ccb* oc = he->outer_ccb();
1953
1954 CGAL_assertion(oc->face() == from_face);
1955
1956 // Notify the observers that we are about to move an outer CCB.
1957 Ccb_halfedge_circulator circ = (Halfedge_handle(he))->ccb();
1958
1959 _notify_before_move_outer_ccb(Face_handle(from_face), Face_handle(to_face),
1960 circ);
1961
1962 // Remove the hole from the current face.
1963 from_face->erase_outer_ccb(oc);
1964
1965 // Modify the component that represents the hole.
1966 oc->set_face(to_face);
1967 to_face->add_outer_ccb(oc, he);
1968
1969 // Notify the observers that we have moved the outer CCB.
1970 _notify_after_move_outer_ccb(circ);
1971 }
1972
1973 //-----------------------------------------------------------------------------
1974 // Move a given inner CCB (hole) from one face to another.
1975 //
1976 template <typename GeomTraits, typename TopTraits>
1977 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_move_inner_ccb(DFace * from_face,DFace * to_face,DHalfedge * he)1978 _move_inner_ccb(DFace* from_face, DFace* to_face, DHalfedge* he)
1979 {
1980 // Get the DCEL record that represents the inner CCB.
1981 DInner_ccb* ic = he->inner_ccb();
1982
1983 CGAL_assertion(ic->face() == from_face);
1984
1985 // Notify the observers that we are about to move an inner CCB.
1986 Ccb_halfedge_circulator circ = (Halfedge_handle(he))->ccb();
1987
1988 _notify_before_move_inner_ccb(Face_handle(from_face), Face_handle(to_face),
1989 circ);
1990
1991 // Remove the hole from the current face.
1992 from_face->erase_inner_ccb(ic);
1993
1994 // Modify the component that represents the hole.
1995 ic->set_face(to_face);
1996 to_face->add_inner_ccb(ic, he);
1997
1998 // Notify the observers that we have moved the inner CCB.
1999 _notify_after_move_inner_ccb(circ);
2000 }
2001
2002 //-----------------------------------------------------------------------------
2003 // Move all inner CCBs (holes) from one face to another.
2004 //
2005 template <typename GeomTraits, typename TopTraits>
2006 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_move_all_inner_ccb(DFace * from_face,DFace * to_face)2007 _move_all_inner_ccb(DFace* from_face, DFace* to_face)
2008 {
2009 // Comment EFEF 2015-09-28: The following loop and the loop at the end of this
2010 // function should be replaced with a pair of notifiers, respectively,
2011 // function_notify_before_move_all_inner_ccb();
2012 // function_notify_after_move_all_inner_ccb();
2013 DInner_ccb_iter ic_it = from_face->inner_ccbs_begin();
2014 while (ic_it != from_face->inner_ccbs_end()) {
2015 DHalfedge* he = *ic_it++;
2016 Ccb_halfedge_circulator circ = (Halfedge_handle(he))->ccb();
2017 _notify_before_move_inner_ccb(Face_handle(from_face), Face_handle(to_face),
2018 circ);
2019 }
2020 ic_it = to_face->splice_inner_ccbs(*from_face);
2021 while (ic_it != to_face->inner_ccbs_end()) {
2022 DHalfedge* he = *ic_it++;
2023 Ccb_halfedge_circulator circ = (Halfedge_handle(he))->ccb();
2024 _notify_after_move_inner_ccb(circ);
2025 }
2026 }
2027
2028 //-----------------------------------------------------------------------------
2029 // Insert the given vertex as an isolated vertex inside the given face.
2030 //
2031 template <typename GeomTraits, typename TopTraits>
2032 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_insert_isolated_vertex(DFace * f,DVertex * v)2033 _insert_isolated_vertex(DFace* f, DVertex* v)
2034 {
2035 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2036 std::cout << "Aos_2: _insert_isolated_vertex (internal)" << std::endl;
2037 if (!v->has_null_point())
2038 std::cout << "v->point: " << v->point() << std::endl;
2039 std::cout << "face : " << f << std::endl;
2040 #endif
2041
2042 Face_handle fh(f);
2043 Vertex_handle vh(v);
2044
2045 // Notify the observers that we are about to insert an isolated vertex
2046 // inside f.
2047 _notify_before_add_isolated_vertex(fh, vh);
2048
2049 // Create an isolated vertex-information object,
2050 DIso_vertex* iv = _dcel().new_isolated_vertex();
2051
2052 // Set a pointer to the face containing the vertex.
2053 iv->set_face(f);
2054
2055 // Initiate a new hole inside the given face.
2056 f->add_isolated_vertex(iv, v);
2057
2058 // Associate the information with the vertex.
2059 v->set_isolated_vertex(iv);
2060
2061 // Notify the observers that we have formed a new isolated vertex.
2062 _notify_after_add_isolated_vertex(vh);
2063 }
2064
2065 //-----------------------------------------------------------------------------
2066 // Move a given isolated vertex from one face to another.
2067 //
2068 template <typename GeomTraits, typename TopTraits>
2069 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_move_isolated_vertex(DFace * from_face,DFace * to_face,DVertex * v)2070 _move_isolated_vertex(DFace* from_face, DFace* to_face, DVertex* v)
2071 {
2072 // Get the DCEL isolated-vertex record.
2073 DIso_vertex* iv = v->isolated_vertex();
2074
2075 // Notify the observers that we are about to move an isolated vertex.
2076 Vertex_handle vh(v);
2077
2078 _notify_before_move_isolated_vertex(Face_handle(from_face),
2079 Face_handle(to_face), vh);
2080
2081 // Set the new face is the isolated vertex-information object.
2082 iv->set_face(to_face);
2083
2084 // Move the isolated vertex from the first face to the other.
2085 from_face->erase_isolated_vertex(iv);
2086 to_face->add_isolated_vertex(iv, v);
2087
2088 // Notify the observers that we have moved the isolated vertex.
2089 _notify_after_move_isolated_vertex(vh);
2090 }
2091
2092 //-----------------------------------------------------------------------------
2093 // Move all isolated vertices from one face to another.
2094 //
2095 template <typename GeomTraits, typename TopTraits>
2096 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_move_all_isolated_vertices(DFace * from_face,DFace * to_face)2097 _move_all_isolated_vertices(DFace* from_face, DFace* to_face)
2098 {
2099 // Comment EFEF 2015-09-28: The following loop and the loop at the end of this
2100 // function should be replaced with a pair of notifiers, respectively,
2101 // function_notify_before_move_all_isolated_vertices();
2102 // function_notify_after_move_all_isolated_vertices();
2103 DIso_vertex_iter iv_it = from_face->isolated_vertices_begin();
2104 while (iv_it != from_face->isolated_vertices_end()) {
2105 DVertex* v = &(*iv_it++);
2106 Vertex_handle vh(v);
2107 _notify_before_move_isolated_vertex(Face_handle(from_face),
2108 Face_handle(to_face),
2109 vh);
2110 }
2111 iv_it = to_face->splice_isolated_vertices(*from_face);
2112 while (iv_it != to_face->isolated_vertices_end()) {
2113 DVertex* v = &(*iv_it++);
2114 Vertex_handle vh(v);
2115 _notify_after_move_isolated_vertex(vh);
2116 }
2117 }
2118
2119 //-----------------------------------------------------------------------------
2120 // Create a new vertex and associate it with the given point.
2121 //
2122 template <typename GeomTraits, typename TopTraits>
2123 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::DVertex*
2124 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_create_vertex(const Point_2 & p)2125 _create_vertex(const Point_2& p)
2126 {
2127 // Notify the observers that we are about to create a new vertex.
2128 Point_2* p_p = _new_point(p);
2129
2130 _notify_before_create_vertex(*p_p);
2131
2132 // Create a new vertex and associate it with the given point.
2133 DVertex* v = _dcel().new_vertex();
2134
2135 v->set_point(p_p);
2136 v->set_boundary(ARR_INTERIOR, ARR_INTERIOR);
2137
2138 // Notify the observers that we have just created a new vertex.
2139 Vertex_handle vh(v);
2140 _notify_after_create_vertex(vh);
2141
2142 return v;
2143 }
2144
2145 //-----------------------------------------------------------------------------
2146 // Create a new vertex on boundary
2147 //
2148 template <typename GeomTraits, typename TopTraits>
2149 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::DVertex*
2150 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_create_boundary_vertex(const X_monotone_curve_2 & cv,Arr_curve_end ind,Arr_parameter_space ps_x,Arr_parameter_space ps_y)2151 _create_boundary_vertex(const X_monotone_curve_2& cv, Arr_curve_end ind,
2152 Arr_parameter_space ps_x, Arr_parameter_space ps_y)
2153 {
2154 CGAL_precondition((ps_x != ARR_INTERIOR) || (ps_y != ARR_INTERIOR));
2155
2156 // Notify the observers that we are about to create a new boundary vertex.
2157 _notify_before_create_boundary_vertex(cv, ind, ps_x, ps_y);
2158
2159 // Create a new vertex and set its boundary conditions.
2160 DVertex* v = _dcel().new_vertex();
2161
2162 v->set_boundary(ps_x, ps_y);
2163
2164 // Act according to the boundary type if there is one:
2165 if (is_open(ps_x, ps_y))
2166 // The curve-end lies on open boundary so the vertex is not associated
2167 // with a valid point.
2168 v->set_point(nullptr);
2169 else {
2170 // Create a boundary vertex associated with a valid point.
2171 Point_2* p_p = (ind == ARR_MIN_END) ?
2172 _new_point(m_geom_traits->construct_min_vertex_2_object()(cv)) :
2173 _new_point(m_geom_traits->construct_max_vertex_2_object()(cv));
2174
2175 v->set_point(p_p);
2176 }
2177
2178 // Notify the observers that we have just created a new boundary vertex.
2179 Vertex_handle vh(v);
2180 _notify_after_create_boundary_vertex(vh);
2181
2182 return v;
2183 }
2184
2185 //-----------------------------------------------------------------------------
2186 // Locate the DCEL features that will be used for inserting the given curve
2187 // end, which has a boundary condition, and set the proper vertex there.
2188 //
2189 template <typename GeomTraits, typename TopTraits>
2190 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::DVertex*
2191 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_place_and_set_curve_end(DFace * f,const X_monotone_curve_2 & cv,Arr_curve_end ind,Arr_parameter_space ps_x,Arr_parameter_space ps_y,DHalfedge ** p_pred)2192 _place_and_set_curve_end(DFace* f,
2193 const X_monotone_curve_2& cv, Arr_curve_end ind,
2194 Arr_parameter_space ps_x, Arr_parameter_space ps_y,
2195 DHalfedge** p_pred)
2196 {
2197 // Use the topology traits to locate the DCEL feature that contains the
2198 // given curve end.
2199 auto obj = m_topol_traits.place_boundary_vertex(f, cv, ind, ps_x, ps_y);
2200 // Act according to the result type.
2201
2202 if (! obj) {
2203 // We have to create a new vertex that reprsents the given curve end.
2204 DVertex* v = _create_boundary_vertex(cv, ind, ps_x, ps_y);
2205
2206 // Notify the topology traits on the creation of the boundary vertex.
2207 m_topol_traits.notify_on_boundary_vertex_creation(v, cv, ind, ps_x, ps_y);
2208
2209 // There are no edges incident to v, therefore no predecessor halfedge.
2210 *p_pred = nullptr;
2211
2212 // Return the vertex that represents the curve end.
2213 return v;
2214 }
2215
2216 DHalfedge** fict_he_p = boost::get<DHalfedge*>(&*obj);
2217 if (fict_he_p != nullptr) {
2218 DHalfedge* fict_he = *fict_he_p;
2219 CGAL_assertion(fict_he != nullptr);
2220 // The curve end is located on a fictitious edge. We first create a new
2221 // vertex that corresponds to the curve end.
2222 DVertex* v = _create_boundary_vertex(cv, ind, ps_x, ps_y);
2223
2224 // Split the fictitious halfedge at the newly created vertex.
2225 // The returned halfedge is the predecessor for the insertion of the curve
2226 // end around v.
2227 _notify_before_split_fictitious_edge(Halfedge_handle(fict_he),
2228 Vertex_handle(v));
2229
2230 *p_pred = m_topol_traits.split_fictitious_edge(fict_he, v);
2231
2232 _notify_after_split_fictitious_edge(Halfedge_handle(*p_pred),
2233 Halfedge_handle((*p_pred)->next()));
2234 return v;
2235 }
2236 DVertex** v_p = boost::get<DVertex*>(&*obj);
2237 CGAL_assertion(v_p != nullptr);
2238 DVertex* v = *v_p;
2239 CGAL_assertion(v != nullptr);
2240 // In this case we are given an existing vertex that represents the curve
2241 // end. We now have to locate the predecessor edge for the insertion of cv
2242 // around this vertex.
2243 *p_pred = m_topol_traits.locate_around_boundary_vertex(v, cv, ind, ps_x, ps_y);
2244 return v;
2245 }
2246
2247 //-----------------------------------------------------------------------------
2248 // Insert an x-monotone curve into the arrangement, such that both its
2249 // endpoints correspond to free arrangement vertices (newly created vertices
2250 // or existing isolated vertices), so a new inner CCB is formed in the face
2251 // that contains the two vertices.
2252 //
2253 template <typename GeomTraits, typename TopTraits>
2254 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::DHalfedge*
2255 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_insert_in_face_interior(DFace * f,const X_monotone_curve_2 & cv,Arr_halfedge_direction cv_dir,DVertex * v1,DVertex * v2)2256 _insert_in_face_interior(DFace* f,
2257 const X_monotone_curve_2& cv,
2258 Arr_halfedge_direction cv_dir,
2259 DVertex* v1, DVertex* v2)
2260 {
2261 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2262 std::cout << "Aos_2: _insert_in_face_interior (internal)" << std::endl;
2263 std::cout << "face : " << f << std::endl;
2264 std::cout << "cv : " << cv << std::endl;
2265 std::cout << "cv_dir: " << cv_dir << std::endl;
2266 if (!v1->has_null_point())
2267 std::cout << "v1->point: " << v1->point() << std::endl;
2268 if (!v2->has_null_point())
2269 std::cout << "v2->point: " << v2->point() << std::endl;
2270 #endif
2271
2272 // Notify the observers that we are about to create a new edge.
2273 _notify_before_create_edge(cv, Vertex_handle(v1), Vertex_handle(v2));
2274
2275 // Create a pair of twin halfedges connecting the two vertices,
2276 // and link them together to form a new connected component, a hole in f.
2277 DHalfedge* he1 = _dcel().new_edge();
2278 DHalfedge* he2 = he1->opposite();
2279 DInner_ccb* ic = _dcel().new_inner_ccb();
2280 X_monotone_curve_2* dup_cv = _new_curve(cv);
2281
2282 ic->set_face(f);
2283 he1->set_curve(dup_cv);
2284
2285 he1->set_next(he2);
2286 he1->set_vertex(v1);
2287 he1->set_inner_ccb(ic);
2288
2289 he2->set_next(he1);
2290 he2->set_vertex(v2);
2291 he2->set_inner_ccb(ic);
2292
2293 // Assign the incident halfedges of the two new vertices.
2294 v1->set_halfedge(he1);
2295 v2->set_halfedge(he2);
2296
2297 // Set the direction of the halfedges
2298 he2->set_direction(cv_dir);
2299
2300 // Create a handle to the new halfedge pointing at the curve target.
2301 Halfedge_handle hh(he2);
2302
2303 // Notify the observers that we have created a new edge.
2304 _notify_after_create_edge(hh);
2305
2306 // Notify the observers that we are about to form a new inner CCB inside f.
2307 _notify_before_add_inner_ccb(Face_handle(f), hh);
2308
2309 // Initiate a new inner CCB inside the given face.
2310 f->add_inner_ccb(ic, he2);
2311
2312 // Notify the observers that we have formed a new inner CCB.
2313 _notify_after_add_inner_ccb(hh->ccb());
2314
2315 return he2;
2316 }
2317
2318 //-----------------------------------------------------------------------------
2319 // Insert an x-monotone curve into the arrangement, such that one of its
2320 // endpoints corresponds to a given arrangement vertex, given the exact
2321 // place for the curve in the circular list around this vertex. The other
2322 // endpoint corrsponds to a free vertex (a newly created vertex or an
2323 // isolated vertex).
2324 //
2325 template <typename GeomTraits, typename TopTraits>
2326 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::DHalfedge*
2327 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_insert_from_vertex(DHalfedge * he_to,const X_monotone_curve_2 & cv,Arr_halfedge_direction cv_dir,DVertex * v)2328 _insert_from_vertex(DHalfedge* he_to, const X_monotone_curve_2& cv,
2329 Arr_halfedge_direction cv_dir,
2330 DVertex* v)
2331 {
2332 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2333 std::cout << "Aos_2: _insert_from_vertex (internal)" << std::endl;
2334 if (!he_to->has_null_curve())
2335 std::cout << "he_to: " << he_to->curve() << std::endl;
2336 else
2337 std::cout << "he_to: fictitious" << std::endl;
2338 std::cout << "f_to: " << (he_to->is_on_inner_ccb() ?
2339 he_to->inner_ccb()->face() :
2340 he_to->outer_ccb()->face()) << std::endl;
2341 std::cout << "cv : " << cv << std::endl;
2342 std::cout << "cv_dir: " << cv_dir << std::endl;
2343 if (!v->has_null_point())
2344 std::cout << "v->point: " << v->point() << std::endl;
2345 #endif
2346
2347 // Get the incident face of the previous halfedge. Note that this will also
2348 // be the incident face of the two new halfedges we are about to create.
2349 DInner_ccb* ic = (he_to->is_on_inner_ccb()) ? he_to->inner_ccb() : nullptr;
2350 DOuter_ccb* oc = (ic == nullptr) ? he_to->outer_ccb() : nullptr;
2351
2352 // The first vertex is the one that the he_to halfedge points to.
2353 // The second vertex is given by v.
2354 DVertex* v1 = he_to->vertex();
2355 DVertex* v2 = v;
2356
2357 // Notify the observers that we are about to create a new edge.
2358 _notify_before_create_edge(cv, Vertex_handle(v1), Vertex_handle(v2));
2359
2360 // Create a pair of twin halfedges connecting the two vertices,
2361 // and associate them with the given curve.
2362 DHalfedge* he1 = _dcel().new_edge();
2363 DHalfedge* he2 = he1->opposite();
2364 X_monotone_curve_2* dup_cv = _new_curve(cv);
2365
2366 he1->set_curve(dup_cv);
2367
2368 he1->set_vertex(v1);
2369 he2->set_vertex(v2);
2370
2371 // Set the component for the new halfedge pair.
2372 if (oc != nullptr) {
2373 // On an outer component:
2374 he1->set_outer_ccb(oc);
2375 he2->set_outer_ccb(oc);
2376 }
2377 else {
2378 // On an inner component:
2379 he1->set_inner_ccb(ic);
2380 he2->set_inner_ccb(ic);
2381 }
2382
2383 // Associate the incident halfedge of the new vertex.
2384 v2->set_halfedge(he2);
2385
2386 // Link the new halfedges around the existing vertex v1.
2387 he2->set_next(he1);
2388 he1->set_next(he_to->next());
2389
2390 he_to->set_next(he2);
2391
2392 // Set the direction of the halfedges
2393 he2->set_direction(cv_dir);
2394
2395 // Notify the observers that we have created a new edge.
2396 _notify_after_create_edge(Halfedge_handle(he2));
2397
2398 // Return a pointer to the new halfedge whose target is the free vertex v.
2399 return he2;
2400 }
2401
2402 //-----------------------------------------------------------------------------
2403 // Insert an x-monotone curve into the arrangement, where the end vertices
2404 // are given by the target points of two given halfedges.
2405 // The two halfedges should be given such that in case a new face is formed,
2406 // it will be the incident face of the halfedge directed from the first
2407 // vertex to the second vertex.
2408 //
2409 template <typename GeomTraits, typename TopTraits>
2410 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::DHalfedge*
2411 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_insert_at_vertices(DHalfedge * he_to,const X_monotone_curve_2 & cv,Arr_halfedge_direction cv_dir,DHalfedge * he_away,bool & new_face,bool & swapped_predecessors,bool allow_swap_of_predecessors)2412 _insert_at_vertices(DHalfedge* he_to,
2413 const X_monotone_curve_2& cv,
2414 Arr_halfedge_direction cv_dir,
2415 DHalfedge* he_away,
2416 bool& new_face,
2417 bool& swapped_predecessors,
2418 bool allow_swap_of_predecessors /* = true */)
2419 {
2420 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2421 std::cout << "_insert_at_vertices: " << cv << std::endl;
2422 #endif
2423 // Comment: This is how the situation looks
2424 // ----to---> >>cv_dir>> ---away--->
2425 // o ===cv=== 0
2426 // <-tonext-- <-awaynext-
2427 // or to be read from right to left ...
2428 // this way, he_to and he_away lie
2429 // BEFORE insertion on the same inner ccb and
2430 // AFTER insertion on the same outer ccb
2431
2432 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2433 std::cout << "Aos_2: _insert_at_vertices (internal)" << std::endl;
2434
2435 if (!he_to->has_null_curve())
2436 std::cout << "he_to: " << he_to->curve() << std::endl;
2437 else
2438 std::cout << "he_to: fictitious" << std::endl;
2439 std::cout << "dir1 : " << he_to->direction() << std::endl;
2440 std::cout << "f_to : " << (he_to->is_on_inner_ccb() ?
2441 he_to->inner_ccb()->face() :
2442 he_to->outer_ccb()->face()) << std::endl;
2443 std::cout << "cv : " << cv << std::endl;
2444 std::cout << "cv_dir: " << cv_dir << std::endl;
2445 if (!he_away->has_null_curve())
2446 std::cout << "he_away: " << he_away->curve() << std::endl;
2447 else
2448 std::cout << "he_away: fictitious" << std::endl;
2449 std::cout << "dir 2 : " << he_away->direction() << std::endl;
2450 std::cout << "f_away: " << (he_away->is_on_inner_ccb() ?
2451 he_away->inner_ccb()->face() :
2452 he_away->outer_ccb()->face()) << std::endl;
2453 #endif
2454
2455 CGAL_precondition(he_to != nullptr);
2456 CGAL_precondition(he_away != nullptr);
2457
2458 // TODO EBEB 2012-10-21 rewrite the code in terms of he_to and he_away instead of prev1 and prev2
2459 // the remainder of the function we deal with this situation adds he1 and
2460 // he2 in this way:
2461 // ----prev1---> ( --he2--> ) ---p2next--->
2462 // o ===cv=== 0
2463 // <---p1next--- ( <--he1-- ) <---prev2----
2464 DHalfedge* prev1 = he_to;
2465 DHalfedge* prev2 = he_away->prev();
2466
2467 CGAL_precondition(prev1 != nullptr);
2468 CGAL_precondition(prev2 != nullptr);
2469 CGAL_precondition(prev1 != prev2);
2470
2471 // in general we do not swap ...
2472 swapped_predecessors = false;
2473
2474 // default values for signs
2475 std::pair<Sign, Sign> signs1(ZERO, ZERO);
2476 std::pair<Sign, Sign> signs2(ZERO, ZERO);
2477 // Remark: signs1 and signs2 are only used later when hole1==hole2
2478
2479 // Comment: This also checks which is the 'cheaper' (previously the
2480 // 'shorter') way to insert the curve. Now cheaper means checking
2481 // less local minima!
2482 if (allow_swap_of_predecessors) {
2483 bool swap_predecessors = false;
2484
2485 // Comment EBEB 2012-08-05 hole1/hole2 appear later as ic1/ic2, but we keep
2486 // them here, as the usage is rather local to decide swapping
2487 DInner_ccb* hole1 = (prev1->is_on_inner_ccb()) ? prev1->inner_ccb() : nullptr;
2488 DInner_ccb* hole2 = (prev2->is_on_inner_ccb()) ? prev2->inner_ccb() : nullptr;
2489
2490 if ((hole1 == hole2) && (hole1 != nullptr)) {
2491 // .. only in this special case, we have to check whether swapping should
2492 // take place
2493
2494 // EBEB 2012-07-26 the following code enables optimizations:
2495 // - avoid length-test
2496 // - search only local minima to find leftmost vertex
2497 // - re-use of signs of ccbs
2498 // signs1/2 are only used when hole1 == hole2,
2499 // thus we have to init them now
2500 Arr_halfedge_direction cv_dir1 = cv_dir;
2501 std::list<std::pair<const DHalfedge*, int> > local_mins1;
2502 signs1 =
2503 _compute_signs_and_local_minima(prev1, cv, cv_dir1, prev2->next(),
2504 std::back_inserter(local_mins1));
2505
2506 Arr_halfedge_direction cv_dir2 = (cv_dir == ARR_LEFT_TO_RIGHT) ?
2507 CGAL::ARR_RIGHT_TO_LEFT : CGAL::ARR_LEFT_TO_RIGHT;
2508 std::list< std::pair< const DHalfedge*, int > > local_mins2;
2509 signs2 =
2510 _compute_signs_and_local_minima(prev2, cv, cv_dir2, prev1->next(),
2511 std::back_inserter(local_mins2));
2512 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2513 std::cout << "signs1.x: " << signs1.first << std::endl;
2514 std::cout << "signs1.y: " << signs1.second << std::endl;
2515 std::cout << "signs2.x: " << signs2.first << std::endl;
2516 std::cout << "signs2.y: " << signs2.second << std::endl;
2517 std::cout << "#local_mins1: " << local_mins1.size() << std::endl;
2518 std::cout << "#local_mins2: " << local_mins2.size() << std::endl;
2519 #endif
2520
2521 if (!m_topol_traits.let_me_decide_the_outer_ccb(signs1, signs2,
2522 swap_predecessors))
2523 {
2524 // COMMENT: The previous solution needed O(min(length1, length2)) steps
2525 // to determine which path is shorter and the search for the
2526 // leftmost vertex on a path needs O(#local_mins) geometric
2527 // comparison. This solution saves the initial loop to
2528 // determine the shorter path and will only need O(min(#local
2529 // _mins1, #local_mins2)) geometric comparisons to determine
2530 // the leftmost vertex on a path.
2531
2532 // If there are no local minima in one the paths, it is expected
2533 // that the topology traits (or its adapter) do decide the outer ccb.
2534 CGAL_assertion(local_mins1.size() > 0);
2535 CGAL_assertion(local_mins2.size() > 0);
2536
2537 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2538 std::cout << "decide swap" << std::endl;
2539 #endif
2540
2541 swap_predecessors =
2542 !((local_mins1.size() < local_mins2.size()) ?
2543 ( _defines_outer_ccb_of_new_face(prev1, cv, prev2->next(),
2544 local_mins1.begin(),
2545 local_mins1.end())) :
2546 (! _defines_outer_ccb_of_new_face(prev2, cv, prev1->next(),
2547 local_mins2.begin(),
2548 local_mins2.end())));
2549 }
2550
2551 // perform the swap
2552 if (swap_predecessors) {
2553 std::swap(prev1, prev2);
2554 cv_dir = (cv_dir == ARR_LEFT_TO_RIGHT) ?
2555 CGAL::ARR_RIGHT_TO_LEFT : CGAL::ARR_LEFT_TO_RIGHT;
2556 std::swap(signs1, signs2);
2557 std::swap(local_mins1, local_mins2);
2558
2559 // and store the value
2560 swapped_predecessors = true;
2561 }
2562 }
2563
2564 // EBEB: For now, local_mins1/2 are local to this pre-check
2565 // Idea: Use it later, however, this spoils uses of _insert_at_vertices
2566 // where allow_swap = false
2567 // On the other hand: this would allow to set representative
2568 // halfedge of ccbs to point to minimal vertex
2569
2570 } // allow_swap_of_predecessors
2571
2572 // Get the vertices that match cv's endpoints.
2573 DVertex* v1 = prev1->vertex();
2574 DVertex* v2 = prev2->vertex();
2575
2576 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2577 std::cout << "Aos_2: _insert_at_vertices (internal)" << std::endl;
2578
2579 std::cout << "cv : " << cv << std::endl;
2580 if (!prev1->has_null_curve())
2581 std::cout << "prev1: " << prev1->curve() << std::endl;
2582 else
2583 std::cout << "prev1: fictitious" << std::endl;
2584 std::cout << "dir1 : " << prev1->direction() << std::endl;
2585 std::cout << "pref: " << (prev1->is_on_inner_ccb() ?
2586 prev1->inner_ccb()->face() :
2587 prev1->outer_ccb()->face()) << std::endl;
2588 if (!prev2->has_null_curve())
2589 std::cout << "prev2: " << prev2->curve() << std::endl;
2590 else
2591 std::cout << "prev2: fictitious" << std::endl;
2592 std::cout << "dir 2: " << prev2->direction() << std::endl;
2593 std::cout << "pref2: " << (prev2->is_on_inner_ccb() ?
2594 prev2->inner_ccb()->face() :
2595 prev2->outer_ccb()->face()) << std::endl;
2596 std::cout << "cv_dir: " << cv_dir << std::endl;
2597 #endif
2598
2599 // Get the components containing the two previous halfedges and the incident
2600 // face (which should be the same for the two components).
2601 DInner_ccb* ic1 = (prev1->is_on_inner_ccb()) ? prev1->inner_ccb() : nullptr;
2602 DOuter_ccb* oc1 = (ic1 == nullptr) ? prev1->outer_ccb() : nullptr;
2603 DFace* f = (ic1 != nullptr) ? ic1->face() : oc1->face();
2604 DInner_ccb* ic2 = (prev2->is_on_inner_ccb()) ? prev2->inner_ccb() : nullptr;
2605 DOuter_ccb* oc2 = (ic2 == nullptr) ? prev2->outer_ccb() : nullptr;
2606
2607 CGAL_precondition_code(DFace* f2 = (ic2 != nullptr) ? ic2->face() : oc2->face());
2608
2609 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2610 std::cout << "ic1: " << ic1 << std::endl;
2611 std::cout << "ic2: " << ic2 << std::endl;
2612 std::cout << "oc1: " << oc1 << std::endl;
2613 std::cout << "oc2: " << oc2 << std::endl;
2614 std::cout << "f1: " << &(*f) << std::endl;
2615
2616 #if 0
2617 DHalfedge* curr = prev1;
2618 if (curr != curr->next()) {
2619 curr = curr->next();
2620 while (curr != prev1) {
2621 if (!curr->has_null_curve())
2622 std::cout << "curr: " << curr->curve() << std::endl;
2623 else
2624 std::cout << "curr: fictitious" << std::endl;
2625 std::cout << "dir: "
2626 << (curr->direction() == CGAL::ARR_LEFT_TO_RIGHT ?
2627 "L2R" : "R2L")
2628 << std::endl;
2629 curr = curr->next();
2630 }
2631 } else {
2632 std::cout << "only prev1" << std::endl;
2633 }
2634 #endif
2635
2636 CGAL_precondition_code(std::cout << "f2: " << &(*f2) << std::endl);
2637
2638 #if 0
2639 curr = prev2;
2640 if (curr != curr->next()) {
2641 curr = curr->next();
2642 while (curr != prev2) {
2643 if (!curr->has_null_curve())
2644 std::cout << "curr: " << curr->curve() << std::endl;
2645 else
2646 std::cout << "curr: fictitious" << std::endl;
2647 std::cout << "dir: "
2648 << (curr->direction() == CGAL::ARR_LEFT_TO_RIGHT ?
2649 "L2R" : "R2L")
2650 << std::endl;
2651 curr = curr->next();
2652 }
2653 } else
2654 std::cout << "only prev2" << std::endl;
2655 #endif
2656 #endif // CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2657
2658 CGAL_precondition_msg
2659 (f == f2, "The two halfedges must share the same incident face.");
2660
2661 // In case the two previous halfedges lie on the same inner component inside
2662 // the face f, we use the topology-traits class to determine whether we have
2663 // to create a new face by splitting f, and if so - whether new face is
2664 // contained in the existing face or just adjacent to it.
2665 bool split_new_face = true;
2666 bool is_split_face_contained = false;
2667
2668 if ((ic1 != nullptr) && (ic1 == ic2)) {
2669
2670 // EBEB 2012-08-06:
2671 // This is new code. It relies on the (computed) signs and replaces to
2672 // trace the ccb again (in particular for torical arrangements)
2673 // TODO EBEB 2012-08-06:
2674 // Check what to do here, when allow_swap_of_predecessors = false and thus
2675 // signs1 and signs2 set to DEFAULT (=ZERO) values.
2676 // swapping is currently only disabled when _insert_at_vertices is called
2677 // from Arr_construction_ss_visitor, which however uses the
2678 // 'swap_predecessors' member of the topology traits' construction helper.
2679 // So it's questionable whether we can combine the light-weigth swap
2680 // information with the slightly more expensive sign computations, to keep
2681 // efficient translated code after compile-time.
2682 std::pair<bool, bool> res =
2683 m_topol_traits.face_split_after_edge_insertion(signs1, signs2);
2684
2685 split_new_face = res.first;
2686 is_split_face_contained = res.second;
2687
2688 // The result <false, true> is illegal:
2689 CGAL_assertion(split_new_face || ! is_split_face_contained);
2690 }
2691
2692 // Notify the observers that we are about to create a new edge.
2693 _notify_before_create_edge(cv, Vertex_handle(v1), Vertex_handle(v2));
2694
2695 // Create a pair of twin halfedges connecting v1 and v2 and associate them
2696 // with the given curve.
2697 DHalfedge* he1 = _dcel().new_edge();
2698 DHalfedge* he2 = he1->opposite();
2699 X_monotone_curve_2* dup_cv = _new_curve(cv);
2700
2701 he1->set_curve(dup_cv);
2702
2703 he1->set_vertex(v1);
2704 he2->set_vertex(v2);
2705
2706 // Connect the new halfedges to the existing halfedges around the two
2707 // incident vertices.
2708 he1->set_next(prev1->next());
2709 he2->set_next(prev2->next());
2710
2711 prev1->set_next(he2);
2712 prev2->set_next(he1);
2713
2714 he2->set_direction(cv_dir);
2715
2716 // Check the various cases of insertion (in the design document: the
2717 // various sub-cases of case 3 in the insertion procedure).
2718 if (((ic1 != nullptr) || (ic2 != nullptr)) && (ic1 != ic2)) {
2719 // In case we have to connect two disconnected components, no new face
2720 // is created.
2721 new_face = false;
2722
2723 // Check whether both halfedges are inner components (holes) in the same
2724 // face, or whether one is a hole and the other is on the outer boundary
2725 // of the face.
2726 Face_handle fh(f);
2727
2728 if ((ic1 != nullptr) && (ic2 != nullptr)) {
2729 // In this case (3.1) we have to connect to inner CCBs (holes) inside f.
2730 // Notify the observers that we are about to merge two holes in the face.
2731 _notify_before_merge_inner_ccb(fh,
2732 (Halfedge_handle(prev1))->ccb(),
2733 (Halfedge_handle(prev2))->ccb(),
2734 Halfedge_handle(he1));
2735
2736 // Remove the inner component prev2 belongs to, and unite it with the
2737 // inner component that prev1 belongs to.
2738 f->erase_inner_ccb(ic2);
2739
2740 // Set the merged component for the two new halfedges.
2741 he1->set_inner_ccb(ic1);
2742 he2->set_inner_ccb(ic1);
2743
2744 if (m_sweep_mode)
2745 {
2746 // Inner CCB are obtained using Halfedge::inner_ccb() which
2747 // performs path reduction and always return valid iCCB
2748 CGAL_assertion(ic1->is_valid());
2749 CGAL_assertion(ic2->is_valid());
2750 ic2->set_next(ic1);
2751 }
2752 else
2753 {
2754 // Make all halfedges along ic2 to point to ic1.
2755 DHalfedge* curr;
2756 for (curr = he2->next(); curr != he1; curr = curr->next())
2757 curr->set_inner_ccb(ic1);
2758
2759 // Delete the redundant inner CCB.
2760 _dcel().delete_inner_ccb(ic2);
2761 }
2762
2763 // Notify the observers that we have merged the two inner CCBs.
2764 _notify_after_merge_inner_ccb(fh, (Halfedge_handle(he1))->ccb());
2765 }
2766 else {
2767 // In this case (3.2) we connect a hole (inner CCB) with an outer CCB
2768 // of the face that contains it. We remove the hole and associate the
2769 // pair of new halfedges with the outer boundary of the face f.
2770 DInner_ccb* del_ic;
2771 DOuter_ccb* oc;
2772 DHalfedge* ccb_first;
2773 DHalfedge* ccb_last;
2774
2775 if (ic1 != nullptr) {
2776 // We remove the inner CCB ic1 and merge in with the outer CCB oc2.
2777 del_ic = ic1;
2778 oc = oc2;
2779 ccb_first = he1->next();
2780 ccb_last = he2;
2781 }
2782 else {
2783 // We remove the inner CCB ic2 and merge in with the outer CCB oc1.
2784 del_ic = ic2;
2785 oc = oc1;
2786 ccb_first = he2->next();
2787 ccb_last = he1;
2788 }
2789
2790 he1->set_outer_ccb(oc);
2791 he2->set_outer_ccb(oc);
2792
2793 // Notify the observers that we are about to remove an inner CCB from
2794 // the face.
2795 _notify_before_remove_inner_ccb(fh, (Halfedge_handle(ccb_first))->ccb());
2796
2797 // Remove the inner CCB from the face, as we have just connected it to
2798 // the outer boundary of its incident face.
2799 f->erase_inner_ccb(del_ic);
2800
2801 // Make all halfedges along the inner CCB to point to the outer CCB of f.
2802 DHalfedge* curr;
2803 for (curr = ccb_first; curr != ccb_last; curr = curr->next())
2804 curr->set_outer_ccb(oc);
2805
2806 // Delete the redundant hole.
2807 _dcel().delete_inner_ccb(del_ic);
2808
2809 // Notify the observers that we have removed an inner ccb.
2810 _notify_after_remove_inner_ccb(fh);
2811 }
2812 }
2813 else if (! split_new_face) {
2814 // RWRW: NEW!
2815 CGAL_assertion((ic1 == ic2) && (ic1 != nullptr));
2816
2817 // Handle the special case where we close an inner CCB, such that
2818 // we form two outer CCBs of the same face.
2819 Face_handle fh(f);
2820
2821 // Notify the obserers we are about to remove an inner CCB from f.
2822 _notify_before_remove_inner_ccb(fh, (Halfedge_handle(he1))->ccb());
2823
2824 // Erase the inner CCB from the incident face and delete the
2825 // corresponding component.
2826 f->erase_inner_ccb(ic1);
2827
2828 _dcel().delete_inner_ccb(ic1);
2829
2830 // Notify the observers that the inner CCB has been removed.
2831 _notify_after_remove_inner_ccb(fh);
2832
2833 // Handle the first split outer CCB (the one containing he1):
2834 // Notify the obserers we are about to add an outer CCB to f.
2835 _notify_before_add_outer_ccb(fh, Halfedge_handle(he1));
2836
2837 // Create a new outer CCB that for the face f, and make he1 the
2838 // representative halfedge of this component.
2839 DOuter_ccb* f_oc1 = _dcel().new_outer_ccb();
2840
2841 f->add_outer_ccb(f_oc1, he1);
2842 f_oc1->set_face(f);
2843 he1->set_outer_ccb(f_oc1);
2844
2845 // Set the component of all halfedges that used to belong to he1's CCB.
2846 DHalfedge* curr;
2847
2848 for (curr = he1->next(); curr != he1; curr = curr->next())
2849 curr->set_outer_ccb(f_oc1);
2850
2851 // Notify the observers that we have added an outer CCB to f.
2852 _notify_after_add_outer_ccb((Halfedge_handle(he1))->ccb());
2853
2854 // Handle the second split outer CCB (the one containing he2):
2855 // Notify the obserers we are about to add an outer CCB to f.
2856 _notify_before_add_outer_ccb(fh, Halfedge_handle(he2));
2857
2858 // Create a new outer CCB that for the face f, and make he2 the
2859 // representative halfedge of this component.
2860 DOuter_ccb* f_oc2 = _dcel().new_outer_ccb();
2861
2862 f->add_outer_ccb(f_oc2, he2);
2863 f_oc2->set_face(f);
2864 he2->set_outer_ccb(f_oc2);
2865
2866 // Set the component of all halfedges that used to belong to he2's CCB.
2867 for (curr = he2->next(); curr != he2; curr = curr->next())
2868 curr->set_outer_ccb(f_oc2);
2869
2870 // Notify the observers that we have added an outer CCB to f.
2871 _notify_after_add_outer_ccb((Halfedge_handle(he2))->ccb());
2872
2873 // Mark that in this case no new face is created:
2874 new_face = false;
2875 }
2876 else if ((ic1 == ic2) && (oc1 == oc2)) {
2877 // In this case we created a pair of halfedge that connect halfedges that
2878 // already belong to the same component. This means we have to cretae a
2879 // new face by splitting the existing face f.
2880 // Notify the observers that we are about to split a face.
2881 Face_handle fh(f);
2882
2883 _notify_before_split_face(fh, Halfedge_handle(he1));
2884
2885 // Create the new face and create a single outer component which should
2886 // point to he2.
2887 DFace* new_f = _dcel().new_face();
2888 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2889 std::cout << "new face: " << new_f << std::endl;
2890 #endif
2891
2892 DOuter_ccb* new_oc = _dcel().new_outer_ccb();
2893
2894 new_face = true;
2895 new_f->add_outer_ccb(new_oc, he2);
2896 new_oc->set_face(new_f);
2897
2898 // Set the components of the new halfedge he2, which should be the new
2899 // outer comoponent of the new face.
2900 // Note that there are several cases for setting he1's component, so we
2901 // do not do it yet.
2902 he2->set_outer_ccb(new_oc);
2903
2904 // Set the component of all halfedges that used to belong to he2's CCB.
2905 DHalfedge* curr;
2906
2907 for (curr = he2->next(); curr != he2; curr = curr->next())
2908 curr->set_outer_ccb(new_oc);
2909
2910 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2911 std::cout << "(=> prev1=" << &(*prev1) << ") he2= " << &(*he2)
2912 << " defines new outer CCB" << std::endl;
2913 std::cout << "he2dir : " << he2->direction() << std::endl;
2914 std::cout << "prev1->face(): " << (prev1->is_on_inner_ccb() ?
2915 prev1->inner_ccb()->face() :
2916 prev1->outer_ccb()->face())
2917 << std::endl;
2918 std::cout << "signs1: " << signs1.first << "," << signs1.second
2919 << std::endl;
2920 #endif
2921
2922 // Check whether the two previous halfedges lie on the same innder CCB
2923 // or on the same outer CCB (distinguish case 3.3 and case 3.4).
2924 bool is_hole;
2925
2926 if (ic1 != nullptr) {
2927 // In this case (3.3) we have two distinguish two sub-cases.
2928 if (is_split_face_contained) {
2929 // Comment: This is true for all non-identification topologies
2930
2931 // The halfedges prev1 and prev2 belong to the same inner component
2932 // (hole) inside the face f, such that the new edge creates a new
2933 // face that is contained in f (case 3.3.1).
2934 is_hole = true;
2935
2936 // In this case, he1 lies on an inner CCB of f.
2937 he1->set_inner_ccb(ic1);
2938
2939 // Note that the current representative of the inner CCB may not
2940 // belong to the hole any more. In this case we replace the hole
2941 // representative by he1.
2942 if (! ic1->halfedge()->is_on_inner_ccb())
2943 ic1->set_halfedge(he1);
2944
2945 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2946 std::cout << "(=> prev2=" << &(*prev2) << ") he1= " << &(*he1)
2947 << " defines new inner CCB" << std::endl;
2948 std::cout << "he1dir : " << he1->direction() << std::endl;
2949 std::cout << "prev2->face(): " << (prev2->is_on_inner_ccb() ?
2950 prev2->inner_ccb()->face() :
2951 prev2->outer_ccb()->face())
2952 << std::endl;
2953 std::cout << "signs2: " << signs2.first << "," << signs2.second
2954 << std::endl;
2955 #endif
2956 }
2957 else {
2958 // Comment: This case can only occur in identification topologies
2959
2960 // The new face we have created should be adjacent to the existing
2961 // face (case 3.3.2).
2962 is_hole = false;
2963
2964 // Notify the obserers we are about to add an outer CCB to f.
2965 _notify_before_add_outer_ccb(fh, Halfedge_handle(he1));
2966
2967 // Create a new outer CCB that for the face f, and make he1 the
2968 // representative halfedge of this component.
2969 DOuter_ccb* f_oc = _dcel().new_outer_ccb();
2970
2971 f->add_outer_ccb(f_oc, he1);
2972 f_oc->set_face(f);
2973 he1->set_outer_ccb(f_oc);
2974
2975 // Set the component of all halfedges that used to belong to he1's
2976 // CCB.
2977 for (curr = he1->next(); curr != he1; curr = curr->next())
2978 curr->set_outer_ccb(f_oc);
2979
2980 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
2981 std::cout << "(=> prev2=" << &(*prev2) << ") he1= " << &(*he1) << " defines new outer CCB" << std::endl;
2982 std::cout << "he1dir : " << he1->direction() << std::endl;
2983 std::cout << "prev2->face(): " << (prev2->is_on_inner_ccb() ?
2984 prev2->inner_ccb()->face() :
2985 prev2->outer_ccb()->face())
2986 << std::endl;
2987 std::cout << "signs2: " << signs2.first << "," << signs2.second
2988 << std::endl;
2989 #endif
2990
2991 // Notify the observers that we have added an outer CCB to f.
2992 _notify_after_add_outer_ccb((Halfedge_handle(he1))->ccb());
2993
2994 // Go over all other outer CCBs of f and check whether they should be
2995 // moved to be outer CCBs of the new face.
2996 DOuter_ccb_iter oc_it = f->outer_ccbs_begin();
2997 DOuter_ccb_iter oc_to_move;
2998
2999
3000 while (oc_it != f->outer_ccbs_end()) {
3001 // Use the topology traits to determine whether the representative
3002 // of the current outer CCB should belong to the same face as he2
3003 // (which is on the outer boundary of the new face).
3004 bool increment = true;
3005 if (*oc_it != he1) {
3006
3007 // he2 is supposed to be a perimetric path and so all of the oc_its,
3008 // we only have to detect which one. We do so by comparing signs of
3009 // ccbs:
3010 // IDEA EBEB 2012-07-28
3011 // store signs of CCB with CCB in DCEL and use them here
3012 // *oc_it is already closed, so we do a full round
3013 // (default = false)
3014 std::pair<Sign, Sign> signs_oc =
3015 _compute_signs(*oc_it, Has_identified_sides_category());
3016
3017 bool move = false;
3018
3019 // TODO EBEB 2013-07-15 refactor into own function
3020 // TODO EBEB 2012-08-07 this either compares signs in left-right
3021 // direction OR signs in bottom-top direction, which will probably
3022 // not work for torus!
3023 if ((signs2.first != CGAL::ZERO) && (signs_oc.first != CGAL::ZERO))
3024 {
3025 if (signs2.first != signs_oc.first) move = true;
3026 }
3027 else if ((signs2.second != CGAL::ZERO) &&
3028 (signs_oc.second != CGAL::ZERO))
3029 {
3030 if (signs2.second != signs_oc.second) move = true;
3031 }
3032
3033 if (move) {
3034 // We increment the itrator before moving the outer CCB, because
3035 // this operation invalidates the iterator.
3036 increment = false;
3037 oc_to_move = oc_it;
3038 ++oc_it;
3039
3040 _move_outer_ccb(f, new_f, *oc_to_move);
3041 }
3042 }
3043
3044 if (increment) ++oc_it;
3045 }
3046 }
3047 }
3048 else {
3049 // In this case the face f is simply split into two (case 3.4).
3050 is_hole = false;
3051
3052 // In this case, he1 lies on an outer CCB of f.
3053 he1->set_outer_ccb(oc1);
3054
3055 // As the outer component of the exisitng face f may associated with
3056 // one of the halfedges along the boundary of the new face, we set it
3057 // to be he1.
3058 oc1->set_halfedge(he1);
3059 }
3060
3061 // Check whether we should mark the original face and the new face as
3062 // bounded or as unbounded faces.
3063 if (! f->is_unbounded())
3064 // The original face is bounded, so the new face split from it is
3065 // obviously bounded.
3066 new_f->set_unbounded(false);
3067 else if (is_hole)
3068 // The new face is a hole inside the original face, so it must be
3069 // bounded.
3070 new_f->set_unbounded(false);
3071 else {
3072 // Use the topology traits to determine whether each of the split
3073 // faces is unbounded. Note that if the new face is bounded, then f
3074 // obviously reamins unbounded and there is no need for further checks.
3075 new_f->set_unbounded(m_topol_traits.is_unbounded(new_f));
3076
3077 if (new_f->is_unbounded())
3078 f->set_unbounded(m_topol_traits.is_unbounded(f));
3079 }
3080
3081 // Notify the observers that we have split the face.
3082 _notify_after_split_face(fh, Face_handle(new_f), is_hole);
3083 }
3084 else {
3085 CGAL_assertion((oc1 != nullptr) && (oc2 != nullptr) && (oc1 != oc2));
3086
3087 // In case prev1 and prev2 belong to different outer CCBs of the same
3088 // face f (case 3.5), we have to merge this ccbs into one. Note that we
3089 // do not create a new face.
3090 new_face = false;
3091
3092 // Notify the observers that we are about to merge two outer CCBs.
3093 Face_handle fh(f);
3094
3095 _notify_before_merge_outer_ccb(fh,
3096 (Halfedge_handle(prev1))->ccb(),
3097 (Halfedge_handle(prev2))->ccb(),
3098 Halfedge_handle(he1));
3099
3100 // Remove the outer component prev2 belongs to, and unite it with the
3101 // outer component that prev1 belongs to.
3102 f->erase_outer_ccb(oc2);
3103
3104 // Set the merged component for the two new halfedges.
3105 he1->set_outer_ccb(oc1);
3106 he2->set_outer_ccb(oc1);
3107
3108 // Make all halfedges along oc2 to point to oc1.
3109 DHalfedge* curr;
3110
3111 for (curr = he2->next(); curr != he1; curr = curr->next())
3112 curr->set_outer_ccb(oc1);
3113
3114 // Delete the redundant outer CCB.
3115 _dcel().delete_outer_ccb(oc2);
3116
3117 // Notify the observers that we have merged the two CCBs.
3118 _notify_after_merge_outer_ccb(fh, (Halfedge_handle(he1))->ccb());
3119 }
3120
3121 // Notify the observers that we have created a new edge.
3122 _notify_after_create_edge(Halfedge_handle(he2));
3123
3124 // TODO EBEB 2012-08-08 add postcondition that checks sanity
3125 #if 0
3126 {
3127 DHalfedge* he1 = he2->opposite();
3128 DInner_ccb* ic1 = (he1->is_on_inner_ccb()) ? he1->inner_ccb() : nullptr;
3129 DOuter_ccb* oc1 = (ic1 == nullptr) ? he1->outer_ccb() : nullptr;
3130 DFace* f1 = (ic1 != nullptr) ? ic1->face() : oc1->face();
3131 DInner_ccb* ic2 = (he2->is_on_inner_ccb()) ? he2->inner_ccb() : nullptr;
3132 DOuter_ccb* oc2 = (ic2 == nullptr) ? he2->outer_ccb() : nullptr;
3133 DFace* f2 = (ic2 != nullptr) ? ic2->face() : oc2->face();
3134 CGAL_postcondition((ic1 != ic2) || (f1 == f2));
3135 }
3136 #endif
3137
3138 // Return the halfedge directed from v1 to v2.
3139 return he2;
3140 }
3141
3142 //-----------------------------------------------------------------------------
3143 // Relocate all inner CCBs (holes) to their proper position,
3144 // immediately after a face has split due to the insertion of a new halfedge.
3145 //
3146 template <typename GeomTraits, typename TopTraits>
3147 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_relocate_inner_ccbs_in_new_face(DHalfedge * new_he)3148 _relocate_inner_ccbs_in_new_face(DHalfedge* new_he)
3149 {
3150 // The given halfedge points to the new face, while its twin points to the
3151 // old face (the one that has just been split).
3152 DFace* new_face = (new_he->is_on_inner_ccb()) ?
3153 new_he->inner_ccb()->face() : new_he->outer_ccb()->face();
3154 DHalfedge* opp_he = new_he->opposite();
3155 const bool opp_on_inner_ccb = opp_he->is_on_inner_ccb();
3156 DFace* old_face = opp_on_inner_ccb ? opp_he->inner_ccb()->face() :
3157 opp_he->outer_ccb()->face();
3158
3159 CGAL_assertion(new_face != old_face);
3160
3161 // Examine the inner CCBs inside the existing old face and move the relevant
3162 // ones into the new face.
3163 DInner_ccb_iter ic_it = old_face->inner_ccbs_begin();
3164 while (ic_it != old_face->inner_ccbs_end()) {
3165 // In case the new edge represents the current component in the old face
3166 // (note we take the opposite halfedge, as it is incident to the old face),
3167 // then the new face already forms a hole in the old face, and we do not
3168 // need to move it.
3169 CGAL_assertion((*ic_it)->is_on_inner_ccb());
3170
3171 if (opp_on_inner_ccb && ((*ic_it)->inner_ccb() == opp_he->inner_ccb())) {
3172 ++ic_it;
3173 continue;
3174 }
3175
3176 // Check whether the current inner CCB is inside new face (we actually
3177 // check if a representative vertex is located in the new face).
3178 if (m_topol_traits.is_in_face(new_face, (*ic_it)->vertex()->point(),
3179 (*ic_it)->vertex()))
3180 {
3181 // We store the current iterator which get then incremented before it
3182 // gets moved, as the move operation invalidates the iterator.
3183 DInner_ccb_iter ic_to_move = ic_it;
3184 ++ic_it;
3185 _move_inner_ccb(old_face, new_face, *ic_to_move); // move the hole
3186 }
3187 else
3188 ++ic_it;
3189 }
3190 }
3191
3192 //-----------------------------------------------------------------------------
3193 // Relocate all isolated vertices to their proper position,
3194 // immediately after a face has split due to the insertion of a new halfedge.
3195 //
3196 template <typename GeomTraits, typename TopTraits>
3197 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_relocate_isolated_vertices_in_new_face(DHalfedge * new_he)3198 _relocate_isolated_vertices_in_new_face(DHalfedge* new_he)
3199 {
3200 // The given halfedge points to the new face, while its twin points to the
3201 // old face (the one that has just been split).
3202 DFace* new_face = (new_he->is_on_inner_ccb()) ?
3203 new_he->inner_ccb()->face() :
3204 new_he->outer_ccb()->face();
3205 DHalfedge* opp_he = new_he->opposite();
3206 DFace* old_face = (opp_he->is_on_inner_ccb()) ?
3207 opp_he->inner_ccb()->face() :
3208 opp_he->outer_ccb()->face();
3209
3210 CGAL_assertion(new_face != old_face);
3211
3212 // Examine the isolated vertices inside the existing old face and move the
3213 // relevant ones into the new face.
3214 DIso_vertex_iter iv_it;
3215 DIso_vertex_iter iv_to_move;
3216
3217 iv_it = old_face->isolated_vertices_begin();
3218 while (iv_it != old_face->isolated_vertices_end()) {
3219 // Check whether the isolated vertex lies inside the new face.
3220 if (m_topol_traits.is_in_face(new_face, iv_it->point(), &(*iv_it))) {
3221 // We increment the isolated vertices itrator before moving the vertex,
3222 // because this operation invalidates the iterator.
3223 iv_to_move = iv_it;
3224 ++iv_it;
3225
3226 // Move the isolated vertex.
3227 _move_isolated_vertex(old_face, new_face, &(*iv_to_move));
3228 }
3229 else
3230 ++iv_it;
3231 }
3232 }
3233
3234 //-----------------------------------------------------------------------------
3235 // Relocate all holes (inner CCBs) and isolated vertices to their proper
3236 // position, immediately after a face has split due to the insertion of a new
3237 // halfedge.
3238 //
3239 template <typename GeomTraits, typename TopTraits>
3240 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_relocate_in_new_face(DHalfedge * new_he)3241 _relocate_in_new_face(DHalfedge* new_he)
3242 {
3243 _relocate_inner_ccbs_in_new_face(new_he);
3244 _relocate_isolated_vertices_in_new_face(new_he);
3245 }
3246
3247 //-----------------------------------------------------------------------------
3248 // Replace the point associated with the given vertex.
3249 //
3250 template <typename GeomTraits, typename TopTraits>
3251 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_modify_vertex(DVertex * v,const Point_2 & p)3252 _modify_vertex(DVertex* v, const Point_2& p)
3253 {
3254 // Notify the observers that we are about to modify a vertex.
3255 Vertex_handle vh(v);
3256 _notify_before_modify_vertex(vh, p);
3257
3258 // Modify the point associated with the vertex.
3259 v->point() = p;
3260
3261 // Notify the observers that we have modified the vertex.
3262 _notify_after_modify_vertex(vh);
3263 }
3264
3265 //-----------------------------------------------------------------------------
3266 // Replace the x-monotone curve associated with the given edge.
3267 //
3268 template <typename GeomTraits, typename TopTraits>
3269 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_modify_edge(DHalfedge * he,const X_monotone_curve_2 & cv)3270 _modify_edge(DHalfedge* he, const X_monotone_curve_2& cv)
3271 {
3272 // Notify the observers that we are about to modify an edge.
3273 Halfedge_handle e(he);
3274 _notify_before_modify_edge(e, cv);
3275
3276 // Modify the curve associated with the halfedge.
3277 he->curve() = cv;
3278
3279 // Notify the observers that we have modified the edge.
3280 _notify_after_modify_edge(e);
3281 }
3282
3283 //-----------------------------------------------------------------------------
3284 // Check if the given vertex represents one of the ends of a given curve.
3285 //
3286 template <typename GeomTraits, typename TopTraits>
3287 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_are_equal(const DVertex * v,const X_monotone_curve_2 & cv,Arr_curve_end ind)3288 _are_equal(const DVertex* v,
3289 const X_monotone_curve_2& cv, Arr_curve_end ind) const
3290 {
3291 // In case the given curve end has boundary conditions, use the topology
3292 // traits to determine whether it is equivalent to v.
3293 const Arr_parameter_space ps_x =
3294 m_geom_traits->parameter_space_in_x_2_object()(cv, ind);
3295 const Arr_parameter_space ps_y =
3296 m_geom_traits->parameter_space_in_y_2_object()(cv, ind);
3297
3298 if ((ps_x != ARR_INTERIOR) || (ps_y != ARR_INTERIOR))
3299 return (m_topol_traits.are_equal(v, cv, ind, ps_x, ps_y));
3300
3301 // Otherwise, the curve end is a valid endpoint. Check that v is also
3302 // associated with a valid point that equals this endpoint.
3303 if (v->has_null_point()) return false;
3304
3305 return (ind == ARR_MIN_END) ?
3306 (m_geom_traits->equal_2_object()
3307 (m_geom_traits->construct_min_vertex_2_object()(cv), v->point())) :
3308 (m_geom_traits->equal_2_object()
3309 (m_geom_traits->construct_max_vertex_2_object()(cv), v->point()));
3310 }
3311
3312 //-----------------------------------------------------------------------------
3313 // Split a given edge into two at a given point, and associate the given
3314 // x-monotone curves with the split edges.
3315 //
3316 template <typename GeomTraits, typename TopTraits>
3317 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::DHalfedge*
3318 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_split_edge(DHalfedge * e,const Point_2 & p,const X_monotone_curve_2 & cv1,const X_monotone_curve_2 & cv2)3319 _split_edge(DHalfedge* e, const Point_2& p,
3320 const X_monotone_curve_2& cv1, const X_monotone_curve_2& cv2)
3321 {
3322 // Allocate a new vertex and associate it with the split point.
3323 // Note that this point must not have any boundary conditions.
3324 DVertex* v = _create_vertex(p);
3325
3326 // Split the edge from the given vertex.
3327 return (_split_edge(e, v, cv1, cv2));
3328 }
3329
3330 //-----------------------------------------------------------------------------
3331 // Split a given edge into two at a given vertex, and associate the given
3332 // x-monotone curves with the split edges.
3333 //
3334 template <typename GeomTraits, typename TopTraits>
3335 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::DHalfedge*
3336 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_split_edge(DHalfedge * e,DVertex * v,const X_monotone_curve_2 & cv1,const X_monotone_curve_2 & cv2)3337 _split_edge(DHalfedge* e, DVertex* v,
3338 const X_monotone_curve_2& cv1, const X_monotone_curve_2& cv2)
3339 {
3340 // Get the split halfedge and its twin, its source and target.
3341 DHalfedge* he1 = e;
3342 DHalfedge* he2 = he1->opposite();
3343 DInner_ccb* ic1 = (he1->is_on_inner_ccb()) ? he1->inner_ccb() : nullptr;
3344 DOuter_ccb* oc1 = (ic1 == nullptr) ? he1->outer_ccb() : nullptr;
3345 DInner_ccb* ic2 = (he2->is_on_inner_ccb()) ? he2->inner_ccb() : nullptr;
3346 DOuter_ccb* oc2 = (ic2 == nullptr) ? he2->outer_ccb() : nullptr;
3347
3348 // Notify the observers that we are about to split an edge.
3349 _notify_before_split_edge(Halfedge_handle(e), Vertex_handle(v), cv1, cv2);
3350
3351 // Allocate a pair of new halfedges.
3352 DHalfedge* he3 = _dcel().new_edge();
3353 DHalfedge* he4 = he3->opposite();
3354
3355 // Connect the new halfedges:
3356 //
3357 // he1 he3
3358 // -------> ------->
3359 // (.) (.)v (.)
3360 // <------- <-------
3361 // he2 he4
3362 //
3363 v->set_halfedge(he4);
3364
3365 if (he1->next() != he2) {
3366 // Connect e3 between e1 and its successor.
3367 he3->set_next(he1->next());
3368
3369 // Insert he4 between he2 and its predecessor.
3370 he2->prev()->set_next(he4);
3371 }
3372 else
3373 // he1 and he2 form an "antenna", so he4 becomes he3's successor.
3374 he3->set_next(he4);
3375
3376 if (oc1 != nullptr)
3377 he3->set_outer_ccb(oc1);
3378 else
3379 he3->set_inner_ccb(ic1);
3380
3381 he3->set_vertex(he1->vertex());
3382 he4->set_vertex(v);
3383 he4->set_next(he2);
3384
3385 if (oc2 != nullptr)
3386 he4->set_outer_ccb(oc2);
3387 else
3388 he4->set_inner_ccb(ic2);
3389
3390 if (he1->vertex()->halfedge() == he1)
3391 // If he1 is the incident halfedge to its target, he3 replaces it.
3392 he1->vertex()->set_halfedge(he3);
3393
3394 // Update the properties of the twin halfedges we have just split.
3395 he1->set_next(he3);
3396 he1->set_vertex(v);
3397
3398 // The direction of he3 is the same as he1's (and the direction of he4 is
3399 // the same as he2).
3400 he3->set_direction(he1->direction());
3401
3402 // Associate cv1 with he1 (and its twin). We allocate a new curve for cv2
3403 // and associate it with he3 (and its twin).
3404 X_monotone_curve_2* dup_cv2 = _new_curve(cv2);
3405
3406 he1->curve() = cv1;
3407 he3->set_curve(dup_cv2);
3408
3409 // Notify the observers that we have split an edge into two.
3410 _notify_after_split_edge(Halfedge_handle(he1), Halfedge_handle(he3));
3411
3412 // Return a handle for one of the existing halfedge that is incident to the
3413 // split point.
3414 return he1;
3415 }
3416
3417 template <typename GeomTraits, typename TopTraits>
3418 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_compute_indices(Arr_parameter_space,Arr_parameter_space,Arr_parameter_space,Arr_parameter_space,int &,int &,boost::mpl::bool_<false>)3419 _compute_indices(Arr_parameter_space /* ps_x_curr */,
3420 Arr_parameter_space /* ps_y_curr */,
3421 Arr_parameter_space /* ps_x_next */,
3422 Arr_parameter_space /* ps_y_next */,
3423 int& /* x_index */, int& /* y_index */,
3424 boost::mpl::bool_<false>) const
3425 { /* nothing if no identification */ }
3426
3427 template <typename GeomTraits, typename TopTraits>
3428 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_compute_indices(Arr_parameter_space ps_x_curr,Arr_parameter_space ps_y_curr,Arr_parameter_space ps_x_next,Arr_parameter_space ps_y_next,int & x_index,int & y_index,boost::mpl::bool_<true>)3429 _compute_indices(Arr_parameter_space ps_x_curr, Arr_parameter_space ps_y_curr,
3430 Arr_parameter_space ps_x_next, Arr_parameter_space ps_y_next,
3431 int& x_index, int& y_index, boost::mpl::bool_<true>) const
3432 {
3433 // If we cross the identification curve in x, then we must update the
3434 // x_index. Note that a crossing takes place in the following cases:
3435 // . .
3436 // . .
3437 // . .
3438 // . v he he . v
3439 // <-------(.)<--------- -------->(.)------->
3440 // . .
3441 // (BEFORE) . (AFTER) (BEFORE) . (AFTER)
3442 // x_index-1. x_index x_index . x_index+1
3443 //
3444 if ((ps_x_curr == ARR_LEFT_BOUNDARY) && (ps_x_next == ARR_RIGHT_BOUNDARY)) {
3445 CGAL_assertion(is_identified(Left_side_category()) &&
3446 is_identified(Right_side_category()));
3447 --x_index; // in "negative" u-direction
3448 }
3449 else if ((ps_x_curr == ARR_RIGHT_BOUNDARY) &&
3450 (ps_x_next == ARR_LEFT_BOUNDARY))
3451 {
3452 CGAL_assertion(is_identified(Left_side_category()) &&
3453 is_identified(Right_side_category()));
3454 ++x_index; // in "positive" u-direction
3455 }
3456
3457 // Check if we cross the identification curve in y.
3458 if ((ps_y_curr == ARR_BOTTOM_BOUNDARY) && (ps_y_next == ARR_TOP_BOUNDARY)) {
3459 CGAL_assertion(is_identified(Bottom_side_category()) &&
3460 is_identified(Top_side_category()));
3461 --y_index; // in "negative" v-direction
3462 }
3463 else if ((ps_y_curr == ARR_TOP_BOUNDARY) &&
3464 (ps_y_next == ARR_BOTTOM_BOUNDARY))
3465 {
3466 CGAL_assertion(is_identified(Bottom_side_category()) &&
3467 is_identified(Top_side_category()));
3468 ++y_index; // in "positive" v-direction
3469 }
3470 }
3471
3472 // Computes signs and locale minima of an open path to be closed by a
3473 // newly inserted curve.
3474 //
3475 // Precondition The OutputIterator must be a back inserter.
3476 // Precondition The traveresed ccb is an inner ccb; thus, it cannot be
3477 // on an open boundary.
3478 // Postcondition If nullptr is a local minimum, it is inserted first.
3479 // No other local minima can be nullptr.
3480 template <typename GeomTraits, typename TopTraits>
3481 template <typename OutputIterator>
3482 std::pair<Sign, Sign>
3483 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_compute_signs_and_local_minima(const DHalfedge * he_to,const X_monotone_curve_2 & cv,Arr_halfedge_direction cv_dir,const DHalfedge * he_away,OutputIterator local_mins_it)3484 _compute_signs_and_local_minima(const DHalfedge* he_to,
3485 const X_monotone_curve_2& cv,
3486 Arr_halfedge_direction cv_dir,
3487 const DHalfedge* he_away,
3488 OutputIterator local_mins_it) const
3489 {
3490 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
3491 std::cout << "he_to: " << he_to->opposite()->vertex()->point()
3492 << " => " << he_to->vertex()->point() << std::endl;
3493 std::cout << "cv: " << cv << std::endl;
3494 std::cout << "cv_dir: " << cv_dir << std::endl;
3495 std::cout << "he_away: " << he_away->opposite()->vertex()->point()
3496 << " => " << he_away->vertex()->point() << std::endl;
3497 #endif
3498
3499 // We go over the sequence of vertices, starting from he_away's target
3500 // vertex, until reaching he_to's source vertex, and find the leftmost
3501 // one. Note that we do this carefully, keeping track of the number of
3502 // times we crossed the identification curve in x or in y (if they exist).
3503 // Note that the path must not be incident to any vertex on open boundary.
3504 typename Traits_adaptor_2::Parameter_space_in_x_2 parameter_space_in_x =
3505 m_geom_traits->parameter_space_in_x_2_object();
3506 typename Traits_adaptor_2::Parameter_space_in_y_2 parameter_space_in_y =
3507 m_geom_traits->parameter_space_in_y_2_object();
3508
3509 // TODO 2012-09-20 check "correction" here too (as in "other" function of this kind
3510 int x_index = 0;
3511 int y_index = 0;
3512
3513 // Obtain the parameter space pair of cv.
3514 Arr_curve_end cv_to_end =
3515 (cv_dir == ARR_LEFT_TO_RIGHT) ? ARR_MIN_END : ARR_MAX_END;
3516 Arr_parameter_space ps_x_cv_to = parameter_space_in_x(cv, cv_to_end);
3517 Arr_parameter_space ps_y_cv_to = parameter_space_in_y(cv, cv_to_end);
3518 Arr_curve_end cv_away_end =
3519 (cv_dir == ARR_LEFT_TO_RIGHT) ? ARR_MAX_END : ARR_MIN_END;
3520 Arr_parameter_space ps_x_cv_away = parameter_space_in_x(cv, cv_away_end);
3521 Arr_parameter_space ps_y_cv_away = parameter_space_in_y(cv, cv_away_end);
3522
3523 // Obtain the parameter space pair of he_to and he_away
3524 Arr_curve_end he_to_tgt_end =
3525 (he_to->direction() == ARR_LEFT_TO_RIGHT) ? ARR_MAX_END : ARR_MIN_END;
3526 Arr_parameter_space ps_x_he_to =
3527 parameter_space_in_x(he_to->curve(), he_to_tgt_end);
3528 Arr_parameter_space ps_y_he_to =
3529 parameter_space_in_y(he_to->curve(), he_to_tgt_end);
3530 Arr_curve_end he_away_src_end =
3531 (he_away->direction() == ARR_LEFT_TO_RIGHT) ? ARR_MIN_END : ARR_MAX_END;
3532 Arr_parameter_space ps_x_he_away =
3533 parameter_space_in_x(he_away->curve(), he_away_src_end);
3534 Arr_parameter_space ps_y_he_away =
3535 parameter_space_in_y(he_away->curve(), he_away_src_end);
3536 Arr_curve_end he_away_tgt_end =
3537 (he_away->direction() == ARR_LEFT_TO_RIGHT) ? ARR_MAX_END : ARR_MIN_END;
3538 Arr_parameter_space ps_x_he_away_tgt =
3539 parameter_space_in_x(he_away->curve(), he_away_tgt_end);
3540 Arr_parameter_space ps_y_he_away_tgt =
3541 parameter_space_in_y(he_away->curve(), he_away_tgt_end);
3542
3543 Arr_parameter_space ps_x_curr, ps_y_curr;
3544 Arr_parameter_space ps_x_next, ps_y_next;
3545 Arr_parameter_space ps_x_save, ps_y_save;
3546
3547 ps_x_curr = ps_x_cv_away;
3548 ps_y_curr = ps_y_cv_away;
3549 ps_x_next = ps_x_he_away;
3550 ps_y_next = ps_y_he_away;
3551 ps_x_save = ps_x_he_away_tgt;
3552 ps_y_save = ps_y_he_away_tgt;
3553
3554 CGAL_assertion(!is_open(ps_x_curr, ps_y_curr));
3555 CGAL_assertion(!is_open(ps_x_next, ps_y_next));
3556
3557 if ((cv_dir == ARR_RIGHT_TO_LEFT) &&
3558 (he_away->direction() == ARR_LEFT_TO_RIGHT)) {
3559 const DHalfedge* null_he = nullptr;
3560 *local_mins_it++ = std::make_pair(null_he, x_index);
3561 }
3562
3563 _compute_indices(ps_x_curr, ps_y_curr, ps_x_next, ps_y_next,
3564 x_index, y_index, Has_identified_sides_category());
3565
3566 const DHalfedge* he = he_away;
3567 while (he != he_to) {
3568 ps_x_curr = ps_x_save;
3569 ps_y_curr = ps_y_save;
3570 CGAL_assertion(!is_open(ps_x_curr, ps_y_curr));
3571
3572 Arr_curve_end he_next_src_end, he_next_tgt_end;
3573 if (he->next()->direction() == ARR_LEFT_TO_RIGHT) {
3574 he_next_src_end = ARR_MIN_END;
3575 he_next_tgt_end = ARR_MAX_END;
3576 }
3577 else {
3578 he_next_src_end = ARR_MAX_END;
3579 he_next_tgt_end = ARR_MIN_END;
3580 }
3581
3582 ps_x_next = parameter_space_in_x(he->next()->curve(), he_next_src_end);
3583 ps_y_next = parameter_space_in_y(he->next()->curve(), he_next_src_end);
3584 CGAL_assertion(!is_open(ps_x_next, ps_y_next));
3585
3586 ps_x_save = parameter_space_in_x(he->next()->curve(), he_next_tgt_end);
3587 ps_y_save = parameter_space_in_y(he->next()->curve(), he_next_tgt_end);
3588
3589 // If the halfedge is directed from right to left and its successor is
3590 // directed from left to right, the target vertex might be the smallest:
3591 if ((he->direction() == ARR_RIGHT_TO_LEFT) &&
3592 (he->next()->direction() == ARR_LEFT_TO_RIGHT))
3593 *local_mins_it++ = std::make_pair(he, x_index);
3594
3595 _compute_indices(ps_x_curr, ps_y_curr, ps_x_next, ps_y_next,
3596 x_index, y_index, Has_identified_sides_category());
3597
3598 // Move to the next halfedge.
3599 he = he->next();
3600 }
3601
3602 ps_x_curr = ps_x_he_to;
3603 ps_y_curr = ps_y_he_to;
3604 ps_x_next = ps_x_cv_to;
3605 ps_y_next = ps_y_cv_to;
3606
3607 CGAL_assertion(!is_open(ps_x_curr, ps_y_curr));
3608 CGAL_assertion(!is_open(ps_x_next, ps_y_next));
3609
3610 if ((he_to->direction() == ARR_RIGHT_TO_LEFT) &&
3611 (cv_dir == ARR_LEFT_TO_RIGHT))
3612 *local_mins_it++ = std::make_pair(he_to, x_index);
3613
3614 _compute_indices(ps_x_curr, ps_y_curr, ps_x_next, ps_y_next, x_index, y_index,
3615 Has_identified_sides_category());
3616
3617 return (std::make_pair(CGAL::sign(x_index), CGAL::sign(y_index)));
3618 }
3619
3620 // Computes the signs of a closed ccb (loop) when deleting he_anchor and its
3621 // opposite belonging to different faces for the case where non of the
3622 // boundaries is identified, thus, return the pair (ZERO, ZERO)
3623 template <typename GeomTraits, typename TopTraits>
3624 std::pair<Sign, Sign>
3625 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_compute_signs(const DHalfedge *,boost::mpl::bool_<false>)3626 _compute_signs(const DHalfedge* /* he_anchor */, boost::mpl::bool_<false>) const
3627 { return (std::make_pair(ZERO, ZERO)); }
3628
3629 // Computes the signs of a closed ccb (loop) when deleting he_anchor and its
3630 // opposite belonging to different faces.
3631 template <typename GeomTraits, typename TopTraits>
3632 std::pair<Sign, Sign>
3633 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_compute_signs(const DHalfedge * he_anchor,boost::mpl::bool_<true>)3634 _compute_signs(const DHalfedge* he_anchor, boost::mpl::bool_<true>) const
3635 {
3636 // We go over the sequence of vertices, starting from he_before's target
3637 // vertex, until reaching he_after's source vertex, and find the leftmost
3638 // one. Note that we do this carefully, keeping track of the number of
3639 // times we crossed the identification curve in x or in y (if they exist).
3640 // Note that the path must not be incident to any vertex on open boundary.
3641 typename Traits_adaptor_2::Parameter_space_in_x_2 parameter_space_in_x =
3642 m_geom_traits->parameter_space_in_x_2_object();
3643 typename Traits_adaptor_2::Parameter_space_in_y_2 parameter_space_in_y =
3644 m_geom_traits->parameter_space_in_y_2_object();
3645 // typename Traits_adaptor_2::Compare_y_at_x_right_2 compare_y_at_x_right_2 =
3646 // m_geom_traits->compare_y_at_x_right_2_object();
3647
3648 // IDEA EBEB 2012-07-28 store indices of local_minima with CCB in DCEL:
3649 // - determine values upon insertion of a curve
3650 // - or if this is not possible, perform the following computation
3651 // on-demand only
3652
3653 // init with edges at first link
3654 // assuming that he_anchor has been removed
3655 const DHalfedge* he_curr = he_anchor;
3656 CGAL_assertion(! he_curr->has_null_curve());
3657 const DHalfedge* he_next = he_anchor->next();
3658 // init edge where loop should end
3659 const DHalfedge* he_end = he_anchor;
3660
3661 int x_index = 0;
3662 int y_index = 0;
3663
3664 // obtain the parameter space pair of he_curr
3665 Arr_curve_end he_curr_tgt_end =
3666 (he_curr->direction() == ARR_LEFT_TO_RIGHT) ? ARR_MAX_END : ARR_MIN_END;
3667 Arr_parameter_space ps_x_save =
3668 parameter_space_in_x(he_curr->curve(), he_curr_tgt_end);
3669 Arr_parameter_space ps_y_save =
3670 parameter_space_in_y(he_curr->curve(), he_curr_tgt_end);
3671
3672 Arr_parameter_space ps_x_curr, ps_y_curr;
3673 Arr_parameter_space ps_x_next, ps_y_next;
3674
3675 // start loop
3676 do {
3677 ps_x_curr = ps_x_save;
3678 ps_y_curr = ps_y_save;
3679 CGAL_assertion(!is_open(ps_x_curr, ps_y_curr));
3680
3681 Arr_curve_end he_next_src_end =
3682 (he_next->direction() == ARR_LEFT_TO_RIGHT) ? ARR_MIN_END : ARR_MAX_END;
3683 ps_x_next = parameter_space_in_x(he_next->curve(), he_next_src_end);
3684 ps_y_next = parameter_space_in_y(he_next->curve(), he_next_src_end);
3685 CGAL_assertion(!is_open(ps_x_next, ps_y_next));
3686
3687 Arr_curve_end he_next_tgt_end =
3688 (he_next->direction() == ARR_LEFT_TO_RIGHT) ? ARR_MAX_END : ARR_MIN_END;
3689 ps_x_save = parameter_space_in_x(he_next->curve(), he_next_tgt_end);
3690 ps_y_save = parameter_space_in_y(he_next->curve(), he_next_tgt_end);
3691
3692 _compute_indices(ps_x_curr, ps_y_curr, ps_x_next, ps_y_next,
3693 x_index, y_index, Has_identified_sides_category());
3694
3695 // iterate
3696 he_curr = he_next;
3697 he_next = he_next->next();
3698 } while (he_curr != he_end);
3699
3700 // Return the leftmost vertex and its x_index (with respect to he_before).
3701 return (std::make_pair(CGAL::sign(x_index), CGAL::sign(y_index)));
3702 }
3703
3704 // Computes the halfedge that points at the smallest vertex in a closed ccb
3705 // when deleting he_anchor and its opposite belonging to same face
3706 // (loop-about-to-split).
3707 template <typename GeomTraits, typename TopTraits>
3708 std::pair<std::pair<Sign, Sign>,
3709 const typename Arrangement_on_surface_2<GeomTraits,
3710 TopTraits>::DHalfedge*>
3711 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_compute_signs_and_min(const DHalfedge * he_anchor,Arr_parameter_space & ps_x_min,Arr_parameter_space & ps_y_min,int & index_min)3712 _compute_signs_and_min(const DHalfedge* he_anchor,
3713 Arr_parameter_space& ps_x_min,
3714 Arr_parameter_space& ps_y_min,
3715 int& index_min) const
3716 {
3717 // Initialize
3718 const DHalfedge* he_min = nullptr;
3719 ps_x_min = ARR_INTERIOR;
3720 ps_y_min = ARR_INTERIOR;
3721 index_min = 0;
3722
3723 // We go over the sequence of vertices, starting from he_before's target
3724 // vertex, until reaching he_after's source vertex, and find the leftmost
3725 // one. Note that we do this carefully, keeping track of the number of
3726 // times we crossed the identification curve in x or in y (if they exist).
3727 // Note that the path must not be incident to any vertex on open boundary.
3728 typename Traits_adaptor_2::Parameter_space_in_x_2 parameter_space_in_x =
3729 m_geom_traits->parameter_space_in_x_2_object();
3730 typename Traits_adaptor_2::Parameter_space_in_y_2 parameter_space_in_y =
3731 m_geom_traits->parameter_space_in_y_2_object();
3732
3733 // init with edges at first link.
3734 // assuming that he_anchor has been removed
3735 const DHalfedge* he_curr = he_anchor->opposite()->prev();
3736 const DHalfedge* he_next = he_anchor->next();
3737 // init edge where loop should end
3738 const DHalfedge* he_end = he_anchor->opposite();
3739
3740 int x_index = 0;
3741 int y_index = 0;
3742
3743 // obtain the parameter space pair of he_curr
3744 Arr_parameter_space ps_x_save, ps_y_save;
3745 if (he_curr->has_null_curve()) {
3746 ps_x_save = he_curr->vertex()->parameter_space_in_x();
3747 ps_y_save = he_curr->vertex()->parameter_space_in_y();
3748 }
3749 else {
3750 Arr_curve_end he_curr_tgt_end =
3751 (he_curr->direction() == ARR_LEFT_TO_RIGHT) ? ARR_MAX_END : ARR_MIN_END;
3752 ps_x_save = parameter_space_in_x(he_curr->curve(), he_curr_tgt_end);
3753 ps_y_save = parameter_space_in_y(he_curr->curve(), he_curr_tgt_end);
3754 }
3755
3756 // TODO EBEB 2012-09-20 check whether this fix is correct
3757 // EBEB 2012-08-22 the 'start' of one (out of two) loops might
3758 // be directed towards the identification.
3759 // In this cases, we have to adapt the index:
3760 int x_correction = 0;
3761 if (ps_x_save == ARR_RIGHT_BOUNDARY) {
3762 x_correction--;
3763 }
3764
3765 Arr_parameter_space ps_x_curr, ps_y_curr;
3766 Arr_parameter_space ps_x_next, ps_y_next;
3767
3768 // Start loop
3769 do {
3770 ps_x_curr = ps_x_save;
3771 ps_y_curr = ps_y_save;
3772
3773 if (he_next->has_null_curve()) {
3774 ps_x_next = he_next->opposite()->vertex()->parameter_space_in_x();
3775 ps_y_next = he_next->opposite()->vertex()->parameter_space_in_y();
3776 ps_x_save = he_next->vertex()->parameter_space_in_x();
3777 ps_y_save = he_next->vertex()->parameter_space_in_y();
3778 }
3779 else {
3780 Arr_curve_end he_next_src_end =
3781 (he_next->direction() == ARR_LEFT_TO_RIGHT) ? ARR_MIN_END : ARR_MAX_END;
3782 ps_x_next = parameter_space_in_x(he_next->curve(), he_next_src_end);
3783 ps_y_next = parameter_space_in_y(he_next->curve(), he_next_src_end);
3784
3785 Arr_curve_end he_next_tgt_end =
3786 (he_next->direction() == ARR_LEFT_TO_RIGHT) ? ARR_MAX_END : ARR_MIN_END;
3787 ps_x_save = parameter_space_in_x(he_next->curve(), he_next_tgt_end);
3788 ps_y_save = parameter_space_in_y(he_next->curve(), he_next_tgt_end);
3789 }
3790
3791 // If the halfedge is directed from right to left and its successor is
3792 // directed from left to right, the target vertex might be the smallest:
3793 if ((he_curr->direction() == ARR_RIGHT_TO_LEFT) &&
3794 (he_next->direction() == ARR_LEFT_TO_RIGHT))
3795 {
3796 const int index_curr = x_index + x_correction;
3797
3798 // Test the halfedge incident to the leftmost vertex.
3799 // Note that we may visit the same vertex several times.
3800
3801 if ((he_min == nullptr) ||
3802 (index_curr < index_min) ||
3803 ((index_curr == index_min) &&
3804 ((he_curr->vertex() != he_min->vertex()) &&
3805 _is_smaller(he_curr, ps_x_curr, ps_y_curr,
3806 he_min, ps_x_min, ps_y_min,
3807 Are_all_sides_oblivious_category()))))
3808 {
3809 index_min = index_curr;
3810 ps_x_min = ps_x_curr;
3811 ps_y_min = ps_y_curr;
3812 he_min = he_curr;
3813 }
3814 }
3815
3816 _compute_indices(ps_x_curr, ps_y_curr, ps_x_next, ps_y_next,
3817 x_index, y_index, Has_identified_sides_category());
3818
3819 // iterate
3820 he_curr = he_next;
3821 he_next = he_next->next();
3822
3823 CGAL_assertion(he_curr != he_anchor);
3824
3825 } while (he_next != he_end);
3826
3827 // Return the leftmost vertex and the signs.
3828 return std::make_pair(std::make_pair(CGAL::sign(x_index), CGAL::sign(y_index)), he_min);
3829 }
3830
3831 /* This is the implementation for the case where all 4 boundary sides are
3832 * oblivious.
3833 */
3834 template <typename GeomTraits, typename TopTraits>
3835 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_smaller(const DHalfedge * he1,Arr_parameter_space,Arr_parameter_space,const DHalfedge * he2,Arr_parameter_space,Arr_parameter_space,Arr_all_sides_oblivious_tag)3836 _is_smaller(const DHalfedge* he1,
3837 Arr_parameter_space /* ps_x1 */, Arr_parameter_space /* ps_y1 */,
3838 const DHalfedge* he2,
3839 Arr_parameter_space /* ps_x2 */, Arr_parameter_space /* ps_y2 */,
3840 Arr_all_sides_oblivious_tag) const
3841 {
3842 CGAL_precondition(he1->direction() == ARR_RIGHT_TO_LEFT);
3843 CGAL_precondition(he2->direction() == ARR_RIGHT_TO_LEFT);
3844 CGAL_precondition(he1->vertex() != he2->vertex());
3845 return
3846 (m_geom_traits->compare_xy_2_object()(he1->vertex()->point(),
3847 he2->vertex()->point()) == SMALLER);
3848 }
3849
3850 /* This is a wrapper for the case where any boundary side is not
3851 * necessarily oblivious.
3852 */
3853 template <typename GeomTraits, typename TopTraits>
3854 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_smaller(const DHalfedge * he1,Arr_parameter_space ps_x1,Arr_parameter_space ps_y1,const DHalfedge * he2,Arr_parameter_space ps_x2,Arr_parameter_space ps_y2,Arr_not_all_sides_oblivious_tag tag)3855 _is_smaller(const DHalfedge* he1,
3856 Arr_parameter_space ps_x1, Arr_parameter_space ps_y1,
3857 const DHalfedge* he2,
3858 Arr_parameter_space ps_x2, Arr_parameter_space ps_y2,
3859 Arr_not_all_sides_oblivious_tag tag) const
3860 {
3861 CGAL_precondition(he1->direction() == ARR_RIGHT_TO_LEFT);
3862 CGAL_precondition(he2->direction() == ARR_RIGHT_TO_LEFT);
3863 CGAL_precondition(he1->vertex() != he2->vertex());
3864
3865 /* If he1 points to a vertex on the left or the bottom boundary, then it
3866 * is the smaller.
3867 */
3868 if ((ps_x1 == ARR_LEFT_BOUNDARY) || (ps_y1 == ARR_BOTTOM_BOUNDARY))
3869 return true;
3870
3871 /* If he2 points to a vertex on the left or the bottom boundary, then it
3872 * is the smaller.
3873 */
3874 if ((ps_x2 == ARR_LEFT_BOUNDARY) || (ps_y2 == ARR_BOTTOM_BOUNDARY))
3875 return false;
3876
3877 return _is_smaller(he1->curve(), he1->vertex()->point(), ps_x1, ps_y1,
3878 he2->curve(), he2->vertex()->point(), ps_x2, ps_y2, tag);
3879 }
3880
3881 /* This is the implementation for the case where all 4 boundary sides are
3882 * oblivious.
3883 */
3884 template <typename GeomTraits, typename TopTraits>
3885 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_smaller(const X_monotone_curve_2 &,const Point_2 & p1,Arr_parameter_space,Arr_parameter_space,const X_monotone_curve_2 &,const Point_2 & p2,Arr_parameter_space,Arr_parameter_space,Arr_all_sides_oblivious_tag)3886 _is_smaller(const X_monotone_curve_2& /* cv1 */, const Point_2& p1,
3887 Arr_parameter_space /* ps_x1 */, Arr_parameter_space /* ps_y1 */,
3888 const X_monotone_curve_2& /* cv2 */, const Point_2& p2,
3889 Arr_parameter_space /* ps_x2 */, Arr_parameter_space /* ps_y2 */,
3890 Arr_all_sides_oblivious_tag) const
3891 {
3892 CGAL_precondition(! m_geom_traits->equal_2_object()(p1, p2));
3893 return (m_geom_traits->compare_xy_2_object()(p1, p2) == SMALLER);
3894 }
3895
3896 /*! This is the implementation for the case where any boundary side is not
3897 * necessarily oblivious.
3898 * This can be further refined as the combination of LEFT and LEFT can occur
3899 * only when the right and left boundary sides are identified.
3900 */
3901 template <typename GeomTraits, typename TopTraits>
3902 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_smaller(const X_monotone_curve_2 & cv1,const Point_2 & p1,Arr_parameter_space ps_x1,Arr_parameter_space ps_y1,const X_monotone_curve_2 & cv2,const Point_2 & p2,Arr_parameter_space ps_x2,Arr_parameter_space ps_y2,Arr_not_all_sides_oblivious_tag)3903 _is_smaller(const X_monotone_curve_2& cv1, const Point_2& p1,
3904 Arr_parameter_space ps_x1, Arr_parameter_space ps_y1,
3905 const X_monotone_curve_2& cv2, const Point_2& p2,
3906 Arr_parameter_space ps_x2, Arr_parameter_space ps_y2,
3907 Arr_not_all_sides_oblivious_tag) const
3908 {
3909 CGAL_precondition(! m_geom_traits->equal_2_object()(p1, p2));
3910
3911 if (ps_x2 == ARR_INTERIOR) {
3912 if (ps_x1 == ARR_INTERIOR) {
3913 if (ps_y2 == ARR_INTERIOR) {
3914 if (ps_y1 == ARR_INTERIOR)
3915 return (m_geom_traits->compare_xy_2_object()(p1,p2) == SMALLER);
3916
3917 // ps1 == {INTERIOR, !INTERIOR}, ps2 == {INTERIOR,INTERIOR},
3918 Comparison_result res =
3919 m_geom_traits->compare_x_on_boundary_2_object()(p2, cv1, ARR_MIN_END);
3920 return
3921 (res == EQUAL) ? (ps_y1 == ARR_BOTTOM_BOUNDARY) : (res == LARGER);
3922 }
3923
3924 if (ps_y1 == ARR_INTERIOR) {
3925 // ps1 == {INTERIOR,INTERIOR}, ps2 == {INTERIOR,!INTERIOR}
3926 Comparison_result res =
3927 m_geom_traits->compare_x_on_boundary_2_object()(p1, cv2, ARR_MIN_END);
3928 return (res == EQUAL) ? (ps_y2 == ARR_TOP_BOUNDARY) : (res == SMALLER);
3929 }
3930
3931 // ps1 == {INTERIOR,!INTERIOR}, ps2 == {INTERIOR,!INTERIOR}
3932 Comparison_result res =
3933 m_geom_traits->compare_x_on_boundary_2_object()(cv1, ARR_MIN_END,
3934 cv2, ARR_MIN_END);
3935 return (res == EQUAL) ?
3936 ((ps_y1 == ARR_BOTTOM_BOUNDARY) && (ps_y2 == ARR_TOP_BOUNDARY)) :
3937 (res == SMALLER);
3938 }
3939
3940 // ps_x2 == ARR_INTERIOR, ps_x == ARR_LEFT_BOUNDARY
3941 CGAL_assertion(ps_x1 == ARR_LEFT_BOUNDARY);
3942 return true;
3943 }
3944 if (ps_x1 == ARR_INTERIOR)
3945 // ps_x2 == ARR_LEFT_BOUNDARY, ps_x == ARR_INTERIOR
3946 return false;
3947
3948 // ps_x2 == ARR_LEFT_BOUNDARY, ps_x == ARR_LEFT_BOUNDARY
3949 Comparison_result res =
3950 m_geom_traits->compare_y_on_boundary_2_object()(p1, p2);
3951 return (res == SMALLER);
3952 }
3953
3954 /* This is the implementation for the case where all 4 boundary sides are
3955 * oblivious.
3956 */
3957 template <typename GeomTraits, typename TopTraits>
3958 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_smaller_near_right(const X_monotone_curve_2 & cv1,const X_monotone_curve_2 & cv2,const Point_2 & p,Arr_parameter_space,Arr_parameter_space,Arr_all_sides_oblivious_tag)3959 _is_smaller_near_right(const X_monotone_curve_2& cv1,
3960 const X_monotone_curve_2& cv2,
3961 const Point_2& p,
3962 Arr_parameter_space /* ps_x */,
3963 Arr_parameter_space /* ps_y */,
3964 Arr_all_sides_oblivious_tag) const
3965 {
3966 return
3967 (m_geom_traits->compare_y_at_x_right_2_object()(cv1, cv2, p) == SMALLER);
3968 }
3969
3970 /*! This is the implementation for the case where any one of the 4 boundary
3971 * sides can be of any type.
3972 */
3973 template <typename GeomTraits, typename TopTraits>
3974 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_smaller_near_right(const X_monotone_curve_2 & cv1,const X_monotone_curve_2 & cv2,const Point_2 & p,Arr_parameter_space ps_x,Arr_parameter_space ps_y,Arr_not_all_sides_oblivious_tag)3975 _is_smaller_near_right(const X_monotone_curve_2& cv1,
3976 const X_monotone_curve_2& cv2,
3977 const Point_2& p,
3978 Arr_parameter_space ps_x, Arr_parameter_space ps_y,
3979 Arr_not_all_sides_oblivious_tag) const
3980 {
3981 CGAL_precondition((ps_x == ARR_INTERIOR) || (ps_x == ARR_LEFT_BOUNDARY));
3982 CGAL_precondition((ps_y == ARR_INTERIOR) || (ps_x == ARR_BOTTOM_BOUNDARY));
3983
3984 if ((ps_x == ARR_INTERIOR) && (ps_y == ARR_INTERIOR))
3985 return
3986 (m_geom_traits->compare_y_at_x_right_2_object()(cv1, cv2, p) == SMALLER);
3987 return
3988 (m_geom_traits->compare_y_near_boundary_2_object()(cv1, cv2, ARR_MIN_END) ==
3989 SMALLER);
3990 }
3991
3992 //-----------------------------------------------------------------------------
3993 // Determine whether a given subsequence (halfedge, curve, halfedge)
3994 // lies in the interior of a new face we are about to create
3995 // Comment: This is how the situation looks
3996 // ----to---> >>cv_dir>> ---away--->
3997 // o ===cv=== 0
3998 // <-tonext-- <-awaynext-
3999 // or to be read from right to left ... this way, he_to and he_away lie
4000 // BEFORE insertion on the same inner ccb and
4001 // AFTER insertion on the same outer ccb
4002 //
4003 // Precondition: The range of local minima [lm_begin,lm_end) is greater than 0.
4004 // That is, there is at least one local minimum, which might be the leftend
4005 // of cv itself.
4006 // Precondition: If the leftend of cv is a local minimum, it must be the first
4007 // in the range.
4008 template <typename GeomTraits, typename TopTraits>
4009 template <typename InputIterator>
4010 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_defines_outer_ccb_of_new_face(const DHalfedge * he_to,const X_monotone_curve_2 & cv,const DHalfedge * he_away,InputIterator lm_begin,InputIterator lm_end)4011 _defines_outer_ccb_of_new_face(const DHalfedge* he_to,
4012 const X_monotone_curve_2& cv,
4013 const DHalfedge* he_away,
4014 InputIterator lm_begin,
4015 InputIterator lm_end) const
4016 {
4017 // Search for the leftmost vertex among the local minima
4018 typename Traits_adaptor_2::Parameter_space_in_x_2 parameter_space_in_x =
4019 m_geom_traits->parameter_space_in_x_2_object();
4020 typename Traits_adaptor_2::Parameter_space_in_y_2 parameter_space_in_y =
4021 m_geom_traits->parameter_space_in_y_2_object();
4022
4023 // check all reported local minima
4024 InputIterator lm_it = lm_begin;
4025
4026 int index_min = lm_it->second;
4027 const DHalfedge* he_min = lm_it->first;
4028 const DVertex* v_min =
4029 (he_min == nullptr) ? he_away->opposite()->vertex() : he_min->vertex();
4030 const X_monotone_curve_2* cv_min =
4031 (he_min == nullptr) ? &cv : &(he_min->curve());
4032 Arr_parameter_space ps_x_min = parameter_space_in_x(*cv_min, ARR_MIN_END);
4033 Arr_parameter_space ps_y_min = parameter_space_in_y(*cv_min, ARR_MIN_END);
4034
4035 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
4036 std::cout << "1 set global min to " << *cv_min << std::endl;
4037 #endif
4038
4039 for (++lm_it; lm_it != lm_end; ++lm_it) {
4040 const DHalfedge* he = lm_it->first;
4041 CGAL_assertion(he->direction() == CGAL::ARR_RIGHT_TO_LEFT);
4042 int index = lm_it->second;
4043 Arr_parameter_space ps_x_he_min =
4044 parameter_space_in_x(he->curve(), ARR_MIN_END);
4045 Arr_parameter_space ps_y_he_min =
4046 parameter_space_in_y(he->curve(), ARR_MIN_END);
4047
4048 // If the following condition is met, the vertex is indeed the smallest:
4049 // The current x_index is smaller than the x_index of the smallest
4050 // recorded, or
4051 // The current x_index is equivalent to the recorded x_index, and
4052 // - No smallest has bin recorded so far, or
4053 // - The current target vertex and the recorded vertex are the same and
4054 // * The current curve is smaller than the recorded curve, or
4055 // - The current curve end is smaller than the recorded curve end.
4056 // smaller than its source, so we should check whether it is also smaller
4057 // Note that we compare the vertices lexicographically: first by the
4058 // indices, then by x, then by y.
4059
4060 if ((index < index_min) ||
4061 ((index == index_min) &&
4062 ((v_min == he->vertex()) ?
4063 _is_smaller_near_right(he->curve(), *cv_min,
4064 v_min->point(), ps_x_min, ps_y_min,
4065 Are_all_sides_oblivious_category()) :
4066 _is_smaller(he->curve(), he->vertex()->point(),
4067 ps_x_he_min, ps_y_he_min,
4068 *cv_min, v_min->point(), ps_x_min, ps_y_min,
4069 Are_all_sides_oblivious_category()))))
4070 {
4071 index_min = index;
4072 cv_min = &(he->curve());
4073 ps_x_min = ps_x_he_min;
4074 ps_y_min = ps_y_he_min;
4075 he_min = he;
4076 v_min = he->vertex();
4077 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
4078 std::cout << "2 set global min to " << *cv_min << std::endl;
4079 #endif
4080 }
4081 }
4082
4083 CGAL_assertion(v_min != nullptr);
4084 CGAL_assertion(!v_min->has_null_point());
4085
4086 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
4087 std::cout << "v_min: " << v_min->point() << std::endl;
4088 std::cout << "he_min: ";
4089 if (he_min)
4090 std::cout << he_min->opposite()->vertex()->point()
4091 << " => " << he_min->vertex()->point();
4092 else std::cout << "nullptr";
4093 std::cout << std::endl;
4094 #endif
4095
4096 CGAL_assertion(! he_min || (he_min->direction() == ARR_RIGHT_TO_LEFT));
4097
4098 // Note that the curves of the leftmost edge and its successor are defined
4099 // to the right of the leftmost vertex. We compare them to the right of this
4100 // point to determine whether he_to (the curve) and he_away are incident to
4101 // the hole to be created or not.
4102 const X_monotone_curve_2& cv_next = (he_min == nullptr) ?
4103 he_away->curve() : ((he_min == he_to) ? cv : he_min->next()->curve());
4104 return _is_above(*cv_min, cv_next, v_min->point(), ps_y_min,
4105 Top_or_bottom_sides_category());
4106 }
4107
4108 // Is the first given x-monotone curve above the second given?
4109 // This function is invoked when the bottom and top boundaries are neither
4110 // identified nor contracted
4111 template <typename GeomTraits, typename TopTraits>
4112 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_above(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,const Point_2 & point,Arr_parameter_space,Arr_boundary_cond_tag)4113 _is_above(const X_monotone_curve_2& xcv1, const X_monotone_curve_2& xcv2,
4114 const Point_2& point,
4115 Arr_parameter_space /* ps_y1 */,
4116 Arr_boundary_cond_tag) const
4117 {
4118 return (m_geom_traits->compare_y_at_x_right_2_object()(xcv1, xcv2, point) ==
4119 LARGER);
4120 }
4121
4122 // Is the first given x-monotone curve above the second given?
4123 // This function is invoked when the bottom and top boundaries are identified
4124 template <typename GeomTraits, typename TopTraits>
4125 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_above(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,const Point_2 & point,Arr_parameter_space ps_y1,Arr_has_identified_side_tag)4126 _is_above(const X_monotone_curve_2& xcv1, const X_monotone_curve_2& xcv2,
4127 const Point_2& point,
4128 Arr_parameter_space ps_y1,
4129 Arr_has_identified_side_tag) const
4130 {
4131 // Check whether the vertex lies on the identification curve in y,
4132 // in which case special care must be taken.
4133 if ((ps_y1 == ARR_BOTTOM_BOUNDARY) || (ps_y1 == ARR_TOP_BOUNDARY)) {
4134 // TODO EBEB 2010-10-08 is this code really executed or should it be part
4135 // of top traits?
4136
4137 // Both current and next curves are incident to the identification curve.
4138 // As v_min is the leftmost vertex, we know that their left ends must have
4139 // a boundary condition of type identification in y.
4140 Arr_parameter_space ps_y2 =
4141 m_geom_traits->parameter_space_in_y_2_object()(xcv2, ARR_MIN_END);
4142
4143 // Check if the curves lie on opposite sides of the identification curve.
4144 if ((ps_y1 == ARR_BOTTOM_BOUNDARY) && (ps_y2 == ARR_TOP_BOUNDARY))
4145 // In this case the current curve is "above" the next one to the right
4146 // of v_min, in a cyclic order around the identification curve.
4147 return true;
4148
4149 if ((ps_y1 == ARR_TOP_BOUNDARY) && (ps_y2 == ARR_BOTTOM_BOUNDARY))
4150 // In this case the current curve is "below" the next one to the right
4151 // of v_min, in a cyclic order around the identification curve.
4152 return false;
4153
4154 // If both curves are on the same side of the identification curve, we
4155 // continue to compare them to the right of v_min.
4156 CGAL_assertion(((ps_y1 == ARR_BOTTOM_BOUNDARY) &&
4157 (ps_y2 == ARR_BOTTOM_BOUNDARY)) ||
4158 ((ps_y1 == ARR_TOP_BOUNDARY) &&
4159 (ps_y2 == ARR_TOP_BOUNDARY)));
4160 }
4161
4162 return _is_above(xcv1, xcv2, point, ps_y1, Arr_all_sides_oblivious_tag());
4163 }
4164
4165 // Is the first given x-monotone curve above the second given?
4166 // This function is invoked when the bottom or top boundaries are contracted
4167 template <typename GeomTraits, typename TopTraits>
4168 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_above(const X_monotone_curve_2 & xcv1,const X_monotone_curve_2 & xcv2,const Point_2 & point,Arr_parameter_space ps_y1,Arr_has_contracted_side_tag)4169 _is_above(const X_monotone_curve_2& xcv1, const X_monotone_curve_2& xcv2,
4170 const Point_2& point,
4171 Arr_parameter_space ps_y1,
4172 Arr_has_contracted_side_tag) const
4173 {
4174 // Check whether the leftmost vertex is a contraction point in y,
4175 // in which case special care must be taken.
4176 if (((ps_y1 == ARR_TOP_BOUNDARY) && is_contracted(Bottom_side_category())) ||
4177 ((ps_y1 == ARR_BOTTOM_BOUNDARY) && is_contracted(Top_side_category())))
4178 {
4179 // Compare the horizontal position of the two curve-ends at the point
4180 // of contraction.
4181 Comparison_result x_res =
4182 m_geom_traits->compare_x_curve_ends_2_object()(xcv1, ARR_MIN_END,
4183 xcv2, ARR_MIN_END);
4184
4185 // Observe that if x_res == EQUAL the given subsequence is always exterior.
4186 return (((ps_y1 == ARR_BOTTOM_BOUNDARY) && (x_res == SMALLER)) ||
4187 ((ps_y1 == ARR_TOP_BOUNDARY) && (x_res == LARGER)));
4188 }
4189
4190 return _is_above(xcv1, xcv2, point, ps_y1, Arr_all_sides_oblivious_tag());
4191 }
4192
4193
4194 //-----------------------------------------------------------------------------
4195 // Remove a pair of twin halfedges from the arrangement.
4196 // In case the removal causes the creation of a new hole, the given halfedge
4197 // should point at this hole.
4198 //
4199 template <typename GeomTraits, typename TopTraits>
4200 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::DFace*
4201 Arrangement_on_surface_2<GeomTraits, TopTraits>::
_remove_edge(DHalfedge * e,bool remove_source,bool remove_target)4202 _remove_edge(DHalfedge* e, bool remove_source, bool remove_target)
4203 {
4204 // Obtain the pair of twin edges to be removed, the connected components they
4205 // belong to and their incident faces.
4206 DHalfedge* he1 = e;
4207 DHalfedge* he2 = e->opposite();
4208 DInner_ccb* ic1 = (he1->is_on_inner_ccb()) ? he1->inner_ccb() : nullptr;
4209 DOuter_ccb* oc1 = (ic1 == nullptr) ? he1->outer_ccb() : nullptr;
4210 DFace* f1 = (oc1 != nullptr) ? oc1->face() : ic1->face();
4211 DInner_ccb* ic2 = (he2->is_on_inner_ccb()) ? he2->inner_ccb() : nullptr;
4212 DOuter_ccb* oc2 = (ic2 == nullptr) ? he2->outer_ccb() : nullptr;
4213 DFace* f2 = (oc2 != nullptr) ? oc2->face() : ic2->face();
4214
4215 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
4216 #if 0
4217 std::cout << "before swap" << std::endl;
4218 std::cout << "he1c: " << he1->curve() << ", " << he1->direction()
4219 << std::endl;
4220 std::cout << "he2c: " << he2->curve() << ", " << he2->direction()
4221 << std::endl;
4222 std::cout << "he1: " << he1 << std::endl;
4223 std::cout << "he2: " << he2 << std::endl;
4224 std::cout << "ic1: " << ic1 << std::endl;
4225 std::cout << "ic2: " << ic2 << std::endl;
4226 std::cout << "oc1: " << oc1 << std::endl;
4227 std::cout << "oc2: " << oc2 << std::endl;
4228 std::cout << "f1 : " << f1 << std::endl;
4229 std::cout << "f2 : " << f2 << std::endl;
4230 #endif
4231 #endif
4232
4233 // will be used for "_hole_creation_on_edge_removal"
4234 std::pair< CGAL::Sign, CGAL::Sign > signs1(ZERO, ZERO);
4235 std::pair< CGAL::Sign, CGAL::Sign > signs2(ZERO, ZERO);
4236
4237 bool swap_he1_he2 = false;
4238 if (f1 != f2) {
4239 // If f1 != f2, the removal of he1 (and its twin halfedge) will cause
4240 // the two incident faces to merge. Thus, swapping is not needed. However,
4241 // it is more efficient to retain the face that has a larger number of
4242 // inner ccbs.
4243
4244 // f1 is the face to be kept by default. If f2 has more holes it is more
4245 // efficient to kept f2
4246 if (f1->number_of_inner_ccbs() < f2->number_of_inner_ccbs())
4247 swap_he1_he2 = true;
4248 }
4249 else {
4250 // If f1 == f2 (same_face-case), then we consider two loops that occur when
4251 // he1 and he2 get removed; if f1 != f2, then he1 and he2 separates the two
4252 // faces that will be merged upon their removal---here both he1 and he2
4253 // belong to a full cycle, and THAT IS WHY we give the f1 == f2 test to
4254 // determine whether end of loop should be he1->opposite() and
4255 // he2->opposite(), respectively.
4256
4257 // If the removal of he1 (and its twin halfedge) form an "antenna", there
4258 // is neither a need to compute signs and nor swapping of the halfedges
4259 if ((he1->next() != he2) && (he2->next() != he1)) {
4260
4261 // In this case one of the following can happen: (a) a new hole will be
4262 // created by the removal of the edge (case 3.2.1 of the removal
4263 // procedure), or (b) an outer CCB will be split into two (case 3.2.2).
4264 // We begin by locating the leftmost vertex along the path from he1 to its
4265 // twin he2 and the leftmost vertex point along the path from the twin to
4266 // he1 (both paths do not include he1 and he2 themselves).
4267
4268 // Comment EFEF 2013-05-31: if we ever find the need to use signs1 and
4269 // signs2 out of this scope (for the non-planar case), the code must be
4270 // dispatched, so that the planar case is not affected.
4271
4272 // Compute signs of ccbs for he1 and he2 used later for
4273 // _hole_creation_on_edge_removal
4274
4275 // Compute the signs and minimum along ccb of he1:
4276 Arr_parameter_space ps_x_min1, ps_y_min1;
4277 int index_min1;
4278 std::pair<std::pair<Sign, Sign>, const DHalfedge*> res1 =
4279 _compute_signs_and_min(he1, ps_x_min1, ps_y_min1, index_min1);
4280 signs1 = res1.first;
4281 const DHalfedge* he_min1 = res1.second;
4282
4283 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
4284 std::cout << "signs1.x: " << signs1.first << std::endl;
4285 std::cout << "signs1.y: " << signs1.second << std::endl;
4286 if (! he_min1->has_null_curve())
4287 std::cout << "he_min1: " << he_min1->curve() << std::endl;
4288 else std::cout << "he_min1 fictitious" << std::endl;
4289 #endif
4290
4291 // Compute the signs and minimum along ccb of he2:
4292 Arr_parameter_space ps_x_min2, ps_y_min2;
4293 int index_min2;
4294 std::pair<std::pair<Sign, Sign>, const DHalfedge*> res2 =
4295 _compute_signs_and_min(he2, ps_x_min2, ps_y_min2, index_min2);
4296 signs2 = res2.first;
4297 const DHalfedge* he_min2 = res2.second;
4298
4299 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
4300 std::cout << "signs2.x: " << signs2.first << std::endl;
4301 std::cout << "signs2.y: " << signs2.second << std::endl;
4302 if (! he_min2->has_null_curve())
4303 std::cout << "he_min2: " << he_min2->curve() << std::endl;
4304 else std::cout << "he_min2 fictitious" << std::endl;
4305 #endif
4306
4307 // TODO EBEB 2012-07-29
4308 // is this the right thing to do for torus, or let TopTraits decide?
4309 bool is_perimetric1 = signs1.first || signs1.second;
4310 bool is_perimetric2 = signs2.first || signs2.second;
4311
4312 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
4313 std::cout << std::endl
4314 << "index 1: " << index_min1
4315 << ", ps_x_min1: " << ps_x_min1
4316 << ", ps_y_min1: " << ps_y_min1
4317 << ", is_perimetric1: " << is_perimetric1
4318 << std::endl;
4319
4320 std::cout << "index 2: " << index_min2
4321 << ", ps_x_min2: " << ps_x_min2
4322 << ", ps_y_min2: " << ps_y_min2
4323 << ", is_perimetric2: " << is_perimetric2
4324 << std::endl;
4325 #endif
4326
4327 if (is_perimetric1 || is_perimetric2) {
4328 #if 1 // this is old code
4329 swap_he1_he2 =
4330 (! is_perimetric1) ? false :
4331 ((! is_perimetric2) ? true : false);
4332 // We are in case (a) and he1 is directed to the new hole to be
4333 // created or
4334 // We are in case (a) and he2 is directed to the new hole to be
4335 // created.
4336 // Both paths are perimetric; thus, we are in case (b).
4337 #else // THIS IS NEW CODE 2012-08-06 which is much easier to read
4338 swap_he1_he2 = !is_perimetric2;
4339 #endif
4340 }
4341 else {
4342 // const DVertex* v_min1 = he_min1->vertex(); const DVertex* v_min2 =
4343 // he_min2->vertex(); Both paths from he1 to he2 and back from he2 to
4344 // he1 are not perimetric, so we are in case (a). As we want to
4345 // determine which halfedge points to the new hole to be created (he1
4346 // or he2), we have to compare the two leftmost vertices
4347 // lexicographically, first by the indices then by x and y. v_min2
4348 // lies to the left of v_min1 if and only if he1 points at the hole we
4349 // are about to create.
4350 //
4351 // +---------------------+
4352 // | |
4353 // | he1 +----+ |
4354 // +--------->+ | |
4355 // | +----+ |
4356 // | v_min1 |
4357 // | |
4358 // v_min2 +---------------------+
4359 //
4360 // Note that if one of the paths we have examined ends at a boundary
4361 // side of the parameter space (and only of the paths may end at a
4362 // boundary side of the parameter space), then the other path becomes
4363 // a hole in a face bounded by the parameter-space boundary.
4364
4365 // TODO EBEB 2012-08-22 check whether this fix is correct
4366 // EBEB 2012-08-22 the 'start' of the two loops might lie
4367 // on different sides of the identification, which is only
4368 // problematic when either he1 or he2 points to the
4369 // identification. In these cases, we have to adapt the indices:
4370 typename Traits_adaptor_2::Parameter_space_in_x_2
4371 parameter_space_in_x =
4372 m_geom_traits->parameter_space_in_x_2_object();
4373
4374 Arr_curve_end he1_tgt_end =
4375 (he1->direction() == ARR_LEFT_TO_RIGHT ? ARR_MAX_END : ARR_MIN_END);
4376 Arr_parameter_space ps_x_he1_tgt =
4377 parameter_space_in_x(he1->curve(), he1_tgt_end);
4378 if (ps_x_he1_tgt == ARR_RIGHT_BOUNDARY) index_min2 -= 1;
4379
4380 Arr_curve_end he2_tgt_end =
4381 (he2->direction() == ARR_LEFT_TO_RIGHT ? ARR_MAX_END : ARR_MIN_END);
4382 Arr_parameter_space ps_x_he2_tgt =
4383 parameter_space_in_x(he2->curve(), he2_tgt_end);
4384 if (ps_x_he2_tgt == ARR_RIGHT_BOUNDARY) index_min1 -= 1;
4385
4386 swap_he1_he2 =
4387 (index_min1 > index_min2) ? false :
4388 ((index_min1 < index_min2) ? true :
4389 _is_smaller(he_min1, ps_x_min1, ps_y_min1,
4390 he_min2, ps_x_min2, ps_y_min2,
4391 Are_all_sides_oblivious_category()));
4392 }
4393 }
4394 }
4395 // swapping?
4396 if (swap_he1_he2) {
4397 // swap all entries
4398 std::swap(he1, he2);
4399 std::swap(ic1, ic2);
4400 std::swap(oc1, oc2);
4401 std::swap(f1 , f2);
4402 // not needed below here std::swap(local_mins1, local_mins2);
4403 std::swap(signs1, signs2);
4404 }
4405
4406 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
4407 #if 0
4408 std::cout << "after swap" << std::endl;
4409 std::cout << "he1c: " << he1->curve() << ", " << he1->direction()
4410 << std::endl;
4411 std::cout << "he1c: " << he2->curve() << ", " << he2->direction()
4412 << std::endl;
4413 std::cout << "he1: " << he1 << std::endl;
4414 std::cout << "he2: " << he2 << std::endl;
4415 std::cout << "ic1: " << ic1 << std::endl;
4416 std::cout << "ic2: " << ic2 << std::endl;
4417 std::cout << "oc1: " << oc1 << std::endl;
4418 std::cout << "oc2: " << oc2 << std::endl;
4419 std::cout << "f1 : " << f1 << std::endl;
4420 std::cout << "f2 : " << f2 << std::endl;
4421 #endif
4422 #endif
4423
4424 // Now the real removal starts.
4425 DHalfedge* prev1 = nullptr;
4426 DHalfedge* prev2 = nullptr;
4427
4428 // Notify the observers that we are about to remove an edge.
4429 Halfedge_handle hh(e);
4430
4431 _notify_before_remove_edge(hh);
4432
4433 // Check if the two incident faces are equal, in which case no face will be
4434 // merged and deleted (and a hole may be created).
4435 if (f1 == f2) {
4436 // Check whether the two halfedges are successors along the face boundary.
4437 if ((he1->next() == he2) && (he2->next() == he1)) {
4438 CGAL_assertion((ic1 != nullptr) && (ic1 == ic2));
4439
4440 // The two halfedges form a "singleton" hole inside the incident face
4441 // (case 1 of the removal procedure, as detailed in the design document),
4442 // so we simply have to remove it.
4443
4444 // Notify before the removal of this hole (inner CCB).
4445 // Erase the inner CCB from the incident face.
4446 // Delete the corresponding component.
4447 // Notify after the removal.
4448 Face_handle fh(f1);
4449 _notify_before_remove_inner_ccb(fh, (Halfedge_handle(he1))->ccb());
4450 f1->erase_inner_ccb(ic1);
4451 _dcel().delete_inner_ccb(ic1);
4452 _notify_after_remove_inner_ccb(fh);
4453
4454 DVertex* v1 = he1->vertex();
4455 DVertex* v2 = he2->vertex();
4456
4457 _delete_curve(he1->curve());
4458 _dcel().delete_edge(he1);
4459
4460 #ifndef CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
4461 _notify_after_remove_edge();
4462 #endif
4463
4464 // Remove the end-vertices, if necessary.
4465 if (remove_target) {
4466 if ((v1->parameter_space_in_x() != ARR_INTERIOR) ||
4467 (v1->parameter_space_in_y() != ARR_INTERIOR))
4468 {
4469 v1->set_halfedge(nullptr); // disconnect the end vertex
4470 _remove_vertex_if_redundant(v1, f1);
4471 }
4472 else {
4473 // Delete the he1's target vertex and its associated point.
4474 _notify_before_remove_vertex(Vertex_handle(v1));
4475
4476 _delete_point(v1->point());
4477 _dcel().delete_vertex(v1);
4478
4479 _notify_after_remove_vertex();
4480 }
4481 }
4482 else
4483 // The remaining target vertex now becomes an isolated vertex inside
4484 // the containing face:
4485 _insert_isolated_vertex(f1, v1);
4486
4487 if (remove_source) {
4488 if ((v2->parameter_space_in_x() != ARR_INTERIOR) ||
4489 (v2->parameter_space_in_y() != ARR_INTERIOR))
4490 {
4491 v2->set_halfedge(nullptr); // disconnect the end vertex
4492 _remove_vertex_if_redundant(v2, f1);
4493 }
4494 else {
4495 // Delete the he1's source vertex and its associated point.
4496 _notify_before_remove_vertex(Vertex_handle(v2));
4497
4498 _delete_point(v2->point());
4499 _dcel().delete_vertex(v2);
4500
4501 _notify_after_remove_vertex();
4502 }
4503 }
4504 else
4505 // The remaining source vertex now becomes an isolated vertex inside
4506 // the containing face:
4507 _insert_isolated_vertex(f1, v2);
4508
4509 #ifdef CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
4510 _notify_after_remove_edge();
4511 #endif
4512
4513 // Return the face that used to contain the hole.
4514 return f1;
4515 }
4516
4517 if ((he1->next() == he2) || (he2->next() == he1)) {
4518 CGAL_assertion((oc1 == oc2) && (ic1 == ic2));
4519
4520 // In this case the two halfedges form an "antenna" (case 2).
4521 // Make he1 point at the tip of this "antenna" (swap the pointer if
4522 // necessary).
4523 bool remove_tip_vertex = remove_target;
4524
4525 if (he2->next() == he1) {
4526 he1 = he2;
4527 he2 = he1->opposite();
4528 remove_tip_vertex = remove_source;
4529 }
4530
4531 // Remove the two halfedges from the boundary chain by connecting
4532 // he1's predecessor with he2's successor.
4533 prev1 = he1->prev();
4534 prev1->set_next(he2->next());
4535
4536 // In case the halfedges to be deleted are represantatives of their
4537 // CCB (note that noth should belong to the same CCB, be it an outer
4538 // CCB or an inner one), make prev1 the components representative.
4539 if ((oc1 != nullptr) &&
4540 ((oc1->halfedge() == he1) || (oc1->halfedge() == he2)))
4541 oc1->set_halfedge(prev1);
4542 else if ((ic1 != nullptr) &&
4543 ((ic1->halfedge() == he1) || (ic1->halfedge() == he2)))
4544 ic1->set_halfedge(prev1);
4545
4546 // In case he2 is the representative halfedge of its target vertex,
4547 // replace it by prev1 (which also points at this vertex).
4548 if (he2->vertex()->halfedge() == he2)
4549 he2->vertex()->set_halfedge(prev1);
4550
4551 DVertex* v1 = he1->vertex();
4552 DVertex* v2 = he2->vertex();
4553
4554 _delete_curve(he1->curve());
4555 _dcel().delete_edge(he1);
4556
4557 #ifndef CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
4558 _notify_after_remove_edge();
4559 #endif
4560
4561 // Try to temove the base vertex, in case it has boundary conditions.
4562 if ((v2->parameter_space_in_x() != ARR_INTERIOR) ||
4563 (v2->parameter_space_in_y() != ARR_INTERIOR))
4564 _remove_vertex_if_redundant(v2, f1);
4565
4566 // Remove the redundant tip vertex, if necessary.
4567 if (remove_tip_vertex) {
4568 if ((v1->parameter_space_in_x() != ARR_INTERIOR) ||
4569 (v1->parameter_space_in_y() != ARR_INTERIOR))
4570 {
4571 v1->set_halfedge(nullptr); // disconnect the end vertex
4572 _remove_vertex_if_redundant(v1, f1);
4573 }
4574 else {
4575 // Delete the vertex that forms the tip of the "antenna".
4576 _notify_before_remove_vertex(Vertex_handle(v1));
4577
4578 _delete_point(v1->point());
4579 _dcel().delete_vertex(v1);
4580
4581 _notify_after_remove_vertex();
4582 }
4583 }
4584 else
4585 // The remaining "antenna" tip now becomes an isolated vertex inside
4586 // the containing face:
4587 _insert_isolated_vertex(f1, v1);
4588
4589 #ifdef CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
4590 _notify_after_remove_edge();
4591 #endif
4592
4593 // Return the incident face.
4594 return f1;
4595 }
4596
4597 // In this case the degree of both end-vertices is at least 2, so we
4598 // can use the two predecessor halfedges of he1 and he2.
4599 bool add_inner_ccb = false;
4600
4601 prev1 = he1->prev();
4602 prev2 = he2->prev();
4603
4604 if ((ic1 != nullptr) && (ic1 == ic2)) {
4605
4606 // If both halfedges lie on the same inner component (hole) inside the
4607 // face (case 3.1), we have to split this component into two holes.
4608 //
4609 // +-----------------------------+
4610 // | prev1 |
4611 // | +----+ / +----+ |
4612 // | | +......+ | |
4613 // | +----+ +----+ |
4614 // | |
4615 // +-----------------------------+
4616 //
4617 // Notify the observers we are about to split an inner CCB.
4618 _notify_before_split_inner_ccb(Face_handle(f1),
4619 (Halfedge_handle
4620 (*(ic1->iterator())))->ccb(),
4621 Halfedge_handle(he1));
4622
4623 // We first make prev1 the new representative halfedge of the first
4624 // inner CCB.
4625 ic1->set_halfedge(prev1);
4626
4627 // Create a new component that represents the new hole we split.
4628 DInner_ccb* new_ic = _dcel().new_inner_ccb();
4629 f1->add_inner_ccb(new_ic, prev2);
4630 new_ic->set_face(f1);
4631
4632 // Associate all halfedges along the hole boundary with the new inner
4633 // component.
4634 DHalfedge* curr;
4635 for (curr = he1->next(); curr != he2; curr = curr->next())
4636 curr->set_inner_ccb(new_ic);
4637
4638 // Notify the observers that the hole has been split.
4639 _notify_after_split_inner_ccb(Face_handle(f1),
4640 (Halfedge_handle(prev1))->ccb(),
4641 (Halfedge_handle(prev2))->ccb());
4642 }
4643 else if (oc1 != oc2) {
4644 // RWRW: NEW!
4645 CGAL_assertion((oc1 != nullptr) && (oc2 != nullptr));
4646
4647 // In case both halfegdes he1 and he2 are incident to the same face
4648 // but lie on different outer CCBs of this face, removing this pair of
4649 // halfedge causes the two components two merge and to become an
4650 // inner CCB in the face.
4651 // We first remove the outer CCB oc1 from f, and inform the observers
4652 // on doing so.
4653 Face_handle fh(f1);
4654
4655 _notify_before_remove_outer_ccb(fh, (Halfedge_handle(he1))->ccb());
4656 f1->erase_outer_ccb(oc1);
4657 _dcel().delete_outer_ccb(oc1);
4658 _notify_after_remove_outer_ccb(fh);
4659
4660 // We now remove the outer CCBs oc2 from f, and inform the observers
4661 // on doing so.
4662 _notify_before_remove_outer_ccb(fh, (Halfedge_handle(he2))->ccb());
4663 f2->erase_outer_ccb(oc2);
4664 _dcel().delete_outer_ccb(oc2);
4665 _notify_after_remove_outer_ccb(fh);
4666
4667 // Mark that we should eventually add a new inner CCB inside the face.
4668 add_inner_ccb = true;
4669 }
4670 else {
4671 CGAL_assertion((oc1 != nullptr) && (oc1 == oc2));
4672
4673 // If both halfedges are incident to the same outer CCB of their
4674 // face (case 3.2), we have to distinguish two sub-cases:
4675 // TODO EBEB 2012-07-30 replace with signs
4676 if (_hole_creation_on_edge_removal(signs1, signs2, true)) {
4677 // We have to create a new hole in the interior of the incident face
4678 // (case 3.2.1):
4679 //
4680 // +-----------------------------+
4681 // | prev1 |
4682 // v +----+ |
4683 // +........>+ | |
4684 // | he1 +----+ |
4685 // | |
4686 // +-----------------------------+
4687 //
4688 // Note that it is guaranteed that he1 points at this new hole, while
4689 // he2 points at the boundary of the face that contains this hole.
4690 // First notify the observers we are about to form a new inner
4691 // CCB inside f1.
4692 _notify_before_add_inner_ccb(Face_handle(f1),
4693 Halfedge_handle(he1->next()));
4694
4695 // Create a new component that represents the new hole.
4696 DInner_ccb* new_ic = _dcel().new_inner_ccb();
4697
4698 f1->add_inner_ccb(new_ic, he1->next());
4699 new_ic->set_face(f1);
4700
4701 // Associate all halfedges along the hole boundary with the new inner
4702 // component.
4703 DHalfedge* curr;
4704 for (curr = he1->next(); curr != he2; curr = curr->next())
4705 curr->set_inner_ccb(new_ic);
4706
4707 // As the outer CCB of f1 may be represented by any of the
4708 // halfedges in between he1 -> ... -> he2 (the halfedges in between
4709 // represent the outer boundary of the new hole that is formed),
4710 // We represent the outer boundary of f1 by prev1, which definitely
4711 // stays on the outer boundary.
4712 oc1->set_halfedge(prev1);
4713
4714 // Notify the observers that a new hole has been formed.
4715 Ccb_halfedge_circulator hccb = (Halfedge_handle(he1->next()))->ccb();
4716
4717 _notify_after_add_inner_ccb(hccb);
4718 }
4719 else {
4720 // We have to split the outer CCB into two outer components
4721 // (case 3.2.2), such that the number of outer CCBs of the face is
4722 // incremented.
4723 //
4724 // +----------------------------+
4725 // | |
4726 // | prev1 |
4727 // +<........+<.................|
4728 // | | |
4729 // | | |
4730 // | | |
4731 // | | |
4732 // | prev2 | |
4733 // +........>+..................|
4734 // | |
4735 // +----------------------------+
4736 //
4737
4738 // First we notify the observers that we are about to split an outer
4739 // component.
4740 _notify_before_split_outer_ccb(Face_handle(f1),
4741 Halfedge_handle(he1)->ccb(),
4742 Halfedge_handle(he1));
4743
4744 // Create a new outer component.
4745 DOuter_ccb* new_oc = _dcel().new_outer_ccb();
4746
4747 f1->add_outer_ccb(new_oc, he1->next());
4748 new_oc->set_face(f1);
4749
4750 // Associate all halfedges from he1 until he2 with the new CCB.
4751 DHalfedge* curr;
4752
4753 for (curr = he1->next(); curr != he2; curr = curr->next())
4754 curr->set_outer_ccb(new_oc);
4755
4756 // As the outer CCB of f1 may be represented by any of the
4757 // halfedges in between he1 -> ... -> he2 (the halfedges in between
4758 // are on the new outer CCB we have just created), we represent the
4759 // former outer CCB by prev1, which definitely stays on it.
4760 oc1->set_halfedge(prev1);
4761
4762 // Notify the observers that a new outer CCB has been formed.
4763 _notify_after_split_outer_ccb(Face_handle(f1),
4764 Halfedge_handle(he1->next())->ccb(),
4765 Halfedge_handle(prev1)->ccb());
4766 }
4767 }
4768
4769 // Disconnect the two halfedges we are about to delete from the edge list.
4770 prev1->set_next(he2->next());
4771 prev2->set_next(he1->next());
4772
4773 // If one of these edges is an incident halfedge of its target vertex,
4774 // replace it by the appropriate predecessor.
4775 if (he1->vertex()->halfedge() == he1)
4776 he1->vertex()->set_halfedge(prev2);
4777
4778 if (he2->vertex()->halfedge() == he2)
4779 he2->vertex()->set_halfedge(prev1);
4780
4781 DVertex* v1 = he1->vertex();
4782 DVertex* v2 = he2->vertex();
4783
4784 _delete_curve(he1->curve());
4785 _dcel().delete_edge(he1);
4786
4787 // RWRW: NEW!
4788 // In case we have to create a new inner CCB inside the face (new removal
4789 // case), do it now.
4790 if (add_inner_ccb) {
4791 // Notify the observers that we are about to create a new inner CCB
4792 // inside the merged face.
4793 Halfedge_handle hh(prev1);
4794
4795 _notify_before_add_inner_ccb(Face_handle(f1), hh);
4796
4797 // Initiate a new inner CCB inside the given face.
4798 DInner_ccb* new_ic = _dcel().new_inner_ccb();
4799
4800 f1->add_inner_ccb(new_ic, prev1);
4801 new_ic->set_face(f1);
4802
4803 // Set the innser CCB of the halfedges along the component boundary.
4804 DHalfedge* curr = prev1;
4805
4806 do {
4807 curr->set_inner_ccb(new_ic);
4808 curr = curr->next();
4809 } while (curr != prev1);
4810
4811 // Notify the observers that we have formed a new inner CCB.
4812 _notify_after_add_inner_ccb(hh->ccb());
4813 }
4814
4815 #ifndef CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
4816 _notify_after_remove_edge();
4817 #endif
4818
4819 // Remove the end vertices, in case they become redundant.
4820 // We defer the removal of the end vertices (in case they are indeed
4821 // redundant) to occur after the observer is notified that the edge has
4822 // been removed, to match the case where the end vertices are associated
4823 // with concrete points, and need to be removed as they became isolated
4824 // vertices, and the user has requested the removal of isolated end vertices.
4825 if ((v1->parameter_space_in_x() != ARR_INTERIOR) ||
4826 (v1->parameter_space_in_y() != ARR_INTERIOR))
4827 _remove_vertex_if_redundant(v1, f1);
4828
4829 if ((v2->parameter_space_in_x() != ARR_INTERIOR) ||
4830 (v2->parameter_space_in_y() != ARR_INTERIOR))
4831 _remove_vertex_if_redundant(v2, f1);
4832
4833 #ifdef CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
4834 _notify_after_remove_edge();
4835 #endif
4836
4837 // Return the incident face.
4838 return f1;
4839 }
4840
4841 CGAL_assertion(f1 != f2);
4842
4843 // The two incident faces are not the same - in this case, the edge we are
4844 // about to delete separates these two faces. We therefore have to delete
4845 // one of these faces and merge it with the other face.
4846 // First notify the observers we are about to merge the two faces.
4847 _notify_before_merge_face(Face_handle(f1), Face_handle(f2),
4848 Halfedge_handle(he1));
4849
4850 // We begin by checking whether one of the faces is a hole inside the other
4851 // face.
4852 DHalfedge* curr;
4853
4854 prev1 = he1->prev();
4855 prev2 = he2->prev();
4856
4857 CGAL_assertion((ic1 == nullptr) || (ic2 == nullptr));
4858
4859 if ((ic1 == nullptr) && (ic2 == nullptr)) {
4860 bool add_inner_ccb = false;
4861
4862 // Comment EFEF 2013-05-31: if we ever find the need to use signs1 and
4863 // signs2 out of this scope (for the non-planar case), the code must be
4864 // dispatched, so that the planar case is not affected.
4865
4866 // Compute the signs of the ccbs for he1 and he2.
4867 // The signs are computed here, a sub case of (f1 != f2), in addition to
4868 // the case (f1 == f2) above. This way unnecessary computations of the
4869 // signs are avoided.
4870
4871 // EFEF 2013-07-29. The call to _compute_signs() is dispatched.
4872 // Currently, only 2 cases are supported, namely, the case where non of
4873 // the boundaries are identified and the case where at least one pair of
4874 // opposite boundaries are identified. However, the code for the latter
4875 // assumes that non of the (other) boundaries is open. A 3rd version
4876 // that supports the remaining case, (for example the cylinder), should
4877 // be developed and used.
4878 signs1 = _compute_signs(he1, Has_identified_sides_category());
4879 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
4880 std::cout << "signs1.x: " << signs1.first << std::endl;
4881 std::cout << "signs1.y: " << signs1.second << std::endl;
4882 #endif
4883
4884 signs2 = _compute_signs(he2, Has_identified_sides_category());
4885 #if CGAL_ARRANGEMENT_ON_SURFACE_INSERT_VERBOSE
4886 std::cout << "signs2.x: " << signs2.first << std::endl;
4887 std::cout << "signs2.y: " << signs2.second << std::endl;
4888 #endif
4889
4890 // Both halfedges lie on the outer boundary of their incident faces
4891 // (case 3.4). We have to distinguish two possible sub-cases.
4892 // TODO EBEB 2012-07-30 replace with signs
4893 if (_hole_creation_on_edge_removal(signs1, signs2, false)) {
4894 // We have to remove the outer CCBs of f1 and f2 that he1 and he2 lie
4895 // on, and create a new hole in the merged face (case 3.4.2).
4896 // We first remove the outer CCB oc1 from f1, and inform the observers
4897 // on doing so.
4898 _notify_before_remove_outer_ccb(Face_handle(f1),
4899 (Halfedge_handle(he1))->ccb());
4900
4901 f1->erase_outer_ccb(oc1);
4902 _dcel().delete_outer_ccb(oc1);
4903
4904 _notify_after_remove_outer_ccb(Face_handle(f1));
4905
4906 // We now remove the outer CCBs oc2 from f2, and inform the observers
4907 // on doing so.
4908 _notify_before_remove_outer_ccb(Face_handle(f2),
4909 (Halfedge_handle(he2))->ccb());
4910
4911 f2->erase_outer_ccb(oc2);
4912 _dcel().delete_outer_ccb(oc2);
4913
4914 _notify_after_remove_outer_ccb(Face_handle(f2));
4915
4916 // Mark that we should eventually add a new inner CCB in the merged face.
4917 add_inner_ccb = true;
4918 }
4919 else {
4920 // f1 and f2 are two adjacent faces (case 3.4.1), so we simply merge
4921 // them.
4922 // We first set the connected component of f2's outer-boundary halfedges
4923 // to be the same as f1's outer component.
4924 for (curr = he2->next(); curr != he2; curr = curr->next())
4925 curr->set_outer_ccb(oc1);
4926 }
4927
4928 _move_all_inner_ccb(f2, f1); // move all inner CCBs from f2 to f1
4929
4930 // In case he1, which is about to be deleted, is a representative
4931 // halfedge of outer component of f1, we replace it by its predecessor.
4932 if (oc1->halfedge() == he1)
4933 oc1->set_halfedge(prev1);
4934
4935 _move_all_isolated_vertices(f2, f1); // move all iso vertices from f2 to f1
4936
4937 // If he1 or he2 are the incident halfedges to their target vertices,
4938 // we replace them by the appropriate predecessors.
4939 if (he1->vertex()->halfedge() == he1)
4940 he1->vertex()->set_halfedge(prev2);
4941
4942 if (he2->vertex()->halfedge() == he2)
4943 he2->vertex()->set_halfedge(prev1);
4944
4945 // Disconnect the two halfedges we are about to delete from the edge
4946 // list.
4947 prev1->set_next(he2->next());
4948 prev2->set_next(he1->next());
4949
4950 // If the face f2 we have just merged with f1 is unbounded, then the
4951 // merged face is also unbounded.
4952 if (f2->is_unbounded())
4953 f1->set_unbounded(true);
4954
4955 // Delete the face f2.
4956 _dcel().delete_face(f2);
4957
4958 // Notify the observers that the faces have been merged.
4959 _notify_after_merge_face(Face_handle(f1));
4960
4961 DVertex* v1 = he1->vertex();
4962 DVertex* v2 = he2->vertex();
4963
4964 _delete_curve(he1->curve());
4965 _dcel().delete_edge(he1);
4966
4967 // In case we have to create a new inner CCB inside the merged face
4968 // (case 3.4.1), do it now.
4969 if (add_inner_ccb) {
4970 // Notify the observers that we are about to create a new inner CCB
4971 // inside the merged face.
4972 Halfedge_handle hh(prev1);
4973
4974 _notify_before_add_inner_ccb(Face_handle(f1), hh);
4975
4976 // Initiate a new inner CCB inside the given face.
4977 DInner_ccb* new_ic = _dcel().new_inner_ccb();
4978
4979 f1->add_inner_ccb(new_ic, prev1);
4980 new_ic->set_face(f1);
4981
4982 // Set the innser CCB of the halfedges along the component boundary.
4983 curr = prev1;
4984 do {
4985 curr->set_inner_ccb(new_ic);
4986 curr = curr->next();
4987 } while (curr != prev1);
4988
4989 // Notify the observers that we have formed a new inner CCB.
4990 _notify_after_add_inner_ccb(hh->ccb());
4991 }
4992
4993 #ifndef CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
4994 _notify_after_remove_edge();
4995 #endif
4996
4997 // Remove the end vertices, in case they become redundant.
4998 // We defer the removal of the end vertices (in case they are indeed
4999 // redundant) to occur after the observer is notified that the edge has
5000 // been removed, to match the case where the end vertices are associated
5001 // with concrete points, and need to be removed as they became isolated
5002 // vertices, and the user has requested the removal of isolated end vertices.
5003 if ((v1->parameter_space_in_x() != ARR_INTERIOR) ||
5004 (v1->parameter_space_in_y() != ARR_INTERIOR))
5005 _remove_vertex_if_redundant(v1, f1);
5006
5007 if ((v2->parameter_space_in_x() != ARR_INTERIOR) ||
5008 (v2->parameter_space_in_y() != ARR_INTERIOR))
5009 _remove_vertex_if_redundant(v2, f1);
5010
5011 #ifdef CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
5012 _notify_after_remove_edge();
5013 #endif
5014
5015 // Return the merged face.
5016 return f1;
5017 }
5018
5019 // In this case we merge a face with another face that now forms a hole
5020 // inside it (case 3.3). We first make sure that f1 contains the hole f2, so
5021 // we can merge f2 with it (we swap roles between the halfedges if
5022 // necessary).
5023 if (ic2 != nullptr) {
5024 he1 = he2;
5025 he2 = he1->opposite();
5026
5027 ic1 = ic2;
5028 ic2 = nullptr;
5029
5030 oc2 = oc1;
5031 oc1 = nullptr;
5032
5033 DFace* tf = f1;
5034 f1 = f2;
5035 f2 = tf;
5036
5037 prev1 = he1->prev();
5038 prev2 = he2->prev();
5039 }
5040
5041 // By removing the edge we open a closed face f2 contained in f1. By doing
5042 // this, the outer boundary of f2 unites with the hole boundary that ic1
5043 // represents. We therefore have to set the component of all halfedges
5044 // along the boundary of f2 to be ic1.
5045 for (curr = he2->next(); curr != he2; curr = curr->next())
5046 curr->set_inner_ccb(ic1);
5047
5048 _move_all_inner_ccb(f2, f1); // move the inner CCBs from f2 to f1
5049 _move_all_isolated_vertices(f2, f1); // move all iso vertices from f2 to f1
5050
5051 // Notice that f2 will be merged with f1, but its boundary will still be
5052 // a hole inside this face. In case he1 is a represantative of this hole,
5053 // replace it by its predecessor.
5054 if (ic1->halfedge() == he1)
5055 ic1->set_halfedge(prev1);
5056
5057 // If he1 or he2 are the incident halfedges to their target vertices,
5058 // we replace them by the appropriate predecessors.
5059 if (he1->vertex()->halfedge() == he1)
5060 he1->vertex()->set_halfedge(prev2);
5061
5062 if (he2->vertex()->halfedge() == he2)
5063 he2->vertex()->set_halfedge(prev1);
5064
5065 // Disconnect the two halfedges we are about to delete from the edge
5066 // list.
5067 prev1->set_next(he2->next());
5068 prev2->set_next(he1->next());
5069
5070 // If the face f2 we have just merged with f1 is unbounded, then the merged
5071 // face is also unbounded.
5072 if (f2->is_unbounded())
5073 f1->set_unbounded(true);
5074
5075 // Delete the face f2.
5076 _dcel().delete_face(f2);
5077
5078 // Notify the observers that the faces have been merged.
5079 _notify_after_merge_face(Face_handle(f1));
5080
5081 DVertex* v1 = he1->vertex();
5082 DVertex* v2 = he2->vertex();
5083
5084 _delete_curve(he1->curve());
5085 _dcel().delete_edge(he1);
5086
5087 #ifndef CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
5088 _notify_after_remove_edge();
5089 #endif
5090
5091 // Remove the end vertices, in case they become redundant.
5092 // We defer the removal of the end vertices (in case they are indeed
5093 // redundant) to occur after the observer is notified that the edge has
5094 // been removed, to match the case where the end vertices are associated
5095 // with concrete points, and need to be removed as they became isolated
5096 // vertices, and the user has requested the removal of isolated end vertices.
5097 if ((v1->parameter_space_in_x() != ARR_INTERIOR) ||
5098 (v1->parameter_space_in_y() != ARR_INTERIOR))
5099 _remove_vertex_if_redundant(v1, f1);
5100
5101 if ((v2->parameter_space_in_x() != ARR_INTERIOR) ||
5102 (v2->parameter_space_in_y() != ARR_INTERIOR))
5103 _remove_vertex_if_redundant(v2, f1);
5104
5105 #ifdef CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
5106 _notify_after_remove_edge();
5107 #endif
5108
5109 // Return the merged face.
5110 return f1;
5111
5112 // TODO EBEB 2012-08-06 it seems that a torus case is missing
5113 }
5114
5115 // Decide whether a hole is created
5116 template <typename GeomTraits, typename TopTraits>
5117 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_hole_creation_on_edge_removal(std::pair<CGAL::Sign,CGAL::Sign> signs1,std::pair<CGAL::Sign,CGAL::Sign> signs2,bool same_face)5118 _hole_creation_on_edge_removal(std::pair< CGAL::Sign, CGAL::Sign > signs1,
5119 std::pair< CGAL::Sign, CGAL::Sign > signs2,
5120 bool same_face) {
5121 // EBEB 2013-07-16 Remark: For tiled surfaces, this function has to respect the
5122 // topology of the tiled surface
5123
5124 // TODO EBEB 2013-07-16 Add code for torus (double identification)
5125 CGAL::Sign sign1 = signs1.first;
5126 CGAL::Sign sign2 = signs2.first;
5127
5128 if (same_face) return true;
5129 return ((CGAL::ZERO != sign1) && (sign1 == opposite(sign2)));
5130 }
5131
5132 //-----------------------------------------------------------------------------
5133 // Remove a vertex in case it becomes redundant after the deletion of an
5134 // incident edge.
5135 //
5136 template <typename GeomTraits, typename TopTraits>
5137 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_remove_vertex_if_redundant(DVertex * v,DFace * f)5138 _remove_vertex_if_redundant(DVertex* v, DFace* f)
5139 {
5140 CGAL_precondition((v->parameter_space_in_x() != ARR_INTERIOR) ||
5141 (v->parameter_space_in_y() != ARR_INTERIOR));
5142
5143 // In case the vertex has no incident halfedges, remove it if it is
5144 // redundant. Otherwise, make it an isolated vertex.
5145 if (v->halfedge() == nullptr) {
5146 if (m_topol_traits.is_redundant(v)) {
5147 // Remove the vertex and notify the observers on doing so.
5148 _notify_before_remove_vertex(Vertex_handle(v));
5149
5150 m_topol_traits.erase_redundant_vertex(v);
5151
5152 // Note the topology traits do not free the vertex - we now do it.
5153 if (! v->has_null_point())
5154 _delete_point(v->point());
5155 _dcel().delete_vertex(v);
5156
5157 _notify_after_remove_vertex();
5158 }
5159 else
5160 // Keep the vertex as an isolated one.
5161 _insert_isolated_vertex(f, v);
5162 return;
5163 }
5164
5165 // Get the first two incident halfedges of v.
5166 DHalfedge* he1 = v->halfedge();
5167 DHalfedge* he2 = he1->next()->opposite();
5168
5169 if (he2->next()->opposite() != he1)
5170 // In this case there are more than two incident edges, so v obviously
5171 // cannot be removed.
5172 return;
5173
5174 if (! he1->has_null_curve() || ! he2->has_null_curve())
5175 // We can only merge fictitious halfedges.
5176 return;
5177
5178 // Now check if the vertex is redundant. If it is, remove it by merging
5179 // its two incident fictitious halfedges.
5180 if (m_topol_traits.is_redundant(v)) {
5181 // Use the topology traits to merge the two fictitious halfedges.
5182 _notify_before_merge_fictitious_edge(Halfedge_handle(he1),
5183 Halfedge_handle(he2));
5184
5185 he1 = m_topol_traits.erase_redundant_vertex(v);
5186
5187 _notify_after_merge_fictitious_edge(Halfedge_handle(he1));
5188
5189 // Note the topology traits do not free the vertex - we now do it.
5190 _notify_before_remove_vertex(Vertex_handle(v));
5191
5192 if (! v->has_null_point())
5193 _delete_point(v->point());
5194 _dcel().delete_vertex(v);
5195
5196 _notify_after_remove_vertex();
5197 }
5198 }
5199
5200 //-----------------------------------------------------------------------------
5201 // Remove an isolated vertex from the interior of a given face (but not from
5202 // the DCEL).
5203 //
5204 template <typename GeomTraits, typename TopTraits>
5205 void Arrangement_on_surface_2<GeomTraits, TopTraits>::
_remove_isolated_vertex(DVertex * v)5206 _remove_isolated_vertex(DVertex* v)
5207 {
5208 // Remove the isolated vertex from the face and delete its record.
5209 DIso_vertex* iv = v->isolated_vertex();
5210 DFace* f = iv->face();
5211
5212 f->erase_isolated_vertex(iv);
5213 _dcel().delete_isolated_vertex(iv);
5214 }
5215
5216 //---------------------------------------------------------------------------
5217 // Check whether the arrangement is valid. In particular, check the
5218 // validity of each vertex, halfedge, and face.
5219 //
5220 template <typename GeomTraits, typename TopTraits>
is_valid()5221 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::is_valid() const
5222 {
5223 Vertex_const_iterator vit;
5224 bool is_vertex_valid;
5225 for (vit = vertices_begin(); vit != vertices_end(); ++vit) {
5226 is_vertex_valid = _is_valid(vit);
5227 if (!is_vertex_valid) {
5228 CGAL_warning_msg(is_vertex_valid, "Invalid vertex.");
5229 return false;
5230 }
5231 }
5232
5233 Halfedge_const_iterator heit;
5234 bool is_halfedge_valid;
5235 for (heit = halfedges_begin(); heit != halfedges_end(); ++heit) {
5236 is_halfedge_valid = _is_valid(heit);
5237 if (! is_halfedge_valid) {
5238 CGAL_warning_msg(is_halfedge_valid, "Invalid halfedge.");
5239 return false;
5240 }
5241 }
5242
5243 Face_const_iterator fit;
5244 bool is_face_valid;
5245
5246 for (fit = faces_begin(); fit != faces_end(); ++fit) {
5247 is_face_valid = _is_valid(fit);
5248 if (! is_face_valid) {
5249 CGAL_warning_msg(is_face_valid, "Invalid face.");
5250 return false;
5251 }
5252 }
5253
5254 bool are_vertices_unique = _are_vertices_unique();
5255 if (! are_vertices_unique) {
5256 CGAL_warning_msg(are_vertices_unique,
5257 "Found two vertices with the same geometric point.");
5258 return false;
5259 }
5260
5261 // If we reached here, the arrangement is valid.
5262 return true;
5263 }
5264
5265 //---------------------------------------------------------------------------
5266 // Check the validity of a vertex.
5267 //
5268 template <typename GeomTraits, typename TopTraits>
5269 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_valid(Vertex_const_handle v)5270 _is_valid(Vertex_const_handle v) const
5271 {
5272 // Do not check isolated vertices, as they have no incident halfedges.
5273 if (v->is_isolated()) return true;
5274
5275 // Make sure that the vertex is the target of all its incident halfedges.
5276 Halfedge_around_vertex_const_circulator circ = v->incident_halfedges();
5277 Halfedge_around_vertex_const_circulator start = circ;
5278
5279 do {
5280 if (circ->target() != v) return false;
5281 ++circ;
5282 } while (circ != start);
5283
5284 // In case of a non-boundary vertex, make sure the curves are correctly
5285 // ordered around this vertex.
5286 if ((v->parameter_space_in_x() == ARR_INTERIOR) &&
5287 (v->parameter_space_in_y() == ARR_INTERIOR))
5288 {
5289 if (! _are_curves_ordered_cw_around_vertrex(v)) return false;
5290 }
5291
5292 return true;
5293 }
5294
5295 //---------------------------------------------------------------------------
5296 // Check the validity of a halfedge.
5297 //
5298 template <typename GeomTraits, typename TopTraits>
5299 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_valid(Halfedge_const_handle he)5300 _is_valid(Halfedge_const_handle he) const
5301 {
5302 // Check relations with the previous and the next halfedges.
5303 if (he->prev()->target() != he->source()) return false;
5304
5305 if (he->target() != he->next()->source()) return false;
5306
5307 // Check relations with the twin.
5308 if (he != he->twin()->twin()) return false;
5309
5310 if (he->source() != he->twin()->target() ||
5311 he->target() != he->twin()->source())
5312 return false;
5313
5314 if (he->direction() == he->twin()->direction()) return false;
5315
5316 // Stop here in case of a fictitious edge.
5317 if (he->is_fictitious()) return true;
5318
5319 // Check that the end points of the curve associated with the halfedge
5320 // really equal the source and target vertices of this halfedge.
5321 const X_monotone_curve_2& cv = he->curve();
5322 const DVertex* source = _vertex(he->source());
5323 const DVertex* target = _vertex(he->target());
5324 Comparison_result res = ((source->parameter_space_in_x() == ARR_INTERIOR) &&
5325 (source->parameter_space_in_y() == ARR_INTERIOR) &&
5326 (target->parameter_space_in_x() == ARR_INTERIOR) &&
5327 (target->parameter_space_in_y() == ARR_INTERIOR)) ?
5328 m_geom_traits->compare_xy_2_object()(source->point(), target->point()) :
5329 ((he->direction() == ARR_LEFT_TO_RIGHT) ? SMALLER : LARGER);
5330
5331 if (res == SMALLER) {
5332 if (he->direction() != ARR_LEFT_TO_RIGHT)
5333 return false;
5334
5335 return (_are_equal(_vertex(he->source()), cv, ARR_MIN_END) &&
5336 _are_equal(_vertex(he->target()), cv, ARR_MAX_END));
5337 }
5338 else if (res == LARGER) {
5339 if (he->direction() != ARR_RIGHT_TO_LEFT)
5340 return false;
5341
5342 return (_are_equal(_vertex(he->source()), cv, ARR_MAX_END) &&
5343 _are_equal(_vertex(he->target()), cv, ARR_MIN_END));
5344 }
5345
5346 // In that case, the source and target of the halfedge are equal.
5347 return false;
5348 }
5349
5350 //---------------------------------------------------------------------------
5351 // Check the validity of a face.
5352 //
5353 template <typename GeomTraits, typename TopTraits>
5354 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_valid(Face_const_handle f)5355 _is_valid(Face_const_handle f) const
5356 {
5357 // Check if all outer components of the face refer to f.
5358 const DFace* p_f = _face(f);
5359 DOuter_ccb_const_iter oc_it;
5360 const DHalfedge* he;
5361 const DOuter_ccb* oc;
5362 for (oc_it = p_f->outer_ccbs_begin(); oc_it != p_f->outer_ccbs_end(); ++oc_it)
5363 {
5364 he = *oc_it;
5365 if (he->is_on_inner_ccb()) return false;
5366
5367 oc = he->outer_ccb();
5368 if (oc->face() != p_f) return false;
5369
5370 if (! _is_outer_ccb_valid(oc, he)) return false;
5371 }
5372
5373 // Check if all inner components of the face refer to f.
5374 DInner_ccb_const_iter ic_it;
5375 const DInner_ccb* ic;
5376
5377 for (ic_it = p_f->inner_ccbs_begin(); ic_it != p_f->inner_ccbs_end(); ++ic_it)
5378 {
5379 he = *ic_it;
5380 if (! he->is_on_inner_ccb()) return false;
5381
5382 ic = he->inner_ccb();
5383 if (ic->face() != p_f) return false;
5384
5385 if (! _is_inner_ccb_valid(ic, he)) return false;
5386 }
5387
5388 // Check if all isolated vertices inside the face refer to f.
5389 DIso_vertex_const_iter iv_it;
5390 const DVertex* v;
5391 const DIso_vertex* iv;
5392 for (iv_it = p_f->isolated_vertices_begin();
5393 iv_it != p_f->isolated_vertices_end(); ++iv_it)
5394 {
5395 v = &(*iv_it);
5396 if (! v->is_isolated()) return false;
5397
5398 iv = v->isolated_vertex();
5399 if (iv->face() != p_f) return false;
5400 }
5401
5402 // If we reached here, the face is valid.
5403 return true;
5404 }
5405
5406 //---------------------------------------------------------------------------
5407 // Check the validity of an outer CCB.
5408 //
5409 template <typename GeomTraits, typename TopTraits>
5410 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_outer_ccb_valid(const DOuter_ccb * oc,const DHalfedge * first)5411 _is_outer_ccb_valid(const DOuter_ccb* oc, const DHalfedge* first) const
5412 {
5413 // Make sure that all halfedges along the CCB refer to the same component.
5414 const DHalfedge* curr = first;
5415 bool found_rep = false;
5416
5417 do {
5418 if (curr->is_on_inner_ccb()) return false;
5419
5420 if (oc != curr->outer_ccb()) return false;
5421
5422 if (! found_rep && oc->halfedge() == curr) found_rep = true;
5423
5424 curr = curr->next();
5425 } while (curr != first);
5426
5427 // Return if we found the CCB representative along the outer CCB.
5428 return found_rep;
5429 }
5430
5431 //---------------------------------------------------------------------------
5432 // Check the validity of an inner CCB.
5433 //
5434 template <typename GeomTraits, typename TopTraits>
5435 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_is_inner_ccb_valid(const DInner_ccb * ic,const DHalfedge * first)5436 _is_inner_ccb_valid(const DInner_ccb* ic, const DHalfedge* first) const
5437 {
5438 // Make sure that all halfedges along the CCB refer to the same component.
5439 const DHalfedge* curr = first;
5440 bool found_rep = false;
5441
5442 do {
5443 if (! curr->is_on_inner_ccb()) return false;
5444
5445 if (ic != curr->inner_ccb()) return false;
5446
5447 if (! found_rep && ic->halfedge() == curr) found_rep = true;
5448
5449 curr = curr->next();
5450 } while (curr != first);
5451
5452 // Return if we found the CCB representative along the inner CCB.
5453 return found_rep;
5454 }
5455
5456 //---------------------------------------------------------------------------
5457 // Check that all vertices are unique (no two vertices with the same
5458 // geometric point).
5459 //
5460 template <typename GeomTraits, typename TopTraits>
5461 bool
_are_vertices_unique()5462 Arrangement_on_surface_2<GeomTraits, TopTraits>::_are_vertices_unique() const
5463 {
5464 if (number_of_vertices() < 2) return true;
5465
5466 // Store all points associated with non-boundary vertices.
5467 std::vector<Point_2> points_vec(number_of_vertices());
5468 Vertex_const_iterator vit;
5469 unsigned int i = 0;
5470
5471 for (vit = vertices_begin(); vit != vertices_end(); ++vit) {
5472 if ((vit->parameter_space_in_x() == ARR_INTERIOR) &&
5473 (vit->parameter_space_in_y() == ARR_INTERIOR))
5474 {
5475 points_vec[i] = vit->point();
5476 ++i;
5477 }
5478 }
5479 points_vec.resize(i);
5480
5481 // Sort the vector of points and make sure no two adjacent points in the
5482 // sorted vector are equal.
5483 typedef typename Traits_adaptor_2::Compare_xy_2 Compare_xy_2;
5484 typedef typename Traits_adaptor_2::Equal_2 Equal_2;
5485
5486 Equal_2 equal = m_geom_traits->equal_2_object();
5487 Compare_xy_2 compare_xy = m_geom_traits->compare_xy_2_object();
5488 Compare_to_less<Compare_xy_2> cmp = compare_to_less(compare_xy);
5489
5490 std::sort(points_vec.begin(), points_vec.end(), cmp);
5491 for (i = 1; i < points_vec.size(); ++i) {
5492 if (equal(points_vec[i-1], points_vec[i])) return false;
5493 }
5494
5495 return true;
5496 }
5497
5498 //---------------------------------------------------------------------------
5499 // Check that the curves around a given vertex are ordered clockwise.
5500 //
5501 template <typename GeomTraits, typename TopTraits>
5502 bool Arrangement_on_surface_2<GeomTraits, TopTraits>::
_are_curves_ordered_cw_around_vertrex(Vertex_const_handle v)5503 _are_curves_ordered_cw_around_vertrex(Vertex_const_handle v) const
5504 {
5505 if (v->degree() < 3) return true;
5506
5507 typename Traits_adaptor_2::Is_between_cw_2 is_between_cw =
5508 m_geom_traits->is_between_cw_2_object();
5509
5510 Halfedge_around_vertex_const_circulator circ = v->incident_halfedges();
5511 Halfedge_around_vertex_const_circulator first = circ;
5512 Halfedge_around_vertex_const_circulator prev, next;
5513 bool eq1, eq2;
5514
5515 do {
5516 prev = circ; --prev;
5517 next = circ; ++next;
5518
5519 if (!is_between_cw(circ->curve(), (circ->direction() == ARR_RIGHT_TO_LEFT),
5520 prev->curve(), (prev->direction() == ARR_RIGHT_TO_LEFT),
5521 next->curve(), (next->direction() == ARR_RIGHT_TO_LEFT),
5522 v->point(), eq1, eq2))
5523 return false;
5524
5525 if (eq1 || eq2) return false;
5526
5527 ++circ;
5528 } while (circ != first);
5529
5530 return true;
5531 }
5532
5533 } // namespace CGAL
5534
5535 #endif
5536