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_decorator.h $
7 // $Id: SM_decorator.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : 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_DECORATOR_H
17 #define CGAL_SM_DECORATOR_H
18
19 #include <CGAL/license/Nef_S2.h>
20
21
22 #include <CGAL/basic.h>
23 #include <CGAL/Nef_S2/SM_const_decorator.h>
24
25 #undef CGAL_NEF_DEBUG
26 #define CGAL_NEF_DEBUG 23
27 #include <CGAL/Nef_2/debug.h>
28 #include <CGAL/Nef_S2/SM_decorator_traits.h>
29 #include <CGAL/Nef_S2/Sphere_map.h>
30 #include <CGAL/Nef_S2/Normalizing.h>
31 #include <CGAL/Unique_hash_map.h>
32 #include <CGAL/IO/Verbose_ostream.h>
33 #ifndef CGAL_I_DO_WANT_TO_USE_GENINFO
34 #include <boost/any.hpp>
35 #endif
36
37 namespace CGAL {
38
39 /*{\Moptions print_title=yes }*/
40 /*{\Moptions outfile=SM_decorator.man }*/
41 /*{\Manpage {SM_decorator}{Sphere_map}
42 {Topological sphere map decorator}{D}}*/
43
44 template <typename Map_>
45 class SM_decorator
46 {
47 public:
48 typedef Map_ Map;
49 typedef Map_ Sphere_map;
50 typedef SM_decorator<Map> Self;
51 typedef SM_decorator_traits<Map> Decorator_traits;
52 /*{\Mdefinition ...}*/
53
54 /*{\Mtypes 5}*/
55
56 typedef CGAL::SM_const_decorator<Map> SM_const_decorator;
57
58 typedef typename Map::Sphere_kernel Sphere_kernel;
59 /*{\Mtypemember spherical geometry.}*/
60
61 typedef typename Map::Sphere_point Sphere_point;
62 /*{\Mtypemember embedding vertices.}*/
63
64 typedef typename Map::Sphere_segment Sphere_segment;
65 /*{\Mtypemember embedding edges.}*/
66
67 typedef typename Map::Sphere_circle Sphere_circle;
68 /*{\Mtypemember embedding loops.}*/
69
70 typedef typename Map::Sphere_direction Sphere_direction;
71 /*{\Mtypemember embedding directions.}*/
72
73 typedef typename Map::Mark Mark;
74 /*{\Mtypemember attributes of objects (vertices, edges, faces).}*/
75
76 typedef size_t Size_type;
77 /*{\Mtypemember size type.}*/
78
79 enum { BEFORE = -1, AFTER = 1 };
80 /*{\Menum insertion order labels.}*/
81
82 typedef typename Sphere_kernel::Aff_transformation_3 Aff_transformation_3;
83
84 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
85 typedef void* GenPtr;
86 #else
87 typedef boost::any GenPtr;
88 #endif
89 typedef typename Map::SVertex SVertex;
90 typedef typename Map::SVertex_handle SVertex_handle;
91 typedef typename Map::SVertex_iterator SVertex_iterator;
92 typedef typename Map::SVertex_const_handle SVertex_const_handle;
93 typedef typename Map::SVertex_const_iterator SVertex_const_iterator;
94 typedef typename Map::SHalfedge SHalfedge;
95 typedef typename Map::SHalfedge_handle SHalfedge_handle;
96 typedef typename Map::SHalfedge_iterator SHalfedge_iterator;
97 typedef typename Map::SHalfedge_const_handle SHalfedge_const_handle;
98 typedef typename Map::SHalfedge_const_iterator SHalfedge_const_iterator;
99 typedef typename Map::SFace SFace;
100 typedef typename Map::SFace_handle SFace_handle;
101 typedef typename Map::SFace_iterator SFace_iterator;
102 typedef typename Map::SFace_const_handle SFace_const_handle;
103 typedef typename Map::SFace_const_iterator SFace_const_iterator;
104 typedef typename Map::SHalfloop SHalfloop;
105 typedef typename Map::SHalfloop_handle SHalfloop_handle;
106 typedef typename Map::SHalfloop_iterator SHalfloop_iterator;
107 typedef typename Map::SHalfloop_const_handle SHalfloop_const_handle;
108 typedef typename Map::SHalfloop_const_iterator SHalfloop_const_iterator;
109 typedef typename Map::Object_handle Object_handle;
110 typedef typename Map::SHalfedge_around_svertex_circulator
111 SHalfedge_around_svertex_circulator;
112 typedef typename Map::SHalfedge_around_sface_circulator
113 SHalfedge_around_sface_circulator;
114 typedef typename Map::SFace_cycle_iterator SFace_cycle_iterator;
115
116 /*{\Mtypemember iterating all face cycles of an face |f|.
117 The iterator has method |bool is_svertex()|, |bool is_shalfedge()|,
118 |bool is_shalfloop()|, and can be converted to the corresponding
119 handles |SVertex_handle|, |SHalfedge_handle|, or
120 |SHalfloop_handle|.}*/
121
122 protected:
123 // don't change this into a shared_ptr even if it seems sensible.
124 // minkowski_sum_3 already has a fix in place that deletes the
125 // object psm_ points to.
126 Map* psm_;
127
128 public:
129 /*{\Mcreation 3}*/
SM_decorator()130 SM_decorator() : psm_(0) {}
SM_decorator(const Self & D)131 SM_decorator(const Self& D) : psm_(D.psm_) {}
132 Self& operator=(const Self& D) { psm_=D.psm_; return *this; }
133
SM_decorator(Map * M)134 SM_decorator(Map* M) : psm_(M) {}
135
136 /*{\Moperations 4 4}*/
137
sphere_map()138 Map* sphere_map() const { return psm_; }
139
map()140 Map* map() { return psm_; }
map()141 const Map* map() const { return psm_; }
142
is_isolated(SVertex_const_handle v)143 bool is_isolated(SVertex_const_handle v) const
144 { return (v->out_sedge() == SHalfedge_handle()); }
145
is_isolated(SVertex_handle v)146 bool is_isolated(SVertex_handle v) const
147 /*{\Mop returns |true| when |v| is linked to the interior of a face.}*/
148 { return (v->out_sedge() == SHalfedge_handle()); }
149
first_out_edge(SVertex_const_handle v)150 SHalfedge_const_handle first_out_edge(SVertex_const_handle v) const
151 { return v->out_sedge(); }
last_out_edge(SVertex_const_handle v)152 SHalfedge_const_handle last_out_edge(SVertex_const_handle v) const
153 { return cap(v->out_sedge()); }
154
first_out_edge(SVertex_handle v)155 SHalfedge_handle first_out_edge(SVertex_handle v) const
156 /*{\Mop returns one edge with source |v|. It's the starting point for
157 the circular iteration over the edges with source |v|.
158 \precond |!is_isolated(v)|.}*/
159 { return v->out_sedge(); }
160
last_out_edge(SVertex_handle v)161 SHalfedge_handle last_out_edge(SVertex_handle v) const
162 /*{\Mop returns one edge with source |v|. \precond |!is_isolated(v)|.}*/
163 { return cap(v->out_sedge()); }
164
cyclic_adj_succ(SHalfedge_const_handle e)165 SHalfedge_const_handle cyclic_adj_succ(SHalfedge_const_handle e) const
166 { return e->sprev()->twin(); }
cyclic_adj_pred(SHalfedge_const_handle e)167 SHalfedge_const_handle cyclic_adj_pred(SHalfedge_const_handle e) const
168 { return e->twin()->snext(); }
169
cyclic_adj_succ(SHalfedge_handle e)170 SHalfedge_handle cyclic_adj_succ(SHalfedge_handle e) const
171 /*{\Mop returns the edge after |e| in the cyclic ordered adjacency list of
172 |e->source()|.}*/
173 { return e->sprev()->twin(); }
174
cyclic_adj_pred(SHalfedge_handle e)175 SHalfedge_handle cyclic_adj_pred(SHalfedge_handle e) const
176 /*{\Mop returns the edge before |e| in the cyclic ordered adjacency list of
177 |e->source()|.}*/
178 { return e->twin()->snext(); }
179
has_shalfloop()180 bool has_shalfloop() const
181 /*{\Mop returns true iff there is a loop.}*/
182 { return psm_->has_shalfloop(); }
183
184 /*{\Mtext \headerline{Iteration} \setopdims{3.3cm}{0cm}}*/
185
svertices_begin()186 SVertex_iterator svertices_begin() const
187 { return psm_->svertices_begin(); }
svertices_end()188 SVertex_iterator svertices_end() const
189 { return psm_->svertices_end(); }
shalfedges_begin()190 SHalfedge_iterator shalfedges_begin() const
191 { return psm_->shalfedges_begin(); }
shalfedges_end()192 SHalfedge_iterator shalfedges_end() const
193 { return psm_->shalfedges_end(); }
sfaces_begin()194 SFace_iterator sfaces_begin() const
195 { return psm_->sfaces_begin(); }
sfaces_end()196 SFace_iterator sfaces_end() const
197 { return psm_->sfaces_end(); }
shalfloops_begin()198 SHalfloop_iterator shalfloops_begin() const
199 { return psm_->shalfloops_begin(); }
shalfloops_end()200 SHalfloop_iterator shalfloops_end() const
201 { return psm_->shalfloops_end(); }
202
shalfloop()203 SHalfloop_handle& shalfloop()
204 { return psm_->shalfloop(); }
shalfloop()205 SHalfloop_const_handle shalfloop() const
206 { return psm_->shalfloop(); }
207
number_of_svertices()208 Size_type number_of_svertices() const
209 /*{\Mop returns the number of vertices.}*/
210 { return psm_->number_of_svertices(); }
211
number_of_shalfedges()212 Size_type number_of_shalfedges() const
213 /*{\Mop returns the number of halfedges.}*/
214 { return psm_->number_of_shalfedges(); }
215
number_of_sedges()216 Size_type number_of_sedges() const
217 /*{\Mop returns the number of edges.}*/
218 { return number_of_shalfedges()/2; }
219
number_of_shalfloops()220 Size_type number_of_shalfloops() const
221 /*{\Mop returns the number of halfloops.}*/
222 { return psm_->number_of_shalfloops(); }
223
number_of_sloops()224 Size_type number_of_sloops() const
225 /*{\Mop returns the number of loops.}*/
226 { return psm_->number_of_shalfloops()/2; }
227
number_of_sfaces()228 Size_type number_of_sfaces() const
229 /*{\Mop returns the number of faces.}*/
230 { return psm_->number_of_sfaces(); }
231
sface_cycles_begin(SFace_handle f)232 SFace_cycle_iterator sface_cycles_begin(SFace_handle f) const
233 /*{\Mop returns an iterator for all bounding face cycles of |f|.
234 The iterator is is convertable to |SVertex_handle|,
235 |SHalfloop_handle|, or |SHalfedge_handle|.}*/
236 { return f->boundary_entry_objects().begin(); }
237
sface_cycles_end(SFace_handle f)238 SFace_cycle_iterator sface_cycles_end(SFace_handle f) const
239 /*{\Mop returns the past the end iterator of |f|.}*/
240 { return f->boundary_entry_objects_.end(); }
241
242 SHalfedge_around_svertex_circulator
out_edges(SVertex_handle v)243 out_edges(SVertex_handle v) const
244 /*{\Mop returns a circulator for the cyclic adjacency list of |v|.
245 \precond the adjacency list is not empty.}*/
246 { return SHalfedge_around_svertex_circulator(first_out_edge(v)); }
247
248 /*{\Mtext \headerline{Update Operations}}*/
249
clear()250 void clear() const
251 /*{\Mop reintializes |P| to the empty map.}*/
252 { psm_->clear(); }
253
is_closed_at_source(SHalfedge_handle e)254 bool is_closed_at_source(SHalfedge_handle e) const
255 /*{\Mop returns |true| when |e->sprev() == e->twin()|.}*/
256 { return e->sprev() == e->twin(); }
257
is_closed_at_target(SHalfedge_handle e)258 bool is_closed_at_target(SHalfedge_handle e) const
259 /*{\Mop returns |true| when |e->snext() == e->twin()|.}*/
260 { return e->snext() == e->twin(); }
261
cas(SHalfedge_handle e)262 SHalfedge_handle cas(SHalfedge_handle e) const
263 { return cyclic_adj_succ(e); }
cap(SHalfedge_handle e)264 SHalfedge_handle cap(SHalfedge_handle e) const
265 { return cyclic_adj_pred(e); }
266
267 template <typename H>
make_twins(H h1,H h2)268 void make_twins(H h1, H h2) const
269 { h1->twin() = h2; h2->twin() = h1; }
270
271 SVertex_handle new_svertex(const Sphere_point& p = Sphere_point())
272 /*{\Mop creates a new vertex.}*/
273 { return map()->new_svertex(p); }
274
new_shalfedge_pair()275 SHalfedge_handle new_shalfedge_pair() {
276 /*{\Xop creates a new edge pair. No connectivity is provided.}*/
277 return map()->new_shalfedge_pair();
278 }
279
new_shalfloop_pair()280 SHalfloop_handle new_shalfloop_pair()
281 /*{\Mop creates a new loop pair.
282 \precond No sloop pair exists in the local graph.}*/
283 { CGAL_assertion(!has_shalfloop());
284 return map()->new_shalfloop_pair();
285 }
286
new_sface()287 SFace_handle new_sface()
288 /*{\Mop creates a new face.}*/
289 { return map()->new_sface(); }
290
delete_vertex_only(SVertex_handle v)291 void delete_vertex_only(SVertex_handle v)
292 /*{\Mop deletes |v| without any connectivity update.}*/
293 { map()->delete_svertex(v); }
294
delete_edge_pair_only(SHalfedge_handle e)295 void delete_edge_pair_only(SHalfedge_handle e)
296 /*{\Mop deletes |e| and its twin without any connectivity update.}*/
297 { map()->delete_shalfedge_pair(e); }
298
delete_halfedge_only(SHalfedge_handle e)299 void delete_halfedge_only(SHalfedge_handle e)
300 /*{\Mop deletes |e| without its twin and without any connectivity update.}*/
301 { map()->delete_shalfedge(e); }
302
delete_face_only(SFace_handle f)303 void delete_face_only(SFace_handle f)
304 /*{\Mop deletes |f| without any connectivity update.}*/
305 { map()->delete_sface(f); }
306
delete_loop_only()307 void delete_loop_only()
308 /*{\Mop deletes the loop and its twin without any connectivity update.}*/
309 { map()->delete_shalfloop_pair(); }
310
311 template <typename H>
is_sm_boundary_object(H h)312 bool is_sm_boundary_object(H h) const
313 { return map()->is_sm_boundary_object(h); }
314
315 template <typename H>
store_sm_boundary_object(H h,SFace_handle f)316 void store_sm_boundary_object(H h, SFace_handle f) {
317 CGAL_assertion(!map()->is_sm_boundary_object(h));
318 f->boundary_entry_objects().push_back(make_object(h));
319 map()->store_sm_boundary_item(h, --(f->sface_cycles_end()));
320 }
321
322 template <typename H>
undo_sm_boundary_object(H h,SFace_handle f)323 void undo_sm_boundary_object(H h, SFace_handle f)
324 { CGAL_assertion(map()->is_sm_boundary_object(h));
325 SFace_cycle_iterator it = map()->sm_boundary_item(h);
326 map()->undef_sm_boundary_item(h);
327 f->boundary_entry_objects().erase(it);
328 }
329
link_as_face_cycle(SHalfedge_handle e,SFace_handle f)330 void link_as_face_cycle(SHalfedge_handle e, SFace_handle f)
331 /*{\Mop creates a new face cycle of |f| and
332 makes |e| the entry point of it.}*/
333 {
334 SHalfedge_around_sface_circulator hfc(e), hend(hfc);
335 CGAL_For_all(hfc,hend) hfc->incident_sface() = f;
336 store_sm_boundary_object(e,f);
337 }
338
link_as_loop(SHalfloop_handle l,SFace_handle f)339 void link_as_loop(SHalfloop_handle l, SFace_handle f)
340 /*{\Mop creates a new trivial face cycle of |f| and
341 makes |l| the singular object of it.}*/
342 { store_sm_boundary_object(l,f); l->incident_sface() = f; }
343
link_as_isolated_vertex(SVertex_handle v,SFace_handle f)344 void link_as_isolated_vertex(SVertex_handle v, SFace_handle f)
345 /*{\Mop creates a new trivial face cycle of |f|.
346 (makes |v| an isolated vertex within |f|).}*/
347 { store_sm_boundary_object(v,f); v->incident_sface() = f; }
348
unlink_as_face_cycle(SHalfedge_handle e)349 void unlink_as_face_cycle(SHalfedge_handle e)
350 /*{\Mop removes the face cycle defined by |e| from |e->incident_sface()|.
351 Does not update the face links of the corresponding face cycle
352 edges. \precond |e| is the entry object of the face cycle.}*/
353 { undo_sm_boundary_object(e,e->incident_sface()); }
354
unlink_as_loop(SHalfloop_handle l)355 void unlink_as_loop(SHalfloop_handle l)
356 /*{\Mop removes the trivial face cycle defined by |l| from
357 |l->incident_sface()|. Does not update |l|'s face link.}*/
358 { undo_sm_boundary_object(l,l->incident_sface()); }
359
unlink_as_isolated_vertex(SVertex_handle v)360 void unlink_as_isolated_vertex(SVertex_handle v)
361 /*{\Mop removes the trivial face cycle defined by |v| from
362 |v->incident_sface()|. Does not update |v|'s face link.
363 \precond |v| is a trivial face cycle of |v->incident_sface()|.}*/
364 { undo_sm_boundary_object(v,v->incident_sface()); }
365
clear_face_cycle_entries(SFace_handle f)366 void clear_face_cycle_entries(SFace_handle f)
367 { map()->reset_sm_object_list(f->boundary_entry_objects());
368 // removes entries of list and the hashed membership
369 }
370
new_shalfedge_pair(SVertex_handle v1,SVertex_handle v2)371 SHalfedge_handle new_shalfedge_pair(SVertex_handle v1,
372 SVertex_handle v2)
373 /*{\Mop creates a new pair of edges |(e1,e2)| representing |(v1,v2)|
374 by appending the |ei| to |A(vi)| $(i=1,2)$.}*/
375 { SHalfedge_handle e1 = new_shalfedge_pair();
376 SHalfedge_handle e2 = e1->twin();
377 if (!is_isolated(v1))
378 set_adjacency_at_source_between(cap(first_out_edge(v1)),e1,
379 first_out_edge(v1));
380 else
381 close_tip_at_source(e1,v1);
382 if (!is_isolated(v2))
383 set_adjacency_at_source_between(cap(first_out_edge(v2)),e2,
384 first_out_edge(v2));
385 else
386 close_tip_at_source(e2,v2);
387 return e1;
388 }
389
390
391 SHalfedge_handle new_shalfedge_pair(SHalfedge_handle e1,
392 SHalfedge_handle e2,
393 int pos1 = AFTER, int pos2 = AFTER)
394 /*{\Mop creates a new pair of edges |(es1,es2)| representing the uedge
395 |\{e1->source(),e2->source()\}| by inserting the |esi| before or after |ei|
396 into the cyclic adjacency list of |ei->source()| depending on |posi|
397 $(i=1,2)$ from |\Mname::BEFORE|, |\Mname::AFTER|.}*/
398 {
399 SHalfedge_handle er = new_shalfedge_pair();
400 SHalfedge_handle ero = er->twin();
401 if (pos1 < 0) { // before e1
402 set_adjacency_at_source_between(cap(e1),er,e1);
403 if ( e1 == first_out_edge(e1->source()) )
404 set_first_out_edge(e1->source(),er);
405 } else { // after e1
406 set_adjacency_at_source_between(e1,er,cas(e1));
407 }
408 if (pos2 < 0) { // before e2
409 set_adjacency_at_source_between(cap(e2),ero,e2);
410 if ( e2 == first_out_edge(e2->source()) )
411 set_first_out_edge(e2->source(),ero);
412 } else { // after e2
413 set_adjacency_at_source_between(e2,ero,cas(e2));
414 }
415 return er;
416 }
417
418 SHalfedge_handle new_shalfedge_pair(SHalfedge_handle e, SVertex_handle v,
419 int pos = AFTER)
420 /*{\Mop creates a new pair of edges |(e1,e2)| representing the uedge
421 |\{e->source(),v\}| by inserting |e1| before or after |e| into cyclic
422 adjacency list of |e->source()| depending on |pos| from |\Mname::BEFORE|,
423 |\Mname::AFTER| and appending |e2| at |A(v)|.}*/
424 {
425 SHalfedge_handle e_new = new_shalfedge_pair();
426 SHalfedge_handle e_opp = e_new->twin();
427 if (pos < 0) { // before e
428 set_adjacency_at_source_between(cap(e),e_new,e);
429 if ( e == first_out_edge(e->source()) )
430 set_first_out_edge(e->source(),e_new);
431 } else // after e
432 set_adjacency_at_source_between(e,e_new,cas(e));
433
434 if (!is_isolated(v)) {
435 SHalfedge_handle e_first = first_out_edge(v);
436 set_adjacency_at_source_between(cap(e_first),e_opp,e_first);
437 } else
438 close_tip_at_source(e_opp,v);
439 return e_new;
440 }
441
442
443 SHalfedge_handle new_shalfedge_pair(SVertex_handle v, SHalfedge_handle e,
444 int pos = AFTER)
445 /*{\Mop symmetric to the previous one.}*/
446 { return new_shalfedge_pair(e,v,pos)->twin(); }
447
delete_edge_pair(SHalfedge_handle e)448 void delete_edge_pair(SHalfedge_handle e)
449 /*{\Mop deletes |e| and its twin and maintains the adjacency at its source
450 and its target.}*/
451 { remove_from_adj_list_at_source(e);
452 remove_from_adj_list_at_source(e->twin());
453 delete_edge_pair_only(e);
454 }
455
split_at(SHalfedge_handle e,Sphere_point sp)456 SHalfedge_handle split_at(SHalfedge_handle e, Sphere_point sp)
457 {
458 CGAL_assertion(sp != e->source()->point());
459 CGAL_assertion(sp != e->twin()->source()->point());
460 CGAL_assertion(Sphere_segment(e->source()->point(),
461 e->twin()->source()->point(),
462 e->circle()).has_on(sp));
463 SVertex_handle v_new = new_svertex(sp);
464 v_new->mark() = e->mark();
465 return split_at(e, v_new);
466 }
467
split_at(SHalfedge_handle e,SVertex_handle v)468 SHalfedge_handle split_at(SHalfedge_handle e, SVertex_handle v)
469 {
470 CGAL_assertion(v->point() != e->source()->point());
471 CGAL_assertion(v->point() != e->twin()->source()->point());
472 CGAL_assertion(Sphere_segment(e->source()->point(),
473 e->twin()->source()->point(),
474 e->circle()).has_on(v->point()));
475
476 SHalfedge_handle e_new = new_shalfedge_pair(v, e->twin());
477 e_new->mark() = e_new->twin()->mark() = e->mark();
478 e_new->circle() = e->circle();
479 e_new->twin()->circle() = e->twin()->circle();
480 if(e->twin()->source()->out_sedge() == e->twin())
481 e->twin()->source()->out_sedge() = e_new->twin();
482 e->twin()->source() = v;
483 e->snext()->sprev() = e_new;
484 e_new->snext() = e->snext();
485 e_new->sprev() = e;
486 e->snext() = e_new;
487 e_new->twin()->snext() = e->twin();
488 e->twin()->sprev() = e_new->twin();
489 e_new->incident_sface() = e->incident_sface();
490 e_new->twin()->incident_sface() = e->twin()->incident_sface();
491 return e_new;
492 }
493
delete_vertex(SVertex_handle v)494 void delete_vertex(SVertex_handle v)
495 /*{\Mop deletes |v| and all outgoing edges |A(v)| as well as their twins.
496 Updates the adjacency at the targets of the edges in |A(v)|.}*/
497 {
498 if (!is_isolated(v)) {
499 SHalfedge_handle e = first_out_edge(v);
500 while ( e != cap(e) )
501 delete_edge_pair(cap(e));
502 delete_edge_pair(e);
503 }
504 delete_vertex_only(v);
505 }
506
delete_face(SFace_handle f)507 void delete_face(SFace_handle f)
508 /*{\Mop deletes the face |f| without consideration of topological
509 linkage.}*/
510 { clear_face_cycle_entries(f); delete_face_only(f); }
511
has_outdeg_two(SVertex_handle v)512 bool has_outdeg_two(SVertex_handle v) const
513 /*{\Mop return true when |v| has outdegree two.}*/
514 // does this work for looping edges?
515 { if (is_isolated(v)) return false;
516 SHalfedge_handle e1 = first_out_edge(v);
517 SHalfedge_handle e2 = last_out_edge(v);
518 return (e1!=e2 && e2==cas(e1));
519 }
520
link_as_prev_next_pair(SHalfedge_handle e1,SHalfedge_handle e2)521 void link_as_prev_next_pair(SHalfedge_handle e1, SHalfedge_handle e2)
522 /*{\Xop makes |e1| and |e2| adjacent in the face cycle
523 $\ldots-|e1-e2|-\ldots$.
524 Afterwards |e1 = e2->sprev()| and |e2 = e1->snext()|.}*/
525 { e1->snext() = e2; e2->sprev() = e1; }
526
merge_edge_pairs_at_target(SHalfedge_handle e)527 void merge_edge_pairs_at_target(SHalfedge_handle e)
528 /*{\Mop merges the edge pairs at |v = e->target()|. |e| and |twin(e)|
529 are preserved, |e->snext()|, |twin(e->snext())| and |v| are deleted
530 in the merger. \precond |v| has outdegree two. The adjacency at
531 |e->source()| and |target(e->snext())| is kept consistent.
532 If |e->snext()| was entry point of |e->incident_sface()| then |e| takes this role.
533 The same holds for |twin(e->snext())| and |face(twin(e))|.}*/
534 {
535 CGAL_NEF_TRACEN("merge_edge_pairs_at_target "<<PH(e));
536 SHalfedge_handle en = e->snext(), eno = en->twin(), enn, enno,
537 eo = e->twin() ;
538 if ( is_closed_at_target(en) ) { enn = eo; enno=e; }
539 else { enn = en->snext(), enno = eno->sprev(); }
540 SVertex_handle v = e->target(), vn = en->target();
541 CGAL_assertion(has_outdeg_two(v));
542 SFace_handle f1 = en->incident_sface(), f2 = eno->incident_sface();
543 // transfer the opposite face cycles e-en-enn to e-enn
544 if ( enn != eno ) {
545 link_as_prev_next_pair(e,enn);
546 link_as_prev_next_pair(enno,eo);
547 } else {
548 link_as_prev_next_pair(e,eo);
549 }
550 // set vertex of e and deal with vertex-halfedge incidence
551 eo->source() = vn;
552
553 if ( first_out_edge(vn) == eno ) set_first_out_edge(vn,eo);
554 if ( is_sm_boundary_object(en) )
555 { undo_sm_boundary_object(en,f1); store_sm_boundary_object(e,f1); }
556 if ( is_sm_boundary_object(eno) )
557 { undo_sm_boundary_object(eno,f2); store_sm_boundary_object(eo,f2); }
558 delete_vertex_only(v);
559 delete_edge_pair_only(en);
560 CGAL_NEF_TRACEN("END "<<PH(e->sprev())<<PH(e)<<PH(e->snext()));
561 }
562
convert_edge_to_loop(SHalfedge_handle e)563 void convert_edge_to_loop(SHalfedge_handle e)
564 /*{\Mop converts the edge at |v = e->target()| to the unique
565 loop |l| of |\Mvar|. |e|, |e->twin()| and |v| are deleted
566 in the conversion. \precond there was no loop in |\Mvar|.
567 As |e| was entry point of |e->incident_sface()| then |l| takes this role.}*/
568 { CGAL_NEF_TRACEN("convert_edge_to_loop "<<PH(e));
569 CGAL_assertion( e->source()==e->target() );
570 CGAL_assertion( !has_shalfloop() );
571 SHalfloop_handle l = new_shalfloop_pair();
572 SVertex_handle v = e->target();
573 SFace_handle f1 = e->incident_sface(), f2 = e->twin()->incident_sface();
574 if( is_sm_boundary_object(e)) {
575 CGAL_assertion( is_sm_boundary_object(e->twin()));
576 undo_sm_boundary_object(e,f1); undo_sm_boundary_object(e->twin(),f2);
577 }
578 link_as_loop(l,f1), link_as_loop(l->twin(),f2);
579 l->circle() = e->circle(); l->twin()->circle() = e->twin()->circle();
580 l->mark() = l->twin()->mark() = e->mark();
581 delete_vertex_only(v);
582 delete_edge_pair_only(e);
583 }
584
flip_diagonal(SHalfedge_handle e)585 void flip_diagonal(SHalfedge_handle e)
586 { SHalfedge_handle r = e->twin();
587 SHalfedge_handle en = e->snext(), enn= en->snext();
588 SHalfedge_handle rn = r->snext(), rnn= rn->snext();
589 CGAL_NEF_TRACEN(PH(e)<<PH(en)<<PH(enn));
590 CGAL_NEF_TRACEN(PH(r)<<PH(rn)<<PH(rnn));
591 CGAL_assertion( enn->snext()==e && rnn->snext()==r );
592 remove_from_adj_list_at_source(e);
593 remove_from_adj_list_at_source(r);
594 set_adjacency_at_source_between(enn,e,en->twin());
595 set_adjacency_at_source_between(rnn,r,rn->twin());
596 }
597
598
599 /*{\Mtext \headerline{Incomplete topological update primitives}}*/
600
601 SHalfedge_handle new_shalfedge_pair_at_source
602 (SHalfedge_handle e, int pos = AFTER) const
603 /*{\Xop creates a new pair of edges |(e1,e2)| representing |(e->source(),())|
604 by inserting |e1| before or after |e| into cyclic adjacency list of
605 |e->source()| depending on |pos| from |\Mname::BEFORE, \Mname::AFTER|.}*/
606 { SHalfedge_handle e_new = new_shalfedge_pair();
607 if (pos < 0) set_adjacency_at_source_between(cap(e),e_new,e);
608 else set_adjacency_at_source_between(e,e_new,cas(e));
609 return e_new;
610 }
611
612 SHalfedge_handle new_shalfedge_pair_at_source
613 (SVertex_handle v, int pos = AFTER)
614 /*{\Mop creates a new pair of edges |(e1,e2)| representing |(v,())|
615 by inserting |e1| at the beginning (BEFORE) or end (AFTER)
616 of adjacency list of |v|.}*/
617 { SHalfedge_handle e1 = new_shalfedge_pair();
618 if (!is_isolated(v)) {
619 SHalfedge_handle ef = first_out_edge(v);
620 if (pos < 0) { // before e1
621 set_adjacency_at_source_between(cap(ef),e1,ef);
622 set_first_out_edge(v,e1);
623 } else {
624 set_adjacency_at_source_between(cap(ef),e1,ef);
625 }
626 } else
627 close_tip_at_source(e1,v);
628 return e1;
629 }
630
delete_edge_pair_at_source(SHalfedge_handle e)631 void delete_edge_pair_at_source(SHalfedge_handle e)
632 /*{\Mop deletes |e| and its twin and maintains the adjacency at its
633 source.}*/
634 { remove_from_adj_list_at_source(e);
635 delete_edge_pair_only(e);
636 }
637
638 void link_as_target_and_append(SVertex_handle v, SHalfedge_handle e, int pos = AFTER)
639 /*{\Mop makes |v| the target of |e| appends |e->twin()| to the adjacency list
640 of |v|.}*/
641 { if (!is_isolated(v)) {
642 SHalfedge_handle ef = first_out_edge(v);
643 set_adjacency_at_source_between(cap(ef), e->twin(), ef);
644 if(pos<0)
645 set_first_out_edge(v,e->twin());
646 } else
647 close_tip_at_target(e,v);
648 }
649
link_as_source_of(SHalfedge_handle e,SVertex_handle v)650 void link_as_source_of(SHalfedge_handle e, SVertex_handle v) const
651 /*{\Mop makes |e->source() = v| and sets |e| as the first
652 out edge if |v| was isolated before.}*/
653 { e->source() = v;
654 if (v->out_sedge() == SHalfedge_handle()) v->out_sedge() = e; }
655
link_as_target_of(SHalfedge_handle e,SVertex_handle v)656 void link_as_target_of(SHalfedge_handle e, SVertex_handle v) const
657 /*{\Mop makes |e->target() = v| and sets |e| as the first
658 in edge if |v| was isolated before.}*/
659 { link_as_source_of(e->twin(),v); }
660
set_adjacency_at_source_between(SHalfedge_handle e,SHalfedge_handle en)661 void set_adjacency_at_source_between(SHalfedge_handle e, SHalfedge_handle en)
662 /*{\Mop makes |e| and |en| neigbors in the cyclic ordered adjacency list
663 around |v=e->source()|. \precond |e->source()==en->source()|.}*/
664 { CGAL_assertion(e->source()==en->source());
665 link_as_prev_next_pair(en->twin(),e);
666 }
667
set_adjacency_at_source_between(SHalfedge_handle e1,SHalfedge_handle e_between,SHalfedge_handle e2)668 void set_adjacency_at_source_between(SHalfedge_handle e1,
669 SHalfedge_handle e_between,
670 SHalfedge_handle e2)
671 /*{\Mop inserts |e_between| into the adjacency list around |e1->source()|
672 between |e1| and |e2| and makes |e1->source()| the source of |e_between|.
673 \precond |e1->source()==e2->source()|.}*/
674 {
675 e_between->source() = e1->source();
676 set_adjacency_at_source_between(e1,e_between);
677 set_adjacency_at_source_between(e_between,e2);
678 }
679
close_tip_at_source(SHalfedge_handle e,SVertex_handle v)680 void close_tip_at_source(SHalfedge_handle e, SVertex_handle v)
681 /*{\Mop sets |v| as source of |e| and closes the tip by setting the
682 corresponding pointers such that |prev(e) == e->twin()| and
683 |next(e->twin()) == e|.}*/
684 { link_as_source_of(e,v);
685 link_as_prev_next_pair(e->twin(),e); }
686
close_tip_at_target(SHalfedge_handle e,SVertex_handle v)687 void close_tip_at_target(SHalfedge_handle e, SVertex_handle v)
688 /*{\Mop sets |v| as target of |e| and closes the tip by setting the
689 corresponding pointers such that |prev(e->twin()) == e| and
690 |e->snext() == e->twin()|.}*/
691 { link_as_target_of(e,v);
692 link_as_prev_next_pair(e,e->twin()); }
693
694
remove_from_adj_list_at_source(SHalfedge_handle e)695 void remove_from_adj_list_at_source(SHalfedge_handle e)
696 /*{\Mop removes a halfedge pair |(e,e->twin()| from the adjacency list
697 of |e->source()|. Afterwards |next(prev(e))==next(e->twin())| and
698 |first_out_edge(e->source())| is valid if |degree(v->source())>1| before
699 the operation.}*/
700 {
701 SVertex_handle v = e->source();
702 if ( is_closed_at_source(e) ) { // last outgoing
703 v->out_sedge() = SHalfedge_handle();
704 } else {
705 if (e == first_out_edge(v)) v->out_sedge() = cap(e);
706 set_adjacency_at_source_between(cap(e),cas(e));
707 }
708 }
709
set_face(SHalfedge_handle e,SFace_handle f)710 void set_face(SHalfedge_handle e, SFace_handle f) const
711 { e->incident_sface() = f; }
set_face(SHalfloop_handle l,SFace_handle f)712 void set_face(SHalfloop_handle l, SFace_handle f) const
713 { l->incident_sface() = f; }
set_face(SVertex_handle v,SFace_handle f)714 void set_face(SVertex_handle v, SFace_handle f) const
715 { v->incident_sface() = f; }
set_first_out_edge(SVertex_handle v,SHalfedge_handle e)716 void set_first_out_edge(SVertex_handle v, SHalfedge_handle e) const
717 { v->out_sedge() = e; }
set_prev(SHalfedge_handle e,SHalfedge_handle ep)718 void set_prev(SHalfedge_handle e, SHalfedge_handle ep) const
719 { e->sprev() = ep; }
set_next(SHalfedge_handle e,SHalfedge_handle en)720 void set_next(SHalfedge_handle e, SHalfedge_handle en) const
721 { e->snext() = en; }
set_source(SHalfedge_handle e,SVertex_handle v)722 void set_source(SHalfedge_handle e, SVertex_handle v) const
723 { e->source() = v; }
724
725 /*{\Mtext \headerline{Associated Information}\restoreopdims}*/
726
set_marks_in_face_cycle(SHalfedge_handle e,Mark m)727 void set_marks_in_face_cycle(SHalfedge_handle e, Mark m) const
728 { SHalfedge_around_sface_circulator hfc(e), hend(hfc);
729 CGAL_For_all(hfc,hend) hfc->mark() = hfc->target()->mark() = m;
730 }
731
info(SVertex_handle v)732 GenPtr& info(SVertex_handle v) const
733 { return v->info(); }
info(SHalfedge_handle e)734 GenPtr& info(SHalfedge_handle e) const
735 { return e->info(); }
info(SFace_handle f)736 GenPtr& info(SFace_handle f) const
737 { return f->info(); }
738
info(SVertex_const_handle v)739 const GenPtr& info(SVertex_const_handle v) const
740 { return v->info(); }
info(SHalfedge_const_handle e)741 const GenPtr& info(SHalfedge_const_handle e) const
742 { return e->info(); }
info(SFace_const_handle f)743 const GenPtr& info(SFace_const_handle f) const
744 { return f->info(); }
745
746
747 /*{\Mtext \headerline{Iteration}}*/
748 /*{\Mtext The list of all objects can be accessed via iterator ranges.
749 For comfortable iteration we also provide iterations macros.
750 The iterator range access operations are of the following kind:\\
751 |SVertex_iterator svertices_begin()/svertices_end()|\\
752 |SHalfedge_iterator shalfedges_begin()/shalfedges_end()|\\
753 |SHalfedge_iterator sedges_begin()/sedges_end()|\\
754 |SFace_iterator sfaces_begin()/sfaces_end()|
755
756 The macros are then |CGAL_forall_svertices_of(v,V)|,
757 |CGAL_forall_shalfedges_of(e,V)|, |CGAL_forall_sedges_of(e,V)|,
758 |CGAL_forall_sfaces_of(f,V)|, |CGAL_forall_sface_cycles_of(fc,F)|.}*/
759
transform(const Aff_transformation_3 & linear)760 void transform( const Aff_transformation_3& linear) {
761 // CGAL_NEF_TRACEN("transform sphere map of vertex" << center_vertex()->point());
762 // The affine transformation is linear, i.e., no translation part.
763 CGAL_precondition( linear.hm(0,3) == 0 &&
764 linear.hm(1,3) == 0 &&
765 linear.hm(2,3) == 0);
766
767 // CGAL_NEF_TRACEN(linear);
768 for (SVertex_iterator i = svertices_begin(); i != svertices_end(); ++i)
769 i->point() = normalized(Sphere_point( i->point().transform( linear)));
770 for (SHalfedge_iterator i = shalfedges_begin(); i !=shalfedges_end(); ++i)
771 i->circle() = Sphere_circle( i->circle().transform( linear));
772 if ( has_shalfloop()) {
773 shalfloop()->circle() = Sphere_circle(shalfloop()->circle()
774 .transform( linear));
775 shalfloop()->twin()->circle()
776 = Sphere_circle(shalfloop()->twin()->circle().transform( linear));
777 }
778 }
779
extract_complement()780 void extract_complement() {
781
782 SVertex_handle sv;
783 CGAL_forall_svertices(sv,*this) sv->mark() = !sv->mark();
784 SHalfedge_handle she;
785 CGAL_forall_shalfedges(she,*this) she->mark() = !she->mark();
786 SHalfloop_handle shl;
787 if(has_shalfloop()) {
788 shl = shalfloop();
789 shl->mark() = shl->twin()->mark() = !shl->mark();
790 }
791 SFace_handle sf;
792 CGAL_forall_sfaces(sf,*this)
793 sf->mark() = !sf->mark();
794 }
795
extract_interior()796 void extract_interior() {
797
798 SVertex_handle sv;
799 CGAL_forall_svertices(sv,*this) sv->mark() = false;
800 SHalfedge_handle she;
801 CGAL_forall_shalfedges(she,*this) she->mark() = false;
802 SHalfloop_handle shl;
803 if(has_shalfloop()) {
804 shl = shalfloop();
805 shl->mark() = shl->twin()->mark() = false;
806 }
807 }
808
extract_boundary()809 void extract_boundary() {
810
811 SVertex_handle sv;
812 CGAL_forall_svertices(sv,*this) sv->mark() = true;
813 SHalfedge_handle she;
814 CGAL_forall_shalfedges(she,*this) she->mark() = true;
815 SHalfloop_handle shl;
816 if(has_shalfloop()) {
817 shl = shalfloop();
818 shl->mark() = shl->twin()->mark() = true;
819 }
820 SFace_handle sf;
821 CGAL_forall_sfaces(sf,*this) sf->mark() = false;
822 }
823
824 bool is_valid( Unique_hash_map<SVertex_handle,bool>& sv_hash,
825 Unique_hash_map<SHalfedge_handle,bool>& se_hash,
826 Unique_hash_map<SFace_handle,bool>& sf_hash,
827 bool verb = false, int level = 0) {
828
829 Verbose_ostream verr(verb);
830 verr << "begin CGAL::SNC_SM_decorator<...>::is_valid( verb=true, "
831 "level = " << level << "):" << std::endl;
832
833 bool valid = true;
834
835 std::size_t count = 0;
836 std::size_t max = 2 * number_of_svertices()
837 + 2 * number_of_shalfedges()
838 + number_of_sfaces()
839 + 2;
840
841 SVertex_handle sv;
842 int isolated_vertices_found = 0;
843 CGAL_forall_svertices(sv,*this) {
844 valid = valid && (!sv_hash[sv]);
845 sv_hash[sv] = true;
846 if(is_isolated(sv))
847 isolated_vertices_found++;
848 valid = valid && (++count <= max);
849 }
850
851 SHalfedge_iterator she;
852 CGAL_forall_shalfedges(she,*this) {
853 valid = valid && she->is_valid(verb, level);
854
855 valid = valid && (she->twin() != she);
856 valid = valid && (she->twin()->twin() == she);
857 valid = valid && (she->snext()->sprev() == she);
858 valid = valid && ((she->sprev() != she && she->snext() != she) ||
859 (she->sprev() == she && she->snext() == she));
860 valid = valid && (she->incident_sface() == she->snext()->incident_sface());
861 valid = valid && (she->incident_sface() == she->sprev()->incident_sface());
862
863 valid = valid && (!se_hash[she]);
864
865 // Plane_3 pl(point(she->source()),point(she->target()),Point_3(0,0,0));
866 // Sphere_point vct(pl.orthogonal_vector());
867 // valid = valid && (normalized(Sphere_point(she->circle().orthogonal_vector())) == normalized(vct) ||
868 // normalized(Sphere_point(she->circle().opposite().orthogonal_vector())) == normalized(vct));
869
870 se_hash[she] = true;
871 valid = valid && (++count <= max);
872 }
873
874 if(has_shalfloop()) {
875 SHalfloop_handle shl = shalfloop();
876 valid = valid && shl->is_valid();
877 valid = valid && shl->twin()->is_valid();
878 valid = valid && (shl->twin() != shl);
879 valid = valid && (shl->twin()->twin() == shl);
880 }
881
882 SFace_iterator sf;
883 SFace_cycle_iterator sfc;
884 int loop_entries_found = 0;
885 int edge_entries_found = 0;
886 int vertex_entries_found = 0;
887 CGAL_forall_sfaces(sf,*this) {
888 valid = valid && sf->is_valid(verb, level);
889 valid = valid && (!sf_hash[sf]);
890 sf_hash[sf] = true;
891
CGAL_forall_sface_cycles_of(sfc,sf)892 CGAL_forall_sface_cycles_of(sfc,sf) {
893 if (sfc.is_shalfloop())
894 loop_entries_found++;
895 else if(sfc.is_shalfedge())
896 edge_entries_found++;
897 else if(sfc.is_svertex())
898 vertex_entries_found++;
899 valid = valid && (++count <= max);
900 }
901
902 valid = valid && (++count <= max);
903 }
904
905 if(has_shalfloop())
906 valid = valid && (loop_entries_found == 2);
907 else
908 valid = valid && (loop_entries_found == 0);
909
910 if(number_of_shalfedges() > 0)
911 valid = valid && (edge_entries_found > 0);
912 else
913 valid = valid && (edge_entries_found == 0);
914
915 valid = valid && (vertex_entries_found == isolated_vertices_found);
916
917 verr << "end of CGAL::SNC_SM_decorator<...>::is_valid(): structure is "
918 << ( valid ? "valid." : "NOT VALID.") << std::endl;
919
920 return valid;
921 }
922
923 template <typename Selection>
change_marks(const Mark & m,const Selection & SP)924 void change_marks(const Mark& m, const Selection& SP) {
925
926 psm_->mark() = SP(m, psm_->mark());
927
928 SVertex_iterator v;
929 CGAL_forall_svertices(v,*this)
930 v->mark() = SP(m, v->mark());
931
932 SHalfedge_iterator e;
933 CGAL_forall_shalfedges(e,*this)
934 e->mark() = SP(m, e->mark());
935
936 SFace_iterator f;
937 CGAL_forall_sfaces(f,*this)
938 f->mark() = SP(m, f->mark());
939 }
940
941 template <typename Selection>
change_marks(const Selection & SP,const Mark & m)942 void change_marks(const Selection& SP, const Mark& m) {
943
944 psm_->mark() = SP(psm_->mark(), m);
945
946 SVertex_iterator v;
947 CGAL_forall_svertices(v,*this)
948 v->mark() = SP(v->mark(),m);
949
950 SHalfedge_iterator e;
951 CGAL_forall_shalfedges(e,*this)
952 e->mark() = SP(e->mark(),m);
953
954 SFace_iterator f;
955 CGAL_forall_sfaces(f,*this)
956 f->mark() = SP(f->mark(),m);
957 }
958
959 void check_integrity_and_topological_planarity(bool faces=true) const {
960 SM_const_decorator C(psm_);
961 C.check_integrity_and_topological_planarity(faces);
962 }
963
964 }; // SM_decorator
965
966
967 } //namespace CGAL
968 #endif // CGAL_SM_DECORATOR_H
969