1 // Copyright (c) 2005,2006,2007,2008,2009,2010,2011 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/Arr_dcel_base.h $
7 // $Id: Arr_dcel_base.h 3cf1853 2021-03-25T10:03:35+01:00 Simon Giraudot
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : Ron Wein <wein@post.tau.ac.il>
12 // (based on old version by: Iddo Hanniel and Oren Nechushtan)
13
14 #ifndef CGAL_ARR_DCEL_BASE_H
15 #define CGAL_ARR_DCEL_BASE_H
16
17 #include <CGAL/license/Arrangement_on_surface_2.h>
18
19 #include <CGAL/disable_warnings.h>
20
21 /*! \file
22 * The definition of the base DCEL class for planar arrangements and its
23 * peripheral records.
24 */
25
26 #include <CGAL/basic.h>
27 #include <CGAL/Arr_enums.h>
28 #include <list>
29 #include <map>
30 #include <CGAL/N_step_adaptor_derived.h>
31 #include <CGAL/Compact_container.h>
32 #include <CGAL/function_objects.h>
33 #include <CGAL/Iterator_project.h>
34 #include <CGAL/Arrangement_2/Arrangement_2_iterators.h>
35 #include <CGAL/assertions.h>
36
37 #include <boost/pool/pool_alloc.hpp>
38
39 namespace CGAL {
40
_clean_pointer(const void * p)41 inline void* _clean_pointer(const void* p)
42 {
43 CGAL_static_assertion(sizeof(void*) == sizeof(size_t));
44 const size_t mask = ~1;
45 const size_t val = (reinterpret_cast<size_t>(p) & mask);
46
47 return (reinterpret_cast<void*>(val));
48 }
49
_set_lsb(const void * p)50 inline void* _set_lsb(const void* p)
51 {
52 const size_t mask = 1;
53 const size_t val = (reinterpret_cast<size_t>(p) | mask);
54 return (reinterpret_cast<void*>( val));
55 }
56
_is_lsb_set(const void * p)57 inline bool _is_lsb_set(const void* p)
58 {
59 const size_t mask = 1;
60 const size_t val = reinterpret_cast<size_t>(p);
61 return ((val & mask) != 0);
62 }
63
64 /*! \class
65 * Base vertex class.
66 */
67 template <typename Point_> class Arr_vertex_base {
68 public:
69 typedef Point_ Point;
70
71 /*! \struct
72 * An auxiliary structure for rebinding the vertex with a new point class.
73 */
74 template<typename PNT> struct rebind { typedef Arr_vertex_base<PNT> other; };
75
76 protected:
77 void* p_inc; // An incident halfedge pointing at the vertex,
78 // or the isolated vertex information (in case it is
79 // isolated). The LSB of the pointer indicates whether
80 // the vertex is isolated.
81 Point* p_pt; // The point associated with the vertex.
82 char pss[2]; // The x and y parameter spaces (condensed in two bytes).
83
84 public:
85 /*! Default constructor. */
Arr_vertex_base()86 Arr_vertex_base() :
87 p_inc(nullptr),
88 p_pt(nullptr)
89 { pss[0] = pss[1] = static_cast<char>(CGAL::ARR_INTERIOR); }
90
91 /*! Destructor. */
~Arr_vertex_base()92 virtual ~Arr_vertex_base() {}
93
for_compact_container()94 void* for_compact_container() const { return static_cast<void*>(p_pt); }
for_compact_container(void * ptr)95 void for_compact_container(void* ptr) { p_pt = static_cast<Point*>(ptr); }
96
97 // Access/modification for pointer squatting
inc()98 void* inc() const { return p_inc; }
set_inc(void * inc)99 void set_inc(void * inc) const
100 { const_cast<Arr_vertex_base&>(*this).p_inc = inc; }
101
102 /*! Check if the point pointer is nullptr. */
has_null_point()103 bool has_null_point() const { return (p_pt == nullptr); }
104
105 /*! Get the point (const version). */
point()106 const Point& point() const
107 {
108 CGAL_assertion(p_pt != nullptr);
109 return (*p_pt);
110 }
111
112 /*! Get the point (non-const version). */
point()113 Point& point()
114 {
115 CGAL_assertion(p_pt != nullptr);
116 return (*p_pt);
117 }
118
119 /*! Set the point (may be a nullptr point). */
set_point(Point * p)120 void set_point(Point* p) { p_pt = p; }
121
122 /*! Get the boundary type in x. */
parameter_space_in_x()123 Arr_parameter_space parameter_space_in_x() const
124 { return (Arr_parameter_space(pss[0])); }
125
126 /*! Get the boundary type in y. */
parameter_space_in_y()127 Arr_parameter_space parameter_space_in_y() const
128 { return (Arr_parameter_space(pss[1])); }
129
130 /*! Set the boundary conditions of the vertex. */
set_boundary(Arr_parameter_space ps_x,Arr_parameter_space ps_y)131 void set_boundary(Arr_parameter_space ps_x, Arr_parameter_space ps_y)
132 {
133 pss[0] = static_cast<char>(ps_x);
134 pss[1] = static_cast<char>(ps_y);
135 return;
136 }
137
138 /*! Assign from another vertex. */
assign(const Arr_vertex_base<Point> & v)139 virtual void assign(const Arr_vertex_base<Point>& v)
140 {
141 p_pt = v.p_pt;
142 pss[0] = v.pss[0];
143 pss[1] = v.pss[1];
144 }
145 };
146
147 /*! \class
148 * Base halfedge class.
149 */
150 template <typename X_monotone_curve_> class Arr_halfedge_base {
151 public:
152 typedef X_monotone_curve_ X_monotone_curve;
153
154 /*! \struct
155 * An auxiliary structure for rebinding the halfedge with a new curve class.
156 */
157 template<typename XCV>
158 struct rebind { typedef Arr_halfedge_base<XCV> other; };
159
160 protected:
161 void* p_opp; // The opposite halfedge.
162 void* p_prev; // The previous halfedge in the component boundary.
163 void* p_next; // The next halfedge in the component boundary.
164
165 void* p_v; // The incident vertex (the target of the halfedge).
166 // The LSB of this pointer is used to store the
167 // direction of the halfedge.
168 void* p_comp; // The component this halfedge belongs to: the incident
169 // face for outer CCBs and the inner CCB information for
170 // inner CCBs. The LSB of the pointer indicates whether
171 // the halfedge lies on the boundary of an inner CCB.
172
173 X_monotone_curve* p_cv; // The associated x-monotone curve.
174
175 public:
176 /*! Default constructor */
Arr_halfedge_base()177 Arr_halfedge_base() :
178 p_opp(nullptr),
179 p_prev(nullptr),
180 p_next(nullptr),
181 p_v(nullptr),
182 p_comp(nullptr),
183 p_cv(nullptr)
184 {}
185
186 /*! Destructor. */
~Arr_halfedge_base()187 virtual ~Arr_halfedge_base() {}
188
for_compact_container()189 void* for_compact_container() const { return static_cast<void*>(p_cv); }
for_compact_container(void * ptr)190 void for_compact_container(void* ptr) { p_cv = static_cast<X_monotone_curve*>(ptr); }
191
192 /*! Check if the curve pointer is nullptr. */
has_null_curve()193 bool has_null_curve() const { return (p_cv == nullptr); }
194
195 /*! Get the x-monotone curve (const version). */
curve()196 const X_monotone_curve& curve() const
197 {
198 CGAL_precondition(p_cv != nullptr);
199 return (*p_cv);
200 }
201
202 /*! Get the x-monotone curve (non-const version). */
curve()203 X_monotone_curve& curve()
204 {
205 CGAL_precondition(p_cv != nullptr);
206 return (*p_cv);
207 }
208
209 /*! Set the x-monotone curve. */
set_curve(X_monotone_curve * c)210 void set_curve(X_monotone_curve* c)
211 {
212 p_cv = c;
213
214 // Set the curve for the opposite halfedge as well.
215 Arr_halfedge_base<X_monotone_curve>* opp =
216 reinterpret_cast<Arr_halfedge_base<X_monotone_curve>* >(p_opp);
217
218 opp->p_cv = c;
219 }
220
221 /*! Assign from another halfedge. */
assign(const Arr_halfedge_base<X_monotone_curve> & he)222 virtual void assign(const Arr_halfedge_base<X_monotone_curve>& he)
223 { p_cv = he.p_cv; }
224 };
225
226 /*!
227 * Base face class.
228 */
229 class Arr_face_base
230 {
231 public:
232 typedef std::list<void*> Outer_ccbs_container;
233 typedef Outer_ccbs_container::iterator Outer_ccb_iterator;
234 typedef Outer_ccbs_container::const_iterator Outer_ccb_const_iterator;
235
236 typedef std::list<void*> Inner_ccbs_container;
237 typedef Inner_ccbs_container::iterator Inner_ccb_iterator;
238 typedef Inner_ccbs_container::const_iterator Inner_ccb_const_iterator;
239
240 typedef std::list<void*> Isolated_vertices_container;
241 typedef Isolated_vertices_container::iterator Isolated_vertex_iterator;
242 typedef Isolated_vertices_container::const_iterator
243 Isolated_vertex_const_iterator;
244
245 protected:
246 enum {
247 IS_UNBOUNDED = 1,
248 IS_FICTITIOUS = 2
249 };
250
251 int flags; // Face flags.
252 Outer_ccbs_container outer_ccbs; // The outer CCBs of the faces.
253 Inner_ccbs_container inner_ccbs; // The inner CCBs of the face.
254 Isolated_vertices_container iso_verts; // The isolated vertices inside
255 // the face.
256 public:
257 /*! Default constructor. */
Arr_face_base()258 Arr_face_base() : flags(0) {}
259
260 /*! Destructor. */
~Arr_face_base()261 virtual ~Arr_face_base() {}
262
263 /*! Check if the face is unbounded. */
is_unbounded()264 bool is_unbounded() const { return ((flags & IS_UNBOUNDED) != 0); }
265
266 /*! Set the face as bounded or unbounded. */
set_unbounded(bool unbounded)267 void set_unbounded(bool unbounded)
268 { flags = (unbounded) ? (flags | IS_UNBOUNDED) : (flags & ~IS_UNBOUNDED); }
269
270 /*! Check if the face is fictitious. */
is_fictitious()271 bool is_fictitious() const { return ((flags & IS_FICTITIOUS) != 0); }
272
273 /*! Set the face as fictitious or valid. */
set_fictitious(bool fictitious)274 void set_fictitious(bool fictitious)
275 { flags = (fictitious) ? (flags | IS_FICTITIOUS) : (flags & ~IS_FICTITIOUS); }
276
277 /*! Assign from another face. */
assign(const Arr_face_base & f)278 virtual void assign(const Arr_face_base& f) { flags = f.flags; }
279 };
280
281 // Forward declarations:
282 template <class V, class H, class F> class Arr_vertex;
283 template <class V, class H, class F> class Arr_halfedge;
284 template <class V, class H, class F> class Arr_face;
285 template <class V, class H, class F> class Arr_outer_ccb;
286 template <class V, class H, class F> class Arr_inner_ccb;
287 template <class V, class H, class F> class Arr_isolated_vertex;
288
289 /*! \class
290 * The default arrangement DCEL vertex class.
291 */
292 template <class V, class H, class F>
293 class Arr_vertex : public V
294 {
295 public:
296
297 typedef V Base;
298 typedef Arr_vertex<V,H,F> Vertex;
299 typedef Arr_halfedge<V,H,F> Halfedge;
300 typedef Arr_isolated_vertex<V,H,F> Isolated_vertex;
301
302 /*! Default constructor. */
Arr_vertex()303 Arr_vertex() {}
304
305 /*! Check if the vertex is isolated. */
is_isolated()306 bool is_isolated() const
307 {
308 // Note that we use the LSB of the p_inc pointer as a Boolean flag.
309 return (_is_lsb_set(this->p_inc));
310 }
311
312 /*! Get an incident halfedge (const version). */
halfedge()313 const Halfedge* halfedge() const
314 {
315 CGAL_precondition(! is_isolated());
316 return (reinterpret_cast<const Halfedge*>(this->p_inc));
317 }
318
319 /*! Get an incident halfedge (non-const version). */
halfedge()320 Halfedge* halfedge()
321 {
322 CGAL_precondition(! is_isolated());
323 return (reinterpret_cast<Halfedge*>(this->p_inc));
324 }
325
326 /*! Set an incident halfedge (for non-isolated vertices). */
set_halfedge(Halfedge * he)327 void set_halfedge(Halfedge* he)
328 {
329 // Set the halfedge pointer and reset the LSB.
330 this->p_inc = he;
331 }
332
333 /*! Get the isolated vertex information (const version). */
isolated_vertex()334 const Isolated_vertex* isolated_vertex() const
335 {
336 CGAL_precondition(is_isolated());
337 return (reinterpret_cast<const Isolated_vertex*>(_clean_pointer
338 (this->p_inc)));
339 }
340
341 /*! Get the isolated vertex information (non-const version). */
isolated_vertex()342 Isolated_vertex* isolated_vertex()
343 {
344 CGAL_precondition(is_isolated());
345 return (reinterpret_cast<Isolated_vertex*>(_clean_pointer(this->p_inc)));
346 }
347
348 /*! Set the isolated vertex information. */
set_isolated_vertex(Isolated_vertex * iv)349 void set_isolated_vertex(Isolated_vertex* iv)
350 {
351 // Set the isolated vertex-information pointer and set its LSB.
352 this->p_inc = _set_lsb(iv);
353 }
354 };
355
356 /*! \class
357 * The default arrangement DCEL halfedge class.
358 */
359 template <class V, class H, class F>
360 class Arr_halfedge : public H
361 {
362 public:
363 typedef H Base;
364 typedef Arr_vertex<V,H,F> Vertex;
365 typedef Arr_halfedge<V,H,F> Halfedge;
366 typedef Arr_face<V,H,F> Face;
367 typedef Arr_outer_ccb<V,H,F> Outer_ccb;
368 typedef Arr_inner_ccb<V,H,F> Inner_ccb;
369
370 /*! Default constructor. */
Arr_halfedge()371 Arr_halfedge() {}
372
373 /*! Get the opposite halfedge (const version). */
opposite()374 const Halfedge* opposite () const
375 { return (reinterpret_cast<const Halfedge*>(this->p_opp)); }
376
377 /*! Get the opposite halfedge (non-const version). */
opposite()378 Halfedge* opposite() { return (reinterpret_cast<Halfedge*>(this->p_opp)); }
379
380 /*! Sets the opposite halfedge. */
set_opposite(Halfedge * he)381 void set_opposite(Halfedge* he) { this->p_opp = he; }
382
383 /*! Get the direction of the halfedge. */
direction()384 Arr_halfedge_direction direction() const
385 {
386 // Note that we use the LSB of the p_v pointer as a Boolean flag.
387 if (_is_lsb_set(this->p_v)) return (ARR_LEFT_TO_RIGHT);
388 else return (ARR_RIGHT_TO_LEFT);
389 }
390
391 /*! Set the direction of the edge (and of its opposite halfedge). */
set_direction(Arr_halfedge_direction dir)392 void set_direction(Arr_halfedge_direction dir)
393 {
394 Halfedge* opp = reinterpret_cast<Halfedge*>(this->p_opp);
395
396 if (dir == ARR_LEFT_TO_RIGHT) {
397 this->p_v = _set_lsb(this->p_v);
398 opp->p_v = _clean_pointer(opp->p_v);
399 }
400 else {
401 this->p_v = _clean_pointer(this->p_v);
402 opp->p_v = _set_lsb(opp->p_v);
403 }
404 }
405
406 /*! Get the previous halfedge along the chain (const version). */
prev()407 const Halfedge* prev() const
408 { return (reinterpret_cast<const Halfedge*>(this->p_prev)); }
409
410 /*! Get the previous halfedge along the chain (const version). */
prev()411 Halfedge* prev() { return (reinterpret_cast<Halfedge*>(this->p_prev)); }
412
413 /*! Set the previous halfedge along the chain. */
set_prev(Halfedge * he)414 void set_prev(Halfedge* he)
415 {
416 this->p_prev = he;
417 he->p_next = this;
418 }
419
420 /*! Get the next halfedge along the chain (const version). */
next()421 const Halfedge* next() const
422 { return (reinterpret_cast<const Halfedge*>(this->p_next)); }
423
424 /*! Get the next halfedge along the chain (const version). */
next()425 Halfedge* next() { return (reinterpret_cast<Halfedge*>(this->p_next)); }
426
427 /*! Set the next halfedge along the chain. */
set_next(Halfedge * he)428 void set_next(Halfedge* he)
429 {
430 this->p_next = he;
431 he->p_prev = this;
432 }
433
434 /*! Get the target vertex (const version). */
vertex()435 const Vertex* vertex() const
436 { return (reinterpret_cast<const Vertex*>(_clean_pointer(this->p_v))); }
437
438 /*! Get the target vertex (non-const version). */
vertex()439 Vertex* vertex()
440 { return (reinterpret_cast<Vertex*>(_clean_pointer(this->p_v))); }
441
442 /*! Set the target vertex. */
set_vertex(Vertex * v)443 void set_vertex(Vertex* v)
444 {
445 // Set the vertex pointer, preserving the content of the LSB.
446 if (_is_lsb_set(this->p_v)) this->p_v = _set_lsb(v);
447 else this->p_v = v;
448 }
449
450 /*! Check whether the halfedge lies on the boundary of an outer CCB. */
is_on_outer_ccb()451 bool is_on_outer_ccb() const { return (!_is_lsb_set(this->p_comp)); }
452
453 /*! Get an incident outer CCB (const version).
454 * \pre The edge does not lie on an inner CCB.
455 */
outer_ccb()456 const Outer_ccb* outer_ccb() const
457 {
458 CGAL_precondition(! is_on_inner_ccb());
459 return (reinterpret_cast<const Outer_ccb*>(this->p_comp));
460 }
461
462 /*! Get an incident outer CCB (non-const version).
463 * \pre The edge does not lie on an inner CCB.
464 */
outer_ccb()465 Outer_ccb* outer_ccb()
466 {
467 CGAL_precondition(! is_on_inner_ccb());
468 return (reinterpret_cast<Outer_ccb*>(this->p_comp));
469 }
470
471 /*! Set the incident outer CCB. */
set_outer_ccb(Outer_ccb * oc)472 void set_outer_ccb(Outer_ccb *oc)
473 {
474 // Set the component pointer and reset its LSB.
475 this->p_comp = oc;
476 }
477
478 /*! Check whether the halfedge lies on the boundary of an inner CCB. */
is_on_inner_ccb()479 bool is_on_inner_ccb() const { return (_is_lsb_set(this->p_comp)); }
480
481 /*! Get an incident inner CCB (const version).
482 * \pre The edge lies on an inner CCB.
483 */
inner_ccb()484 const Inner_ccb* inner_ccb() const
485 {
486 CGAL_precondition(is_on_inner_ccb());
487
488 const Inner_ccb* out = reinterpret_cast<const Inner_ccb*>(_clean_pointer(this->p_comp));
489 if (out->is_valid())
490 return out;
491
492 // else reduce path and get valid iccb
493 const Inner_ccb* valid = out->next();
494 while (!valid->is_valid())
495 valid = valid->next();
496 const_cast<Inner_ccb*>(out)->set_next(const_cast<Inner_ccb*>(valid));
497 const_cast<Halfedge*>(this)->set_inner_ccb(valid);
498 return valid;
499 }
500
501 /*! Get an incident inner CCB (non-const version).
502 * \pre The edge lies on an inner CCB.
503 */
inner_ccb()504 Inner_ccb* inner_ccb()
505 {
506 CGAL_precondition(is_on_inner_ccb());
507
508 Inner_ccb* out = reinterpret_cast<Inner_ccb*>(_clean_pointer(this->p_comp));
509 if (out->is_valid())
510 return out;
511
512 // else reduce path and get valid iccb
513 Inner_ccb* valid = out->next();
514 while (!valid->is_valid())
515 valid = valid->next();
516 out->set_next(valid);
517 set_inner_ccb(valid);
518 return valid;
519 }
520
inner_ccb_no_redirect()521 Inner_ccb* inner_ccb_no_redirect()
522 {
523 CGAL_precondition(is_on_inner_ccb());
524 return reinterpret_cast<Inner_ccb*>(_clean_pointer(this->p_comp));
525 }
526
527 /*! Set the incident inner CCB. */
set_inner_ccb(const Inner_ccb * ic)528 void set_inner_ccb(const Inner_ccb *ic)
529 {
530 // Set the component pointer and set its LSB.
531 this->p_comp = _set_lsb(ic);
532 }
533 };
534
535 /*! \class
536 * The default arrangement DCEL face class.
537 */
538 template <class V, class H, class F>
539 class Arr_face : public F,
540 public Compact_container_base
541 {
542 public:
543 typedef F Base;
544 typedef Arr_vertex<V,H,F> Vertex;
545 typedef Arr_halfedge<V,H,F> Halfedge;
546 typedef Arr_face<V,H,F> Face;
547 typedef Arr_outer_ccb<V,H,F> Outer_ccb;
548 typedef Arr_inner_ccb<V,H,F> Inner_ccb;
549 typedef Arr_isolated_vertex<V,H,F> Isolated_vertex;
550
551 typedef Inner_ccb Hole;
552
553 private:
554 typedef Cast_function_object<void*, Halfedge*> _Ccb_to_halfedge_cast;
555 // typedef Cast_function_object<const void*, const Halfedge*>
556 // _Const_ccb_to_halfedge_cast;
557 typedef _Ccb_to_halfedge_cast _Const_ccb_to_halfedge_cast;
558
559 public:
560
561 /*! Default constructor. */
Arr_face()562 Arr_face()
563 {}
564
565 // Definition of the outer CCB iterators:
566 typedef Iterator_project<typename F::Outer_ccb_iterator,
567 _Ccb_to_halfedge_cast> Outer_ccb_iterator;
568
569 typedef Iterator_project<typename F::Outer_ccb_const_iterator,
570 _Const_ccb_to_halfedge_cast>
571 Outer_ccb_const_iterator;
572
573 /*! Get the number of outer CCBs the face has. */
number_of_outer_ccbs()574 size_t number_of_outer_ccbs() const { return (this->outer_ccbs.size()); }
575
576 /*! Get an iterator for the first outer CCB of the face. */
outer_ccbs_begin()577 Outer_ccb_iterator outer_ccbs_begin() { return (this->outer_ccbs.begin()); }
578
579 /*! Get a past-the-end iterator for the outer CCBs inside the face. */
outer_ccbs_end()580 Outer_ccb_iterator outer_ccbs_end() { return (this->outer_ccbs.end()); }
581
582 /*! Get an const iterator for the first outer CCB inside the face. */
outer_ccbs_begin()583 Outer_ccb_const_iterator outer_ccbs_begin() const
584 { return (this->outer_ccbs.begin()); }
585
586 /*! Get a const past-the-end iterator for the outer CCBs inside the face. */
outer_ccbs_end()587 Outer_ccb_const_iterator outer_ccbs_end() const
588 { return (this->outer_ccbs.end()); }
589
590 /*! Add an outer CCB to the face. */
add_outer_ccb(Outer_ccb * oc,Halfedge * h)591 void add_outer_ccb(Outer_ccb *oc, Halfedge *h)
592 { oc->set_iterator(this->outer_ccbs.insert(this->outer_ccbs.end(), h)); }
593
594 /*! Erase an outer CCB of the face. */
erase_outer_ccb(Outer_ccb * oc)595 void erase_outer_ccb(Outer_ccb *oc)
596 { this->outer_ccbs.erase(oc->iterator().current_iterator()); }
597
598 // Definition of the inner CCB iterators:
599 typedef Iterator_project<typename F::Inner_ccb_iterator,
600 _Ccb_to_halfedge_cast> Inner_ccb_iterator;
601
602 typedef Iterator_project<typename F::Inner_ccb_const_iterator,
603 _Const_ccb_to_halfedge_cast>
604 Inner_ccb_const_iterator;
605
606 typedef Inner_ccb_iterator Hole_iterator;
607 typedef Inner_ccb_const_iterator Hole_const_iterator;
608
609 /*! Get the number of inner CCBs the face has. */
number_of_inner_ccbs()610 size_t number_of_inner_ccbs() const { return (this->inner_ccbs.size()); }
611
612 /*! Get an iterator for the first inner CCB of the face. */
inner_ccbs_begin()613 Inner_ccb_iterator inner_ccbs_begin() { return (this->inner_ccbs.begin()); }
614
615 /*! Get a past-the-end iterator for the inner CCBs inside the face. */
inner_ccbs_end()616 Inner_ccb_iterator inner_ccbs_end() { return (this->inner_ccbs.end()); }
617
618 /*! Get an const iterator for the first inner CCB inside the face. */
inner_ccbs_begin()619 Inner_ccb_const_iterator inner_ccbs_begin() const
620 { return (this->inner_ccbs.begin()); }
621
622 /*! Get a const past-the-end iterator for the inner CCBs inside the face. */
inner_ccbs_end()623 Inner_ccb_const_iterator inner_ccbs_end() const
624 { return (this->inner_ccbs.end()); }
625
626 /*! Add an inner CCB to the face. */
add_inner_ccb(Inner_ccb * ic,Halfedge * h)627 void add_inner_ccb(Inner_ccb* ic, Halfedge* h)
628 { ic->set_iterator(this->inner_ccbs.insert(this->inner_ccbs.end(), h)); }
629
630 /*! Erase an inner CCB of the face. */
erase_inner_ccb(Inner_ccb * ic)631 void erase_inner_ccb(Inner_ccb* ic)
632 { this->inner_ccbs.erase(ic->iterator().current_iterator()); }
633
634 /*! Move all inner CCBs (holes) from the face to another. */
splice_inner_ccbs(Arr_face & other)635 Inner_ccb_iterator splice_inner_ccbs(Arr_face& other)
636 {
637 const bool was_empty = this->inner_ccbs.empty();
638 typename Base::Inner_ccbs_container::iterator previous =
639 this->inner_ccbs.end();
640 if (!was_empty) --previous;
641 this->inner_ccbs.splice(this->inner_ccbs.end(), other.inner_ccbs);
642 if (was_empty) previous = this->inner_ccbs.begin();
643 else ++previous;
644 for (typename Base::Inner_ccbs_container::iterator it = previous;
645 it != this->inner_ccbs.end(); ++it)
646 {
647 Inner_ccb* ccb = static_cast<Halfedge*>(*it)->inner_ccb();
648 ccb->set_iterator(it);
649 ccb->set_face(this);
650 }
651 return previous;
652 }
653
654 // Backward compatibility:
number_of_holes()655 size_t number_of_holes() const { return number_of_inner_ccbs(); }
holes_begin()656 Hole_iterator holes_begin() { return inner_ccbs_begin(); }
holes_end()657 Hole_iterator holes_end() { return inner_ccbs_end(); }
holes_begin()658 Hole_const_iterator holes_begin() const { return inner_ccbs_begin(); }
holes_end()659 Hole_const_iterator holes_end() const { return inner_ccbs_end(); }
660
661 // Definition of the isloated vertices iterators:
662 typedef I_Dereference_iterator<
663 typename F::Isolated_vertex_iterator,
664 Vertex,
665 typename F::Isolated_vertex_iterator::difference_type,
666 typename F::Isolated_vertex_iterator::iterator_category>
667 Isolated_vertex_iterator;
668
669 typedef I_Dereference_const_iterator<
670 typename F::Isolated_vertex_const_iterator,
671 typename F::Isolated_vertex_iterator,
672 Vertex,
673 typename F::Isolated_vertex_iterator::difference_type,
674 typename F::Isolated_vertex_iterator::iterator_category>
675 Isolated_vertex_const_iterator;
676
677 /*! Get the number of isloated vertices inside the face. */
number_of_isolated_vertices()678 size_t number_of_isolated_vertices() const
679 { return (this->iso_verts.size()); }
680
681 /*! Get an iterator for the first isloated vertex inside the face. */
isolated_vertices_begin()682 Isolated_vertex_iterator isolated_vertices_begin()
683 { return (this->iso_verts.begin()); }
684
685 /*! Get a past-the-end iterator for the isloated vertices inside the face. */
isolated_vertices_end()686 Isolated_vertex_iterator isolated_vertices_end()
687 { return (this->iso_verts.end()); }
688
689 /*! Get an const iterator for the first isloated vertex inside the face. */
isolated_vertices_begin()690 Isolated_vertex_const_iterator isolated_vertices_begin() const
691 { return (this->iso_verts.begin()); }
692
693 /*! Get a const past-the-end iterator for the isloated vertices inside the
694 * face. */
isolated_vertices_end()695 Isolated_vertex_const_iterator isolated_vertices_end() const
696 { return (this->iso_verts.end()); }
697
698 /*! Add an isloated vertex inside the face. */
add_isolated_vertex(Isolated_vertex * iv,Vertex * v)699 void add_isolated_vertex(Isolated_vertex *iv, Vertex* v)
700 { iv->set_iterator(this->iso_verts.insert(this->iso_verts.end(), v)); }
701
702 /*! Erase an isloated vertex from the face. */
erase_isolated_vertex(Isolated_vertex * iv)703 void erase_isolated_vertex(Isolated_vertex *iv)
704 { this->iso_verts.erase(iv->iterator().current_iterator()); }
705
706 /*! Move all isolated vertices from the face to another. */
splice_isolated_vertices(Arr_face & other)707 Isolated_vertex_iterator splice_isolated_vertices(Arr_face& other)
708 {
709 const bool was_empty = this->iso_verts.empty();
710 typename Base::Isolated_vertices_container::iterator previous =
711 this->iso_verts.end();
712 if (!was_empty) --previous;
713 this->iso_verts.splice(this->iso_verts.end(), other.iso_verts);
714 if (was_empty) previous = this->iso_verts.begin();
715 else ++previous;
716 for (typename Base::Isolated_vertices_container::iterator it = previous;
717 it != this->iso_verts.end(); ++it)
718 {
719 Isolated_vertex* iv = static_cast<Vertex*>(*it)->isolated_vertex();
720 iv->set_iterator(it);
721 iv->set_face(this);
722 }
723 return previous;
724 }
725 };
726
727 /*! \class
728 * Representation of an outer CCB.
729 */
730 template <class V, class H, class F>
731 class Arr_outer_ccb {
732 public:
733 typedef Arr_outer_ccb<V,H,F> Self;
734 typedef Arr_halfedge<V,H,F> Halfedge;
735 typedef Arr_face<V,H,F> Face;
736 typedef typename Face::Outer_ccb_iterator Outer_ccb_iterator;
737
738 private:
739 Face* p_f; // The face the contains the CCB in its interior.
740 Outer_ccb_iterator iter; // The outer CCB identifier.
741 bool iter_is_not_singular;
742
743 public:
744 /*! Default constructor. */
Arr_outer_ccb()745 Arr_outer_ccb() : p_f(nullptr), iter_is_not_singular(false) {}
746
747 /*! Copy constructor. */
Arr_outer_ccb(const Arr_outer_ccb & other)748 Arr_outer_ccb(const Arr_outer_ccb& other) :
749 p_f(other.p_f), iter_is_not_singular(other.iter_is_not_singular)
750 { if (other.iter_is_not_singular) iter = other.iter; }
751
for_compact_container()752 void* for_compact_container() const { return static_cast<void*>(p_f); }
for_compact_container(void * ptr)753 void for_compact_container(void* ptr) { p_f = static_cast<Face*>(ptr); }
754
755 /*! Get a halfedge along the component (const version). */
halfedge()756 const Halfedge* halfedge() const { return (*iter); }
757
758 /*! Get a halfedge along the component (non-const version). */
halfedge()759 Halfedge* halfedge() { return (*iter); }
760
761 /*! Set a representative halfedge for the component. */
set_halfedge(Halfedge * he)762 void set_halfedge(Halfedge* he) { *iter = he; }
763
764 /*! Get the incident face (const version). */
face()765 const Face* face() const { return (p_f); }
766
767 /*! Get the incident face (non-const version). */
face()768 Face* face() { return (p_f); }
769
770 /*! Set the incident face. */
set_face(Face * f)771 void set_face(Face* f) { p_f = f; }
772
773 /*! Get the iterator (const version). */
iterator()774 Outer_ccb_iterator iterator() const
775 {
776 CGAL_assertion(iter_is_not_singular);
777 return (iter);
778 }
779
780 /*! Get the iterator (non-const version). */
iterator()781 Outer_ccb_iterator iterator()
782 {
783 CGAL_assertion(iter_is_not_singular);
784 return (iter);
785 }
786
787 /*! Set the outer CCB iterator. */
set_iterator(Outer_ccb_iterator it)788 void set_iterator(Outer_ccb_iterator it)
789 {
790 iter = it;
791 iter_is_not_singular = true;
792 }
793 };
794
795 /*! \class
796 * Representation of an inner CCB.
797 */
798 template <class V, class H, class F>
799 class Arr_inner_ccb : public Compact_container_base
800 {
801 public:
802 typedef Arr_inner_ccb<V,H,F> Self;
803 typedef Arr_halfedge<V,H,F> Halfedge;
804 typedef Arr_face<V,H,F> Face;
805 typedef typename Face::Inner_ccb_iterator Inner_ccb_iterator;
806
807 private:
808 union
809 {
810 Face* f; // The face the contains the CCB in its interior.
811 Arr_inner_ccb* icc; // next inner CCB in chain to valid icc
812 } f_or_icc;
813 Inner_ccb_iterator iter; // The inner CCB identifier.
814 enum
815 {
816 ITER_IS_SINGULAR, // singular = default iterator, not initialized
817 ITER_IS_NOT_SINGULAR, // not singular = iterator was assigned and is valid
818 INVALID // invalid = the inner CCB is invalid and
819 // only links to another inner CCB
820 // in chain to valid CCB
821 } status;
822
823 public:
824 /*! Default constructor. */
Arr_inner_ccb()825 Arr_inner_ccb() : status(ITER_IS_SINGULAR) { f_or_icc.f = nullptr; }
826
827 /*! Copy constructor. */
Arr_inner_ccb(const Arr_inner_ccb & other)828 Arr_inner_ccb(const Arr_inner_ccb& other) :
829 f_or_icc(other.f_or_icc), status(other.status)
830 { if (other.status == ITER_IS_NOT_SINGULAR) iter = other.iter; }
831
832 /*! Get a halfedge along the component (const version). */
halfedge()833 const Halfedge* halfedge() const
834 {
835 CGAL_assertion (is_valid());
836 return (*iter);
837 }
838
839 /*! Get a halfedge along the component (non-const version). */
halfedge()840 Halfedge* halfedge()
841 {
842 CGAL_assertion (is_valid());
843 return (*iter);
844 }
845
846 /*! Set a representative halfedge for the component. */
set_halfedge(Halfedge * he)847 void set_halfedge(Halfedge *he)
848 {
849 CGAL_assertion (is_valid());
850 *iter = he;
851 }
852
853 /*! Get the incident face (const version). */
face()854 const Face* face() const
855 {
856 CGAL_assertion (status != INVALID);
857 return f_or_icc.f;
858 }
859
860 /*! Get the incident face (non-const version). */
face()861 Face* face()
862 {
863 CGAL_assertion (status != INVALID);
864 return f_or_icc.f;
865 }
866
867 /*! Set the incident face. */
set_face(Face * f)868 void set_face(Face* f)
869 {
870 CGAL_assertion (status != INVALID);
871 f_or_icc.f = f;
872 }
873
874 /*! Get the iterator (const version). */
iterator()875 Inner_ccb_iterator iterator() const
876 {
877 CGAL_assertion(status == ITER_IS_NOT_SINGULAR);
878 return (iter);
879 }
880
881 /*! Get the iterator (non-const version). */
iterator()882 Inner_ccb_iterator iterator()
883 {
884 CGAL_assertion(status == ITER_IS_NOT_SINGULAR);
885 return (iter);
886 }
887
888 /*! Set the inner CCB iterator. */
set_iterator(Inner_ccb_iterator it)889 void set_iterator(Inner_ccb_iterator it)
890 {
891 CGAL_assertion (is_valid());
892 iter = it;
893 status = ITER_IS_NOT_SINGULAR;
894 }
895
896 /*! Check validity */
is_valid()897 bool is_valid() const { return (status != INVALID); }
898
899 /*! Get the next CCB to primary chain. */
next()900 Arr_inner_ccb* next() const
901 {
902 CGAL_assertion (status == INVALID);
903 return f_or_icc.icc;
904 }
905
906 /*! Set the next CCB to primary chain. */
set_next(Arr_inner_ccb * next)907 void set_next(Arr_inner_ccb* next)
908 {
909 status = INVALID;
910 f_or_icc.icc = next;
911 }
912
913 };
914
915 /*! \class
916 * Representation of an isolated vertex.
917 */
918 template <class V, class H, class F>
919 class Arr_isolated_vertex {
920 public:
921 typedef Arr_isolated_vertex<V,H,F> Self;
922 typedef Arr_face<V,H,F> Face;
923 typedef typename Face::Isolated_vertex_iterator Isolated_vertex_iterator;
924
925 private:
926 Face* p_f; // The containing face.
927 Isolated_vertex_iterator iv_it; // The isolated vertex identifier.
928 bool iter_is_not_singular;
929
930 public:
931 /*! Default constructor. */
Arr_isolated_vertex()932 Arr_isolated_vertex() : p_f(nullptr), iter_is_not_singular(false) {}
933
934 /*! Copy constructor. */
Arr_isolated_vertex(const Arr_isolated_vertex & other)935 Arr_isolated_vertex(const Arr_isolated_vertex& other) :
936 p_f(other.p_f), iter_is_not_singular(other.iter_is_not_singular)
937 { if (other.iter_is_not_singular) iv_it = other.iv_it; }
938
for_compact_container()939 void* for_compact_container() const { return static_cast<void*>(p_f); }
for_compact_container(void * ptr)940 void for_compact_container(void* ptr) { p_f = static_cast<Face*>(ptr); }
941
942 /*! Get the containing face (const version). */
face()943 const Face* face() const { return (p_f); }
944
945 /*! Get the containing face (non-const version). */
face()946 Face* face() { return (p_f); }
947
948 /*! Set the incident face, the one that contains the isolated vertex. */
set_face(Face * f)949 void set_face(Face* f) { p_f = f; }
950
951 /*! Get the isolated vertex iterator (const version). */
iterator()952 Isolated_vertex_iterator iterator() const
953 {
954 CGAL_assertion(iter_is_not_singular);
955 return (iv_it);
956 }
957
958 /*! Get the isolated vertex iterator (non-const version). */
iterator()959 Isolated_vertex_iterator iterator()
960 {
961 CGAL_assertion(iter_is_not_singular);
962 return (iv_it);
963 }
964
965 /*! Set the isolated vertex iterator. */
set_iterator(Isolated_vertex_iterator iv)966 void set_iterator(Isolated_vertex_iterator iv)
967 {
968 iv_it = iv;
969 iter_is_not_singular = true;
970 }
971 };
972
973 /*! \class
974 * The arrangement DCEL class.
975 */
976 template <class V, class H, class F,
977 class Allocator = boost::fast_pool_allocator<int> >
978 class Arr_dcel_base {
979 public:
980 // Define the vertex, halfedge and face types.
981 typedef Arr_dcel_base<V,H,F> Self;
982 typedef Arr_vertex<V,H,F> Vertex;
983 typedef Arr_halfedge<V,H,F> Halfedge;
984 typedef Arr_face<V,H,F> Face;
985 typedef Arr_outer_ccb<V,H,F> Outer_ccb;
986 typedef Arr_inner_ccb<V,H,F> Inner_ccb;
987 typedef Arr_isolated_vertex<V,H,F> Isolated_vertex;
988
989 typedef Inner_ccb Hole;
990
991 protected:
992
993 typedef std::allocator_traits<Allocator> Allocator_traits;
994 typedef typename Allocator_traits::template rebind_alloc<Vertex> Vertex_allocator;
995 typedef typename Allocator_traits::template rebind_alloc<Halfedge> Halfedge_allocator;
996 typedef typename Allocator_traits::template rebind_alloc<Face> Face_allocator;
997 typedef typename Allocator_traits::template rebind_alloc<Outer_ccb> Outer_ccb_allocator;
998 typedef typename Allocator_traits::template rebind_alloc<Inner_ccb> Inner_ccb_allocator;
999 typedef typename Allocator_traits::template rebind_alloc<Isolated_vertex> Iso_vert_allocator;
1000
1001 typedef Compact_container<Vertex, Vertex_allocator> Vertex_list;
1002 typedef Compact_container<Halfedge, Halfedge_allocator> Halfedge_list;
1003 typedef Compact_container<Face, Face_allocator> Face_list;
1004 typedef Compact_container<Outer_ccb, Outer_ccb_allocator> Outer_ccb_list;
1005 typedef Compact_container<Inner_ccb, Inner_ccb_allocator> Inner_ccb_list;
1006 typedef Compact_container<Isolated_vertex, Iso_vert_allocator> Iso_vert_list;
1007
1008 public:
1009 typedef typename Halfedge_list::size_type Size;
1010 typedef typename Halfedge_list::size_type size_type;
1011 typedef typename Halfedge_list::difference_type difference_type;
1012 typedef typename Halfedge_list::difference_type Difference;
1013 typedef std::bidirectional_iterator_tag iterator_category;
1014
1015 protected:
1016
1017 Vertex_list vertices; // The vertices container.
1018 Halfedge_list halfedges; // The halfedges container.
1019 Face_list faces; // The faces container.
1020 Outer_ccb_list out_ccbs; // The outer CCBs.
1021 Inner_ccb_list in_ccbs; // The inner CCBs.
1022 Iso_vert_list iso_verts; // The isolated vertices.
1023
1024 public:
1025 // Definitions of iterators.
1026 typedef typename Vertex_list::iterator Vertex_iterator;
1027 typedef typename Halfedge_list::iterator Halfedge_iterator;
1028 typedef typename Face_list::iterator Face_iterator;
1029 typedef CGAL::N_step_adaptor_derived<Halfedge_iterator, 2>
1030 Edge_iterator;
1031 typedef typename Inner_ccb_list::iterator Inner_ccb_iterator;
1032
1033 // Definitions of const iterators.
1034 typedef typename Vertex_list::const_iterator Vertex_const_iterator;
1035 typedef typename Halfedge_list::const_iterator Halfedge_const_iterator;
1036 typedef typename Face_list::const_iterator Face_const_iterator;
1037 typedef CGAL::N_step_adaptor_derived<Halfedge_const_iterator, 2>
1038 Edge_const_iterator;
1039
1040 private:
1041 // Copy constructor - not supported.
1042 Arr_dcel_base(const Self&);
1043
1044 // Assignment operator - not supported.
1045 Self& operator=(const Self&);
1046
1047 public:
1048 /// \name Construction and destruction.
1049 //@{
1050 /*! Default constructor. */
Arr_dcel_base()1051 Arr_dcel_base() {}
1052
1053 /*! Destructor. */
~Arr_dcel_base()1054 ~Arr_dcel_base() { delete_all(); }
1055 //@}
1056
1057 /// \name The DCEL size.
1058 //@{
1059 /*! Get the number of DCEL vertices. */
size_of_vertices()1060 Size size_of_vertices() const { return (vertices.size()); }
1061
1062 /*! Get the number of DCEL halfedges (twice the number of edges). */
size_of_halfedges()1063 Size size_of_halfedges() const { return (halfedges.size()); }
1064
1065 /*! Get the number of DCEL faces. */
size_of_faces()1066 Size size_of_faces() const { return (faces.size()); }
1067
1068 /*! Get the number of outer CCBs. */
size_of_outer_ccbs()1069 Size size_of_outer_ccbs() const { return (out_ccbs.size()); }
1070
1071 /*! Get the number of inner CCBs. */
size_of_inner_ccbs()1072 Size size_of_inner_ccbs() const { return (in_ccbs.size()); }
1073
1074 /*! Get the number of isolated vertices. */
size_of_isolated_vertices()1075 Size size_of_isolated_vertices() const { return (iso_verts.size()); }
1076 //@}
1077
1078 /// \name Obtaining iterators.
1079 //@{
vertices_begin()1080 Vertex_iterator vertices_begin() { return vertices.begin(); }
vertices_end()1081 Vertex_iterator vertices_end() { return vertices.end(); }
1082 Iterator_range<Prevent_deref<Vertex_iterator> >
vertex_handles()1083 vertex_handles()
1084 {
1085 return make_prevent_deref_range(vertices_begin(), vertices_end());
1086 }
halfedges_begin()1087 Halfedge_iterator halfedges_begin() { return halfedges.begin();}
halfedges_end()1088 Halfedge_iterator halfedges_end() { return halfedges.end(); }
1089 Iterator_range<Prevent_deref<Halfedge_iterator> >
halfedge_handles()1090 halfedge_handles()
1091 {
1092 return make_prevent_deref_range(halfedges_begin(), halfedges_end());
1093 }
faces_begin()1094 Face_iterator faces_begin() { return faces.begin(); }
faces_end()1095 Face_iterator faces_end() { return faces.end(); }
1096 Iterator_range<Prevent_deref<Face_iterator> >
face_handles()1097 face_handles()
1098 {
1099 return make_prevent_deref_range(faces_begin(), faces_end());
1100 }
edges_begin()1101 Edge_iterator edges_begin() { return halfedges.begin(); }
edges_end()1102 Edge_iterator edges_end() { return halfedges.end(); }
1103 Iterator_range<Prevent_deref<Edge_iterator> >
edge_handles()1104 edge_handles()
1105 {
1106 return make_prevent_deref_range(edges_begin(), edges_end());
1107 }
1108
inner_ccbs_begin()1109 Inner_ccb_iterator inner_ccbs_begin() { return in_ccbs.begin(); }
inner_ccbs_end()1110 Inner_ccb_iterator inner_ccbs_end() { return in_ccbs.end(); }
1111 //@}
1112
1113 /// \name Obtaining constant iterators.
1114 //@{
vertices_begin()1115 Vertex_const_iterator vertices_begin() const { return vertices.begin(); }
vertices_end()1116 Vertex_const_iterator vertices_end() const { return vertices.end(); }
1117 Iterator_range<Prevent_deref<Vertex_const_iterator> >
vertex_handles()1118 vertex_handles() const
1119 {
1120 return make_prevent_deref_range(vertices_begin(), vertices_end());
1121 }
halfedges_begin()1122 Halfedge_const_iterator halfedges_begin() const { return halfedges.begin(); }
halfedges_end()1123 Halfedge_const_iterator halfedges_end() const { return halfedges.end(); }
1124 Iterator_range<Prevent_deref<Halfedge_const_iterator> >
halfedge_handles()1125 halfedge_handles() const
1126 {
1127 return make_prevent_deref_range(halfedges_begin(), halfedges_end());
1128 }
faces_begin()1129 Face_const_iterator faces_begin() const { return faces.begin(); }
faces_end()1130 Face_const_iterator faces_end() const { return faces.end(); }
1131 Iterator_range<Prevent_deref<Face_const_iterator> >
face_handles()1132 face_handles() const
1133 {
1134 return make_prevent_deref_range(faces_begin(), faces_end());
1135 }
edges_begin()1136 Edge_const_iterator edges_begin() const { return halfedges.begin(); }
edges_end()1137 Edge_const_iterator edges_end() const { return halfedges.end(); }
1138 Iterator_range<Prevent_deref<Edge_const_iterator> >
edge_handles()1139 edge_handles() const
1140 {
1141 return make_prevent_deref_range(edges_begin(), edges_end());
1142 }
1143 //@}
1144
1145 // \name Creation of new DCEL features.
1146 //@{
1147 /*! Create a new vertex. */
new_vertex()1148 Vertex* new_vertex()
1149 {
1150 return &*vertices.emplace();
1151 }
1152
1153 /*! Create a new pair of opposite halfedges. */
new_edge()1154 Halfedge* new_edge()
1155 {
1156 // Create two new halfedges.
1157 Halfedge* h1 = _new_halfedge();
1158 Halfedge* h2 = _new_halfedge();
1159
1160 // Pair them together.
1161 h1->set_opposite(h2);
1162 h2->set_opposite(h1);
1163
1164 return (h1);
1165 }
1166
1167 /*! Create a new face. */
new_face()1168 Face* new_face()
1169 {
1170 return &*faces.emplace();
1171 }
1172
1173 /*! Create a new outer CCB. */
new_outer_ccb()1174 Outer_ccb* new_outer_ccb()
1175 {
1176 return &*out_ccbs.emplace();
1177 }
1178
1179 /*! Create a new inner CCB. */
new_inner_ccb()1180 Inner_ccb* new_inner_ccb()
1181 {
1182 return &*in_ccbs.emplace();
1183 }
1184
1185 /*! Create a new isolated vertex. */
new_isolated_vertex()1186 Isolated_vertex* new_isolated_vertex()
1187 {
1188 return &*iso_verts.emplace();
1189 }
1190 //@}
1191
1192 /// \name Deletion of DCEL features.
1193 //@{
1194 /*! Delete an existing vertex. */
delete_vertex(Vertex * v)1195 void delete_vertex(Vertex* v)
1196 {
1197 vertices.erase (vertices.iterator_to(*v));
1198 }
1199
1200 /*! Delete an existing pair of opposite halfedges. */
delete_edge(Halfedge * h)1201 void delete_edge(Halfedge *h)
1202 {
1203 Halfedge* h_opp = h->opposite();
1204 _delete_halfedge(h);
1205 _delete_halfedge(h_opp);
1206 }
1207
1208 /*! Delete an existing face. */
delete_face(Face * f)1209 void delete_face(Face* f)
1210 {
1211 faces.erase (faces.iterator_to(*f));
1212 }
1213
1214 /*! Delete an existing outer CCB. */
delete_outer_ccb(Outer_ccb * oc)1215 void delete_outer_ccb(Outer_ccb* oc)
1216 {
1217 out_ccbs.erase (out_ccbs.iterator_to(*oc));
1218 }
1219
1220 /*! Delete an existing inner CCB. */
delete_inner_ccb(Inner_ccb * ic)1221 void delete_inner_ccb(Inner_ccb* ic)
1222 {
1223 in_ccbs.erase (in_ccbs.iterator_to(*ic));
1224 }
1225
1226 /*! Delete an existing isolated vertex. */
delete_isolated_vertex(Isolated_vertex * iv)1227 void delete_isolated_vertex(Isolated_vertex* iv)
1228 {
1229 iso_verts.erase (iso_verts.iterator_to(*iv));
1230 }
1231
1232 /*! Delete all DCEL features. */
delete_all()1233 void delete_all()
1234 {
1235 // Free all vertices.
1236 Vertex_iterator vit = vertices.begin(), v_curr;
1237 while (vit != vertices.end()) {
1238 v_curr = vit;
1239 ++vit;
1240 delete_vertex(&(*v_curr));
1241 }
1242
1243 // Free all halfedges.
1244 Halfedge_iterator hit = halfedges.begin(), h_curr;
1245 while (hit != halfedges.end()) {
1246 h_curr = hit;
1247 ++hit;
1248 _delete_halfedge(&(*h_curr));
1249 }
1250
1251 // Free all faces.
1252 Face_iterator fit = faces.begin(), f_curr;
1253 while (fit != faces.end()) {
1254 f_curr = fit;
1255 ++fit;
1256 delete_face(&(*f_curr));
1257 }
1258
1259 // Free all outer CCBs.
1260 typename Outer_ccb_list::iterator ocit = out_ccbs.begin(), oc_curr;
1261 while (ocit != out_ccbs.end()) {
1262 oc_curr = ocit;
1263 ++ocit;
1264 delete_outer_ccb(&(*oc_curr));
1265 }
1266
1267 // Free all inner CCBs.
1268 typename Inner_ccb_list::iterator icit = in_ccbs.begin(), ic_curr;
1269 while (icit != in_ccbs.end()) {
1270 ic_curr = icit;
1271 ++icit;
1272 delete_inner_ccb(&(*ic_curr));
1273 }
1274
1275 // Free all isolated vertices.
1276 typename Iso_vert_list::iterator ivit = iso_verts.begin(), iv_curr;
1277 while (ivit != iso_verts.end()) {
1278 iv_curr = ivit;
1279 ++ivit;
1280 delete_isolated_vertex(&(*iv_curr));
1281 }
1282 }
1283 //@}
1284
1285 /*! Assign our DCEL the contents of another DCEL.
1286 */
assign(const Self & dcel)1287 void assign(const Self& dcel)
1288 {
1289 // Clear the current contents of the DCEL.
1290 delete_all();
1291
1292 // Create duplicated of the DCEL features and map the features of the
1293 // given DCEL to their corresponding duplicates.
1294 typedef std::map<const Vertex*, Vertex*> Vertex_map;
1295 typedef std::map<const Halfedge*, Halfedge*> Halfedge_map;
1296 typedef std::map<const Face*, Face*> Face_map;
1297 typedef std::map<const Outer_ccb*, Outer_ccb*> Outer_ccb_map;
1298 typedef std::map<const Inner_ccb*, Inner_ccb*> Inner_ccb_map;
1299 typedef std::map<const Isolated_vertex*, Isolated_vertex*> Iso_vert_map;
1300
1301 Vertex_map v_map;
1302 Vertex_const_iterator vit;
1303 Vertex* dup_v;
1304
1305 for (vit = dcel.vertices_begin(); vit != dcel.vertices_end(); ++vit) {
1306 dup_v = new_vertex();
1307 dup_v->assign(*vit);
1308 v_map.insert(typename Vertex_map::value_type(&(*vit), dup_v));
1309 }
1310
1311 Halfedge_map he_map;
1312 Halfedge_const_iterator hit;
1313 Halfedge* dup_h;
1314
1315 for (hit = dcel.halfedges_begin(); hit != dcel.halfedges_end(); ++hit) {
1316 dup_h = _new_halfedge();
1317 dup_h->assign(*hit);
1318 he_map.insert(typename Halfedge_map::value_type(&(*hit), dup_h));
1319 }
1320
1321 Face_map f_map;
1322 Face_const_iterator fit;
1323 Face* dup_f;
1324
1325 for (fit = dcel.faces_begin(); fit != dcel.faces_end(); ++fit) {
1326 dup_f = new_face();
1327 dup_f->assign(*fit);
1328 f_map.insert(typename Face_map::value_type(&(*fit), dup_f));
1329 }
1330
1331 Outer_ccb_map oc_map;
1332 typename Outer_ccb_list::const_iterator ocit;
1333 Outer_ccb* dup_oc;
1334
1335 for (ocit = dcel.out_ccbs.begin(); ocit != dcel.out_ccbs.end(); ++ocit) {
1336 dup_oc = new_outer_ccb();
1337 oc_map.insert(typename Outer_ccb_map::value_type(&(*ocit), dup_oc));
1338 }
1339
1340 Inner_ccb_map ic_map;
1341 typename Inner_ccb_list::const_iterator icit;
1342 Inner_ccb* dup_ic;
1343
1344 for (icit = dcel.in_ccbs.begin(); icit != dcel.in_ccbs.end(); ++icit) {
1345 dup_ic = new_inner_ccb();
1346 ic_map.insert(typename Inner_ccb_map::value_type(&(*icit), dup_ic));
1347 }
1348
1349 Iso_vert_map iv_map;
1350 typename Iso_vert_list::const_iterator ivit;
1351 Isolated_vertex* dup_iv;
1352
1353 for (ivit = dcel.iso_verts.begin(); ivit != dcel.iso_verts.end(); ++ivit) {
1354 dup_iv = new_isolated_vertex();
1355 iv_map.insert(typename Iso_vert_map::value_type(&(*ivit), dup_iv));
1356 }
1357
1358 // Update the vertex records.
1359 const Vertex* v;
1360 const Halfedge* h;
1361 const Face* f;
1362 const Outer_ccb* oc;
1363 const Inner_ccb* ic;
1364 const Isolated_vertex* iv;
1365
1366 for (vit = dcel.vertices_begin(); vit != dcel.vertices_end(); ++vit) {
1367 v = &(*vit);
1368 dup_v = (v_map.find(v))->second;
1369
1370 if (v->is_isolated()) {
1371 // Isolated vertex - set its information.
1372 iv = v->isolated_vertex();
1373 dup_iv = (iv_map.find(iv))->second;
1374
1375 dup_v->set_isolated_vertex(dup_iv);
1376 }
1377 else {
1378 // Regular vertex - set its incident halfedge.
1379 h = v->halfedge();
1380 dup_h = (he_map.find(h))->second;
1381
1382 dup_v->set_halfedge(dup_h);
1383 }
1384 }
1385
1386 // Update the halfedge records.
1387 const Halfedge* opp;
1388 const Halfedge* prev;
1389 const Halfedge* next;
1390 Halfedge* dup_opp;
1391 Halfedge* dup_prev;
1392 Halfedge* dup_next;
1393
1394 for (hit = dcel.halfedges_begin(); hit != dcel.halfedges_end(); ++hit) {
1395 h = &(*hit);
1396 v = h->vertex();
1397 opp = h->opposite();
1398 prev = h->prev();
1399 next = h->next();
1400
1401 dup_h = (he_map.find(h))->second;
1402 dup_v = (v_map.find(v))->second;
1403 dup_opp = (he_map.find(opp))->second;
1404 dup_prev = (he_map.find(prev))->second;
1405 dup_next = (he_map.find(next))->second;
1406
1407 dup_h->set_vertex(dup_v);
1408 dup_h->set_opposite(dup_opp);
1409 dup_h->set_prev(dup_prev);
1410 dup_h->set_next(dup_next);
1411 dup_h->set_direction(h->direction());
1412
1413 if (h->is_on_inner_ccb()) {
1414 // The halfedge lies on an inner CCB - set its inner CCB record.
1415 ic = h->inner_ccb();
1416 dup_ic = (ic_map.find(ic))->second;
1417 dup_h->set_inner_ccb(dup_ic);
1418 }
1419 else {
1420 // The halfedge lies on an outer CCB - set its outer CCB record.
1421 oc = h->outer_ccb();
1422 dup_oc = (oc_map.find(oc))->second;
1423 dup_h->set_outer_ccb(dup_oc);
1424 }
1425 }
1426
1427 // Update the face records, along with the CCB records and isolated vertex
1428 // records.
1429 typename Face::Outer_ccb_const_iterator out_ccb_it;
1430 typename Face::Inner_ccb_const_iterator in_ccb_it;
1431 typename Face::Isolated_vertex_const_iterator iso_vert_it;
1432 const Halfedge* hccb;
1433 const Vertex* iso_vert;
1434 Halfedge* dup_hccb;
1435 Vertex* dup_iso_vert;
1436
1437 for (fit = dcel.faces_begin(); fit != dcel.faces_end(); ++fit) {
1438 f = &(*fit);
1439 dup_f = (f_map.find(f))->second;
1440 dup_f->set_unbounded(f->is_unbounded());
1441 dup_f->set_fictitious(f->is_fictitious());
1442
1443 // Assign the outer CCBs of the face.
1444 for (out_ccb_it = f->outer_ccbs_begin();
1445 out_ccb_it != f->outer_ccbs_end(); ++out_ccb_it)
1446 {
1447 hccb = *out_ccb_it;
1448
1449 dup_hccb = (he_map.find(hccb))->second;
1450 dup_oc = dup_hccb->outer_ccb();
1451
1452 dup_oc->set_face(dup_f);
1453 dup_f->add_outer_ccb(dup_oc, dup_hccb);
1454 }
1455
1456 // Assign the inner CCBs of the face.
1457 for (in_ccb_it = f->inner_ccbs_begin();
1458 in_ccb_it != f->inner_ccbs_end(); ++in_ccb_it)
1459 {
1460 hccb = *in_ccb_it;
1461
1462 dup_hccb = (he_map.find(hccb))->second;
1463 dup_ic = dup_hccb->inner_ccb();
1464
1465 dup_ic->set_face(dup_f);
1466 dup_f->add_inner_ccb(dup_ic, dup_hccb);
1467 }
1468
1469 // Assign the isolated vertices.
1470 for (iso_vert_it = f->isolated_vertices_begin();
1471 iso_vert_it != f->isolated_vertices_end(); ++iso_vert_it)
1472 {
1473 iso_vert = &(*iso_vert_it);
1474
1475 dup_iso_vert = (v_map.find(iso_vert))->second;
1476 dup_iv = dup_iso_vert->isolated_vertex();
1477
1478 dup_iv->set_face(dup_f);
1479 dup_f->add_isolated_vertex(dup_iv, dup_iso_vert);
1480 }
1481 }
1482 }
1483
1484 protected:
1485 /*! Create a new halfedge. */
_new_halfedge()1486 Halfedge* _new_halfedge()
1487 {
1488 return &*halfedges.emplace();
1489 }
1490
1491 /*! Delete an existing halfedge. */
_delete_halfedge(Halfedge * h)1492 void _delete_halfedge(Halfedge* h)
1493 {
1494 halfedges.erase (halfedges.iterator_to(*h));
1495 }
1496 };
1497
1498 } //namespace CGAL
1499
1500 #include <CGAL/enable_warnings.h>
1501
1502 #endif
1503