1 // Copyright (c) 1997-2000 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_overlayer.h $
7 // $Id: SM_overlayer.h c586c3c 2020-11-18T08:56:02+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 // Peter Hachenberger <hachenberger@mpi-sb.mpg.de>
13
14 #ifndef CGAL_SM_OVERLAYER_H
15 #define CGAL_SM_OVERLAYER_H
16
17 #include <CGAL/license/Nef_S2.h>
18
19
20 #include <CGAL/basic.h>
21 #include <CGAL/Union_find.h>
22 #include <CGAL/Nef_2/Segment_overlay_traits.h>
23 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
24 #include <CGAL/Nef_2/geninfo.h>
25 #else
26 #include <boost/any.hpp>
27 #endif
28 #include <CGAL/Nef_S2/Sphere_geometry.h>
29 #include <CGAL/Nef_S2/SM_decorator.h>
30 #include <CGAL/Nef_S2/SM_const_decorator.h>
31 #include <CGAL/Nef_S2/SM_point_locator.h>
32 #include <CGAL/Nef_S2/SM_io_parser.h>
33 #include <CGAL/Nef_S2/ID_support_handler.h>
34 #undef CGAL_NEF_DEBUG
35 #define CGAL_NEF_DEBUG 131
36 #include <CGAL/Nef_2/debug.h>
37
38 #ifndef CGAL_USE_LEDA
39 #define LEDA_MEMORY(t)
40 #else
41 #include <LEDA/system/memory.h>
42 #endif
43
44 #include <CGAL/use.h>
45
46 namespace CGAL {
47
48 template <typename Decorator_, typename I>
49 struct SMO_from_segs {
50 typedef Decorator_ SM_decorator;
51 typedef typename SM_decorator::SVertex_handle Vertex_handle;
52 typedef typename SM_decorator::SHalfedge_handle Halfedge_handle;
53 typedef typename SM_decorator::Sphere_point Point;
54 typedef typename SM_decorator::Sphere_segment Segment;
55 typedef CGAL::Unique_hash_map<I,bool> Iterator_map;
56 SM_decorator G;
57 const Iterator_map& M;
SMO_from_segsSMO_from_segs58 SMO_from_segs(SM_decorator Gi, const Iterator_map& Mi) : G(Gi),M(Mi) {}
59
new_vertexSMO_from_segs60 Vertex_handle new_vertex(const Point& p)
61 { Vertex_handle v = G.new_svertex(p);
62 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
63 geninfo<Halfedge_handle>::create(G.info(v));
64 #else
65 G.info(v)=Halfedge_handle();
66 #endif
67 return v;
68 }
69
link_as_target_and_appendSMO_from_segs70 void link_as_target_and_append(Vertex_handle v, Halfedge_handle e)
71 { G.link_as_target_and_append(v,e); }
72
new_halfedge_pair_at_sourceSMO_from_segs73 Halfedge_handle new_halfedge_pair_at_source(Vertex_handle v)
74 { Halfedge_handle e =
75 G.new_shalfedge_pair_at_source(v,SM_decorator::BEFORE);
76 return e;
77 }
78
supporting_segmentSMO_from_segs79 void supporting_segment(Halfedge_handle e, I it) const
80 { if ( M[it] ) e->mark() = true; }
81
trivial_segmentSMO_from_segs82 void trivial_segment(Vertex_handle v, I it) const
83 { if ( M[it] ) v->mark() = true; }
84
starting_segmentSMO_from_segs85 void starting_segment(Vertex_handle v, I it) const
86 { if ( M[it] ) v->mark() = true; }
87
passing_segmentSMO_from_segs88 void passing_segment(Vertex_handle v, I it) const
89 { if ( M[it] ) v->mark() = true; }
90
ending_segmentSMO_from_segs91 void ending_segment(Vertex_handle v, I it) const
92 { if ( M[it] ) v->mark() = true; }
93
halfedge_belowSMO_from_segs94 void halfedge_below(Vertex_handle v, Halfedge_handle e) const
95 {
96 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
97 geninfo<Halfedge_handle>::access(G.info(v)) = e;
98 #else
99 G.info(v)=e;
100 #endif
101 }
102
halfedge_belowSMO_from_segs103 Halfedge_handle halfedge_below(Vertex_handle v) const
104 {
105 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
106 return geninfo<Halfedge_handle>::access(G.info(v));
107 #else
108 return
109 boost::any_cast<Halfedge_handle>( G.info(v) );
110 #endif
111 }
112
assert_equal_marksSMO_from_segs113 void assert_equal_marks(Vertex_handle v1, Vertex_handle v2) const
114 {
115 CGAL_USE(v1);
116 CGAL_USE(v2);
117 CGAL_assertion(v1->mark()==v2->mark());
118 }
119
discard_infoSMO_from_segs120 void discard_info(Vertex_handle v) const
121 {
122 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
123 geninfo<Halfedge_handle>::clear(G.info(v));
124 #else
125 G.info(v)=boost::any();
126 #endif
127 }
128
assert_equal_marksSMO_from_segs129 void assert_equal_marks(Halfedge_handle e1, Halfedge_handle e2) const
130 {
131 CGAL_USE(e1);
132 CGAL_USE(e2);
133 CGAL_assertion(e1->mark()==e2->mark());
134 }
135
discard_infoSMO_from_segs136 void discard_info(Halfedge_handle ) const {}
137
clear_temporary_vertex_infoSMO_from_segs138 void clear_temporary_vertex_info() const
139 { Vertex_handle v;
140 CGAL_forall_svertices(v,G)
141 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
142 geninfo<Halfedge_handle>::clear(G.info(v));
143 #else
144 G.info(v)=boost::any();
145 #endif
146
147 }
148
149
150 }; // SMO_from_segs
151
152
153 template <typename SM_overlayer, typename IT, typename INFO>
154 struct SMO_from_sm {
155 typedef typename SM_overlayer::SM_const_decorator SM_const_decorator;
156 typedef typename SM_overlayer::SVertex_handle Vertex_handle;
157 typedef typename SM_overlayer::SHalfedge_handle Halfedge_handle;
158 typedef typename SM_overlayer::Sphere_point Point;
159 typedef typename SM_overlayer::Sphere_segment Segment;
160
161 SM_overlayer G;
162 CGAL::Unique_hash_map<IT,INFO>& M;
SMO_from_smSMO_from_sm163 SMO_from_sm(SM_overlayer Gi,
164 SM_const_decorator* /* pGIi */,
165 CGAL::Unique_hash_map<IT,INFO>& Mi) :
166 G(Gi), M(Mi) {}
167
new_vertexSMO_from_sm168 Vertex_handle new_vertex(const Point& p)
169 { CGAL_NEF_TRACEN(" new vertex " << p);
170 Vertex_handle v = G.new_svertex(p);
171 G.assoc_info(v);
172 return v;
173 }
174
link_as_target_and_appendSMO_from_sm175 void link_as_target_and_append(Vertex_handle v, Halfedge_handle e)
176 { CGAL_NEF_TRACEN(" link as target and append "
177 << e->source()->point() << "->"
178 << v->point());
179 G.link_as_target_and_append(v,e); }
180
new_halfedge_pair_at_sourceSMO_from_sm181 Halfedge_handle new_halfedge_pair_at_source(Vertex_handle v)
182 { CGAL_NEF_TRACEN(" new halfedge pair at source " << v->point());
183 Halfedge_handle e =
184 G.new_shalfedge_pair_at_source(v,SM_overlayer::BEFORE);
185 G.assoc_info(e);
186 return e;
187 }
188
halfedge_belowSMO_from_sm189 void halfedge_below(Vertex_handle v, Halfedge_handle e) const
190 {
191 CGAL_NEF_TRACEN(" edge below " << v->point() << ":");
192 CGAL_NEF_TRACEN(&*e);
193 G.halfedge_below(v) = e;
194 }
195
supporting_segmentSMO_from_sm196 void supporting_segment(Halfedge_handle e, IT it) const
197 { INFO& si = M[it];
198 G.is_forward(e) = true;
199 if ( si._from == -1 ) return; // equatorial segment
200 G.supp_object(e,si._from) = si._o;
201 CGAL_NEF_TRACEN(" supporting segment "<<si._from<<":"<<*it);
202 }
203
trivial_segmentSMO_from_sm204 void trivial_segment(Vertex_handle v, IT it) const
205 { INFO& si = M[it];
206 CGAL_assertion( ! si._o.empty() );
207 typename SM_const_decorator::SHalfedge_const_handle se;
208 typename SM_const_decorator::SHalfloop_const_handle sl;
209 typename SM_const_decorator::SVertex_const_handle sv;
210 if(CGAL::assign(se, si._o)) {
211 if(se->source()->point() != v->point())
212 se = se->twin();
213 if(se->source()->point() != v->point())
214 G.supp_object(v,si._from) = si._o;
215 else
216 G.supp_object(v,si._from) = make_object(se->source());
217 } else if(CGAL::assign(sl, si._o)) {
218 G.supp_object(v,si._from) = si._o;
219 } else if(CGAL::assign(sv, si._o)) {
220 CGAL_assertion(sv->point() == v->point());
221 G.supp_object(v,si._from) = si._o;
222 } else
223 CGAL_error_msg( "wrong handle");
224
225 CGAL_NEF_TRACEN("trivial_segment " << si._from << ":" << v->point());
226 // debug();
227 }
228
starting_segmentSMO_from_sm229 void starting_segment(Vertex_handle v, IT it) const
230 { INFO& si = M[it];
231 if ( si._from == -1 ) return;
232 typename SM_const_decorator::SHalfedge_const_handle se;
233 typename SM_const_decorator::SHalfloop_const_handle sl;
234 if(CGAL::assign(se, si._o)) {
235 if(se->source()->point() != v->point()) {
236 se = se->twin();
237 if(se->source()->point() != v->point()) {
238 G.supp_object(v,si._from) = si._o;
239 return;
240 }
241 }
242 G.supp_object(v,si._from) = make_object(se->source());
243 CGAL_NEF_TRACEN("starting_segment " << si._from << ":"<<
244 v->point() << " " << se->source()->point());
245 } else if(CGAL::assign(sl, si._o)) {
246 G.supp_object(v,si._from) = si._o;
247 } else
248 CGAL_error_msg( "wrong object");
249 // debug();
250 }
251
ending_segmentSMO_from_sm252 void ending_segment(Vertex_handle v, IT it) const
253 { INFO& si = M[it];
254 if ( si._from == -1 ) return;
255 typename SM_const_decorator::SHalfedge_const_handle se;
256 typename SM_const_decorator::SHalfloop_const_handle sl;
257 if(CGAL::assign(se, si._o)) {
258 if(se->source()->point() != v->point()) {
259 se = se->twin();
260 if(se->source()->point() != v->point()) {
261 G.supp_object(v,si._from) = si._o;
262 return;
263 }
264 }
265 G.supp_object(v,si._from) = make_object(se->source());
266 CGAL_NEF_TRACEN("ending_segment " << si._from << ":"<<
267 v->point() << ":" <<
268 se->source()->point() << "->" <<
269 se->twin()->source()->point());
270 } else if(CGAL::assign(sl, si._o)) {
271 G.supp_object(v,si._from) = si._o;
272 } else
273 CGAL_error_msg( "wrong object");
274 // debug();
275 }
276
passing_segmentSMO_from_sm277 void passing_segment(Vertex_handle v, IT it) const
278 { INFO& si = M[it];
279 if ( si._from == -1 ) return;
280 G.supp_object(v,si._from) = si._o;
281 CGAL_NEF_TRACEN("passing_segment " << si._from << ":"<< v->point());
282 // debug();
283 }
284
halfedge_belowSMO_from_sm285 Halfedge_handle halfedge_below(Vertex_handle v) const
286 { return G.halfedge_below(v); }
287
assert_equal_marksSMO_from_sm288 void assert_equal_marks(Vertex_handle v1, Vertex_handle v2) const
289 {
290 CGAL_USE(v1);
291 CGAL_USE(v2);
292 CGAL_NEF_TRACEV(G.mark(v1,0));CGAL_NEF_TRACEV(G.mark(v1,1));
293 CGAL_NEF_TRACEV(G.mark(v2,0));CGAL_NEF_TRACEV(G.mark(v2,1));
294 CGAL_assertion(G.mark(v1,0)==G.mark(v2,0)&&
295 G.mark(v1,1)==G.mark(v2,1)); }
discard_infoSMO_from_sm296 void discard_info(Vertex_handle v) const
297 { G.discard_info(v); }
298
assert_equal_marksSMO_from_sm299 void assert_equal_marks(Halfedge_handle e1, Halfedge_handle e2) const
300 {
301 CGAL_USE(e1);
302 CGAL_USE(e2);
303 CGAL_assertion(G.mark(e1,0)==G.mark(e2,0) &&
304 G.mark(e1,1)==G.mark(e2,1));
305 }
306
discard_infoSMO_from_sm307 void discard_info(Halfedge_handle e) const
308 { G.discard_info(e); }
309
debugSMO_from_sm310 void debug() const {
311 typename SM_overlayer::SVertex_iterator svii;
312 CGAL_forall_svertices(svii, G) {
313 typename SM_overlayer::SVertex_const_handle vs;
314 typename SM_overlayer::SHalfedge_const_handle es;
315 if(CGAL::assign(vs, G.supp_object(svii,0)))
316 std::cerr << svii->point() << " supported by svertex " << vs->point() << std::endl;
317 else if(CGAL::assign(es, G.supp_object(svii,0)))
318 std::cerr << svii->point() << " supported by sedge" << std::endl;
319 else
320 std::cerr << svii->point() << " is neither supported by svertex or sedge" << std::endl;
321 if(CGAL::assign(vs, G.supp_object(svii,1)))
322 std::cerr << svii->point() << " supported by svertex" << vs->point() << std::endl;
323 else if(CGAL::assign(es, G.supp_object(svii,1)))
324 std::cerr << svii->point() << " supported by sedge" << std::endl;
325 else
326 std::cerr << svii->point() << " is neither supported by svertex or sedge" << std::endl;
327 }
328 }
329
330 }; // SMO_from_sm
331
332 template <typename SM_decorator, typename ITERATOR>
333 class SMO_decorator {
334 public:
335 typedef SM_decorator Graph;
336 typedef typename SM_decorator::SVertex_handle SVertex_handle;
337 typedef typename SM_decorator::SHalfedge_handle SHalfedge_handle;
338 typedef typename SM_decorator::Sphere_point Point_2;
339 typedef typename SM_decorator::Sphere_segment Segment_2;
340 SM_decorator G;
341
SMO_decorator(Graph Gi)342 SMO_decorator(Graph Gi) : G(Gi) {}
343
new_vertex(const Point_2 & p)344 SVertex_handle new_vertex(const Point_2& p)
345 { return G.snew_vertex(p); }
346
link_as_target_and_append(SVertex_handle v,SHalfedge_handle e)347 void link_as_target_and_append(SVertex_handle v, SHalfedge_handle e)
348 { G.link_as_target_and_append(v,e); }
349
new_halfedge_pair_at_source(SVertex_handle v)350 SHalfedge_handle new_halfedge_pair_at_source(SVertex_handle v)
351 { return G.new_shalfedge_pair_at_source(v,Graph::BEFORE); }
352
supporting_segment(SHalfedge_handle,ITERATOR)353 void supporting_segment(SHalfedge_handle /*e*/, ITERATOR /*it*/) {}
halfedge_below(SVertex_handle,SHalfedge_handle)354 void halfedge_below(SVertex_handle /*v*/, SHalfedge_handle /*e*/) {}
trivial_segment(SVertex_handle,ITERATOR)355 void trivial_segment(SVertex_handle /*v*/, ITERATOR /*it*/) {}
starting_segment(SVertex_handle,ITERATOR)356 void starting_segment(SVertex_handle /*v*/, ITERATOR /*it*/) {}
passing_segment(SVertex_handle,ITERATOR)357 void passing_segment(SVertex_handle /*v*/, ITERATOR /*it*/) {}
ending_segment(SVertex_handle,ITERATOR)358 void ending_segment(SVertex_handle /*v*/, ITERATOR /*it*/) {}
359
360
361 }; // SMO_decorator
362
363 // ============================================================================
364 // ============================================================================
365
366 /*{\Manpage {SM_overlayer}{SM_decorator}{Overlay in the sphere}{O}}*/
367
368 template <typename SM_decorator_>
369 class SM_overlayer : public SM_decorator_ {
370 public:
371
372 /*{\Mdefinition An instance |\Mvar| of data type |\Mname| is a
373 decorator object offering sphere map overlay calculation. Overlay is
374 either calculated from two sphere maps or from a set of halfspaces.
375 The result is stored in a sphere map |M| that carries the geometry and
376 the topology of the overlay.
377
378 The template parameter provides the underlying topological interface
379 to sphere maps. The template parameter |SM_decorator| has to be a model
380 conforming to our map decorator concept |SM_decorator|. The concept
381 also describes the interface how the topological information stored in
382 |M| can be extracted or extended.
383
384 The overlay of a set of sphere segments $S$ is stored in a sphere map
385 $M = (V,E,L,F)$. Vertices are either the endpoints of segments (trivial
386 segments are allowed) or the result of the internal intersection of
387 two segments. Between two vertices there's an edge if there's a
388 segment that supports the spherical embedding of $e$ and if there's no
389 vertex in the relative interior of the embedding of $e$.
390
391 The faces refer to the maximal connected open point sets of the
392 spherical subdivision implied by the embedding of the vertices and
393 edges. SFaces are bounded by possibly several face cycles\cgalFootnote{For
394 the definition of sphere maps and their concepts see the manual page
395 of |SM_decorator|.} including isolated vertices. The overlay process
396 in the method |create_from_segments| creates the objects and the
397 topology of the result. The method starts from zero- and
398 one-dimensional geometric objects in $S$ and produces a spherical
399 structure where each point of the sphere can be assigned to an object
400 (vertex, edge, loop, or face) of |M|.
401
402 The overlay of two sphere maps $M_i = (V_i, E_i, L_i, F_i)$ has the
403 additional aspect that we already start from two spherical
404 subdivisions. We use the index $i=0,1$ defining the reference to
405 $M_i$, unindexed variables refer to the resulting sphere map $M$. The
406 $1$-skeleta of the two maps subdivide the edges, loops, and faces of
407 the complementary structure into smaller units. This means vertices,
408 edges, and loops of $M_i$ can split edges and loops of $M_{1-i}$ and
409 face cycles of $M_i$ subdivide faces of $M_{1-i}$. The 1-skeleton $G$
410 of $M$ is defined by the overlay of the embedding of the 1-skeleta of
411 $M_0$ and $M_1$ (Take a trivial segment for each vertex and a segment
412 for each edge, and a circle for a loop, and use the overlay definition
413 of a set of segments and loops above). The faces of $M$ refer to the
414 maximal connected open point sets of the spherical subdivision implied
415 by the embedding of $G$. Each object from the output tuple $(V,E,F)$
416 has a \emph{supporting} object $u_i$ in each of the two input
417 structures. Imagine the two maps to be transparent balls, where one
418 contains the other. Then each point of the sphere is covered by an
419 object from each of the input structures. This support relationship
420 from the input structures to the output structure defines an
421 information flow. Each supporting object $u_i$ of $u$ $(i=0,1)$
422 carries an associated information $|mark|(u_i)$. After the subdivision
423 operation this information is attributed to the output object $u$ by
424 $|mark|(u,i)$.}*/
425
426 typedef SM_decorator_ SM_decorator;
427 typedef typename SM_decorator::Map Map;
428 typedef SM_decorator Base;
429 typedef SM_overlayer<SM_decorator_> Self;
430 typedef CGAL::SM_const_decorator<Map> SM_const_decorator;
431 typedef CGAL::SM_point_locator<SM_const_decorator> SM_point_locator;
432
433 // typedef typename SM_const_decorator::Constructor_parameter
434 // Constructor_const_parameter;
435 typedef typename SM_const_decorator::SVertex_const_handle SVertex_const_handle;
436 typedef typename SM_const_decorator::SHalfedge_const_handle SHalfedge_const_handle;
437 typedef typename SM_const_decorator::SHalfloop_const_handle SHalfloop_const_handle;
438 typedef typename SM_const_decorator::SFace_const_handle SFace_const_handle;
439 typedef typename SM_const_decorator::SVertex_const_iterator SVertex_const_iterator;
440 typedef typename SM_const_decorator::SHalfedge_const_iterator SHalfedge_const_iterator;
441 typedef typename SM_const_decorator::SFace_const_iterator SFace_const_iterator;
442
443 // typedef typename Base::Constructor_parameter Constructor_parameter;
444 typedef typename Base::SVertex_handle SVertex_handle;
445 typedef typename Base::SHalfedge_handle SHalfedge_handle;
446 typedef typename Base::SHalfloop_handle SHalfloop_handle;
447 typedef typename Base::SFace_handle SFace_handle;
448 typedef typename Base::SVertex_iterator SVertex_iterator;
449 typedef typename Base::SHalfedge_iterator SHalfedge_iterator;
450 typedef typename Base::SFace_iterator SFace_iterator;
451 typedef typename Base::Object_handle Object_handle;
452
453 typedef typename Base::SHalfedge_around_svertex_circulator
454 SHalfedge_around_svertex_circulator;
455 typedef typename Base::SHalfedge_around_sface_circulator
456 SHalfedge_around_sface_circulator;
457 typedef typename Base::SFace_cycle_iterator
458 SFace_cycle_iterator;
459
460 typedef std::pair<SHalfedge_handle,SHalfedge_handle> SHalfedge_pair;
461
462 /*{\Mtypes 3}*/
463
464 typedef typename Base::Sphere_kernel Sphere_kernel;
465 /*{\Mtypemember the geometry kernel.}*/
466 typedef typename Sphere_kernel::Sphere_point Sphere_point;
467 /*{\Mtypemember the point type of the sphere geometry.}*/
468 typedef typename Sphere_kernel::Sphere_segment Sphere_segment;
469 /*{\Mtypemember the segment type of the sphere geometry.}*/
470 typedef typename Sphere_kernel::Sphere_circle Sphere_circle;
471 /*{\Mtypemember the circle type of the sphere geometry.}*/
472 typedef typename Base::Mark Mark;
473 /*{\Mtypemember the mark of sphere map objects.}*/
474
475 typedef typename Base::GenPtr GenPtr;
476
477
478 using Base::info;
479 using Base::set_first_out_edge;
480 using Base::first_out_edge;
481 using Base::last_out_edge;
482 using Base::out_edges;
483 using Base::link_as_loop;
484 using Base::link_as_face_cycle;
485 using Base::link_as_prev_next_pair;
486 using Base::link_as_isolated_vertex;
487 using Base::is_isolated;
488 using Base::set_source;
489 using Base::set_face;
490 using Base::delete_vertex_only;
491 using Base::delete_face_only;
492 using Base::delete_edge_pair;
493 using Base::delete_edge_pair_only;
494 using Base::is_sm_boundary_object;
495 using Base::undo_sm_boundary_object;
496 using Base::store_sm_boundary_object;
497 using Base::clear_face_cycle_entries;
498 using Base::is_closed_at_source;
499 using Base::has_outdeg_two;
500 using Base::convert_edge_to_loop;
501 using Base::merge_edge_pairs_at_target;
502
503
504 /*{\Mgeneralization SM_decorator}*/
505
506 protected:
507 SM_const_decorator PI[2];
508 const Sphere_kernel& K;
509
510 public:
511
512 // ---------------------------------------------------------------
513
514 struct Seg_info { // to transport information from input to output
515 Object_handle _o; int _from;
516
Seg_infoSeg_info517 Seg_info() : _o(), _from(-1) {}
Seg_infoSeg_info518 Seg_info(SVertex_const_handle v, int i)
519 { _o=make_object(v); _from=i; }
Seg_infoSeg_info520 Seg_info(SHalfedge_const_handle e, int i)
521 { _o=make_object(e); _from=i; }
Seg_infoSeg_info522 Seg_info(SHalfloop_const_handle l, int i)
523 { _o=make_object(l); _from=i; }
Seg_infoSeg_info524 Seg_info(const Seg_info& si)
525 { _o=si._o; _from=si._from; }
526 Seg_info& operator=(const Seg_info& si)
527 { _o=si._o; _from=si._from; return *this; }
528 LEDA_MEMORY(Seg_info)
529 }; // Seg_info
530
531 typedef std::list<Sphere_segment> Seg_list;
532 typedef typename Seg_list::iterator Seg_iterator;
533 typedef std::pair<Seg_iterator,Seg_iterator> Seg_it_pair;
534 typedef std::pair<Sphere_segment,Sphere_segment> Seg_pair;
535 typedef CGAL::Unique_hash_map<Seg_iterator,Seg_info> Seg_map;
536
537 // ---------------------------------------------------------------
538
539 struct vertex_info {
540 Mark m[2];
541 Object_handle o_supp[2];
542 SHalfedge_handle e_below;
543
vertex_infovertex_info544 vertex_info()
545 {
546 m[0]=m[1]=Mark();
547 o_supp[0]=o_supp[1]=Object_handle();
548 }
549
550 LEDA_MEMORY(vertex_info)
551 }; // vertex_info
552
assoc_info(SVertex_handle v)553 void assoc_info(SVertex_handle v) const
554 {
555 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
556 geninfo<vertex_info>::create(info(v));
557 #else
558 info(v)=vertex_info();
559 #endif
560 }
561
discard_info(SVertex_handle v)562 void discard_info(SVertex_handle v) const
563 {
564 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
565 geninfo<vertex_info>::clear(info(v));
566 #else
567 info(v)=boost::any();
568 #endif
569 }
570
ginfo(SVertex_handle v)571 vertex_info& ginfo(SVertex_handle v) const
572 {
573 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
574 return geninfo<vertex_info>::access(info(v));
575 #else
576 return
577 *boost::any_cast<vertex_info>(&info(v));
578 #endif
579 }
580
mark(SVertex_handle v,int i)581 Mark& mark(SVertex_handle v, int i) const
582 { return ginfo(v).m[i]; }
583
supp_object(SVertex_handle v,int i)584 Object_handle& supp_object(SVertex_handle v, int i) const
585 { return ginfo(v).o_supp[i]; }
586
halfedge_below(SVertex_handle v)587 SHalfedge_handle& halfedge_below(SVertex_handle v) const
588 { return ginfo(v).e_below; }
589
590 // ---------------------------------------------------------------
591
592 struct edge_info {
593 Mark m[2];
594 Mark mf[2];
595 Object_handle o_supp[2];
596 bool forw;
edge_infoedge_info597 edge_info()
598 { m[0]=m[1]=mf[0]=mf[1]=Mark();
599 o_supp[0]=o_supp[1]=Object_handle();
600 forw=false; }
601 LEDA_MEMORY(edge_info)
602 };
603
assoc_info(SHalfedge_handle e)604 void assoc_info(SHalfedge_handle e) const
605 {
606 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
607 geninfo<edge_info>::create(info(e));
608 geninfo<edge_info>::create(info(e->twin()));
609 #else
610 info(e)=edge_info();
611 info(e->twin())=edge_info();
612 #endif
613 }
614
discard_info(SHalfedge_handle e)615 void discard_info(SHalfedge_handle e) const
616 {
617 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
618 geninfo<edge_info>::clear(info(e));
619 geninfo<edge_info>::clear(info(e->twin()));
620 #else
621 info(e)=boost::any();
622 info(e->twin())=boost::any();
623 #endif
624 }
625
ginfo(SHalfedge_handle e)626 edge_info& ginfo(SHalfedge_handle e) const
627 {
628 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
629 return geninfo<edge_info>::access(info(e));
630 #else
631 return
632 *boost::any_cast<edge_info>(&info(e));
633 #endif
634 }
635
mark(SHalfedge_handle e,int i)636 Mark& mark(SHalfedge_handle e, int i) const
637 { return ginfo(e).m[i]; }
638
supp_object(SHalfedge_handle e,int i)639 Object_handle& supp_object(SHalfedge_handle e, int i) const
640 // uedge information we store in the smaller one
641 { if (&*e < &*(e->twin())) return ginfo(e).o_supp[i];
642 else return ginfo(e->twin()).o_supp[i]; }
643
incident_mark(SHalfedge_handle e,int i)644 Mark& incident_mark(SHalfedge_handle e, int i) const
645 // biedge information we store in the edge
646 { return ginfo(e).mf[i]; }
647
is_forward(SHalfedge_handle e)648 bool& is_forward(SHalfedge_handle e) const
649 // biedge information we store in the edge
650 { return ginfo(e).forw; }
651
652 // ---------------------------------------------------------------
653
654 struct face_info {
655 Mark m[2];
face_infoface_info656 face_info() { m[0]=m[1]=Mark(); }
657 LEDA_MEMORY(face_info)
658 };
659
assoc_info(SFace_handle f)660 void assoc_info(SFace_handle f) const
661 {
662 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
663 geninfo<face_info>::create(info(f));
664 #else
665 info(f)=face_info();
666 #endif
667 }
668
discard_info(SFace_handle f)669 void discard_info(SFace_handle f) const
670 {
671 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
672 geninfo<face_info>::clear(info(f));
673 #else
674 info(f)=boost::any();
675 #endif
676 }
677
ginfo(SFace_handle f)678 face_info& ginfo(SFace_handle f) const
679 {
680 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
681 return geninfo<face_info>::access(info(f));
682 #else
683 return
684 *boost::any_cast<face_info>(&info(f));
685 #endif
686 }
687
mark(SFace_handle f,int i)688 Mark& mark(SFace_handle f, int i) const
689 { return ginfo(f).m[i]; }
690
691 // ---------------------------------------------------------------
692
693 template <typename Below_accessor>
determine_face(SHalfedge_handle e,const std::vector<SHalfedge_handle> & MinimalSHalfedge,const CGAL::Unique_hash_map<SHalfedge_handle,int> & SFaceCycle,const Below_accessor & D)694 SFace_handle determine_face(SHalfedge_handle e,
695 const std::vector<SHalfedge_handle>& MinimalSHalfedge,
696 const CGAL::Unique_hash_map<SHalfedge_handle,int>& SFaceCycle,
697 const Below_accessor& D)
698 { CGAL_NEF_TRACEN("determine_face "<<PH(e));
699 int fc = SFaceCycle[e];
700 SHalfedge_handle e_min = MinimalSHalfedge[fc];
701 SHalfedge_handle e_below = D.halfedge_below(e_min->target());
702 if(e_below == SHalfedge_handle())
703 return SFace_handle();
704 SFace_handle f = e_below->incident_sface();
705 if ( f != SFace_handle() ) return f; // has already a face
706 // e_below also has no face
707 f = determine_face(e_below, MinimalSHalfedge, SFaceCycle,D);
708 if(f != SFace_handle())
709 link_as_face_cycle(e_below,f);
710 return f;
711 }
712
segment(SM_const_decorator,SHalfedge_const_handle e)713 Sphere_segment segment(SM_const_decorator ,
714 SHalfedge_const_handle e) const
715 { return K.construct_segment(e->source()->point(),
716 e->target()->point(),
717 e->circle()); }
718
trivial_segment(SM_const_decorator,SVertex_const_handle v)719 Sphere_segment trivial_segment(SM_const_decorator ,
720 SVertex_const_handle v) const
721 { Sphere_point p = v->point();
722 return K.construct_segment(p,p); }
723
two_segments(SM_const_decorator,SHalfedge_const_handle e)724 Seg_pair two_segments(SM_const_decorator ,
725 SHalfedge_const_handle e) const
726 // we know that e->source()==e->target()
727 { return e->circle().split_at(e->source()->point()); }
728
two_segments(SM_const_decorator,SHalfloop_const_handle l)729 Seg_pair two_segments(SM_const_decorator ,
730 SHalfloop_const_handle l) const
731 { return l->circle().split_at_xy_plane(); }
732
733
734 // ---------------------------------------------------------------
735 // INTERFACE INTERFACE INTERFACE INTERFACE INTERFACE INTERFACE
736 // ---------------------------------------------------------------
737
738 /*{\Mcreation 6}*/
739
740 SM_overlayer(Map* M,
Base(M)741 const Sphere_kernel& G = Sphere_kernel()) : Base(M), K(G) {}
742 /*{\Mcreate |\Mvar| is a decorator object manipulating the map
743 of |v|.}*/
744
745 /*{\Moperations 1.1 1}*/
746
747 template <typename Forward_iterator>
748 void create_from_segments(
749 Forward_iterator start, Forward_iterator end);
750 /*{\Mop produces the sphere map which is the overlay of the
751 segments from the iterator range |[start,end)|. \precond
752 |Forward_iterator| has value type |Sphere_segment|.}*/
753
754 template <typename Forward_iterator>
755 void create_from_circles(Forward_iterator start, Forward_iterator end);
756 /*{\Mop produces the sphere map which is the overlay of the
757 circles from the iterator range |[start,end)|. \precond
758 |Forward_iterator| has value type |Sphere_circle|.}*/
759
760 void create(const Sphere_circle& c);
761 /*{\Mop produces the sphere map which consists of one loop
762 and the two halfspheres incident to it.}*/
763
764 void subdivide(const Map* M0, const Map* M1,
765 bool with_trivial_segments = false);
766
767 template <typename Association>
768 void subdivide(const Map* M0, const Map* M1,
769 Association& A,
770 bool with_trivial_segments = false);
771 /*{\Mop constructs the overlay of the sphere maps |M0| and |M1| in
772 |M|, where all objects (vertices, halfedges, faces) of |M| are
773 \emph{enriched} by the marks of the supporting objects of the two
774 input structures: e.g. let |v| be a vertex supported by a node |v0| in
775 |M0| and by a face |f1| in |M1| and |D0|, |D1| be decorators of
776 type |SM_decorator| on |M0|,|M1|. Then |\Mvar.mark(v,0) = D0.v0->mark()|
777 and |\Mvar.mark(v,1) = D1.f1->mark()|.}*/
778
779 template <typename Selection>
780 void select(const Selection& SP) const;
781 /*{\Mop sets the marks of all objects according to the selection
782 predicate |SP|. |Selection| has to be a function object type with a
783 function operator\\
784 [[Mark operator()(Mark m0, Mark m1) const]]\\
785 For each object |u| of |M| enriched by the marks of the supporting
786 objects according to the previous procedure |subdivide|, after this
787 operation |\Mvar.u->mark() = SP ( \Mvar.mark(u,0),\Mvar.mark(u,1)
788 )|. The additional marks are invalidated afterwards.
789 \precond subdivide() was called before.}*/
790
791 void simplify();
792 /*{\Mop simplifies the structure of |M| according to the marks of
793 its objects. An edge |e| separating two faces |f1| and |f2| and equal
794 marks |e->mark() == f1->mark() == f2->mark()| is removed and the faces are
795 unified. An isolated vertex |v| in a face |f| with |v->mark()==f->mark()|
796 is removed. A vertex |v| with outdegree two, two collinear out-edges
797 |e1|,|e2| and equal marks |v->mark() == e1->mark() == e2->mark()| is removed
798 and the edges are unified.}*/
799
800 int check_sphere(const Seg_list& L, bool compute_halfsphere[3][2]) const;
801
802 template <typename Iterator>
803 void subdivide_segments(Iterator start, Iterator end) const;
804 template <typename Iterator, typename T>
805 void partition_to_halfsphere(Iterator start, Iterator end,
806 Seg_list& L, CGAL::Unique_hash_map<Iterator,T>& M,
807 Sphere_circle xycircle, Sphere_circle yzcircle, bool include_equator) const;
808
809 template <typename Mark_accessor>
810 void merge_halfsphere_maps(SVertex_handle v1, SVertex_handle v2,
811 const Mark_accessor& D);
812 template <typename Mark_accessor>
813 void merge_nodes(SHalfedge_handle e1, SHalfedge_handle e2,
814 const Mark_accessor& D);
815
816 template <typename Below_accessor, typename Halfsphere_geometry>
817 void create_face_objects(SHalfedge_iterator e_start, SHalfedge_iterator e_end,
818 SVertex_iterator v_start, SVertex_iterator v_end,
819 const Below_accessor& D,
820 const Halfsphere_geometry& SG);
821
822 template <typename Below_accessor>
823 void complete_face_support(SVertex_iterator v_start, SVertex_iterator v_end,
824 const Below_accessor& D, std::vector<Mark>& mohs, int offset, bool both=true) const;
825
826 void complete_sface_marks() const;
827
828 void set_outer_face_mark(int offset, const std::vector<Mark>& mohs);
829
830 template <typename Association>
831 void transfer_data(Association& A);
832
833 void dump(std::ostream& os = std::cerr) const
834 { SM_io_parser<Base>::dump(*this,os); }
835
836 }; // SM_overlayer<SM_decorator>
837
838 template <typename Map>
839 template <typename Forward_iterator>
840 void SM_overlayer<Map>::
create_from_segments(Forward_iterator start,Forward_iterator end)841 create_from_segments(Forward_iterator start, Forward_iterator end)
842 {
843 CGAL_NEF_TRACEN("creating from segment iterator range");
844 Seg_list L(start,end);
845 Unique_hash_map<Seg_iterator,bool> From_input(false);
846 Seg_iterator it;
847 CGAL_forall_iterators(it,L) From_input[it]=true;
848 Seg_list L_pos,L_neg;
849 partition_to_halfsphere(L.begin(), L.end(), L_pos, From_input,
850 Sphere_circle(0,0,1), Sphere_circle(1,0,0), true);
851 partition_to_halfsphere(L.begin(), L.end(), L_neg, From_input,
852 Sphere_circle(0,0,-1), Sphere_circle(1,0,0), true);
853
854 typedef SMO_from_segs<Self,Seg_iterator> SM_output;
855 typedef typename Sphere_kernel::Positive_halfsphere_geometry PH_geometry;
856 typedef CGAL::Segment_overlay_traits<
857 Seg_iterator, SM_output, PH_geometry> PHS_traits;
858 typedef CGAL::generic_sweep<PHS_traits> Positive_halfsphere_sweep;
859
860 typedef typename Sphere_kernel::Negative_halfsphere_geometry NH_geometry;
861 typedef CGAL::Segment_overlay_traits<
862 Seg_iterator, SM_output, NH_geometry> NHS_traits;
863 typedef CGAL::generic_sweep<NHS_traits> Negative_halfsphere_sweep;
864
865 SVertex_iterator v;
866 SHalfedge_iterator e;
867 SM_output O(*this,From_input);
868
869 typedef typename PHS_traits::INPUT Input_range;
870 PH_geometry ph_g;
871 Positive_halfsphere_sweep SP(
872 Input_range(L_pos.begin(),L_pos.end()),O,
873 ph_g);
874 SP.sweep();
875 //CGAL_NEF_TRACEN("POS SWEEP\n"<<(dump(std::cerr),""));
876 v=--this->svertices_end(); e=--this->shalfedges_end();
877 NH_geometry nh_g;
878 Negative_halfsphere_sweep SM(
879 Input_range(L_neg.begin(),L_neg.end()),O,
880 nh_g);
881 SM.sweep();
882 //CGAL_NEF_TRACEN("NEG SWEEP\n"<<(dump(std::cerr),""));
883 ++v; ++e;
884 // now two CCs of sphere graph are calculated
885 // v = first vertex of CC in negative x-sphere
886 // e = first edge of CC in negative x-sphere
887
888 create_face_objects(this->shalfedges_begin(), e, this->svertices_begin(), v, O,
889 PH_geometry());
890 create_face_objects(e, this->shalfedges_end(), v, this->svertices_end(), O,
891 NH_geometry());
892
893 SHalfedge_iterator u;
894 CGAL_forall_sedges(u,*this) {
895 Sphere_segment s(u->source()->point(),u->target()->point());
896 u->circle() = s.sphere_circle();
897 u->twin()->circle() = s.sphere_circle().opposite();
898 }
899
900 merge_halfsphere_maps(this->svertices_begin(),v,O);
901 this->check_integrity_and_topological_planarity();
902
903 O.clear_temporary_vertex_info();
904 }
905
906 template <typename Map>
907 template <typename Forward_iterator>
908 void SM_overlayer<Map>::
create_from_circles(Forward_iterator start,Forward_iterator end)909 create_from_circles(Forward_iterator start, Forward_iterator end)
910 {
911 CGAL_NEF_TRACEN("creating from circle iterator range");
912 Seg_list L;
913 Unique_hash_map<Seg_iterator,bool> From_input(false);
914 for ( ; start != end; ++start ) {
915 std::pair<Sphere_segment,Sphere_segment> spair =
916 start->split_at_xy_plane();
917 L.push_back(spair.first); L.push_back(spair.second);
918 }
919 Seg_iterator it;
920 CGAL_forall_iterators(it,L) From_input[it]=true;
921 Seg_list L_pos,L_neg;
922 partition_to_halfsphere(L.begin(), L.end(), L_pos, From_input,
923 Sphere_circle(0,0,1), Sphere_circle(1,0,0), true);
924 partition_to_halfsphere(L.begin(), L.end(), L_neg, From_input,
925 Sphere_circle(0,0,-1), Sphere_circle(1,0,0), true);
926
927 typedef SMO_from_segs<Self,Seg_iterator> SM_output;
928 typedef typename Sphere_kernel::Positive_halfsphere_geometry PH_geometry;
929 typedef CGAL::Segment_overlay_traits<
930 Seg_iterator, SM_output, PH_geometry> PHS_traits;
931 typedef CGAL::generic_sweep<PHS_traits> Positive_halfsphere_sweep;
932
933 typedef typename Sphere_kernel::Negative_halfsphere_geometry NH_geometry;
934 typedef CGAL::Segment_overlay_traits<
935 Seg_iterator, SM_output, NH_geometry> NHS_traits;
936 typedef CGAL::generic_sweep<NHS_traits> Negative_halfsphere_sweep;
937
938 SVertex_iterator v;
939 SHalfedge_iterator e;
940 SM_output O(*this,From_input);
941
942 typedef typename PHS_traits::INPUT Input_range;
943 PH_geometry ph_g;
944 Positive_halfsphere_sweep SP(
945 Input_range(L_pos.begin(),L_pos.end()),O,
946 ph_g);
947 SP.sweep();
948 //CGAL_NEF_TRACEN("POS SWEEP\n"<<(dump(std::cerr),""));
949 v=--this->svertices_end(); e=--this->shalfedges_end();
950 NH_geometry nh_geom;
951 Negative_halfsphere_sweep SM(
952 Input_range(L_neg.begin(),L_neg.end()), O,
953 nh_geom);
954 SM.sweep();
955 //CGAL_NEF_TRACEN("NEG SWEEP\n"<<(dump(std::cerr),""));
956 ++v; ++e;
957 // now two CCs of sphere graph are calculated
958 // v = first vertex of CC in negative x-sphere
959 // e = first edge of CC in negative x-sphere
960
961 create_face_objects(this->shalfedges_begin(), e, this->svertices_begin(), v, O,
962 PH_geometry());
963 create_face_objects(e, this->shalfedges_end(), v, this->svertices_end(), O,
964 NH_geometry());
965
966 SHalfedge_iterator u;
967 CGAL_forall_sedges(u,*this) {
968 Sphere_segment s(u->source()->point(),u->target()->point());
969 u->circle() = s.sphere_circle();
970 u->twin()->circle() = s.sphere_circle().opposite();
971 }
972
973 merge_halfsphere_maps(this->svertices_begin(),v,O);
974 this->check_integrity_and_topological_planarity();
975
976 O.clear_temporary_vertex_info();
977 }
978
979 #ifdef CGAL_NEF_NEW_CHECK_SPHERE
980 template <typename Map>
981 int SM_overlayer<Map>::
check_sphere(const Seg_list & L,bool compute_halfsphere[3][2])982 check_sphere(const Seg_list& L, bool compute_halfsphere[3][2]) const {
983
984 int chsp = 0;
985 CGAL_NEF_TRACEN("chsp " << chsp);
986
987 typename Seg_list::const_iterator it;
988 CGAL_forall_iterators(it,L) {
989 CGAL_NEF_TRACEN("source " << it->source());
990 CGAL_NEF_TRACEN("target " << it->target());
991
992 if((chsp&1)!=1)
993 if(it->source().hx()>0 || it->target().hx()>0)
994 chsp|=1;
995 if((chsp&2)!=2)
996 if(it->source().hx()<0 || it->target().hx()<0)
997 chsp|=2;
998 if((chsp&4)!=4)
999 if(it->source().hy()>0 || it->target().hy()>0)
1000 chsp|=4;
1001 if((chsp&8)!=8)
1002 if(it->source().hy()<0 || it->target().hy()<0)
1003 chsp|=8;
1004 if((chsp&16)!=16)
1005 if(it->source().hz()>0 || it->target().hz()>0)
1006 chsp|=16;
1007 if((chsp&32)!=32)
1008 if(it->source().hz()<0 || it->target().hz()<0)
1009 chsp|=32;
1010 CGAL_NEF_TRACEN("chsp " << chsp);
1011 if(chsp == 63)
1012 break;
1013 }
1014
1015 CGAL_forall_iterators(it,L) {
1016 CGAL_NEF_TRACEN("chsp " << chsp);
1017 if(chsp == 63)
1018 break;
1019
1020 // int l = it->compare_length_to_halfcircle();
1021 CGAL_NEF_TRACEN("source " << it->source());
1022 CGAL_NEF_TRACEN("target " << it->target());
1023 CGAL_NEF_TRACEN("cicle " << it->sphere_circle());
1024 CGAL_NEF_TRACEN("is long " << it->is_long());
1025
1026 if(it->is_short()) continue;
1027
1028 CGAL_NEF_TRACEN("not short");
1029 CGAL_NEF_TRACEN("circle " << it->sphere_circle());
1030 if(it->is_long()) {
1031 if((chsp&60)!=60 &&
1032 it->sphere_circle().orthogonal_vector().x()!=0) chsp|=60;
1033 if((chsp&51)!=51 &&
1034 it->sphere_circle().orthogonal_vector().y()!=0) chsp|=51;
1035 if((chsp&15)!=15 &&
1036 it->sphere_circle().orthogonal_vector().z()!=0) chsp|=15;
1037 } else {
1038
1039 int n = 0;
1040 if(it->source().hx()==0) ++n;
1041 if(it->source().hy()==0) ++n;
1042 if(it->source().hz()==0) ++n;
1043 CGAL_assertion(n<3);
1044
1045 CGAL_NEF_TRACEN("n " << n);
1046 CGAL_NEF_TRACEN("number of coordinats =0:" << n);
1047 if(n==0) {
1048 if((chsp&60)!=60 &&
1049 it->sphere_circle().orthogonal_vector().x()!=0) chsp|=60;
1050 if((chsp&51)!=51 &&
1051 it->sphere_circle().orthogonal_vector().y()!=0) chsp|=51;
1052 if((chsp&15)!=15 &&
1053 it->sphere_circle().orthogonal_vector().z()!=0) chsp|=15;
1054 } else if(n==1) {
1055 if((chsp&48)!=48 && it->source().z()==0) {
1056 Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(1,0,0));
1057 CGAL_NEF_TRACEN("intersection " << i);
1058 if(!it->has_on_after_intersection(i)) i=i.antipode();
1059 if(i.z() > 0) chsp|=16;
1060 else if(i.z() < 0) chsp|=32;
1061 } else if((chsp&3)!=3 && it->source().x()==0) {
1062 Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(0,1,0));
1063 CGAL_NEF_TRACEN("intersection " << i);
1064 if(!it->has_on_after_intersection(i)) i=i.antipode();
1065 if(i.x() > 0) chsp|=1;
1066 else if(i.x() < 0) chsp|=2;
1067 } else if((chsp&12)!=12) {
1068 Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(1,0,0));
1069 CGAL_NEF_TRACEN("intersection " << i);
1070 if(!it->has_on_after_intersection(i)) i=i.antipode();
1071 if(i.y() > 0) chsp|=4;
1072 else if(i.y() < 0) chsp|=8;
1073 }
1074 } else { // n==2
1075 if((chsp&60)!=60 && it->source().x()!=0) {
1076 Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(1,0,0));
1077 CGAL_NEF_TRACEN("intersection " << i);
1078 if(!it->has_on_after_intersection(i)) i=i.antipode();
1079 if((chsp&12)!=12)
1080 if(i.y() > 0) chsp|=4;
1081 else if(i.y() < 0) chsp|=8;
1082 if((chsp&48)!=48)
1083 if(i.z() > 0) chsp|=16;
1084 else if(i.z() < 0) chsp|=32;
1085 } else if((chsp&51)!=51 && it->source().y()!=0) {
1086 Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(0,1,0));
1087 CGAL_NEF_TRACEN("intersection " << i);
1088 if(!it->has_on_after_intersection(i)) i=i.antipode();
1089 if((chsp&3)!=3)
1090 if(i.x() > 0) chsp|=1;
1091 else if(i.x() < 0) chsp|=2;
1092 if((chsp&48)!=48)
1093 if(i.z() > 0) chsp|=16;
1094 else if(i.z() < 0) chsp|=32;
1095 } else if((chsp&15)!=15 && it->source().z()!=0) {
1096 Sphere_point i = intersection(it->sphere_circle(), Sphere_circle(0,0,1));
1097 CGAL_NEF_TRACEN("intersection " << i);
1098 if(!it->has_on_after_intersection(i)) i=i.antipode();
1099 if((chsp&3)!=3)
1100 if(i.x() > 0) chsp|=1;
1101 else if(i.x() < 0) chsp|=2;
1102 if((chsp&12)!=12)
1103 if(i.y() > 0) chsp|=4;
1104 else if(i.y() < 0) chsp|=8;
1105 }
1106 }
1107 }
1108 }
1109
1110 CGAL_NEF_TRACEN("chsp " << chsp);
1111
1112 compute_halfsphere[0][0] = (chsp&1)==1;
1113 compute_halfsphere[0][1] = (chsp&2)==2;
1114 compute_halfsphere[1][0] = (chsp&4)==4;
1115 compute_halfsphere[1][1] = (chsp&8)==8;
1116 compute_halfsphere[2][0] = (chsp&16)==16;
1117 compute_halfsphere[2][1] = (chsp&32)==32;
1118
1119 if((chsp&1)==0) {
1120 compute_halfsphere[0][1]=true;
1121 return 0;
1122 }
1123 if((chsp&2)==0) {
1124 compute_halfsphere[0][0]=true;
1125 return 1;
1126 }
1127 if((chsp&4)==0) {
1128 compute_halfsphere[1][1]=true;
1129 return 2;
1130 }
1131 if((chsp&8)==0) {
1132 compute_halfsphere[1][0]=true;
1133 return 3;
1134 }
1135 if((chsp&16)==0) {
1136 compute_halfsphere[2][1]=true;
1137 return 4;
1138 }
1139 if((chsp&32)==0) {
1140 compute_halfsphere[2][0]=true;
1141 return 5;
1142 }
1143
1144 return -1;
1145 }
1146 #else
1147 template <typename Map>
1148 int SM_overlayer<Map>::
check_sphere(const Seg_list & L,bool compute_halfsphere[3][2])1149 check_sphere(const Seg_list& L, bool compute_halfsphere[3][2]) const {
1150
1151 for(int i=0; i<6; i++)
1152 compute_halfsphere[i/2][i%2] = false;
1153
1154 CGAL_NEF_TRACEN("compute_halfsphere (at begin)");
1155 for(int i=0; i<6; ++i)
1156 CGAL_NEF_TRACEN(" " << i << " : " << compute_halfsphere[i/2][i%2]);
1157
1158 typename Seg_list::const_iterator it;
1159 CGAL_forall_iterators(it,L) {
1160 if(!compute_halfsphere[0][0])
1161 if(it->source().hx()>0 || it->target().hx()>0)
1162 compute_halfsphere[0][0] = true;
1163 if(!compute_halfsphere[0][1])
1164 if(it->source().hx()<0 || it->target().hx()<0)
1165 compute_halfsphere[0][1] = true;
1166 if(!compute_halfsphere[1][0])
1167 if(it->source().hy()>0 || it->target().hy()>0)
1168 compute_halfsphere[1][0] = true;
1169 if(!compute_halfsphere[1][1])
1170 if(it->source().hy()<0 || it->target().hy()<0)
1171 compute_halfsphere[1][1] = true;
1172 if(!compute_halfsphere[2][0])
1173 if(it->source().hz()>0 || it->target().hz()>0)
1174 compute_halfsphere[2][0] = true;
1175 if(!compute_halfsphere[2][1])
1176 if(it->source().hz()<0 || it->target().hz()<0)
1177 compute_halfsphere[2][1] = true;
1178 }
1179
1180 CGAL_NEF_TRACEN("compute_halfsphere (after vertices)");
1181 for(int i=0; i<6; ++i)
1182 CGAL_NEF_TRACEN(" " << i << " : " << compute_halfsphere[i/2][i%2]);
1183
1184
1185 if(!compute_halfsphere[2][0]) {
1186 CGAL_forall_iterators(it,L) {
1187 if((it->source().hz()==0 && it->target().hz()==0)
1188 || it->is_long()) {
1189 compute_halfsphere[2][0] = true;
1190 break;
1191 }
1192 }
1193 }
1194
1195 if(!compute_halfsphere[2][0]) {
1196 compute_halfsphere[2][1] = true;
1197 return 4;
1198 }
1199
1200 if(!compute_halfsphere[2][1]) {
1201 CGAL_forall_iterators(it,L) {
1202 if(it->is_long() || (it->source().hz()==0 && it->target().hz()==0)) {
1203 compute_halfsphere[2][1] = true;
1204 break;
1205 }
1206 }
1207 }
1208
1209 if(!compute_halfsphere[2][1])
1210 return 5;
1211
1212 if(!compute_halfsphere[0][0]) {
1213 CGAL_forall_iterators(it,L) {
1214 if((it->source().hx()==0 && it->target().hx()==0) || it->is_long()) {
1215 compute_halfsphere[0][0] = true;
1216 break;
1217 }
1218 }
1219 }
1220
1221 if(!compute_halfsphere[0][0]) {
1222 compute_halfsphere[0][1] = true;
1223 return 0;
1224 }
1225
1226 if(!compute_halfsphere[0][1]) {
1227 CGAL_forall_iterators(it,L) {
1228 if((it->source().hx()==0 && it->target().hx()==0) || it->is_long()) {
1229 compute_halfsphere[0][1] = true;
1230 break;
1231 }
1232 }
1233 }
1234
1235 if(!compute_halfsphere[0][1])
1236 return 1;
1237
1238
1239 if(!compute_halfsphere[1][0]) {
1240 CGAL_forall_iterators(it,L) {
1241 if((it->source().hy()==0 && it->target().hy()==0) || it->is_long()) {
1242 compute_halfsphere[1][0] = true;
1243 break;
1244 }
1245 }
1246 }
1247
1248 if(!compute_halfsphere[1][0]) {
1249 compute_halfsphere[1][1] = true;
1250 return 2;
1251 }
1252
1253 if(!compute_halfsphere[1][1]) {
1254 CGAL_forall_iterators(it,L) {
1255 if((it->source().hy()==0 && it->target().hy()==0) || it->is_long()) {
1256 compute_halfsphere[1][1] = true;
1257 break;
1258 }
1259 }
1260 }
1261
1262 if(!compute_halfsphere[1][1])
1263 return 3;
1264 return -1;
1265 }
1266 #endif
1267
1268 template <typename Map>
1269 void SM_overlayer<Map>::
create(const Sphere_circle & c)1270 create(const Sphere_circle& c)
1271 { SHalfloop_handle l1 = this->new_shalfloop_pair();
1272 SHalfloop_handle l2 = l1->twin();
1273 l1->circle() = c; l2->circle() = c.opposite();
1274 SFace_handle f1 = this->new_sface();
1275 SFace_handle f2 = this->new_sface();
1276 link_as_loop(l1,f1);
1277 link_as_loop(l2,f2);
1278 }
1279
1280 template <typename Map>
1281 void SM_overlayer<Map>::
subdivide(const Map * M0,const Map * M1,bool with_trivial_segments)1282 subdivide(const Map* M0, const Map* M1,
1283 bool with_trivial_segments) {
1284 PI[0] = SM_const_decorator(M0);
1285 PI[1] = SM_const_decorator(M1);
1286 bool compute_halfsphere[3][2];
1287 int cs=0;
1288
1289 Seg_list L;
1290 Seg_map From;
1291 for (int i=0; i<2; ++i) {
1292 SVertex_const_iterator v;
1293 CGAL_forall_svertices(v,PI[i]) {
1294 CGAL_NEF_TRACEN(v->point() << " from " << i << " mark " << v->mark());
1295 if ( !PI[i].is_isolated(v) ) continue;
1296 cs = -1;
1297 L.push_back(trivial_segment(PI[i],v));
1298 From[--L.end()] = Seg_info(v,i);
1299 }
1300 SHalfedge_const_iterator e;
1301 CGAL_forall_sedges(e,PI[i]) {
1302 if ( e->source() == e->target() ) {
1303 if(with_trivial_segments) {
1304 CGAL_NEF_TRACEN("trivial segment " << e->source()->point());
1305 v = e->source();
1306 L.push_back(trivial_segment(PI[i],v));
1307 From[--L.end()] = Seg_info(v,i);
1308 } else {
1309 CGAL_NEF_TRACEN("once around " << e->source()->point());
1310 Seg_pair p = two_segments(PI[i],e);
1311 L.push_back(p.first);
1312 L.push_back(p.second);
1313 From[--L.end()] = From[--(--L.end())] = Seg_info(e,i);
1314 }
1315 } else {
1316 CGAL_NEF_TRACEN("normal segment " << e->source()->point()
1317 << "->" << e->twin()->source()->point());
1318 L.push_back(segment(PI[i],e));
1319 From[--L.end()] = Seg_info(e,i);
1320 }
1321 }
1322 if ( PI[i].has_shalfloop() ) {
1323 CGAL_NEF_TRACEN("loop ");
1324 SHalfloop_const_handle shl = PI[i].shalfloop();
1325 Seg_pair p = two_segments(PI[i],shl);
1326 L.push_back(p.first);
1327 L.push_back(p.second.opposite());
1328 From[--L.end()] = From[--(--L.end())] =
1329 Seg_info(shl,i);
1330 }
1331 }
1332
1333 CGAL_assertion_code(typename Seg_list::iterator it);
1334 CGAL_assertion_code(CGAL_forall_iterators(it,L) CGAL_NEF_TRACEN(" "<<*it));
1335
1336 #ifdef CGAL_NEF3_SPHERE_SWEEP_OPTIMIZATION_OFF
1337 cs = -1;
1338 compute_halfsphere[2][0]=true;
1339 compute_halfsphere[2][1]=true;
1340 #else
1341 if(cs != -1)
1342 cs = check_sphere(L, compute_halfsphere);
1343 #endif
1344
1345 CGAL_NEF_TRACEN("compute_halfsphere\n cs = " << cs);
1346 for(int i=0; i<6; ++i)
1347 CGAL_NEF_TRACEN(" " << i << " : " << compute_halfsphere[i/2][i%2]);
1348 Seg_list L_pos,L_neg;
1349
1350 switch(cs) {
1351 case 1:
1352 partition_to_halfsphere(L.begin(), L.end(), L_pos, From,
1353 Sphere_circle(1,0,0), Sphere_circle(0,0,-1),
1354 compute_halfsphere[0][1]);
1355 break;
1356 case 0:
1357 partition_to_halfsphere(L.begin(), L.end(), L_neg, From,
1358 Sphere_circle(-1,0,0), Sphere_circle(0,0,-1),
1359 compute_halfsphere[0][0]);
1360 break;
1361 case 3:
1362 partition_to_halfsphere(L.begin(), L.end(), L_pos, From,
1363 Sphere_circle(0,1,0), Sphere_circle(1,0,0),
1364 compute_halfsphere[1][1]);
1365 break;
1366 case 2:
1367 partition_to_halfsphere(L.begin(), L.end(), L_neg, From,
1368 Sphere_circle(0,-1,0), Sphere_circle(1,0,0),
1369 compute_halfsphere[1][0]);
1370 break;
1371 case 5:
1372 partition_to_halfsphere(L.begin(), L.end(), L_pos, From,
1373 Sphere_circle(0,0,1), Sphere_circle(1,0,0),
1374 compute_halfsphere[2][1]);
1375 break;
1376 case 4:
1377 partition_to_halfsphere(L.begin(), L.end(), L_neg, From,
1378 Sphere_circle(0,0,-1), Sphere_circle(1,0,0),
1379 compute_halfsphere[2][0]);
1380 break;
1381 case -1:
1382 partition_to_halfsphere(L.begin(), L.end(), L_pos, From,
1383 Sphere_circle(0,0,1), Sphere_circle(1,0,0), true);
1384 partition_to_halfsphere(L.begin(), L.end(), L_neg, From,
1385 Sphere_circle(0,0,-1), Sphere_circle(1,0,0), true);
1386 break;
1387 default: CGAL_error_msg( "wrong value");
1388 }
1389
1390 cs = cs==-1 ? 2 : cs/2;
1391
1392 #ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
1393 timer_sphere_sweeps.start();
1394 #endif
1395
1396 typedef SMO_from_sm<Self,Seg_iterator,Seg_info> SM_output;
1397 typedef typename Sphere_kernel::Positive_halfsphere_geometry PH_geometry;
1398 typedef typename Sphere_kernel::Negative_halfsphere_geometry NH_geometry;
1399
1400 typedef CGAL::Segment_overlay_traits<
1401 Seg_iterator, SM_output, PH_geometry> PHS_traits;
1402 typedef CGAL::generic_sweep<PHS_traits> Positive_halfsphere_sweep;
1403
1404 typedef CGAL::Segment_overlay_traits<
1405 Seg_iterator, SM_output, NH_geometry> NHS_traits;
1406 typedef CGAL::generic_sweep<NHS_traits> Negative_halfsphere_sweep;
1407
1408 typedef typename PHS_traits::INPUT Input_range;
1409
1410 SVertex_handle v;
1411 SHalfedge_handle e;
1412 SM_output O(*this,PI,From);
1413
1414 if(compute_halfsphere[cs][0]) {
1415 PH_geometry phg(cs);
1416 Positive_halfsphere_sweep SP(
1417 Input_range(L_pos.begin(),L_pos.end()),O,phg);
1418 SP.sweep();
1419 v=--this->svertices_end(); e=--this->shalfedges_end();
1420 #ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
1421 number_of_sphere_sweeps++;
1422 #endif
1423 }
1424
1425 if(compute_halfsphere[cs][1]) {
1426 NH_geometry nhg(cs);
1427 Negative_halfsphere_sweep SM(
1428 Input_range(L_neg.begin(),L_neg.end()),O,
1429 nhg);
1430 SM.sweep();
1431 #ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
1432 number_of_sphere_sweeps++;
1433 #endif
1434 }
1435
1436 #ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
1437 timer_sphere_sweeps.stop();
1438 #endif
1439
1440 if(compute_halfsphere[cs][0]) {
1441 ++v;
1442 ++e;
1443 }
1444 else {
1445 v = this->svertices_begin();
1446 e = this->shalfedges_begin();
1447 }
1448
1449 if(compute_halfsphere[cs][0])
1450 create_face_objects(this->shalfedges_begin(), e, this->svertices_begin(), v, O,
1451 PH_geometry(cs));
1452 if(compute_halfsphere[cs][1])
1453 create_face_objects(e, this->shalfedges_end(), v, this->svertices_end(), O,
1454 NH_geometry(cs));
1455
1456 CGAL_forall_sedges(e,*this) {
1457 e->circle() = Sphere_circle(e->source()->point(), e->twin()->source()->point());
1458 e->twin()->circle() = e->circle().opposite();
1459 CGAL_NEF_TRACEN(PH(e) << " with circle " << e->circle());
1460 }
1461
1462 std::vector<Mark> mohs(4);
1463 SM_point_locator L0(M0);
1464 SM_point_locator L1(M1);
1465
1466 L0.marks_of_halfspheres(mohs, 0, cs);
1467 L1.marks_of_halfspheres(mohs, 2, cs);
1468
1469 CGAL_NEF_TRACEN("mohs[0]=" << mohs[0]);
1470 CGAL_NEF_TRACEN("mohs[1]=" << mohs[1]);
1471 CGAL_NEF_TRACEN("mohs[2]=" << mohs[2]);
1472 CGAL_NEF_TRACEN("mohs[3]=" << mohs[3]);
1473
1474 CGAL_NEF_TRACEN("compute_halfsphrere\n cs = " << cs <<
1475 "\n [cs][0] = " << compute_halfsphere[cs][0] <<
1476 "\n [cs][1] = " << compute_halfsphere[cs][1]);
1477 /*
1478 SVertex_iterator svii;
1479 CGAL_forall_svertices(svii, *this) {
1480 SVertex_const_handle vs;
1481 SHalfedge_const_handle es;
1482 if(CGAL::assign(vs, supp_object(svii,0)))
1483 std::cerr << svii->point() << " supported by svertex " << vs->point() << std::endl;
1484 else if(CGAL::assign(es, supp_object(svii,0)))
1485 std::cerr << svii->point() << " supported by sedge" << std::endl;
1486 else
1487 std::cerr << svii->point() << " is neither supported by svertex or sedge" << std::endl;
1488 if(CGAL::assign(vs, supp_object(svii,1)))
1489 std::cerr << svii->point() << " supported by svertex " << vs->point() << std::endl;
1490 else if(CGAL::assign(es, supp_object(svii,1)))
1491 std::cerr << svii->point() << " supported by sedge" << std::endl;
1492 else
1493 std::cerr << svii->point() << " is neither supported by svertex or sedge" << std::endl;
1494 }
1495 */
1496 if(compute_halfsphere[cs][0])
1497 complete_face_support(this->svertices_begin(), v, O, mohs, 0,
1498 compute_halfsphere[cs][1]);
1499 if(compute_halfsphere[cs][1])
1500 complete_face_support(v, this->svertices_end(), O, mohs, 1,
1501 compute_halfsphere[cs][0]);
1502
1503 complete_sface_marks();
1504
1505 // DEBUG CODE: to do: have all svertices a halfedge below associated?
1506 CGAL_NEF_TRACEN("Vertex info after swep");
1507 CGAL_assertion_code(SVertex_iterator svi);
1508 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
1509 CGAL_assertion_code(
1510 for(svi=this->svertices_begin(); svi!=this->svertices_end(); svi++) {
1511 CGAL_NEF_TRACEN("vertex "<<svi->point()<<" info "<< info(svi)<< " marks "<<mark(svi,0)<<" "<<mark(svi,1));
1512 }
1513 )
1514 #else
1515 CGAL_assertion_code(
1516 for(svi=this->svertices_begin(); svi!=this->svertices_end(); svi++) {
1517 CGAL_NEF_TRACEN("vertex "<<svi->point()<< " marks "<<mark(svi,0)<<" "<<mark(svi,1));
1518 }
1519 )
1520 #endif
1521 if(compute_halfsphere[cs][0] && compute_halfsphere[cs][1])
1522 merge_halfsphere_maps(this->svertices_begin(),v,O);
1523 else
1524 set_outer_face_mark(compute_halfsphere[cs][1], mohs);
1525
1526 CGAL_assertion_code(this->check_integrity_and_topological_planarity());
1527
1528 CGAL_NEF_TRACEN("subdivided");
1529 CGAL_assertion_code(CGAL_forall_svertices(v,*this) CGAL_NEF_TRACEN(PH(v)));
1530 }
1531
1532 template <typename Map>
1533 template <typename Association>
1534 void SM_overlayer<Map>::
subdivide(const Map * M0,const Map * M1,Association & A,bool with_trivial_segments)1535 subdivide(const Map* M0, const Map* M1,
1536 Association& A,
1537 bool with_trivial_segments)
1538 {
1539 PI[0] = SM_const_decorator(M0);
1540 PI[1] = SM_const_decorator(M1);
1541
1542 bool compute_halfsphere[3][2];
1543 int cs=0;
1544
1545 Seg_list L;
1546 Seg_map From;
1547 for (int i=0; i<2; ++i) {
1548 SVertex_const_iterator v;
1549 CGAL_forall_svertices(v,PI[i]) {
1550 CGAL_NEF_TRACEN(v->point() << " from " << i << " mark " << v->mark());
1551 if ( !PI[i].is_isolated(v) ) continue;
1552 cs = -1;
1553 L.push_back(trivial_segment(PI[i],v));
1554 From[--L.end()] = Seg_info(v,i);
1555 }
1556 SHalfedge_const_iterator e;
1557 CGAL_forall_sedges(e,PI[i]) {
1558 if ( e->source() == e->target() ) {
1559 if(with_trivial_segments) {
1560 CGAL_NEF_TRACEN("trivial segment " << e->source()->point());
1561 v = e->source();
1562 L.push_back(trivial_segment(PI[i],v));
1563 From[--L.end()] = Seg_info(v,i);
1564 } else {
1565 CGAL_NEF_TRACEN("once around " << e->source()->point());
1566 Seg_pair p = two_segments(PI[i],e);
1567 L.push_back(p.first);
1568 L.push_back(p.second);
1569 From[--L.end()] = From[--(--L.end())] = Seg_info(e,i);
1570 }
1571 } else {
1572 CGAL_NEF_TRACEN("normal segment " << e->source()->point());
1573 L.push_back(segment(PI[i],e));
1574 From[--L.end()] = Seg_info(e,i);
1575 }
1576 }
1577 if ( PI[i].has_shalfloop() ) {
1578 cs = -1;
1579 CGAL_NEF_TRACEN("loop ");
1580 SHalfloop_const_handle shl = PI[i].shalfloop();
1581 Seg_pair p = two_segments(PI[i],shl);
1582 L.push_back(p.first);
1583 L.push_back(p.second.opposite());
1584 From[--L.end()] = From[--(--L.end())] =
1585 Seg_info(shl,i);
1586 }
1587 }
1588
1589 CGAL_assertion_code(typename Seg_list::iterator it);
1590 CGAL_assertion_code(CGAL_forall_iterators(it,L) CGAL_NEF_TRACEN(" "<<*it));
1591
1592 #ifdef CGAL_NEF3_SPHERE_SWEEP_OPTIMIZATION_OFF
1593 cs = -1;
1594 #endif
1595 if(cs != -1)
1596 cs = check_sphere(L, compute_halfsphere);
1597 else {
1598 compute_halfsphere[2][0]=true;
1599 compute_halfsphere[2][1]=true;
1600 }
1601
1602 CGAL_NEF_TRACEN("compute_halfsphere\n cs = " << cs);
1603 for(int i=0; i<6; ++i)
1604 CGAL_NEF_TRACEN(" " << i << " : " << compute_halfsphere[i/2][i%2]);
1605 Seg_list L_pos,L_neg;
1606
1607 switch(cs) {
1608 case 1:
1609 partition_to_halfsphere(L.begin(), L.end(), L_pos, From,
1610 Sphere_circle(1,0,0), Sphere_circle(0,0,-1),
1611 compute_halfsphere[0][1]);
1612 break;
1613 case 0:
1614 partition_to_halfsphere(L.begin(), L.end(), L_neg, From,
1615 Sphere_circle(-1,0,0), Sphere_circle(0,0,-1),
1616 compute_halfsphere[0][0]);
1617 break;
1618 case 3:
1619 partition_to_halfsphere(L.begin(), L.end(), L_pos, From,
1620 Sphere_circle(0,1,0), Sphere_circle(1,0,0),
1621 compute_halfsphere[1][1]);
1622 break;
1623 case 2:
1624 partition_to_halfsphere(L.begin(), L.end(), L_neg, From,
1625 Sphere_circle(0,-1,0), Sphere_circle(1,0,0),
1626 compute_halfsphere[1][0]);
1627 break;
1628 case 5:
1629 partition_to_halfsphere(L.begin(), L.end(), L_pos, From,
1630 Sphere_circle(0,0,1), Sphere_circle(1,0,0),
1631 compute_halfsphere[2][1]);
1632 break;
1633 case 4:
1634 partition_to_halfsphere(L.begin(), L.end(), L_neg, From,
1635 Sphere_circle(0,0,-1), Sphere_circle(1,0,0),
1636 compute_halfsphere[2][0]);
1637 break;
1638 case -1:
1639 partition_to_halfsphere(L.begin(), L.end(), L_pos, From,
1640 Sphere_circle(0,0,1), Sphere_circle(1,0,0), true);
1641 partition_to_halfsphere(L.begin(), L.end(), L_neg, From,
1642 Sphere_circle(0,0,-1), Sphere_circle(1,0,0), true);
1643 break;
1644 default: CGAL_error_msg( "wrong value");
1645 }
1646
1647 cs = cs==-1 ? 2 : cs/2;
1648
1649 #ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
1650 timer_sphere_sweeps.start();
1651 #endif
1652
1653 typedef SMO_from_sm<Self,Seg_iterator,Seg_info> SM_output;
1654 typedef typename Sphere_kernel::Positive_halfsphere_geometry PH_geometry;
1655 typedef typename Sphere_kernel::Negative_halfsphere_geometry NH_geometry;
1656
1657 typedef CGAL::Segment_overlay_traits<
1658 Seg_iterator, SM_output, PH_geometry> PHS_traits;
1659 typedef CGAL::generic_sweep<PHS_traits> Positive_halfsphere_sweep;
1660
1661 typedef CGAL::Segment_overlay_traits<
1662 Seg_iterator, SM_output, NH_geometry> NHS_traits;
1663 typedef CGAL::generic_sweep<NHS_traits> Negative_halfsphere_sweep;
1664
1665 typedef typename PHS_traits::INPUT Input_range;
1666
1667 SVertex_handle v;
1668 SHalfedge_handle e;
1669 SM_output O(*this,PI,From);
1670
1671 if(compute_halfsphere[cs][0]) {
1672 PH_geometry phg(cs);
1673
1674 /*
1675 // the following is only needed for indexed items
1676 SHalfedge_const_handle se;
1677 SHalfloop_const_handle sl;
1678 for(Seg_iterator it=L_pos.begin(); it!=L_pos.end();++it) {
1679 CGAL_NEF_TRACEN("pos " << *it);
1680 if(phg.compare_xy(it->target(),it->source())<0) {
1681 Object_handle o = From[it]._o;
1682 if(CGAL::assign(se, o)) {
1683 if(it->sphere_circle() == se->circle())
1684 From[it] = Seg_info(se->twin(), From[it]._from);
1685 } else if(CGAL::assign(sl, o)) {
1686 if(it->sphere_circle() == sl->circle())
1687 From[it] = Seg_info(sl->twin(), From[it]._from);
1688 }
1689 }
1690 }
1691 */
1692
1693 Positive_halfsphere_sweep SP(
1694 Input_range(L_pos.begin(),L_pos.end()),O,phg);
1695 SP.sweep();
1696 v=--this->svertices_end(); e=--this->shalfedges_end();
1697 #ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
1698 number_of_sphere_sweeps++;
1699 #endif
1700 }
1701
1702 if(compute_halfsphere[cs][1]) {
1703 NH_geometry nhg(cs);
1704
1705 /*
1706 SHalfedge_const_handle se;
1707 SHalfloop_const_handle sl;
1708 for(Seg_iterator it=L_neg.begin(); it!=L_neg.end();++it) {
1709 CGAL_NEF_TRACEN("neg " << *it);
1710 if(nhg.compare_xy(it->target(),it->source())<0) {
1711 Object_handle o = From[it]._o;
1712 if(CGAL::assign(se, o)) {
1713 if(it->sphere_circle() == se->circle())
1714 From[it] = Seg_info(se->twin(), From[it]._from);
1715 } else if(CGAL::assign(sl, o)) {
1716 if(it->sphere_circle() == sl->circle())
1717 From[it] = Seg_info(sl->twin(), From[it]._from);
1718 }
1719 }
1720 }
1721 */
1722
1723 Negative_halfsphere_sweep SM(
1724 Input_range(L_neg.begin(),L_neg.end()),O,
1725 nhg);
1726 SM.sweep();
1727 #ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
1728 number_of_sphere_sweeps++;
1729 #endif
1730 }
1731
1732 #ifdef CGAL_NEF3_TIMER_SPHERE_SWEEPS
1733 timer_sphere_sweeps.stop();
1734 #endif
1735
1736 if(compute_halfsphere[cs][0]) {
1737 ++v;
1738 ++e;
1739 }
1740 else {
1741 v = this->svertices_begin();
1742 e = this->shalfedges_begin();
1743 }
1744
1745 if(compute_halfsphere[cs][0])
1746 create_face_objects(this->shalfedges_begin(), e, this->svertices_begin(), v, O,
1747 PH_geometry(cs));
1748 if(compute_halfsphere[cs][1])
1749 create_face_objects(e, this->shalfedges_end(), v, this->svertices_end(), O,
1750 NH_geometry(cs));
1751
1752 CGAL_forall_sedges(e,*this) {
1753 e->circle() = Sphere_circle(e->source()->point(), e->twin()->source()->point());
1754 e->twin()->circle() = e->circle().opposite();
1755 CGAL_NEF_TRACEN(PH(e) << " with circle " << e->circle());
1756 }
1757
1758 std::vector<Mark> mohs(4);
1759 SM_point_locator L0(M0);
1760 SM_point_locator L1(M1);
1761
1762 L0.marks_of_halfspheres(mohs, 0, cs);
1763 L1.marks_of_halfspheres(mohs, 2, cs);
1764
1765 CGAL_NEF_TRACEN("mohs[0]=" << mohs[0]);
1766 CGAL_NEF_TRACEN("mohs[1]=" << mohs[1]);
1767 CGAL_NEF_TRACEN("mohs[2]=" << mohs[2]);
1768 CGAL_NEF_TRACEN("mohs[3]=" << mohs[3]);
1769
1770 CGAL_NEF_TRACEN("compute_halfsphrere\n cs = " << cs <<
1771 "\n [cs][0] = " << compute_halfsphere[cs][0] <<
1772 "\n [cs][1] = " << compute_halfsphere[cs][1]);
1773 /*
1774 SVertex_iterator svii;
1775 CGAL_forall_svertices(svii, *this) {
1776 SVertex_const_handle vs;
1777 SHalfedge_const_handle es;
1778 if(CGAL::assign(vs, supp_object(svii,0)))
1779 std::cerr << svii->point() << " supported by svertex " << vs->point() << std::endl;
1780 else if(CGAL::assign(es, supp_object(svii,0)))
1781 std::cerr << svii->point() << " supported by sedge" << std::endl;
1782 else
1783 std::cerr << svii->point() << " is neither supported by svertex or sedge" << std::endl;
1784 if(CGAL::assign(vs, supp_object(svii,1)))
1785 std::cerr << svii->point() << " supported by svertex " << vs->point() << std::endl;
1786 else if(CGAL::assign(es, supp_object(svii,1)))
1787 std::cerr << svii->point() << " supported by sedge" << std::endl;
1788 else
1789 std::cerr << svii->point() << " is neither supported by svertex or sedge" << std::endl;
1790 }
1791 */
1792 if(compute_halfsphere[cs][0])
1793 complete_face_support(this->svertices_begin(), v, O, mohs, 0,
1794 compute_halfsphere[cs][1]);
1795 if(compute_halfsphere[cs][1])
1796 complete_face_support(v, this->svertices_end(), O, mohs, 1,
1797 compute_halfsphere[cs][0]);
1798
1799 complete_sface_marks();
1800
1801 // DEBUG CODE: to do: have all svertices a halfedge below associated?
1802 CGAL_NEF_TRACEN("Vertex info after swep");
1803 CGAL_assertion_code(SVertex_iterator svi);
1804 #ifdef CGAL_I_DO_WANT_TO_USE_GENINFO
1805 CGAL_assertion_code(
1806 for(svi=this->svertices_begin(); svi!=this->svertices_end(); svi++) {
1807 CGAL_NEF_TRACEN("vertex "<<svi->point() <<" info "<<info(svi) << " marks "<<mark(svi,0)<<" "<<mark(svi,1));
1808 }
1809 )
1810 #else
1811 CGAL_assertion_code(
1812 for(svi=this->svertices_begin(); svi!=this->svertices_end(); svi++) {
1813 CGAL_NEF_TRACEN("vertex "<<svi->point() << " marks "<<mark(svi,0)<<" "<<mark(svi,1));
1814 }
1815 )
1816 #endif
1817
1818
1819 transfer_data(A);
1820
1821 if(compute_halfsphere[cs][0] && compute_halfsphere[cs][1])
1822 merge_halfsphere_maps(this->svertices_begin(),v,O);
1823 else
1824 set_outer_face_mark(compute_halfsphere[cs][1], mohs);
1825
1826 CGAL_assertion_code(this->check_integrity_and_topological_planarity());
1827
1828 CGAL_NEF_TRACEN("subdivided");
1829 CGAL_assertion_code(CGAL_forall_svertices(v,*this) CGAL_NEF_TRACEN(PH(v)));
1830 }
1831
1832 template <typename Map>
1833 template <typename Association>
1834 void SM_overlayer<Map>::
transfer_data(Association & A)1835 transfer_data(Association& A) {
1836
1837 SVertex_iterator sv;
1838 SHalfedge_handle se;
1839 SVertex_const_handle sv0,sv1;
1840 SHalfedge_const_handle se0, se1;
1841 SHalfloop_const_handle sl0, sl1;
1842
1843 CGAL_forall_svertices(sv, *this) {
1844 // std::cerr << "svertex " << sv->point() << std::endl;
1845 Object_handle o0 = supp_object(sv,0), o1 = supp_object(sv,1);
1846 if(o0.empty()) {
1847 if(CGAL::assign(sv1, o1))
1848 A.handle_support(sv, sv1);
1849 else
1850 continue;
1851 } else if(CGAL::assign(se0, o0)) {
1852 if(o1.empty())
1853 continue;
1854 else if(assign(se1, o1))
1855 A.handle_support(sv, se0, se1);
1856 else if(CGAL::assign(sv1, o1))
1857 A.handle_support(sv, se0, sv1);
1858 else if(CGAL::assign(sl1, o1))
1859 A.handle_support(sv, se0, sl1);
1860 else
1861 CGAL_error_msg( "wrong handle");
1862 } else if(CGAL::assign(sv0, o0)) {
1863 if(o1.empty())
1864 A.handle_support(sv, sv0);
1865 else if(CGAL::assign(se1, o1))
1866 A.handle_support(sv, sv0, se1);
1867 else if(CGAL::assign(sv1, o1))
1868 A.handle_support(sv, sv0, sv1);
1869 else if(CGAL::assign(sl1, o1))
1870 A.handle_support(sv, sv0, sl1);
1871 else
1872 CGAL_error_msg( "wrong handle");
1873 } else if(CGAL::assign(sl0, o0)) {
1874 if(o1.empty())
1875 continue;
1876 else if(CGAL::assign(sv1, o1))
1877 A.handle_support(sv, sl0, sv1);
1878 else if(CGAL::assign(se1, o1))
1879 A.handle_support(sv, sl0, se1);
1880 else if(CGAL::assign(sl1, o1))
1881 A.handle_support(sv, sl0, sl1);
1882 } else
1883 CGAL_error_msg( "wrong handle");
1884 }
1885
1886 CGAL_forall_sedges(se, *this) {
1887 CGAL_assertion(is_forward(se));
1888 Object_handle o0 = supp_object(se,0), o1 = supp_object(se,1);
1889 if(o0.empty()) {
1890 if(assign(se1, o1))
1891 A.handle_support(se, se1);
1892 else if(assign(sl1, o1))
1893 A.handle_support(se, sl1);
1894 else
1895 continue; // CGAL_error_msg( "wrong handle");
1896 } else if(assign(se0, o0)) {
1897 if(o1.empty())
1898 A.handle_support(se, se0);
1899 else if(assign(se1, o1))
1900 A.handle_support(se, se0, se1);
1901 else if(assign(sl1, o1))
1902 A.handle_support(se, se0, sl1);
1903 else
1904 CGAL_error_msg( "wrong handle");
1905 } else if(assign(sl0, o0)) {
1906 if(o1.empty())
1907 A.handle_support(se, sl0);
1908 else if(assign(se1, o1))
1909 A.handle_support(se, sl0, se1);
1910 else if(assign(sl1, o1))
1911 A.handle_support(se, sl0, sl1);
1912 else
1913 CGAL_error_msg( "wrong handle");
1914 } else
1915 CGAL_error_msg( "wrong handle");
1916 }
1917 }
1918
1919 template <typename Map>
1920 void SM_overlayer<Map>::
set_outer_face_mark(int offset,const std::vector<Mark> & mohs)1921 set_outer_face_mark(int offset, const std::vector<Mark>& mohs) {
1922
1923 SFace_handle sf = this->new_sface();
1924 assoc_info(sf);
1925 mark(sf, 0) = mohs[offset];
1926 mark(sf, 1) = mohs[offset+2];
1927
1928 SHalfedge_iterator e;
1929 CGAL_forall_shalfedges(e, *this) {
1930 if ( e->incident_sface() != SFace_handle() ) continue;
1931 link_as_face_cycle(e,sf);
1932 }
1933
1934 SVertex_handle v;
1935 CGAL_forall_svertices(v, *this) {
1936 if(!is_isolated(v) || v->incident_sface() != SFace_handle()) continue;
1937 link_as_isolated_vertex(v,sf);
1938 }
1939 }
1940
1941 template <typename Map>
1942 template <typename Iterator, typename T>
1943 void SM_overlayer<Map>::
partition_to_halfsphere(Iterator start,Iterator beyond,Seg_list & L,CGAL::Unique_hash_map<Iterator,T> & M,Sphere_circle xycircle,Sphere_circle yzcircle,bool include_equator)1944 partition_to_halfsphere(Iterator start, Iterator beyond, Seg_list& L,
1945 CGAL::Unique_hash_map<Iterator,T>& M,
1946 Sphere_circle xycircle, Sphere_circle yzcircle,
1947 bool include_equator) const
1948 { CGAL_NEF_TRACEN("partition_to_halfsphere ");
1949 // CGAL_assertion(pos!=0);
1950 Sphere_segment s1,s2;
1951 // Sphere_circle xycircle(0,0,pos);
1952 if(include_equator) {
1953 while ( start != beyond) {
1954 int i = start->intersection(xycircle,s1,s2);
1955 CGAL_NEF_TRACEN("segment " << start->source() << " " << start->target());
1956 if (i>1) {
1957 L.push_back(s2); M[--L.end()] = M[start];
1958 CGAL_NEF_TRACEN(">1 " << s2.source() << " " << s2.target());
1959 }
1960 if (i>0) {
1961 L.push_back(s1); M[--L.end()] = M[start];
1962 CGAL_NEF_TRACEN(">0 " << s1.source() << " " << s1.target());
1963 }
1964 ++start;
1965 }
1966 }
1967 else {
1968 while(start != beyond) {
1969 L.push_back(*start);
1970 M[--L.end()] = M[start];
1971 ++start;
1972 }
1973 }
1974
1975 // now all segments are split into hemispheres
1976 // we still have to:
1977 // - split segments containing our special poles y^-, y^+
1978 // - split halfcircles
1979 // - add four equator segments
1980
1981 // Sphere_circle yzcircle(1,0,0);
1982 typename Seg_list::iterator it, itl;
1983
1984 CGAL_forall_iterators(it,L) { CGAL_NEF_TRACEN(" "<<*it);
1985 if ( equal_as_sets(it->sphere_circle(),xycircle) ) {
1986 CGAL_NEF_TRACEN(" splitting xy seg "<<*it);
1987 bool added=false;
1988 int n1 = it->intersection(yzcircle,s1,s2);
1989 if (n1 > 1 && !s2.is_degenerate()) {
1990 M[ L.insert(it,s2) ] = M[it];
1991 added=true;
1992 CGAL_NEF_TRACEN(">1 " << s2.source() << " " << s2.target());
1993 }
1994 if (n1 > 0 && !s1.is_degenerate()) {
1995 M[ L.insert(it,s1) ] = M[it];
1996 added = true;
1997 CGAL_NEF_TRACEN(">1 " << s1.source() << " " << s1.target());
1998 }
1999 int n2 = it->intersection(yzcircle.opposite(),s1,s2);
2000 if (n2 > 1 && !s2.is_degenerate()) {
2001 M[ L.insert(it,s2) ] = M[it];
2002 added=true;
2003 CGAL_NEF_TRACEN(">1 " << s2.source() << " " << s2.target());
2004 }
2005 if (n2 > 0 && !s1.is_degenerate()) {
2006 M[ L.insert(it,s1) ] = M[it];
2007 added=true;
2008 CGAL_NEF_TRACEN(">1 " << s1.source() << " " << s1.target());
2009 }
2010 if(added) {
2011 itl = it; --it; M[itl] = T(); L.erase(itl);
2012 }
2013 // at least one item was appended
2014 }
2015 }
2016
2017 CGAL_forall_iterators(it,L) {
2018 if ( it->is_halfcircle() ) {
2019 CGAL_NEF_TRACEN(" splitting halfcircle "<<*it);
2020 Sphere_segment s1,s2;
2021 it->split_halfcircle(s1,s2);
2022 CGAL_NEF_TRACEN(" into " << s1);
2023 CGAL_NEF_TRACEN(" into " << s2);
2024 *it = s2;
2025 M[ L.insert(it,s1) ] = M[it];
2026 }
2027 }
2028
2029 if(include_equator) {
2030 // append 4 xy-equator segments:
2031 Sphere_point S(0,-1,0),N(0,1,0);
2032 Sphere_segment sp(S,N,xycircle);
2033 Sphere_segment sm(S,N,xycircle.opposite());
2034 Sphere_segment s[4];
2035 sp.split_halfcircle(s[0],s[1]);
2036 sm.split_halfcircle(s[2],s[3]);
2037 L.insert(L.end(),s,s+4);
2038 }
2039 }
2040
2041 template <typename Map>
2042 template <typename Below_accessor, typename Halfsphere_geometry>
2043 void SM_overlayer<Map>::
create_face_objects(SHalfedge_iterator e_start,SHalfedge_iterator e_end,SVertex_iterator v_start,SVertex_iterator v_end,const Below_accessor & D,const Halfsphere_geometry & SG)2044 create_face_objects(SHalfedge_iterator e_start, SHalfedge_iterator e_end,
2045 SVertex_iterator v_start, SVertex_iterator v_end,
2046 const Below_accessor& D,
2047 const Halfsphere_geometry& SG)
2048 {
2049 CGAL_NEF_TRACEN("create_face_objects()");
2050 if(e_start != e_end) {
2051 CGAL::Unique_hash_map<SHalfedge_handle,int> SFaceCycle(-1);
2052 std::vector<SHalfedge_handle> MinimalSHalfedge;
2053 SHalfedge_around_sface_circulator hfc(last_out_edge(v_start)),hend(hfc);
2054 CGAL_NEF_TRACEN("equator cycle "<<PH(hfc));
2055 CGAL_For_all(hfc,hend) SFaceCycle[hfc]=0; // outer face cycle = 0
2056 MinimalSHalfedge.push_back(first_out_edge(v_start)->twin());
2057 int i=1;
2058 for (SHalfedge_iterator e = e_start; e != e_end; ++e) {
2059 if ( SFaceCycle[e] >= 0 ) continue; // already assigned
2060 SHalfedge_around_sface_circulator hfc(e),hend(hfc);
2061 SHalfedge_handle e_min = e;
2062 CGAL_NEF_TRACEN("");
2063 CGAL_NEF_TRACEN(" face cycle numbering "<<i);
2064 CGAL_For_all(hfc,hend) {
2065 SFaceCycle[hfc]=i; // assign face cycle number
2066 if (hfc->twin()->source() == e_min->twin()->source()) {
2067 Sphere_point p1 = hfc->source()->point(),
2068 p2 = hfc->twin()->source()->point(),
2069 p3 = hfc->snext()->twin()->source()->point();
2070 if ( SG.orientation(p1,p2,p3) <= 0 )
2071 e_min = hfc;
2072 } else if ( SG.compare_xy(hfc->twin()->source()->point(), e_min->twin()->source()->point()) < 0 )
2073 e_min = hfc;
2074 CGAL_NEF_TRACEN(PH(hfc));
2075 } CGAL_NEF_TRACEN("");
2076 MinimalSHalfedge.push_back(e_min);
2077 ++i;
2078 }
2079
2080 for (int j=1; j<i; ++j) {
2081 SHalfedge_handle e = MinimalSHalfedge[j];
2082 CGAL_NEF_TRACEN(" face cycle "<<j<<" minimal halfedge "<<PH(e));
2083 Sphere_point p1 = e->source()->point(),
2084 p2 = e->twin()->source()->point(),
2085 p3 = e->snext()->twin()->source()->point();
2086 if ( SG.orientation(p1,p2,p3) > 0 ) { // left_turn => outer face cycle
2087 SFace_handle f = this->new_sface();
2088 link_as_face_cycle(e,f);
2089 CGAL_NEF_TRACEN(" creating new face object "<<&*f<<" bd "<<&*e);
2090 }
2091 }
2092
2093 for (SHalfedge_iterator e = e_start; e != e_end; ++e) {
2094 if ( e->incident_sface() != SFace_handle() ) continue;
2095 if ( SFaceCycle[e] == 0 ) continue;
2096 CGAL_NEF_TRACEN("linking hole "<<PH(e));
2097 SFace_handle f = determine_face(e,MinimalSHalfedge,SFaceCycle,D);
2098 if(f != SFace_handle())
2099 link_as_face_cycle(e,f);
2100 }
2101 }
2102
2103 for (SVertex_iterator v = v_start; v != v_end; ++v) {
2104 if ( !is_isolated(v) ) continue;
2105 SHalfedge_handle e_below = D.halfedge_below(v);
2106 CGAL_assertion( e_below != SHalfedge_handle() || e_start == e_end );
2107 if(e_below != SHalfedge_handle())
2108 link_as_isolated_vertex(v,e_below->incident_sface());
2109 }
2110
2111 }
2112
2113 template <typename Map>
2114 template <typename Below_accessor>
2115 void SM_overlayer<Map>::
complete_face_support(SVertex_iterator v_start,SVertex_iterator v_end,const Below_accessor &,std::vector<Mark> & mohs,int offset,bool both)2116 complete_face_support(SVertex_iterator v_start, SVertex_iterator v_end,
2117 const Below_accessor& , std::vector<Mark>& mohs, int offset, bool both) const
2118 { CGAL_NEF_TRACEN("complete_face_support");
2119 for (SVertex_iterator v = v_start; v != v_end; ++v) {
2120 CGAL_NEF_TRACEN("VERTEX = "<<PH(v));
2121 Mark m_buffer[2] {};
2122 SHalfedge_handle e_below = halfedge_below(v);
2123 if ( v == v_start ) {
2124 for (int i=0; i<2; ++i){
2125 m_buffer[i] = mohs[offset+2*i];
2126 }
2127 } else if ( e_below != SHalfedge_handle() ) {
2128 for (int i=0; i<2; ++i) {
2129 CGAL_NEF_TRACEN("edge below "<< PH(e_below) << " " << mark(e_below,i));
2130 m_buffer[i] = incident_mark(e_below,i);
2131 }
2132 } else { // e_below does not exist
2133 // CGAL_assertion( v->point().hz() == 0 &&
2134 // ( offset == 0 ? (v->point().hx() >= 0) : (v->point().hx()<=0)) );
2135 if(!is_isolated(v)) {
2136 if(!both) {
2137 for (int i=0; i<2; ++i)
2138 m_buffer[i] = mohs[offset+2*i];
2139 CGAL_NEF_TRACEN("no edge below ");
2140 } else {
2141 for (int i=0; i<2; ++i)
2142 m_buffer[i] = incident_mark(first_out_edge(v)->sprev(),i);
2143 }
2144 }
2145 } CGAL_NEF_TRACEN(" faces right-below "<<m_buffer[0]<<" "<<m_buffer[1]);
2146
2147 for (int i=0; i<2; ++i) {
2148 Object_handle o = supp_object(v,i);
2149 if ( o.empty() ) {
2150 CGAL_NEF_TRACEN("no vertex support");
2151 mark(v,i) = m_buffer[i]; continue;
2152 }
2153 SVertex_const_handle vs;
2154 SHalfedge_const_handle es;
2155 SHalfloop_const_handle ls;
2156 if ( CGAL::assign(vs,o) ) {
2157 CGAL_NEF_TRACEN("support by svertex");
2158 mark(v,i) = vs->mark(); continue;
2159 }
2160 if ( CGAL::assign(es,supp_object(v,i)) ) {
2161 CGAL_NEF_TRACEN("support by sedge");
2162 if ( es->source()->point() == v->point() )
2163 { mark(v,i) = es->source()->mark(); continue; }
2164 if ( es->target()->point() == v->point() )
2165 { mark(v,i) = es->target()->mark(); continue; }
2166 mark(v,i) = es->mark(); continue;
2167 }
2168 if ( CGAL::assign(ls,o) ) {
2169 mark(v,i) = ls->mark();
2170 CGAL_NEF_TRACEN("loop " << ls->circle()); continue; }
2171 CGAL_error_msg("wrong handle");
2172 } CGAL_NEF_TRACEN(" vertex marks "<<mark(v,0)<<" "<<mark(v,1));
2173
2174 if ( is_isolated(v) ) continue;
2175 SHalfedge_around_svertex_circulator e(first_out_edge(v)), hend(e);
2176 CGAL_For_all(e,hend) {
2177 if ( !is_forward(e) ) break;
2178 CGAL_NEF_TRACEN(" forward edge "<<PH(e));
2179 for (int i=0; i<2; ++i) {
2180 if ( ! supp_object(e,i).empty() ) {
2181 SHalfedge_const_handle ei;
2182 if ( CGAL::assign(ei,supp_object(e,i)) ) {
2183 if (!equal_not_opposite(ei->circle(),e->circle()))
2184 ei = ei->twin();
2185 CGAL_assertion( ei->circle() == e->circle() );
2186 CGAL_NEF_TRACEN(" supporting edge "<<i<<" "<<PH(ei));
2187 incident_mark(e->twin(),i) =
2188 ei->twin()->incident_sface()->mark();
2189 mark(e,i) = mark(e->twin(),i) = ei->mark();
2190 incident_mark(e,i) = m_buffer[i] =
2191 ei->incident_sface()->mark();
2192 }
2193 SHalfloop_const_handle li;
2194 if ( CGAL::assign(li,supp_object(e,i)) ) {
2195 if (!equal_not_opposite(li->circle(),e->circle()))
2196 li = li->twin();
2197 CGAL_assertion( li->circle() == e->circle() );
2198 CGAL_NEF_TRACEN(" supporting loop "<<i<<" "<<PH(li));
2199 incident_mark(e->twin(),i) =
2200 li->twin()->incident_sface()->mark();
2201 mark(e,i) = mark(e->twin(),i) = li->mark();
2202 incident_mark(e,i) = m_buffer[i] =
2203 li->incident_sface()->mark();
2204 }
2205 } else { CGAL_NEF_TRACEN(" support from face below "<<i);
2206 incident_mark(e->twin(),i) = mark(e,i) = mark(e->twin(),i) =
2207 incident_mark(e,i) = m_buffer[i];
2208 }
2209 } CGAL_NEF_TRACEN(" face marks "<<m_buffer[0]<<" "<<m_buffer[1]);
2210 }
2211
2212 CGAL_NEF_TRACEN(" mark of "<<PH(v)<<" "<<mark(v,0)<<" "<<mark(v,1));
2213 }
2214 }
2215
2216 template <typename Map>
complete_sface_marks()2217 void SM_overlayer<Map>::complete_sface_marks() const {
2218 SFace_iterator f;
2219 for (f = this->sfaces_begin(); f != this->sfaces_end(); ++f) {
2220 assoc_info(f);
2221 SFace_cycle_iterator boundary_object(f->sface_cycles_begin());
2222 if (!boundary_object.is_shalfedge() )
2223 CGAL_error_msg("Outer face cycle should be first.");
2224 SHalfedge_handle e(boundary_object);
2225 for (int i=0; i<2; ++i) mark(f,i) = incident_mark(e,i);
2226 }
2227 }
2228
2229 template <typename Map>
2230 template <typename Mark_accessor>
2231 void SM_overlayer<Map>::
merge_nodes(SHalfedge_handle e1,SHalfedge_handle e2,const Mark_accessor & D)2232 merge_nodes(SHalfedge_handle e1, SHalfedge_handle e2,
2233 const Mark_accessor& D)
2234 {
2235 SVertex_handle v1 = e1->source(), v2 = e2->target();
2236 CGAL_NEF_TRACEN("merge_nodes "<<PH(v1)<<PH(v2));
2237 CGAL_assertion(v1->point()==v2->point());
2238 SHalfedge_handle ep1 = e1->sprev(), en2 = e2->snext();
2239 SHalfedge_around_svertex_circulator eav(out_edges(v2)),ee(eav);
2240 CGAL_For_all(eav,ee) { set_source(eav,v1); }
2241 link_as_prev_next_pair(e2,e1);
2242 link_as_prev_next_pair(ep1,en2);
2243 D.assert_equal_marks(v1,v2);
2244 D.discard_info(v2);
2245 delete_vertex_only(v2);
2246 }
2247
2248 template <typename Map>
2249 template <typename Mark_accessor>
2250 void SM_overlayer<Map>::
merge_halfsphere_maps(SVertex_handle v1,SVertex_handle v2,const Mark_accessor & D)2251 merge_halfsphere_maps(SVertex_handle v1, SVertex_handle v2,
2252 const Mark_accessor& D)
2253 { CGAL_NEF_TRACEN("merging halfspheres "<<PH(v1)<<PH(v2));
2254 CGAL_assertion(v1->point()==v2->point());
2255 std::list<SHalfedge_pair> L_equator;
2256 SHalfedge_around_sface_circulator
2257 ep(last_out_edge(v1)), en(first_out_edge(v2)->twin());
2258 do {
2259 L_equator.push_back(SHalfedge_pair(ep,en));
2260 merge_nodes(ep,en,D); ++ep; --en;
2261 } while ( ep->source() != v1 );
2262
2263 typename std::list<SHalfedge_pair>::iterator it;
2264 CGAL_forall_iterators(it,L_equator) {
2265 SHalfedge_handle e1 = it->first, e2 = it->second;
2266 SHalfedge_handle e1t = e1->twin(), e2t = e2->twin();
2267 CGAL_NEF_TRACEV(PH(e1));CGAL_NEF_TRACEV(PH(e2));
2268 SHalfedge_handle e2tp = e2t->sprev();
2269 SHalfedge_handle e2tn = e2t->snext();
2270 link_as_prev_next_pair(e2tp,e1);
2271 link_as_prev_next_pair(e1,e2tn);
2272 SFace_handle f = e2t->incident_sface();
2273 if ( is_sm_boundary_object(e2t) )
2274 { undo_sm_boundary_object(e2t,f); store_sm_boundary_object(e1,f); }
2275 set_face(e1,f);
2276 if ( e2 == first_out_edge(e2->source()) )
2277 set_first_out_edge(e2->source(),e1t);
2278 D.discard_info(e2);
2279 delete_edge_pair_only(e2);
2280 }
2281 }
2282
2283 template <typename Map>
2284 template <typename Selection>
2285 void SM_overlayer<Map>::
select(const Selection & SP)2286 select(const Selection& SP) const
2287 {
2288 SVertex_iterator v;
2289 CGAL_forall_svertices(v,*this) {
2290 v->mark() = SP(mark(v,0),mark(v,1));
2291 discard_info(v);
2292 }
2293 SHalfedge_iterator e;
2294 CGAL_forall_sedges(e,*this) {
2295 e->mark() = SP(mark(e,0),mark(e,1));
2296 e->twin()->mark() = SP(mark(e->twin(),0),mark(e->twin(),1));
2297 CGAL_assertion(e->mark() == e->twin()->mark());
2298 discard_info(e);
2299 }
2300 SFace_iterator f;
2301 CGAL_forall_sfaces(f,*this) {
2302 f->mark() = SP(mark(f,0),mark(f,1));
2303 discard_info(f);
2304 }
2305
2306 }
2307
2308 template <typename Map>
simplify()2309 void SM_overlayer<Map>::simplify()
2310 {
2311 CGAL_NEF_TRACEN("simplifying");
2312
2313 typedef typename CGAL::Union_find<SFace_handle>::handle Union_find_handle;
2314 CGAL::Unique_hash_map< SFace_handle, Union_find_handle> Pitem(nullptr);
2315 CGAL::Unique_hash_map< SVertex_handle, Union_find_handle> Vitem(nullptr);
2316 CGAL::Union_find< SFace_handle> UF;
2317
2318 SFace_iterator f;
2319 CGAL_forall_sfaces(f,*this) {
2320 Pitem[f] = UF.make_set(f);
2321 clear_face_cycle_entries(f);
2322 }
2323
2324 if ( this->has_shalfloop() ) {
2325 SHalfloop_handle l = this->shalfloop();
2326 SFace_handle f = *(UF.find(Pitem[l->incident_sface()]));
2327 link_as_loop(l,f);
2328 f = *(UF.find(Pitem[l->twin()->incident_sface()]));
2329 link_as_loop(l->twin(),f);
2330 }
2331
2332 SHalfedge_iterator e, en;
2333 for(e = this->shalfedges_begin(); e != this->shalfedges_end(); e = en) {
2334 en = e; ++en; if ( en==e->twin() ) ++en;
2335 CGAL_NEF_TRACEN("can simplify ? " << PH(e));
2336 CGAL_NEF_TRACEN(e->mark() << " " <<
2337 e->incident_sface()->mark() << " " <<
2338 e->twin()->incident_sface()->mark());
2339 if (( e->mark() == e->incident_sface()->mark() &&
2340 e->mark() == e->twin()->incident_sface()->mark())){
2341 CGAL_NEF_TRACEN("deleting "<<PH(e));
2342 if ( !UF.same_set(Pitem[e->incident_sface()],
2343 Pitem[e->twin()->incident_sface()]) ) {
2344
2345 UF.unify_sets( Pitem[e->incident_sface()],
2346 Pitem[e->twin()->incident_sface()] );
2347 CGAL_NEF_TRACEN("unioning disjoint faces");
2348 }
2349
2350 CGAL_NEF_TRACEN("is_closed_at_source " << is_closed_at_source(e) <<
2351 " " << is_closed_at_source(e->twin()));
2352
2353 if ( is_closed_at_source(e) )
2354 Vitem[e->source()] = Pitem[e->incident_sface()];
2355
2356 if ( is_closed_at_source(e->twin()))
2357 Vitem[e->target()] = Pitem[e->incident_sface()];
2358
2359 delete_edge_pair(e);
2360 }
2361 }
2362
2363 CGAL::Unique_hash_map<SHalfedge_handle,bool> linked(false);
2364 for (e = this->shalfedges_begin(); e != this->shalfedges_end(); ++e) {
2365 if ( linked[e] ) continue;
2366 SHalfedge_around_sface_circulator hfc(e),hend(hfc);
2367 SFace_handle f = *(UF.find( Pitem[e->incident_sface()]));
2368 CGAL_For_all(hfc,hend) { set_face(hfc,f); linked[hfc]=true; }
2369 store_sm_boundary_object(e,f);
2370 }
2371
2372 SVertex_iterator v,vn;
2373 for(v = this->svertices_begin(); v != this->svertices_end(); v=vn) {
2374 vn=v; ++vn;
2375 if ( is_isolated(v) ) {
2376
2377 if(Vitem[v] != nullptr) {
2378 set_face(v,*(UF.find(Vitem[v])));
2379 CGAL_NEF_TRACEN("incident face of " << PH(v) << " set to " << &*(v->incident_sface()));
2380 }
2381 else {
2382 set_face(v, *(UF.find(Pitem[v->incident_sface()])));
2383 CGAL_NEF_TRACEN("isolated svertex " << PH(v) <<
2384 " already has incident face " << &*(v->incident_sface()));
2385 }
2386
2387 if ( v->mark() == v->incident_sface()->mark() ) {
2388 CGAL_NEF_TRACEN("removing isolated vertex"<<PH(v));
2389 delete_vertex_only(v);
2390 }
2391 else
2392 store_sm_boundary_object(v,v->incident_sface()); // isolated, but should stay
2393 } else { // v not isolated
2394 SHalfedge_handle e2 = first_out_edge(v), e1 = e2->sprev();
2395 if ( has_outdeg_two(v) &&
2396 v->mark() == e1->mark() && v->mark() == e2->mark() &&
2397 e1->circle() == e2->circle() ) {
2398 CGAL_NEF_TRACEN("collinear at "<<PH(v)<<PH(e1)<<PH(e2));
2399 if ( e1 == e2 ){ CGAL_NEF_TRACEN("edge_to_loop"); convert_edge_to_loop(e1);}
2400 else {CGAL_NEF_TRACEN("merge_edge_pairs"); merge_edge_pairs_at_target(e1); }
2401 }
2402 }
2403 }
2404
2405 SFace_iterator fn;
2406 for (f = fn = this->sfaces_begin(); f != this->sfaces_end(); f=fn) {
2407 ++fn;
2408 Union_find_handle pit = Pitem[f];
2409 if ( UF.find(pit) != pit ) {
2410 CGAL_NEF_TRACEN("delete face " << &*f);
2411 delete_face_only(f);
2412 }
2413 }
2414 }
2415
2416 template <typename Map>
2417 template <typename Iterator>
2418 void SM_overlayer<Map>::
subdivide_segments(Iterator start,Iterator end)2419 subdivide_segments(Iterator start, Iterator end) const
2420 {
2421 typedef SMO_decorator<SM_decorator,Iterator> SM_output;
2422 typedef typename Sphere_kernel::Positive_halfsphere_geometry PH_geometry;
2423 typedef CGAL::Segment_overlay_traits<
2424 Iterator, SM_output, PH_geometry> PHS_traits;
2425 typedef CGAL::generic_sweep<PHS_traits> Positive_halfsphere_sweep;
2426
2427 typedef typename Sphere_kernel::Negative_halfsphere_geometry NH_geometry;
2428 typedef CGAL::Segment_overlay_traits<
2429 Iterator, SM_output, NH_geometry> NHS_traits;
2430 typedef CGAL::generic_sweep<NHS_traits> Negative_halfsphere_sweep;
2431
2432 std::list<Sphere_segment> Lp,Lm;
2433 partition_xy( start, end, Lp , +1);
2434 partition_xy( start, end, Lm , -1);
2435 // both lists initialized with four quarter segments
2436 // supporting the xy-equator thereby separating the
2437 // two halfspheres
2438 // all other segments in the range are split into their
2439 // connected components with respect to the xy-plane.
2440
2441 SVertex_handle v1,v2;
2442 SM_output O(*this);
2443 typedef typename PHS_traits::INPUT Input_range;
2444 Positive_halfsphere_sweep SP(Input_range(Lp.begin(),Lp.end()),O);
2445 SP.sweep();
2446 //CGAL_NEF_TRACEN("POS SWEEP\n"<<(dump(std::cerr),""));
2447 v1= this->vertices_begin(); v2=--this->vertices_end();
2448 Negative_halfsphere_sweep SM(Input_range(Lm.begin(),Lm.end()),O);
2449 SM.sweep();
2450 //CGAL_NEF_TRACEN("NEG SWEEP\n"<<(dump(std::cerr),""));
2451 ++v2;
2452 // now two CCs of sphere graph calculated
2453 // v1 = first node of CC in positive xy-sphere
2454 // v2 = first node of CC in negative xy-sphere
2455
2456 merge_halfsphere_maps(v1,v2,O);
2457 this->check_integrity_and_topological_planarity(false);
2458 }
2459
2460
2461 } //namespace CGAL
2462
2463 #endif //CGAL_SM_OVERLAYER_H
2464