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_S2/include/CGAL/Nef_S2/SM_const_decorator.h $
7 // $Id: SM_const_decorator.h 9c6712c 2021-02-08T19:32:33+00: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 // Peter Hachenberger <hachenberger@mpi-sb.mpg.de>
16 #ifndef CGAL_SM_CONST_DECORATOR_H
17 #define CGAL_SM_CONST_DECORATOR_H
18
19 #include <CGAL/license/Nef_S2.h>
20
21
22 #include <CGAL/basic.h>
23 #include <CGAL/circulator.h>
24 #include <CGAL/Unique_hash_map.h>
25 #include <CGAL/Nef_2/Object_index.h>
26 #include <CGAL/Nef_S2/SM_iteration.h>
27 #include <CGAL/Nef_S2/SM_decorator_traits.h>
28 #include <string>
29 #include <list>
30 #include <sstream>
31 #undef CGAL_NEF_DEBUG
32 #define CGAL_NEF_DEBUG 67
33 #include <CGAL/Nef_2/debug.h>
34 #ifndef CGAL_I_DO_WANT_TO_USE_GENINFO
35 #include <boost/any.hpp>
36 #endif
37
38 namespace CGAL {
39
40 template <typename Map_>
41 class SM_const_decorator {
42
43 typedef SM_const_decorator<Map_> Self;
44 public:
45
46 typedef Map_ Map;
47 typedef const Map_ Sphere_map;
48 typedef SM_decorator_const_traits<Map> Decorator_traits;
49
50 /*{\Mdefinition ...}*/
51
52 /*{\Mtypes 5}*/
53
54 typedef typename Map::Sphere_kernel Sphere_kernel;
55 /*{\Mtypemember spherical geometry.}*/
56
57 typedef typename Map::Sphere_point Sphere_point;
58 /*{\Mtypemember embedding vertices.}*/
59
60 typedef typename Map::Sphere_segment Sphere_segment;
61 /*{\Mtypemember embedding edges.}*/
62
63 typedef typename Map::Sphere_circle Sphere_circle;
64 /*{\Mtypemember embedding loops.}*/
65
66 typedef typename Map::Sphere_direction Sphere_direction;
67 /*{\Mtypemember embedding directions.}*/
68
69 typedef typename Map::Mark Mark;
70 /*{\Mtypemember attributes of objects (vertices, edges, faces).}*/
71
72 typedef size_t Size_type;
73 /*{\Mtypemember size type.}*/
74
75 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
76 typedef void* GenPtr;
77 #else
78 typedef boost::any GenPtr;
79 #endif
80
81
82 // typedef typename Map::Constructor_const_parameter Constructor_parameter;
83 typedef typename Map::SVertex_const_handle SVertex_const_handle;
84 typedef typename Map::SVertex_const_iterator SVertex_const_iterator;
85 typedef typename Map::SHalfedge_const_handle SHalfedge_const_handle;
86 typedef typename Map::SHalfedge_const_iterator SHalfedge_const_iterator;
87 typedef typename Map::SHalfloop_const_handle SHalfloop_const_handle;
88 typedef typename Map::SHalfloop_const_iterator SHalfloop_const_iterator;
89 typedef typename Map::SFace_const_handle SFace_const_handle;
90 typedef typename Map::SFace_const_iterator SFace_const_iterator;
91
92 /*{\Mtext Local types are handles, iterators and circulators of the
93 following kind: |SVertex_handle|, |SVertex_iterator|, |SHalfedge_handle|,
94 |SHalfedge_iterator|, |SHalfloop_handle|, |SHalfloop_iterator|,
95 |SFace_handle|, |SFace_iterator|. Additionally the following
96 circulators are defined.}*/
97
98 typedef typename Map::SHalfedge_around_svertex_const_circulator
99 SHalfedge_around_svertex_const_circulator;
100 /*{\Mtypemember circulating the adjacency list of an vertex |v|.}*/
101
102 typedef typename Map::SHalfedge_around_sface_const_circulator
103 SHalfedge_around_sface_const_circulator;
104 /*{\Mtypemember circulating the face cycle of an face |f|.}*/
105
106 typedef typename Map::SFace_cycle_const_iterator
107 SFace_cycle_const_iterator;
108 /*{\Mtypemember iterating all sface cycles of an sface |f|.
109 The iterator has method |bool is_svertex()|, |bool is_shalfedge()|,
110 |bool is_shalfloop()|, and can be converted to the corresponding
111 handles |SVertex_const_handle|, |SHalfedge_const_handle|, or
112 |SHalfloop_const_handle|.}*/
113
114 protected:
115 const Map* psm_;
116
set_sm(const Map * W)117 void set_sm(const Map* W) {
118 psm_ = W;
119 }
120
121 public:
122
123 /*{\Mcreation 3}*/
SM_const_decorator()124 SM_const_decorator() : psm_(0) {}
SM_const_decorator(const Self & D)125 SM_const_decorator(const Self& D) : psm_(D.psm_) {}
126 Self& operator=(const Self& D) { psm_=D.psm_; return *this; }
127
SM_const_decorator(const Map * M)128 SM_const_decorator(const Map* M) : psm_(M) {}
129 /*{\Mcreate constructs a plane map decorator exploring |M|.}*/
130
131 /*{\Moperations 4 4}*/
132
sphere_map()133 const Map* sphere_map() const { return psm_; }
134
is_isolated(SVertex_const_handle v)135 bool is_isolated(SVertex_const_handle v) const
136 /*{\Mop returns |true| when |v| is linked to the interior of a face.}*/
137 { return (SHalfedge_const_handle(v->out_sedge()) == SHalfedge_const_handle()); }
138
first_out_edge(SVertex_const_handle v)139 SHalfedge_const_handle first_out_edge(SVertex_const_handle v) const
140 /*{\Mop returns one edge with source |v|. It's the starting point for
141 the circular iteration over the edges with source |v|.
142 \precond |!is_isolated(v)|.}*/
143 { return v->out_sedge(); }
144
last_out_edge(SVertex_const_handle v)145 SHalfedge_const_handle last_out_edge(SVertex_const_handle v) const
146 /*{\Mop returns one edge with source |v|. \precond |!is_isolated(v)|.}*/
147 { return cap(v->out_sedge()); }
148
cyclic_adj_succ(SHalfedge_const_handle e)149 SHalfedge_const_handle cyclic_adj_succ(SHalfedge_const_handle e) const
150 /*{\Mop returns the edge after |e| in the cyclic ordered adjacency list of
151 |e->source()|.}*/
152 { return e->sprev()->twin(); }
153
cyclic_adj_pred(SHalfedge_const_handle e)154 SHalfedge_const_handle cyclic_adj_pred(SHalfedge_const_handle e) const
155 /*{\Mop returns the edge before |e| in the cyclic ordered adjacency list of
156 |e->source()|.}*/
157 { return e->twin()->snext(); }
158
159
160 /*{\Mtext \headerline{Iteration} \setopdims{3.3cm}{0cm}}*/
161
svertices_begin()162 SVertex_const_iterator svertices_begin() const
163 { return psm_->svertices_begin(); }
svertices_end()164 SVertex_const_iterator svertices_end() const
165 { return psm_->svertices_end(); }
shalfedges_begin()166 SHalfedge_const_iterator shalfedges_begin() const
167 { return psm_->shalfedges_begin(); }
shalfedges_end()168 SHalfedge_const_iterator shalfedges_end() const
169 { return psm_->shalfedges_end(); }
sfaces_begin()170 SFace_const_iterator sfaces_begin() const
171 { return psm_->sfaces_begin(); }
sfaces_end()172 SFace_const_iterator sfaces_end() const
173 { return psm_->sfaces_end(); }
shalfloops_begin()174 SHalfloop_const_iterator shalfloops_begin() const
175 { return psm_->shalfloops_begin(); }
shalfloops_end()176 SHalfloop_const_iterator shalfloops_end() const
177 { return psm_->shalfloops_end(); }
178
shalfloop()179 SHalfloop_const_handle shalfloop() const
180 /*{\Mop returns access to the loop.}*/
181 { return psm_->shalfloop(); }
182
has_shalfloop()183 bool has_shalfloop() const
184 /*{\Mop returns true iff there is a loop.}*/
185 { return psm_->has_shalfloop(); }
186
187 SHalfedge_around_svertex_const_circulator
out_edges(SVertex_const_handle v)188 out_edges(SVertex_const_handle v) const
189 /*{\Mop returns a circulator for the cyclic adjacency list of |v|.
190 \precond the adjacency list is not empty.}*/
191 { return SHalfedge_around_svertex_const_circulator(first_out_edge(v)); }
192
sface_cycles_begin(SFace_const_handle f)193 SFace_cycle_const_iterator sface_cycles_begin(SFace_const_handle f) const
194 /*{\Mop returns an iterator for all bounding face cycles of |f|.
195 The iterator is is convertable to |SVertex_const_handle|,
196 |SHalfloop_const_handle|, or |SHalfedge_const_handle|.}*/
197 { return f->boundary_entry_objects_.begin(); }
198
sface_cycles_end(SFace_const_handle f)199 SFace_cycle_const_iterator sface_cycles_end(SFace_const_handle f) const
200 /*{\Mop returns the past the end iterator of |f|.}*/
201 { return f->boundary_entry_objects_.end(); }
202
203 /*{\Mtext \headerline{Statistics and Integrity}}*/
204
number_of_svertices()205 Size_type number_of_svertices() const
206 /*{\Mop returns the number of vertices.}*/
207 { return psm_->number_of_svertices(); }
208
number_of_shalfedges()209 Size_type number_of_shalfedges() const
210 /*{\Mop returns the number of halfedges.}*/
211 { return psm_->number_of_shalfedges(); }
212
number_of_sedges()213 Size_type number_of_sedges() const
214 /*{\Mop returns the number of edges.}*/
215 { return number_of_shalfedges()/2; }
216
number_of_shalfloops()217 Size_type number_of_shalfloops() const
218 /*{\Mop returns the number of halfloops.}*/
219 { return psm_->number_of_shalfloops(); }
220
number_of_sloops()221 Size_type number_of_sloops() const
222 /*{\Mop returns the number of loops.}*/
223 { return psm_->number_of_shalfloops()/2; }
224
number_of_sfaces()225 Size_type number_of_sfaces() const
226 /*{\Mop returns the number of faces.}*/
227 { return psm_->number_of_sfaces(); }
228
229 Size_type number_of_sface_cycles() const;
230 /*{\Mop returns the number of face cycles.}*/
231
232 Size_type number_of_connected_components() const;
233 /*{\Mop calculates the number of connected components of |P|.}*/
234
235 void print_statistics(std::ostream& os = std::cout) const
236 /*{\Mop print the statistics of |P|: the number of vertices, edges,
237 and faces.}*/
238 {
239 os << "Sphere Map - Statistics\n";
240 os << "|V| = " << number_of_svertices() << std::endl;
241 os << "|E| = " << number_of_shalfedges() << std::endl;
242 os << "|L| = " << number_of_shalfloops() << std::endl;
243 os << "|F| = " << number_of_sfaces() << std::endl;
244 os << "|Fcs| = " << number_of_sface_cycles() << std::endl << std::endl;
245 }
246
247 void check_integrity_and_topological_planarity(bool faces=true) const;
248 /*{\Mop checks the link structure and the genus of |P|.}*/
249
cas(SHalfedge_const_handle e)250 SHalfedge_const_handle cas(SHalfedge_const_handle e) const
251 { return cyclic_adj_succ(e); }
252
cap(SHalfedge_const_handle e)253 SHalfedge_const_handle cap(SHalfedge_const_handle e) const
254 { return cyclic_adj_pred(e); }
255
256 template <typename H>
is_sm_boundary_object(H h)257 bool is_sm_boundary_object(H h) const
258 { return psm_->is_sm_boundary_object(h); }
259
260 /*{\Mtext \headerline{Associated Information}\restoreopdims}*/
261
262 /*{\Mtext \headerline{Iteration}}*/
263 /*{\Mtext The list of all objects can be accessed via iterator ranges.
264 For comfortable iteration we also provide iterations macros.
265 The iterator range access operations are of the following kind:\\
266 |SVertex_iterator svertices_begin()/svertices_end()|\\
267 |SHalfedge_iterator shalfedges_begin()/shalfedges_end()|\\
268 |SHalfloop_iterator shalfloops_begin()/shalfloops_end()|\\
269 |SFace_iterator sfaces_begin()/sfaces_end()|
270
271 The macros are then |CGAL_forall_svertices(v,M)|,
272 |CGAL_forall_shalfedges(e,M)|, |CGAL_forall_sedges(e,M)|,
273 |CGAL_forall_sfaces(f,M)|, |CGAL_forall_sface_cycles_of(fc,F)|
274 where |M| is a sphere map and |F| is a sface.}*/
275
276 private:
277 std::string get_svertex_index(SVertex_const_handle) const;
278
279 }; // SM_const_decorator
280
281
282
283 template <typename SM_>
284 std::string SM_const_decorator<SM_>::
get_svertex_index(SVertex_const_handle v)285 get_svertex_index(SVertex_const_handle v) const
286 {
287 Object_index<SVertex_const_handle>
288 VI(svertices_begin(),svertices_end(),'v');
289 return VI(v);
290 }
291
292 template <typename SM_>
293 void SM_const_decorator<SM_>::
check_integrity_and_topological_planarity(bool faces)294 check_integrity_and_topological_planarity(bool faces) const
295 {
296 CGAL_NEF_TRACEN("check_integrity_and_topological_planarity:");
297 #ifdef CGAL_USE_TRACE
298 Object_index<SHalfedge_const_iterator>
299 EI(shalfedges_begin(),shalfedges_end(),'e');
300 #endif
301 SVertex_const_handle v;
302 int iso_vert_num=0;
303 /* check the source links of out edges and count isolated vertices */
304 CGAL_forall_svertices(v,*this) {
305 if ( is_isolated(v) ) {
306 if ( faces )
307 CGAL_assertion_msg(v->incident_sface() != SFace_const_handle(), get_svertex_index(v).c_str());
308 ++iso_vert_num;
309 } else {
310 CGAL_assertion_code(SHalfedge_const_handle e=first_out_edge(v));
311 CGAL_assertion_msg(e != SHalfedge_const_handle(), get_svertex_index(v).c_str());
312 CGAL_NEF_TRACEN(v->point()<<" "<<EI[first_out_edge(v)]);
313 CGAL_assertion_msg(e->source() == v, get_svertex_index(v).c_str());
314 }
315 }
316
317 /* check the bidirected links and the face pointer init */
318 SHalfedge_const_iterator e;
319 CGAL_forall_shalfedges(e,*this) {
320 CGAL_assertion( e->twin()->twin() == e );
321 CGAL_assertion( e->source() != SVertex_const_handle() );
322 CGAL_assertion( e->snext() != SHalfedge_const_handle() );
323 CGAL_assertion( e->snext()->sprev() == e );
324 CGAL_assertion( e->target() == e->snext()->source() );
325 CGAL_assertion( e->sprev() != SHalfedge_const_handle() );
326 CGAL_assertion( e->sprev()->snext() == e );
327 CGAL_assertion( e->sprev()->twin()->source() == e->source() );
328 if ( !faces ) continue;
329 CGAL_assertion( e->incident_sface() != SFace_const_handle() );
330 CGAL_assertion( e->snext()->incident_sface() == e->incident_sface() );
331 CGAL_assertion( e->sprev()->incident_sface() == e->incident_sface() );
332 }
333
334 int fc_num(0),iv_num(0);
335 SFace_const_iterator f;
336 SFace_cycle_const_iterator fci;
337 CGAL_forall_sfaces(f,*this) {
338 CGAL_forall_sface_cycles_of(fci,f) {
339 if ( fci.is_shalfedge() ) {
340 CGAL_assertion( SHalfedge_const_handle(fci)->incident_sface() == f );
341 ++fc_num;
342 } else if ( fci.is_svertex() ) {
343 CGAL_assertion( SVertex_const_handle(fci)->incident_sface() == f );
344 ++iv_num;
345 } else if( fci.is_shalfloop() ) {
346 CGAL_assertion( SHalfloop_const_handle(fci)->incident_sface() == f );
347 ++fc_num;
348 } else CGAL_error_msg("damn generic handle.");
349 }
350 }
351
352 CGAL_assertion_code(std::size_t v_num = number_of_svertices() -
353 iso_vert_num +
354 number_of_shalfloops());
355 CGAL_assertion_code(std::size_t e_num = number_of_sedges() +
356 number_of_shalfloops());
357 CGAL_assertion_code(std::size_t c_num = number_of_connected_components() -
358 iso_vert_num
359 + number_of_sloops());
360 CGAL_assertion_code(std::size_t f_num = number_of_sface_cycles() - c_num + 1);
361 CGAL_assertion_code(CGAL_NEF_TRACEV(fc_num));
362 CGAL_assertion_code(CGAL_NEF_TRACEV(iv_num));
363 CGAL_assertion_code(CGAL_NEF_TRACEV(iso_vert_num));
364 CGAL_assertion_code(CGAL_NEF_TRACEV(v_num));
365 CGAL_assertion_code(CGAL_NEF_TRACEV(e_num));
366 CGAL_assertion_code(CGAL_NEF_TRACEV(c_num));
367 CGAL_assertion_code(CGAL_NEF_TRACEV(f_num));
368 /* this means all face cycles and all isolated vertices are
369 indeed referenced from a face */
370 /* every isolated vertex increases the component count
371 one face cycle per component is redundent except one
372 finally check the Euler formula: */
373 CGAL_assertion( v_num - e_num + f_num == 1 + c_num );
374 }
375
376 template <typename SM_>
377 typename SM_const_decorator<SM_>::Size_type
378 SM_const_decorator<SM_>::
number_of_sface_cycles()379 number_of_sface_cycles() const
380 {
381 unsigned int fc_num=0;
382 CGAL::Unique_hash_map<SHalfedge_const_handle,bool> visited;
383 SHalfedge_const_iterator e;
384 CGAL_forall_shalfedges(e,*this) {
385 if (visited[e]) continue;
386 SHalfedge_around_sface_const_circulator hfc(e), hend(hfc);
387 CGAL_For_all(hfc,hend) visited[hfc]=true;
388 ++fc_num;
389 }
390 if ( has_shalfloop() ) fc_num += 2;
391 return fc_num;
392 }
393
394 template <typename SM_>
395 typename SM_const_decorator<SM_>::Size_type
396 SM_const_decorator<SM_>::
number_of_connected_components()397 number_of_connected_components() const
398 {
399 int comp_num=0;
400 CGAL::Unique_hash_map<SVertex_const_iterator,bool> visited(false);
401 SVertex_const_iterator v;
402 CGAL_forall_svertices(v,*this) {
403 if (visited[v]) continue;
404 std::list<SVertex_const_iterator> L;
405 L.push_back(v); visited[v]=true;
406 /* we keep the invariant that all nodes which have been stacked
407 are marked visited */
408 while (!L.empty()) {
409 SVertex_const_iterator vc = L.front(); L.pop_front();
410 if ( is_isolated(vc) ) continue;
411 SHalfedge_around_svertex_const_circulator
412 havc(first_out_edge(vc)), hend(havc);
413 CGAL_For_all(havc,hend) {
414 if (!visited[havc->target()]) {
415 L.push_back(havc->target()); visited[havc->target()]=true;
416 }
417 }
418 }
419 ++comp_num;
420 }
421 return comp_num;
422 }
423
424 } //namespace CGAL
425 #endif // CGAL_SM_CONST_DECORATOR_H
426