1 // Copyright (c) 1997-2002 Max-Planck-Institute Saarbruecken (Germany).
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org).
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Nef_3/include/CGAL/Nef_3/SNC_structure.h $
7 // $Id: SNC_structure.h 458ecf1 2021-06-08T17:32:12+01:00 Giles Bathgate
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : Michael Seel <seel@mpi-sb.mpg.de>
12 // Miguel Granados <granados@mpi-sb.mpg.de>
13 // Susan Hert <hert@mpi-sb.mpg.de>
14 // Lutz Kettner <kettner@mpi-sb.mpg.de>
15 #ifndef CGAL_SNC_STRUCTURE_H
16 #define CGAL_SNC_STRUCTURE_H
17
18 #include <CGAL/license/Nef_3.h>
19
20
21 #include <CGAL/basic.h>
22 #include <CGAL/Unique_hash_map.h>
23 #include <CGAL/In_place_list.h>
24 #include <CGAL/Nef_3/SNC_list.h>
25 #include <CGAL/Nef_S2/Generic_handle_map.h>
26 #include <CGAL/Nef_2/Object_handle.h>
27 #include <CGAL/Nef_3/SNC_iteration.h>
28 #include <CGAL/Nef_2/iterator_tools.h>
29 #include <CGAL/Nef_S2/Sphere_geometry.h>
30 #include <list>
31
32 #undef CGAL_NEF_DEBUG
33 #define CGAL_NEF_DEBUG 41
34 #include <CGAL/Nef_2/debug.h>
35 #include <CGAL/Nef_2/Object_index.h>
36
37 #include <boost/optional.hpp>
38 #include <boost/none.hpp>
39
40 namespace CGAL {
41
42 template <typename HE>
43 struct move_shalfedge_around_facet {
forwardmove_shalfedge_around_facet44 void forward(HE& e) const { e = (e->next()); }
backwardmove_shalfedge_around_facet45 void backward(HE& e) const { e = (e->prev()); }
46 };
47
48 template <class Object, class Hash_map, class Union_find>
merge_sets(Object o1,Object o2,Hash_map & hash,Union_find & uf)49 void merge_sets( Object o1, Object o2, Hash_map& hash, Union_find& uf) {
50 //CGAL_assertion( hash[o1] != 0 && hash[o2] != 0);
51 CGAL_assertion( hash.is_defined(o1) && hash.is_defined(o2));
52 if( !uf.same_set( hash[o1], hash[o2]))
53 uf.unify_sets( hash[o1], hash[o2]);
54 }
55
56 template <typename K, typename I, typename M> class SNC_sphere_map;
57 template <typename S> class SM_decorator;
58 template <typename S> class SNC_decorator;
59
60 /*{\Manpage {SNC_structure}{Items}{Selective Nef Complex}{C}}*/
61
62 template <typename Kernel_, typename Items_, typename Mark_>
63 class SNC_structure {
64 /*{\Mdefinition The extended Wuerzburg structure is the topological
65 structure of Nef polyhedra. It is programmed around the local
66 graphs of the vertices of a Nef polyhedron, which describe the
67 point set completely. All other concepts are either derived from
68 the local graph or added for the comfort of the user.}*/
69
70 public:
71 /*{\Mtypes 7}*/
72
73 typedef Items_ Items;
74 typedef Kernel_ Kernel;
75 typedef Mark_ Mark;
76 typedef SNC_structure<Kernel,Items,Mark> Self;
77
78 // typedef bool Mark;
79 typedef CGAL::SNC_decorator<Self> SNC_decorator;
80
81 typedef typename Kernel::FT FT;
82 typedef typename Kernel::RT RT;
83 typedef CGAL::Sphere_geometry<Kernel> Sphere_kernel;
84
85 typedef SNC_sphere_map<Kernel, Items, Mark> Sphere_map;
86 typedef CGAL::SM_decorator<Sphere_map> SM_decorator;
87
88 typedef typename Kernel::Point_3 Point_3;
89 /*{\Mtypemember embedding vertices.}*/
90 typedef typename Kernel::Plane_3 Plane_3;
91 /*{\Mtypemember supporting facets.}*/
92 typedef typename Kernel::Vector_3 Vector_3;
93 /*{\Mtypemember normal vectors.}*/
94 typedef typename Kernel::Direction_3 Direction_3;
95 /*{\Mtypemember normal directions.}*/
96 typedef typename Kernel::Segment_3 Segment_3;
97 /*{\Mtypemember segments in space.}*/
98 typedef typename Kernel::Line_3 Line_3;
99 /*{\Mtypemember lines in space.}*/
100 typedef typename Kernel::Ray_3 Ray_3;
101 /*{\Mtypemember rays in space.}*/
102 typedef typename Kernel::Triangle_3 Triangle_3;
103 /*{\Mtypemember triangles in space.}*/
104
105 typedef typename Kernel::Aff_transformation_3 Aff_transformation_3;
106
107 typedef typename Sphere_kernel::Sphere_point Sphere_point;
108 /*{\Mtypemember points on the unit sphere.}*/
109 typedef typename Sphere_kernel::Sphere_segment Sphere_segment;
110 /*{\Mtypemember segments on the unit sphere.}*/
111 typedef typename Sphere_kernel::Sphere_circle Sphere_circle;
112 /*{\Mtypemember segments on the unit sphere.}*/
113 typedef typename Sphere_kernel::Sphere_direction Sphere_direction;
114 /*{\Mtypemember directions on the unit sphere.}*/
115 typedef size_t Size_type;
116 /*{\Mtypemember size type.}*/
117
118 private:
119 friend class CGAL::SM_decorator<Sphere_map>;
120 friend class CGAL::SNC_decorator<Self>;
121
122 /*{\Mtext For all objects |Vertex|, |Halfedge|, |Halffacet|, |Volume|
123 there are handle and iterator types |xxx_handle|, |xxx_iterator|.
124 Additionally all objects of the local graph of a vertex
125 |SVertex|, |SHalfedge|, |SHalfloop|, |SFace| are accessed via handles
126 and iterators. There's no type |SHalfloop_iterator|, as there is
127 at most one |SLoop| pair per vertex.}*/
128
129
130 public:
131 typedef Sphere_map Vertex_base;
132 typedef SNC_in_place_list_sm<Vertex_base> Vertex;
133 typedef CGAL::In_place_list<Vertex,false> Vertex_list;
134 typedef CGAL_ALLOCATOR(Vertex) Vertex_alloc;
135 typedef typename Vertex_list::iterator Vertex_handle;
136 typedef typename Vertex_list::const_iterator Vertex_const_handle;
137 typedef typename Vertex_list::iterator Vertex_iterator;
138 typedef typename Vertex_list::const_iterator Vertex_const_iterator;
139
140 typedef typename Items::template Halffacet<SNC_structure> Halffacet_base;
141 typedef SNC_in_place_list_halffacet<Halffacet_base> Halffacet;
142 typedef CGAL::In_place_list<Halffacet,false> Halffacet_list;
143 typedef CGAL_ALLOCATOR(Halffacet) Halffacet_alloc;
144 typedef typename Halffacet_list::iterator Halffacet_handle;
145 typedef typename Halffacet_list::const_iterator Halffacet_const_handle;
146 typedef typename Halffacet_list::iterator Halffacet_iterator;
147 typedef typename Halffacet_list::const_iterator Halffacet_const_iterator;
148
149 typedef typename Items::template Volume<SNC_structure> Volume_base;
150 typedef SNC_in_place_list_volume<Volume_base> Volume;
151 typedef CGAL::In_place_list<Volume,false> Volume_list;
152 typedef CGAL_ALLOCATOR(Volume) Volume_alloc;
153 typedef typename Volume_list::iterator Volume_handle;
154 typedef typename Volume_list::const_iterator Volume_const_handle;
155 typedef typename Volume_list::iterator Volume_iterator;
156 typedef typename Volume_list::const_iterator Volume_const_iterator;
157
158 typedef typename Items::template SVertex<SNC_structure> SVertex_base;
159 typedef SNC_in_place_list_svertex<SVertex_base> SVertex;
160 typedef CGAL::In_place_list<SVertex,false> SVertex_list;
161 typedef CGAL_ALLOCATOR(SVertex) SVertex_alloc;
162 typedef typename SVertex_list::iterator SVertex_handle;
163 typedef typename SVertex_list::const_iterator SVertex_const_handle;
164 typedef typename SVertex_list::iterator SVertex_iterator;
165 typedef typename SVertex_list::const_iterator SVertex_const_iterator;
166
167 typedef typename Items::template SVertex<SNC_structure> Halfedge_base;
168 typedef SNC_in_place_list_svertex<SVertex_base> Halfedge;
169 typedef CGAL::In_place_list<SVertex,false> Halfedge_list;
170 typedef CGAL_ALLOCATOR(SVertex) Halfedge_alloc;
171 typedef typename SVertex_list::iterator Halfedge_handle;
172 typedef typename SVertex_list::const_iterator Halfedge_const_handle;
173 typedef typename SVertex_list::iterator Halfedge_iterator;
174 typedef typename SVertex_list::const_iterator Halfedge_const_iterator;
175
176 typedef typename Items::template SHalfedge<SNC_structure> SHalfedge_base;
177 typedef SNC_in_place_list_shalfedge<SHalfedge_base> SHalfedge;
178 typedef CGAL::In_place_list<SHalfedge,false> SHalfedge_list;
179 typedef CGAL_ALLOCATOR(SHalfedge) SHalfedge_alloc;
180 typedef typename SHalfedge_list::iterator SHalfedge_handle;
181 typedef typename SHalfedge_list::const_iterator SHalfedge_const_handle;
182 typedef typename SHalfedge_list::iterator SHalfedge_iterator;
183 typedef typename SHalfedge_list::const_iterator SHalfedge_const_iterator;
184
185 typedef typename Items::template SHalfloop<SNC_structure> SHalfloop_base;
186 typedef SNC_in_place_list_shalfloop<SHalfloop_base> SHalfloop;
187 typedef CGAL::In_place_list<SHalfloop,false> SHalfloop_list;
188 typedef CGAL_ALLOCATOR(SHalfloop) SHalfloop_alloc;
189 typedef typename SHalfloop_list::iterator SHalfloop_handle;
190 typedef typename SHalfloop_list::const_iterator SHalfloop_const_handle;
191 typedef typename SHalfloop_list::iterator SHalfloop_iterator;
192 typedef typename SHalfloop_list::const_iterator SHalfloop_const_iterator;
193
194 typedef typename Items::template SFace<SNC_structure> SFace_base;
195 typedef SNC_in_place_list_sface<SFace_base> SFace;
196 typedef CGAL::In_place_list<SFace,false> SFace_list;
197 typedef CGAL_ALLOCATOR(SFace) SFace_alloc;
198 typedef typename SFace_list::iterator SFace_handle;
199 typedef typename SFace_list::const_iterator SFace_const_handle;
200 typedef typename SFace_list::iterator SFace_iterator;
201 typedef typename SFace_list::const_iterator SFace_const_iterator;
202
203 typedef CGAL::Object_handle Object_handle;
204 typedef std::list<Object_handle> Object_list;
205 typedef Object_list::iterator Object_iterator;
206 typedef Object_list::const_iterator Object_const_iterator;
207 typedef Object_list::const_iterator Object_const_handle;
208
209 typedef typename Sphere_map::SHalfedge_around_svertex_circulator
210 SHalfedge_around_svertex_circulator;
211 typedef typename Sphere_map::SHalfedge_around_sface_circulator
212 SHalfedge_around_sface_circulator;
213 typedef typename Sphere_map::SHalfedge_around_svertex_const_circulator
214 SHalfedge_around_svertex_const_circulator;
215 typedef typename Sphere_map::SHalfedge_around_sface_const_circulator
216 SHalfedge_around_sface_const_circulator;
217
218 typedef typename Sphere_map::Infi_box Infi_box;
219 typedef typename Infi_box::Standard_kernel Standard_kernel;
220
221 typedef Vertex_handle Constructor_parameter;
222 typedef Vertex_const_handle Constructor_const_parameter;
223
224 // Halffacet triangle
225
226 #ifdef CGAL_NEF_LIST_OF_TRIANGLES
227 class Halffacet_triangle_handle : public Halffacet_handle {
228 typedef Halffacet_handle Base;
229 Triangle_3* triangle;
230 public:
Halffacet_triangle_handle()231 Halffacet_triangle_handle() : Base() {}
Halffacet_triangle_handle(Halffacet_handle h,Triangle_3 & t)232 Halffacet_triangle_handle( Halffacet_handle h, Triangle_3& t) :
233 Base(h), triangle(&t) {}
get_triangle()234 Triangle_3& get_triangle() { return *triangle; }
transform(const Aff_transformation_3 & t)235 void transform(const Aff_transformation_3& t) {
236 *triangle = Triangle_3((*triangle)[0].transform(t),
237 (*triangle)[1].transform(t),
238 (*triangle)[2].transform(t));
239 }
240 };
241 #else
242 class Halffacet_triangle_const_handle : public Halffacet_const_handle {
243 typedef Halffacet_const_handle Base;
244 Triangle_3 triangle;
245 public:
Halffacet_triangle_const_handle()246 Halffacet_triangle_const_handle() : Base() {}
Halffacet_triangle_const_handle(Halffacet_const_handle h,Triangle_3 & t)247 Halffacet_triangle_const_handle( Halffacet_const_handle h, Triangle_3& t) :
248 Base(h), triangle(t) {}
get_triangle()249 Triangle_3 get_triangle() { return triangle; }
transform(const Aff_transformation_3 & t)250 void transform(const Aff_transformation_3& t) {
251 triangle = Triangle_3(triangle[0].transform(t),
252 triangle[1].transform(t),
253 triangle[2].transform(t));
254 }
255 };
256
257 class Halffacet_triangle_handle : public Halffacet_handle {
258 typedef Halffacet_handle Base;
259 Triangle_3 triangle;
260 public:
Halffacet_triangle_handle()261 Halffacet_triangle_handle() : Base() {}
Halffacet_triangle_handle(Halffacet_handle h,Triangle_3 & t)262 Halffacet_triangle_handle( Halffacet_handle h, Triangle_3& t) :
263 Base(h), triangle(t) {}
get_triangle()264 Triangle_3 get_triangle() { return triangle; }
transform(const Aff_transformation_3 & t)265 void transform(const Aff_transformation_3& t) {
266 triangle = Triangle_3(triangle[0].transform(t),
267 triangle[1].transform(t),
268 triangle[2].transform(t));
269 }
270 };
271 #endif
272
273 class Halffacet_cycle_iterator : public Object_iterator
274 /*{\Mtypemember a generic handle to an object in the boundary
275 of a facet. Convertible to |Object_handle|.}*/
276 { typedef Object_iterator Ibase;
277 public:
Halffacet_cycle_iterator()278 Halffacet_cycle_iterator() : Ibase() {}
Halffacet_cycle_iterator(const Ibase & b)279 Halffacet_cycle_iterator(const Ibase& b) : Ibase(b) {}
280
is_shalfedge()281 bool is_shalfedge() const
282 { SHalfedge_handle e; return CGAL::assign(e,Ibase::operator*()); }
is_shalfloop()283 bool is_shalfloop() const
284 { SHalfloop_handle l; return CGAL::assign(l,Ibase::operator*()); }
285
SHalfedge_handle()286 operator SHalfedge_handle() const
287 { SHalfedge_handle e; CGAL::assign(e,Ibase::operator*()); return e; }
SHalfloop_handle()288 operator SHalfloop_handle() const
289 { SHalfloop_handle l; CGAL::assign(l,Ibase::operator*()); return l; }
290
Object_handle()291 operator Object_handle() const { return Ibase::operator*(); }
292 Object_handle& operator*() const { return Ibase::operator*(); }
293 Object_handle operator->() const
294 { CGAL_error_msg("not impl."); return Object_handle();}
295 };
296
297 class Halffacet_cycle_const_iterator : public Object_const_iterator
298 /*{\Mtypemember a generic handle to an object in the boundary
299 of a facet. Convertible to |Object_handle|.}*/
300 { typedef Object_const_iterator Ibase;
301 public:
Halffacet_cycle_const_iterator()302 Halffacet_cycle_const_iterator() : Ibase() {}
Halffacet_cycle_const_iterator(const Ibase & b)303 Halffacet_cycle_const_iterator(const Ibase& b) : Ibase(b) {}
304
is_shalfedge()305 bool is_shalfedge() const
306 { SHalfedge_handle e; return CGAL::assign(e,Ibase::operator*()); }
is_shalfloop()307 bool is_shalfloop() const
308 { SHalfloop_handle l; return CGAL::assign(l,Ibase::operator*()); }
309
SHalfedge_const_handle()310 operator SHalfedge_const_handle() const
311 { SHalfedge_handle e; CGAL::assign(e,Ibase::operator*());
312 return SHalfedge_const_handle(e); }
SHalfloop_const_handle()313 operator SHalfloop_const_handle() const
314 { SHalfloop_handle l; CGAL::assign(l,Ibase::operator*());
315 return SHalfloop_const_handle(l); }
316
Object_handle()317 operator Object_handle() const { return Ibase::operator*(); }
318 const Object_handle& operator*() const { return Ibase::operator*(); }
319 Object_handle operator->() const
320 { CGAL_error_msg("not impl."); return Object_handle();}
321 };
322
323 class SFace_cycle_iterator : public Object_iterator
324 /*{\Mtypemember a generic iterator to an object in the boundary
325 of a sface. Convertible to |Object_handle|.}*/
326 { typedef Object_iterator Ibase;
327 public:
SFace_cycle_iterator()328 SFace_cycle_iterator() : Ibase() {}
SFace_cycle_iterator(const Ibase & b)329 SFace_cycle_iterator(const Ibase& b) : Ibase(b) {}
330
is_svertex()331 bool is_svertex() const
332 { SVertex_handle v; return CGAL::assign(v,Ibase::operator*()); }
is_shalfedge()333 bool is_shalfedge() const
334 { SHalfedge_handle e; return CGAL::assign(e,Ibase::operator*()); }
is_shalfloop()335 bool is_shalfloop() const
336 { SHalfloop_handle l; return CGAL::assign(l,Ibase::operator*()); }
SVertex_handle()337 operator SVertex_handle() const
338 { SVertex_handle v; CGAL::assign(v,Ibase::operator*()); return v; }
SHalfedge_handle()339 operator SHalfedge_handle() const
340 { SHalfedge_handle e; CGAL::assign(e,Ibase::operator*()); return e; }
SHalfloop_handle()341 operator SHalfloop_handle() const
342 { SHalfloop_handle l; CGAL::assign(l,Ibase::operator*()); return l; }
343
Object_handle()344 operator Object_handle() const { return Ibase::operator*(); }
345 Object_handle& operator*() const { return Ibase::operator*(); }
346 Object_handle operator->() const
347 { return Object_handle(); }
348 };
349
350 class SFace_cycle_const_iterator : public Object_const_iterator
351 /*{\Mtypemember a generic iterator to an object in the boundary
352 of a facet. Convertible to |Object_handle|.}*/
353 { typedef Object_const_iterator Ibase;
354 public:
SFace_cycle_const_iterator()355 SFace_cycle_const_iterator() : Ibase() {}
SFace_cycle_const_iterator(const Ibase & b)356 SFace_cycle_const_iterator(const Ibase& b) : Ibase(b) {}
357
is_svertex()358 bool is_svertex() const
359 { SVertex_handle v; return CGAL::assign(v,Ibase::operator*()); }
is_shalfedge()360 bool is_shalfedge() const
361 { SHalfedge_handle e; return CGAL::assign(e,Ibase::operator*()); }
is_shalfloop()362 bool is_shalfloop() const
363 { SHalfloop_handle l; return CGAL::assign(l,Ibase::operator*()); }
SVertex_const_handle()364 operator SVertex_const_handle() const
365 { SVertex_handle v; CGAL::assign(v,Ibase::operator*());
366 return SVertex_const_handle(v); }
SHalfedge_const_handle()367 operator SHalfedge_const_handle() const
368 { SHalfedge_handle e; CGAL::assign(e,Ibase::operator*());
369 return SHalfedge_const_handle(e); }
SHalfloop_const_handle()370 operator SHalfloop_const_handle() const
371 { SHalfloop_handle l; CGAL::assign(l,Ibase::operator*());
372 return SHalfloop_const_handle(l); }
373
Object_handle()374 operator Object_handle() const { return Ibase::operator*(); }
375 const Object_handle& operator*() const { return Ibase::operator*(); }
376 Object_handle operator->() const
377 { return Object_handle(); }
378 };
379
380
381 class Shell_entry_iterator : public Object_iterator
382 /*{\Mtypemember a generic iterator to an object in the boundary
383 of a shell. Convertible to |SFace_handle|.}*/
384 { typedef Object_iterator Ibase;
385 public:
Shell_entry_iterator()386 Shell_entry_iterator() : Ibase() {}
Shell_entry_iterator(const Ibase & b)387 Shell_entry_iterator(const Ibase& b) : Ibase(b) {}
388
SFace_handle()389 operator SFace_handle() const
390 { SFace_handle f;
391 CGAL_assertion( CGAL::assign(f,Ibase::operator*()) );
392 CGAL::assign(f,Ibase::operator*()); return f; }
393
Object_handle()394 operator Object_handle() const { return Ibase::operator*(); }
395 Object_handle& operator*() const { return Ibase::operator*(); }
396 Object_handle operator->() const
397 { return Object_handle(); }
398 };
399
400 class Shell_entry_const_iterator : public Object_const_iterator
401 { typedef Object_const_iterator Ibase;
402 public:
Shell_entry_const_iterator()403 Shell_entry_const_iterator() : Ibase() {}
Shell_entry_const_iterator(const Ibase & b)404 Shell_entry_const_iterator(const Ibase& b) : Ibase(b) {}
405
SFace_const_handle()406 operator SFace_const_handle() const
407 { SFace_handle f;
408 CGAL_assertion( CGAL::assign(f,Ibase::operator*()) );
409 CGAL::assign(f,Ibase::operator*());
410 return SFace_const_handle(f); }
411
Object_handle()412 operator Object_handle() const { return Ibase::operator*(); }
413 const Object_handle& operator*() const { return Ibase::operator*(); }
414 Object_handle operator->() const
415 { return Object_handle(); }
416 };
417
418 typedef CircFromIt<SHalfedge_const_iterator,
419 move_shalfedge_around_facet<SHalfedge_const_iterator> >
420 SHalfedge_around_facet_const_circulator;
421
422 // Mutable Circulators:
423
424 typedef CircFromIt<SHalfedge_iterator,
425 move_shalfedge_around_facet<SHalfedge_iterator> >
426 SHalfedge_around_facet_circulator;
427
428
429 /*{\Mcreation 3}*/
430 /*{\Mtext |\Mname| is default and copy constructible. Note that copy
431 construction means cloning an isomorphic structure and is thus an
432 expensive operation.}*/
433
SNC_structure()434 SNC_structure() :
435 boundary_item_(boost::none), sm_boundary_item_(boost::none),
436 vertices_(), halfedges_(), halffacets_(), volumes_(),
437 shalfedges_(), shalfloops_(), sfaces_() {}
~SNC_structure()438 ~SNC_structure() { CGAL_NEF_TRACEN("~SNC_structure: clearing "<<this); clear(); }
439
SNC_structure(const Self & D)440 SNC_structure(const Self& D) :
441 boundary_item_(boost::none), sm_boundary_item_(boost::none),
442 vertices_(D.vertices_), halfedges_(D.halfedges_),
443 halffacets_(D.halffacets_), volumes_(D.volumes_),
444 shalfedges_(D.shalfedges_), shalfloops_(D.shalfloops_),
445 sfaces_(D.sfaces_)
446 { pointer_update(D); }
447
448 Self& operator=(const Self& D) {
449 if ( this == &D )
450 return *this;
451 clear();
452 boundary_item_.clear(boost::none);
453 sm_boundary_item_.clear(boost::none);
454 vertices_ = D.vertices_;
455 halfedges_ = D.halfedges_;
456 halffacets_ = D.halffacets_;
457 volumes_ = D.volumes_;
458 shalfedges_ = D.shalfedges_;
459 shalfloops_ = D.shalfloops_;
460 sfaces_ = D.sfaces_;
461 pointer_update(D);
462 return *this;
463 }
464
clear_boundary()465 void clear_boundary() {
466 boundary_item_.clear(boost::none);
467 sm_boundary_item_.clear(boost::none);
468 }
469
clear_snc_boundary()470 void clear_snc_boundary() {
471 boundary_item_.clear(boost::none);
472 }
473
clear()474 void clear() {
475 boundary_item_.clear(boost::none);
476 sm_boundary_item_.clear(boost::none);
477 vertices_.destroy();
478 halfedges_.destroy();
479 halffacets_.destroy();
480 volumes_.destroy();
481 shalfedges_.destroy();
482 shalfloops_.destroy();
483 sfaces_.destroy();
484 }
485
486 template <typename H>
is_boundary_object(H h)487 bool is_boundary_object(H h)
488 { return boundary_item_[h]!=boost::none; }
489 template <typename H>
is_sm_boundary_object(H h)490 bool is_sm_boundary_object(H h)
491 { return sm_boundary_item_[h]!=boost::none; }
492
493 template <typename H>
boundary_item(H h)494 Object_iterator& boundary_item(H h)
495 { return *boundary_item_[h]; }
496 template <typename H>
sm_boundary_item(H h)497 Object_iterator& sm_boundary_item(H h)
498 { return *sm_boundary_item_[h]; }
499
500 template <typename H>
store_boundary_item(H h,Object_iterator o)501 void store_boundary_item(H h, Object_iterator o)
502 { boundary_item_[h] = o; }
503 template <typename H>
store_sm_boundary_item(H h,Object_iterator o)504 void store_sm_boundary_item(H h, Object_iterator o)
505 { sm_boundary_item_[h] = o; }
506
507 template <typename H>
undef_boundary_item(H h)508 void undef_boundary_item(H h)
509 { CGAL_assertion(boundary_item_[h]!=boost::none);
510 boundary_item_[h] = boost::none; }
511 template <typename H>
undef_sm_boundary_item(H h)512 void undef_sm_boundary_item(H h)
513 { CGAL_assertion(sm_boundary_item_[h]!=boost::none);
514 sm_boundary_item_[h] = boost::none; }
515
reset_iterator_hash(Object_iterator it)516 void reset_iterator_hash(Object_iterator it)
517 { SVertex_handle sv;
518 SHalfedge_handle se;
519 SHalfloop_handle sl;
520 if ( CGAL::assign(se,*it) ) {
521 if( is_boundary_object(se))
522 undef_boundary_item(se);
523 return;
524 }
525 if ( CGAL::assign(sl,*it) ) {
526 if( is_boundary_object(sl))
527 undef_boundary_item(sl);
528 return;
529 }
530 if ( CGAL::assign(sv,*it) ) {
531 if( is_boundary_object(sv))
532 undef_boundary_item(sv);
533 return;
534 }
535 }
536
reset_sm_object_list(Object_list & L)537 void reset_sm_object_list(Object_list& L)
538 { Object_iterator oit;
539 CGAL_forall_iterators(oit,L) reset_sm_iterator_hash(oit);
540 L.clear();
541 }
542
reset_sm_iterator_hash(Object_iterator it)543 void reset_sm_iterator_hash(Object_iterator it)
544 { SVertex_handle sv;
545 SHalfedge_handle se;
546 SHalfloop_handle sl;
547 if ( CGAL::assign(se,*it) ) {
548 if( is_sm_boundary_object(se))
549 undef_sm_boundary_item(se);
550 return;
551 }
552 if ( CGAL::assign(sl,*it) ) {
553 if( is_sm_boundary_object(sl))
554 undef_sm_boundary_item(sl);
555 return;
556 }
557 if ( CGAL::assign(sv,*it) ) {
558 if( is_sm_boundary_object(sv))
559 undef_sm_boundary_item(sv);
560 return;
561 }
562 }
563
reset_object_list(Object_list & L)564 void reset_object_list(Object_list& L)
565 { Object_iterator oit;
566 CGAL_forall_iterators(oit,L) reset_iterator_hash(oit);
567 L.clear();
568 }
569
570 /*{\Moperations 2.5 3}*/
571
572 // The constant iterators and circulators.
vertices_begin()573 Vertex_const_iterator vertices_begin() const
574 { return vertices_.begin();}
vertices_end()575 Vertex_const_iterator vertices_end() const
576 { return vertices_.end();}
halfedges_begin()577 Halfedge_const_iterator halfedges_begin() const
578 { return halfedges_.begin();}
halfedges_end()579 Halfedge_const_iterator halfedges_end() const
580 { return halfedges_.end();}
halffacets_begin()581 Halffacet_const_iterator halffacets_begin() const
582 { return halffacets_.begin();}
halffacets_end()583 Halffacet_const_iterator halffacets_end() const
584 { return halffacets_.end();}
volumes_begin()585 Volume_const_iterator volumes_begin() const
586 { return volumes_.begin();}
volumes_end()587 Volume_const_iterator volumes_end() const
588 { return volumes_.end();}
589
svertices_begin()590 SVertex_const_iterator svertices_begin() const
591 { return halfedges_.begin();}
svertices_end()592 SVertex_const_iterator svertices_end() const
593 { return halfedges_.end();}
shalfedges_begin()594 SHalfedge_const_iterator shalfedges_begin() const
595 { return shalfedges_.begin();}
shalfedges_end()596 SHalfedge_const_iterator shalfedges_end() const
597 { return shalfedges_.end();}
shalfloops_begin()598 SHalfloop_const_iterator shalfloops_begin() const
599 { return shalfloops_.begin();}
shalfloops_end()600 SHalfloop_const_iterator shalfloops_end() const
601 { return shalfloops_.end();}
sfaces_begin()602 SFace_const_iterator sfaces_begin() const
603 { return sfaces_.begin();}
sfaces_end()604 SFace_const_iterator sfaces_end() const
605 { return sfaces_.end();}
606
vertices_begin()607 Vertex_iterator vertices_begin() { return vertices_.begin();}
vertices_end()608 Vertex_iterator vertices_end() { return vertices_.end();}
halfedges_begin()609 Halfedge_iterator halfedges_begin() { return halfedges_.begin();}
halfedges_end()610 Halfedge_iterator halfedges_end() { return halfedges_.end();}
halffacets_begin()611 Halffacet_iterator halffacets_begin() { return halffacets_.begin();}
halffacets_end()612 Halffacet_iterator halffacets_end() { return halffacets_.end();}
volumes_begin()613 Volume_iterator volumes_begin() { return volumes_.begin();}
volumes_end()614 Volume_iterator volumes_end() { return volumes_.end();}
615
svertices_begin()616 SVertex_iterator svertices_begin() { return halfedges_.begin();}
svertices_end()617 SVertex_iterator svertices_end() { return halfedges_.end();}
shalfedges_begin()618 SHalfedge_iterator shalfedges_begin() { return shalfedges_.begin();}
shalfedges_end()619 SHalfedge_iterator shalfedges_end() { return shalfedges_.end();}
shalfloops_begin()620 SHalfloop_iterator shalfloops_begin() { return shalfloops_.begin();}
shalfloops_end()621 SHalfloop_iterator shalfloops_end() { return shalfloops_.end();}
sfaces_begin()622 SFace_iterator sfaces_begin() { return sfaces_.begin();}
sfaces_end()623 SFace_iterator sfaces_end() { return sfaces_.end();}
624
625 /*{\Mtext The list of all objects can be accessed via iterator ranges.
626 For comfortable iteration we also provide iterations macros.
627 The iterator range access operations are of the following kind:\\
628 |Vertex_iterator vertices_begin()/vertices_end()|\\
629 |Halfedge_iterator halfedges_begin()/halfedges_end()|\\
630 |Halffacet_iterator halffacets_begin()/halffacets_end()|\\
631 |Volume_iterator volumes_begin()/volumes_end()|
632
633 The macros are then |CGAL_forall_vertices(v,\Mvar)|,
634 |CGAL_forall_halfedges(e,\Mvar)|, |CGAL_forall_edges(e,\Mvar)|,
635 |CGAL_forall_halffacets(f,\Mvar)|, |CGAL_forall_facets(f,\Mvar)|,
636 |CGAL_forall_volumes(w,\Mvar)|.}*/
637
number_of_vertices()638 Size_type number_of_vertices() const { return vertices_.size(); }
639 /*{\Mop returns the number of vertices.}*/
number_of_halfedges()640 Size_type number_of_halfedges() const { return halfedges_.size(); }
641 /*{\Mop returns the number of (directed edges).}*/
number_of_edges()642 Size_type number_of_edges() const { return halfedges_.size()/2; }
643 /*{\Mop returns the number of (directed edges).}*/
number_of_halffacets()644 Size_type number_of_halffacets() const { return halffacets_.size();}
645 /*{\Mop returns the number of halffacets.}*/
number_of_facets()646 Size_type number_of_facets() const { return halffacets_.size()/2;}
647 /*{\Mop returns the number of facets.}*/
number_of_volumes()648 Size_type number_of_volumes() const { return volumes_.size();}
649 /*{\Mop returns the number of volumes.}*/
number_of_svertices()650 Size_type number_of_svertices() const { return halfedges_.size();}
651 /*{\Mop returns the number of svertices.}*/
number_of_shalfedges()652 Size_type number_of_shalfedges() const { return shalfedges_.size();}
653 /*{\Mop returns the number of sedges.}*/
number_of_shalfloops()654 Size_type number_of_shalfloops() const { return shalfloops_.size();}
655 /*{\Mop returns the number of sloops.}*/
number_of_sfaces()656 Size_type number_of_sfaces() const { return sfaces_.size();}
657 /*{\Mop returns the number of sfaces.}*/
658
659 void print_statistics(std::ostream& os = std::cout) const
660 /*{\Mop print the statistics of |P|: the number of vertices, edges,
661 faces, volumes and sobjects.}*/
662 {
663 os << "Selective Nef Complex - Statistics\n";
664 os << "|V| = " << number_of_vertices() << std::endl;
665 os << "|E| = " << number_of_halfedges() << std::endl;
666 os << "|F| = " << number_of_halffacets() << std::endl;
667 os << "|C| = " << number_of_volumes() << std::endl;
668 os << "|VS| = " << number_of_svertices() << std::endl;
669 os << "|ES| = " << number_of_shalfedges() << std::endl;
670 os << "|LS| = " << number_of_shalfloops() << std::endl;
671 os << "|FS| = " << number_of_sfaces() << std::endl;
672 os << std::endl;
673 }
674
is_empty()675 bool is_empty() const {
676 /*{\Mop returns true if |\Mvar| is empty, false otherwise.}*/
677 return number_of_vertices() == 0 &&
678 number_of_halfedges() == 0 &&
679 number_of_halffacets() == 0 &&
680 number_of_volumes() == 0 &&
681 number_of_shalfedges() == 0 &&
682 number_of_shalfloops() == 0 &&
683 number_of_sfaces() == 0;
684 }
685
has_bbox_only()686 bool has_bbox_only() const {
687 /*{\Mop returns true if |\Mvar| is only the infimaximal box,
688 false otherwise.}*/
689 return (number_of_vertices() == 8 &&
690 number_of_edges() == 12 &&
691 number_of_facets() == 6 &&
692 number_of_volumes() == 2 &&
693 (++volumes_begin())->mark() == false);
694 }
695
696 Vertex_handle new_vertex(const Point_3& p = Point_3(), Mark m = Mark())
697 /*{\Mop returns a new vertex at point |p| marked by |m|.}*/ {
698 Vertex_handle vh = new_vertex_only();
699 vh->point() = p;
700 vh->mark() = m;
701 vh->sncp() = this;
702 vh->svertices_begin() = vh->svertices_last() = svertices_end();
703 vh->shalfedges_begin() = vh->shalfedges_last() = shalfedges_end();
704 vh->sfaces_begin() = vh->sfaces_last() = sfaces_end();
705 vh->shalfloop() = shalfloops_end();
706 return vh;
707 }
708
709 Halfedge_handle new_halfedge_pair(Vertex_handle v1, Vertex_handle v2,
710 Mark m = Mark())
711 /*{\Mop creates a new halfedge pair between the vertices $v_1$
712 and $v_2$. The edge is marked by |m|.}*/ {
713 SM_decorator D1(&*v1);
714 SM_decorator D2(&*v2);
715 SVertex_handle e1 = D1.new_vertex();
716 SVertex_handle e2 = D2.new_vertex();
717 make_twins(e1,e2);
718 e1->mark() = m;
719 return e1;
720 }
721
722 Halffacet_handle new_halffacet_pair(const Plane_3& h = Plane_3(),
723 Mark m = Mark())
724 /*{\Mop creates a new facet supported by the plane |h| and
725 marked with |m|.}*/ {
726 Halffacet_handle f1 = new_halffacet_only();
727 Halffacet_handle f2 = new_halffacet_only();
728 f1->plane() = h; f2->plane() = h.opposite();
729 make_twins(f1,f2);
730 f1->mark() = f2->mark() = m;
731 return f1;
732 }
733
734 Volume_handle new_volume(Mark m = Mark())
735 /*{\Mop creates a new volume marked with |m|.}*/ {
736 Volume_handle vh = new_volume_only();
737 vh->mark() = m;
738 return vh;
739 }
740
741 template <typename H>
make_twins(H h1,H h2)742 void make_twins(H h1, H h2) {
743 h1->twin() = h2; h2->twin() = h1;
744 }
745
delete_vertex(Vertex_handle v)746 void delete_vertex(Vertex_handle v)
747 /*{\Mop deletes the vertex including the objects in its local graph.}*/ {
748 CGAL_NEF_TRACEN("~ deleting vertex "<<&*v<<" from "<<&*this);
749 v->clear(true);
750 delete_vertex_only(v);
751 CGAL_NEF_TRACEN("~~ vertex deleted"<<&*v);
752 }
753
delete_halfedge_pair(Halfedge_handle e)754 void delete_halfedge_pair(Halfedge_handle e)
755 /*{\Mop deletes the halfedge pair of |e,twin(e)|. Does not care about
756 incident objects in the local graph of |source(e)|.}*/ {
757 CGAL_NEF_TRACEN("~ deleting halfedges pair "<<&*e<<", "<<&*(e->twin())<<
758 " from "<<&*this);
759 Halfedge_handle et = e->twin();
760 SM_decorator D1(&*e->center_vertex()), D2(&*et->center_vertex());
761 D1.delete_vertex(e);
762 D2.delete_vertex(et);
763 }
764
delete_halffacet_pair(Halffacet_handle f)765 void delete_halffacet_pair(Halffacet_handle f)
766 /*{\Mop deletes the halffacet pair |f,twin(f)|. Does not care about
767 boundary cycle objects.}*/ {
768 CGAL_NEF_TRACEN("~ deleting halffacets pair "<<&*f<<", "<<&*(f->twin())<<
769 " from "<<&*this);
770 reset_object_list(f->boundary_entry_objects());
771 reset_object_list(f->twin()->boundary_entry_objects());
772 delete_halffacet_only(f->twin());
773 delete_halffacet_only(f);
774 }
775
delete_volume(Volume_handle c)776 void delete_volume(Volume_handle c)
777 /*{\Mop deletes the volume |c|. Does not care about shell objects.}*/ {
778 CGAL_NEF_TRACEN("~ deleting volume "<<&*c<<" from "<<&*this);
779 reset_object_list(c->shell_entry_objects());
780 delete_volume_only(c);
781 }
782
783 Vertex_alloc vertex_allocator;
get_vertex_node(const Vertex &)784 Vertex* get_vertex_node( const Vertex& ) {
785 Vertex* p = vertex_allocator.allocate(1);
786 std::allocator_traits<Vertex_alloc>::construct(vertex_allocator, p);
787 return p;
788 }
put_vertex_node(Vertex * p)789 void put_vertex_node( Vertex* p) {
790 std::allocator_traits<Vertex_alloc>::destroy(vertex_allocator,p);
791 vertex_allocator.deallocate( p, 1);
792 }
793
794 Halfedge_alloc halfedge_allocator;
get_halfedge_node(const Halfedge &)795 Halfedge* get_halfedge_node( const Halfedge&) {
796 Halfedge* p = halfedge_allocator.allocate(1);
797 std::allocator_traits<Halfedge_alloc>::construct(halfedge_allocator, p);
798 return p;
799 }
put_halfedge_node(Halfedge * p)800 void put_halfedge_node( Halfedge* p) {
801 std::allocator_traits<Halfedge_alloc>::destroy(halfedge_allocator,p);
802 halfedge_allocator.deallocate( p, 1);
803 }
804
805 Halffacet_alloc halffacet_allocator;
get_halffacet_node(const Halffacet &)806 Halffacet* get_halffacet_node( const Halffacet& ) {
807 Halffacet* p = halffacet_allocator.allocate(1);
808 std::allocator_traits<Halffacet_alloc>::construct(halffacet_allocator, p);
809 return p;
810 }
put_halffacet_node(Halffacet * p)811 void put_halffacet_node( Halffacet* p) {
812 std::allocator_traits<Halffacet_alloc>::destroy(halffacet_allocator,p);
813 halffacet_allocator.deallocate( p, 1);
814 }
815
816 Volume_alloc volume_allocator;
get_volume_node(const Volume &)817 Volume* get_volume_node( const Volume& ) {
818 Volume* p = volume_allocator.allocate(1);
819 std::allocator_traits<Volume_alloc>::construct(volume_allocator, p);
820 return p;
821 }
put_volume_node(Volume * p)822 void put_volume_node( Volume* p) {
823 std::allocator_traits<Volume_alloc>::destroy(volume_allocator,p);
824 volume_allocator.deallocate( p, 1);
825 }
826
827 SHalfedge_alloc shalfedge_allocator;
get_shalfedge_node(const SHalfedge &)828 SHalfedge* get_shalfedge_node( const SHalfedge& ) {
829 SHalfedge* p = shalfedge_allocator.allocate(1);
830 std::allocator_traits<SHalfedge_alloc>::construct(shalfedge_allocator, p);
831 return p;
832 }
put_shalfedge_node(SHalfedge * p)833 void put_shalfedge_node( SHalfedge* p) {
834 std::allocator_traits<SHalfedge_alloc>::destroy(shalfedge_allocator,p);
835 shalfedge_allocator.deallocate( p, 1);
836 }
837
838 SHalfloop_alloc shalfloop_allocator;
get_shalfloop_node(const SHalfloop &)839 SHalfloop* get_shalfloop_node( const SHalfloop& ) {
840 SHalfloop* p = shalfloop_allocator.allocate(1);
841 std::allocator_traits<SHalfloop_alloc>::construct(shalfloop_allocator, p);
842 return p;
843 }
put_shalfloop_node(SHalfloop * p)844 void put_shalfloop_node( SHalfloop* p) {
845 std::allocator_traits<SHalfloop_alloc>::destroy(shalfloop_allocator,p);
846 shalfloop_allocator.deallocate( p, 1);
847 }
848
849 SFace_alloc sface_allocator;
get_sface_node(const SFace &)850 SFace* get_sface_node( const SFace& ) {
851 SFace* p = sface_allocator.allocate(1);
852 std::allocator_traits<SFace_alloc>::construct(sface_allocator, p);
853 return p;
854 }
put_sface_node(SFace * p)855 void put_sface_node( SFace* p) {
856 std::allocator_traits<SFace_alloc>::destroy(sface_allocator,p);
857 sface_allocator.deallocate( p, 1);
858 }
859
860
new_vertex_only()861 Vertex_handle new_vertex_only() {
862 vertices_.push_back(* get_vertex_node(Vertex()));
863 CGAL_NEF_TRACEN(" new vertex only "<<&*(--vertices_end()));
864 return --vertices_end();
865 }
new_halfedge_only(Halfedge_handle e)866 Halfedge_handle new_halfedge_only(Halfedge_handle e) {
867 Halfedge_handle ne = halfedges_.insert(e, * get_halfedge_node(Halfedge()));
868 CGAL_NEF_TRACEN(" after "<<&*e<<" new halfedge only "<<&*ne);
869 return ne;
870 }
new_halfedge_only()871 Halfedge_handle new_halfedge_only() {
872 CGAL_NEF_TRACEN(" new halfedge only "<<&*(--halfedges_end()));
873 halfedges_.push_back( * get_halfedge_node(Halfedge()));
874 return --halfedges_end();
875 }
new_halffacet_only()876 Halffacet_handle new_halffacet_only() {
877 halffacets_.push_back( * get_halffacet_node(Halffacet()));
878 CGAL_NEF_TRACEN(" new halffacet only "<<&*(--halffacets_end()));
879 return --halffacets_end();
880 }
new_volume_only()881 Volume_handle new_volume_only() {
882 volumes_.push_back( * get_volume_node(Volume()));
883 CGAL_NEF_TRACEN(" new volume only "<<&*(--volumes_end()));
884 return --volumes_end();
885 }
new_shalfedge_only()886 SHalfedge_handle new_shalfedge_only() {
887 shalfedges_.push_back( * get_shalfedge_node(SHalfedge()));
888 CGAL_NEF_TRACEN(" new shalfedge only "<<&*(--shalfedges_end()));
889 return --shalfedges_end();
890 }
new_shalfedge_only(SHalfedge_handle se)891 SHalfedge_handle new_shalfedge_only(SHalfedge_handle se) {
892 SHalfedge_handle nse = shalfedges_.insert(se, * get_shalfedge_node(SHalfedge()));
893 CGAL_NEF_TRACEN(" after " << &*se << " new shalfedge only " << &*nse);
894 return nse;
895 }
new_shalfloop_only()896 SHalfloop_handle new_shalfloop_only() {
897 shalfloops_.push_back( * get_shalfloop_node(SHalfloop()));
898 CGAL_NEF_TRACEN(" new shalfloop only "<<&*(--shalfloops_end()));
899 return --shalfloops_end();
900 }
new_sface_only()901 SFace_handle new_sface_only() {
902 sfaces_.push_back( * get_sface_node(SFace()));
903 CGAL_NEF_TRACEN(" new sface only "<<&*(--sfaces_end()));
904 return --sfaces_end();
905 }
new_sface_only(SFace_handle sf)906 SFace_handle new_sface_only(SFace_handle sf) {
907 SFace_handle nsf = sfaces_.insert(sf, * get_sface_node(SFace()));
908 CGAL_NEF_TRACEN(" after " << &*sf << " new sface only " << &*nsf);
909 return nsf;
910 }
911
delete_vertex_only(Vertex_handle h)912 void delete_vertex_only(Vertex_handle h) {
913 CGAL_NEF_TRACEN("~ deleting vertex only "<<&*h<<" from "<<&*this);
914 vertices_.erase(h);
915 put_vertex_node(&*h);
916 }
delete_halfedge_only(Halfedge_handle h)917 void delete_halfedge_only(Halfedge_handle h) {
918 CGAL_NEF_TRACEN("~ deleting halfedge only "<<&*h<<" from "<<&*this);
919 CGAL_assertion(!is_sm_boundary_object(h));
920 halfedges_.erase(h);
921 put_halfedge_node(&*h);
922 }
delete_halffacet_only(Halffacet_handle h)923 void delete_halffacet_only(Halffacet_handle h) {
924 CGAL_NEF_TRACEN("~ deleting halffacet only "<<&*h<<" from "<<&*this);
925 halffacets_.erase(h);
926 put_halffacet_node(&*h);
927 }
delete_volume_only(Volume_handle h)928 void delete_volume_only(Volume_handle h) {
929 CGAL_NEF_TRACEN("~ deleting volume only "<<&*h<<" from "<<&*this);
930 volumes_.erase(h);
931 put_volume_node(&*h);
932 }
delete_shalfedge_only(SHalfedge_handle h)933 void delete_shalfedge_only(SHalfedge_handle h) {
934 CGAL_NEF_TRACEN("~ deleting shalfedge only "<<&*h<<" from "<<&*this);
935 CGAL_assertion(!is_sm_boundary_object(h));
936 shalfedges_.erase(h);
937 put_shalfedge_node(&*h);
938 }
delete_shalfloop_only(SHalfloop_handle h)939 void delete_shalfloop_only(SHalfloop_handle h) {
940 CGAL_NEF_TRACEN("~ deleting shalfloop only "<<&*h<<" from "<<&*this);
941 CGAL_assertion(!is_sm_boundary_object(h));
942 shalfloops_.erase(h);
943 put_shalfloop_node(&*h);
944 }
delete_sface_only(SFace_handle h)945 void delete_sface_only(SFace_handle h) {
946 CGAL_NEF_TRACEN("~ deleting sface only "<<&*h<<" from "<<&*this);
947 CGAL_assertion(!is_boundary_object(h));
948 sfaces_.erase(h);
949 put_sface_node(&*h);
950 }
951 //SL: in the following function, I guess the sizeof(void*) is related to the void* info that was
952 //used together with geninfo to store an arbitrary type. I replaced that with any and did not changed that
bytes()953 std::size_t bytes() {
954 // bytes used for the SNC_structure
955
956 std::size_t result = sizeof(Self);
957 result += number_of_vertices() * (sizeof(Vertex)
958 - sizeof(Point_3));
959 result += number_of_halfedges() * (sizeof(Halfedge)
960 - sizeof(Sphere_point));
961 result += number_of_halffacets() * (sizeof(Halffacet)
962 - sizeof(Plane_3));
963 result += number_of_volumes() * sizeof(Volume);
964 result += number_of_shalfedges() * (sizeof(SHalfedge)
965 - sizeof(Sphere_circle));
966 result += number_of_shalfloops() * sizeof(SHalfloop);
967 result += number_of_sfaces() * sizeof(SFace);
968
969 Halffacet_iterator hf;
970 CGAL_forall_halffacets(hf, *this) {
971 Halffacet_cycle_iterator fc;
972 CGAL_forall_facet_cycles_of(fc, hf)
973 result += sizeof(*fc) + 2 * sizeof(void*);
974 }
975
976 Volume_iterator c;
977 CGAL_forall_volumes(c, *this) {
978 Shell_entry_iterator sei;
979 CGAL_forall_shells_of(sei,c)
980 result += sizeof(*sei) + 2 * sizeof(void*);
981 }
982
983 SFace_iterator sf;
984 CGAL_forall_sfaces(sf, *this) {
985 SFace_cycle_iterator sfc;
986 CGAL_forall_sface_cycles_of(sfc,sf)
987 result += sizeof(*sfc) + 2 * sizeof(void*);
988 }
989
990 return result;
991 }
992
993 //SL: in the following function, I guess the sizeof(void*) is related to the void* info that was
994 //used together with geninfo to store an arbitrary type. I replaced that with any and did not changed that
bytes_reduced()995 std::size_t bytes_reduced() {
996 // bytes used for the SNC_structure
997
998 std::size_t result = sizeof(Self);
999 result += number_of_vertices() * (sizeof(Vertex)
1000 - sizeof(Point_3)
1001 - sizeof(SHalfloop_iterator)
1002 - 2 * sizeof(Mark)
1003 - sizeof(void*));
1004 result += number_of_halfedges() * (sizeof(Halfedge)
1005 - sizeof(SHalfedge_handle)
1006 - sizeof(SFace_handle)
1007 - sizeof(void*)
1008 - sizeof(Sphere_point));
1009 result += number_of_halffacets() * (sizeof(Halffacet)
1010 - sizeof(Plane_3));
1011 result += number_of_volumes() * sizeof(Volume);
1012 result += number_of_shalfedges() * (sizeof(SHalfedge)
1013 - sizeof(SVertex_handle)
1014 - 3 * sizeof(SHalfedge_handle)
1015 - sizeof(SFace_handle)
1016 - sizeof(void*)
1017 - sizeof(Mark)
1018 - sizeof(Sphere_circle));
1019 result += number_of_sfaces() * (sizeof(SFace)
1020 - sizeof(void*)
1021 - sizeof(Mark)
1022 - sizeof(Object_list));
1023
1024 Halffacet_iterator hf;
1025 CGAL_forall_halffacets(hf, *this) {
1026 Halffacet_cycle_iterator fc;
1027 CGAL_forall_facet_cycles_of(fc, hf)
1028 result += sizeof(*fc) + 2 * sizeof(void*);
1029 }
1030
1031 Volume_iterator c;
1032 CGAL_forall_volumes(c, *this) {
1033 Shell_entry_iterator sei;
1034 CGAL_forall_shells_of(sei,c)
1035 result += sizeof(*sei) + 2 * sizeof(void*);
1036 }
1037
1038 return result;
1039 }
1040
bytes_reduced2()1041 std::size_t bytes_reduced2() {
1042 // bytes used for the SNC_structure
1043
1044 std::size_t result = sizeof(Self);
1045 result += number_of_vertices() * (sizeof(Mark)
1046 + sizeof(SNC_structure*)
1047 + sizeof(Object_list)
1048 + 2 * sizeof(SFace_handle));
1049 result += number_of_halfedges() * (sizeof(Vertex_handle)
1050 + sizeof(SVertex_handle)
1051 + sizeof(Mark)
1052 + 2 * sizeof(Object_handle));
1053 result += number_of_halffacets() * (sizeof(Halffacet)
1054 - sizeof(Plane_3));
1055 result += number_of_volumes() * sizeof(Volume);
1056 result += number_of_shalfedges() * (2 * sizeof(SHalfedge_handle)
1057 + sizeof(Halffacet_handle));
1058 result += number_of_shalfloops() * sizeof(SHalfloop);
1059 result += number_of_sfaces() * (sizeof(Vertex_handle)
1060 + sizeof(Volume_handle));
1061
1062 Halffacet_iterator hf;
1063 CGAL_forall_halffacets(hf, *this) {
1064 Halffacet_cycle_iterator fc;
1065 CGAL_forall_facet_cycles_of(fc, hf)
1066 result += sizeof(*fc) + 2 * sizeof(void*);
1067 }
1068
1069 Volume_iterator c;
1070 CGAL_forall_volumes(c, *this) {
1071 Shell_entry_iterator sei;
1072 CGAL_forall_shells_of(sei,c)
1073 result += sizeof(*sei) + 2 * sizeof(void*);
1074 }
1075
1076 return result;
1077 }
1078
1079 protected:
1080 void pointer_update(const Self& D);
1081
1082 typedef boost::optional<Object_iterator> Optional_object_iterator ;
1083 private:
1084 Generic_handle_map<Optional_object_iterator> boundary_item_;
1085 Generic_handle_map<Optional_object_iterator> sm_boundary_item_;
1086 protected:
1087 Vertex_list vertices_;
1088 Halfedge_list halfedges_;
1089 Halffacet_list halffacets_;
1090 Volume_list volumes_;
1091 SHalfedge_list shalfedges_;
1092 SHalfloop_list shalfloops_;
1093 SFace_list sfaces_;
1094
1095 }; // SNC_structure
1096
1097
1098 template <typename Kernel, typename Items, typename Mark>
1099 void SNC_structure<Kernel,Items,Mark>::
pointer_update(const SNC_structure<Kernel,Items,Mark> & D)1100 pointer_update(const SNC_structure<Kernel,Items,Mark>& D)
1101 {
1102 CGAL::Unique_hash_map<Vertex_const_handle,Vertex_handle> VM;
1103 CGAL::Unique_hash_map<Halfedge_const_handle,Halfedge_handle> EM;
1104 CGAL::Unique_hash_map<Halffacet_const_handle,Halffacet_handle> FM;
1105 CGAL::Unique_hash_map<Volume_const_handle,Volume_handle> CM;
1106 CGAL::Unique_hash_map<SHalfedge_const_handle,SHalfedge_handle> SEM;
1107 CGAL::Unique_hash_map<SHalfloop_const_handle,SHalfloop_handle> SLM;
1108 CGAL::Unique_hash_map<SFace_const_handle,SFace_handle> SFM;
1109 Vertex_const_iterator vc = D.vertices_begin();
1110 Vertex_iterator v = vertices_begin();
1111 for ( ; vc != D.vertices_end(); ++vc,++v) VM[vc] = v;
1112 VM[D.vertices_end()] = vertices_end();
1113 Halfedge_const_iterator ec = D.halfedges_begin();
1114 Halfedge_iterator e = halfedges_begin();
1115 for ( ; ec != D.halfedges_end(); ++ec,++e) EM[ec] = e;
1116 EM[D.halfedges_end()] = halfedges_end();
1117 Halffacet_const_iterator fc = D.halffacets_begin();
1118 Halffacet_iterator f = halffacets_begin();
1119 for ( ; fc != D.halffacets_end(); ++fc,++f) FM[fc] = f;
1120 FM[D.halffacets_end()] = halffacets_end();
1121 Volume_const_iterator cc = D.volumes_begin();
1122 Volume_iterator c = volumes_begin();
1123 for ( ; cc != D.volumes_end(); ++cc,++c) CM[cc] = c;
1124 CM[D.volumes_end()] = volumes_end();
1125 SHalfedge_const_iterator sec = D.shalfedges_begin();
1126 SHalfedge_iterator se = shalfedges_begin();
1127 for ( ; sec != D.shalfedges_end(); ++sec,++se) SEM[sec] = se;
1128 SEM[D.shalfedges_end()] = shalfedges_end();
1129 SHalfloop_const_iterator slc = D.shalfloops_begin();
1130 SHalfloop_iterator sl = shalfloops_begin();
1131 for ( ; slc != D.shalfloops_end(); ++slc,++sl) SLM[slc] = sl;
1132 SLM[D.shalfloops_end()] = shalfloops_end();
1133 SFace_const_iterator sfc = D.sfaces_begin();
1134 SFace_iterator sf = sfaces_begin();
1135 for ( ; sfc != D.sfaces_end(); ++sfc,++sf) SFM[sfc] = sf;
1136 SFM[D.sfaces_end()] = sfaces_end();
1137
1138 CGAL_forall_vertices(v,*this) {
1139 // Local Graph update: (SVertices are postponed/updated as Edges)
1140 v->sncp() = this;
1141 v->svertices_begin() = EM[v->svertices_begin()];
1142 v->svertices_last() = EM[v->svertices_last()];
1143 v->shalfedges_begin() = SEM[v->shalfedges_begin()];
1144 v->shalfedges_last() = SEM[v->shalfedges_last()];
1145 v->sfaces_begin() = SFM[v->sfaces_begin()];
1146 v->sfaces_last() = SFM[v->sfaces_last()];
1147 v->shalfloop() = SLM[v->shalfloop()];
1148 }
1149 // Halfedge update:
1150 CGAL_forall_halfedges(e,*this) {
1151 e->center_vertex() = VM[e->center_vertex()];
1152 e->twin() = EM[e->twin()];
1153 e->out_sedge() = SEM[e->out_sedge()];
1154 e->incident_sface() = SFM[e->incident_sface()];
1155 }
1156 // Halffacet update
1157 CGAL_forall_halffacets(f,*this) {
1158 f->twin() = FM[f->twin()];
1159 f->incident_volume() = CM[f->incident_volume()];
1160 Halffacet_cycle_iterator ftc;
1161 for(ftc = f->facet_cycles_begin(); ftc != f->facet_cycles_end(); ++ftc) {
1162 if (ftc.is_shalfedge() ) {
1163 se = SHalfedge_handle(ftc);
1164 *ftc = make_object(SEM[se]);
1165 store_boundary_item(se,ftc);
1166 } else if (ftc.is_shalfloop() ) {
1167 sl = SHalfloop_handle(ftc);
1168 *ftc = make_object(SLM[sl]);
1169 store_boundary_item(sl,ftc);
1170 } else CGAL_error_msg("damn wrong boundary item in facet.");
1171 }
1172 }
1173
1174 // Volume update
1175 CGAL_forall_volumes(c,*this) {
1176 Shell_entry_iterator sei;
1177 CGAL_forall_shells_of(sei,c) {
1178 sf = sei; // conversion from generic iterator to sface const handle
1179 *sei = make_object(SFM[sf]);
1180 store_boundary_item(sf,sei);
1181 }
1182 }
1183
1184 CGAL_forall_shalfedges(se,*this) {
1185 se->source() = EM[se->source()];
1186 se->sprev() = SEM[se->sprev()]; se->snext() = SEM[se->snext()];
1187 se->incident_sface() = SFM[se->incident_sface()];
1188 se->twin() = SEM[se->twin()];
1189 se->prev() = SEM[se->prev()]; se->next() = SEM[se->next()];
1190 se->facet() = FM[se->facet()];
1191 }
1192
1193 CGAL_forall_shalfloops(sl,*this) {
1194 sl->twin() = SLM[sl->twin()];
1195 sl->incident_sface() = SFM[sl->incident_sface()];
1196 sl->facet() = FM[sl->facet()];
1197 }
1198 for ( slc = D.shalfloops_begin(), sl = shalfloops_begin();
1199 slc != D.shalfloops_end(); ++slc, ++sl) {
1200 /* It is possible that the is_twin() property differs for equivalent
1201 sloops on both SNC structures. So, we need to store the correct
1202 selection mark in the correct (non-twin) facet of a shalfloop pair. */
1203 CGAL_assertion_code( if( slc->is_twin() == sl->is_twin())
1204 CGAL_assertion( slc->mark() == sl->mark()));
1205 if( !sl->is_twin() && slc->is_twin()) sl->mark() = sl->twin()->mark();
1206 }
1207
1208 CGAL_forall_sfaces(sf,*this) {
1209 sf->center_vertex() = VM[sf->center_vertex()];
1210 sf->volume() = CM[sf->volume()];
1211 SFace_cycle_iterator sfc;
1212 for(sfc = sf->sface_cycles_begin();
1213 sfc != sf->sface_cycles_end(); ++sfc)
1214 {
1215 if (sfc.is_svertex()) {
1216 SVertex_handle sv(sfc);
1217 sv = EM[sv];
1218 *sfc = make_object(sv);
1219 store_sm_boundary_item(sv,sfc);
1220 } else if (sfc.is_shalfedge()) {
1221 se = SHalfedge_handle(sfc);
1222 se = SEM[se];
1223 *sfc = make_object(se);
1224 store_sm_boundary_item(se,sfc);
1225 } else if (sfc.is_shalfloop()) {
1226 sl = SHalfloop_handle(sfc);
1227 sl = SLM[sl];
1228 *sfc = make_object(sl);
1229 store_sm_boundary_item(sl,sfc);
1230 } else CGAL_error_msg("damn wrong boundary item in sface.");
1231 }
1232 }
1233 }
1234
1235 } //namespace CGAL
1236 #endif // CGAL_SNC_STRUCTURE_H
1237