1 // Copyright (c) 2005, 2006 Fernando Luis Cacciola Carballal. All rights reserved.
2 //
3 // This file is part of CGAL (www.cgal.org).
4 //
5 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Straight_skeleton_2/include/CGAL/Straight_skeleton_2/Polygon_offset_builder_2_impl.h $
6 // $Id: Polygon_offset_builder_2_impl.h 14644c4 2020-10-07T19:33:36+02:00 Mael Rouxel-Labbé
7 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
8 //
9 // Author(s) : Fernando Cacciola <fernando_cacciola@ciudad.com.ar>
10 //
11 #ifndef CGAL_POLYGON_OFFSET_BUILDER_2_IMPL_H
12 #define CGAL_POLYGON_OFFSET_BUILDER_2_IMPL_H 1
13
14 #include <CGAL/license/Straight_skeleton_2.h>
15
16 #include <algorithm>
17 #include <vector>
18
19 namespace CGAL {
20
21
22 template<class Ss, class Gt, class Cont, class Visitor>
Polygon_offset_builder_2(Ss const & aSs,Traits const & aTraits,Visitor const & aVisitor)23 Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::Polygon_offset_builder_2( Ss const& aSs, Traits const& aTraits, Visitor const& aVisitor )
24 :
25 mTraits (aTraits)
26 ,mVisitor(aVisitor)
27 {
28
29 int lMaxID = -1 ;
30
31 for ( Halfedge_const_handle lHE = aSs.halfedges_begin() ; lHE != aSs.halfedges_end() ; ++ lHE )
32 {
33 if ( lHE->id() > lMaxID )
34 lMaxID = lHE->id() ;
35
36 if ( !lHE->is_bisector() && handle_assigned(lHE->face()) )
37 mBorders.push_back(lHE);
38 }
39
40 CGAL_POLYOFFSET_TRACE(2, "Border count: " << mBorders.size() ) ;
41
42 CGAL_POLYOFFSET_TRACE(2, "Highest Bisector ID: " << lMaxID ) ;
43
44 mBisectorData.resize(lMaxID+1);
45
46 ResetBisectorData();
47 }
48
49
50 template<class Ss, class Gt, class Cont, class Visitor>
51 typename Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::Halfedge_const_handle
LocateHook(FT aTime,Halfedge_const_handle aBisector,bool aIncludeLastBisector,Hook_position & rPos)52 Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::LocateHook( FT aTime
53 , Halfedge_const_handle aBisector
54 , bool aIncludeLastBisector
55 , Hook_position& rPos
56 )
57 {
58 CGAL_POLYOFFSET_TRACE(2,"Locate hook at " << aTime ) ;
59 CGAL_POLYOFFSET_TRACE(2,"Start halfedge: " << e2str(*aBisector) ) ;
60
61 Halfedge_const_handle rHook ;
62
63 while ( aBisector->is_bisector() && ( aIncludeLastBisector ? true : aBisector->prev()->is_bisector() ) )
64 {
65 Halfedge_const_handle lPrev = aBisector->prev();
66 Halfedge_const_handle lNext = aBisector->next();
67
68 CGAL_POLYOFFSET_TRACE(2,"Testing hook on " << e2str(*aBisector) ) ;
69 CGAL_POLYOFFSET_TRACE(4, "Next: " << e2str(*lNext) << " - Prev: " << e2str(*lPrev) ) ;
70
71 if ( !IsVisited(aBisector) )
72 {
73 if ( aBisector->slope() != ZERO )
74 {
75 // A hook is found here if 'aTime' is within the bisector time interval.
76 //
77 // Depending on the bisector slope, src-time might be smaller or larger than tgt-time,
78 // so the test is:
79 //
80 // (src-time <= time <= tgt-time ) || ( tgt-time <= time <= src-time )
81 //
82
83 Comparison_result lTimeWrtSrcTime = lPrev->is_bisector() ? Compare_offset_against_event_time(aTime,lPrev ->vertex()) : LARGER ;
84 Comparison_result lTimeWrtTgtTime = lNext->is_bisector() ? Compare_offset_against_event_time(aTime,aBisector->vertex()) : LARGER ;
85 CGAL_POLYOFFSET_TRACE(3," TimeWrtSrcTime: " << lTimeWrtSrcTime << " TimeWrtTgtTime: " << lTimeWrtTgtTime ) ;
86
87 //
88 // The above test expressed in terms of comparisons of src/tgt time against aTime is:
89 //
90 // ( ( time-wrt-src-time == ZERO || time-wrt-src-time == SMALLER )
91 // && ( time-wrt-tgt-time == ZERO || time-wrt-tgt-time == LARGER )
92 // )
93 //
94 // || -the same with src/tgt inverted-
95 //
96 // ( ( time-wrt-tgt-time == ZERO || time-wrt-tgt-time == SMALLER )
97 // && ( time-wrt-src-time == ZERO || time-wrt-src-time == LARGER )
98 // )
99 //
100 // But since bisectors of slope zero are skipped, both comparisons cannot be zero, thus, the test above is really:
101 //
102 // ( ( time-wrt-src-time == ZERO || time-wrt-src-time == SMALLER ) && ( time-wrt-tgt-time == LARGER ) )
103 // || ( ( time-wrt-src-time == SMALLER ) && ( time-wrt-tgt-time == ZERO || time-wrt-tgt-time == LARGER ) )
104 // || ( ( time-wrt-tgt-time == ZERO || time-wrt-tgt-time == SMALLER ) && ( time-wrt-src-time == LARGER ) )
105 // || ( ( time-wrt-tgt-time == SMALLER ) && ( time-wrt-src-time == ZERO || time-wrt-src-time == LARGER ) )
106 //
107 // Which actually boils down to this:
108 //
109 if ( lTimeWrtSrcTime != lTimeWrtTgtTime )
110 {
111 CGAL_stskel_intrinsic_test_assertion( !CGAL_SS_i::is_time_clearly_not_within_possibly_inexact_bisector_time_interval(aTime,aBisector) ) ;
112
113 rPos = ( lTimeWrtTgtTime == EQUAL ? TARGET : lTimeWrtSrcTime == EQUAL ? SOURCE : INSIDE ) ;
114
115 rHook = aBisector ;
116
117 CGAL_POLYOFFSET_TRACE(2, " Hook found here at " << Hook_position2Str(rPos) ) ;
118
119 break ;
120 }
121 else
122 {
123 CGAL_stskel_intrinsic_test_assertion( !CGAL_SS_i::is_time_clearly_within_possibly_inexact_bisector_time_interval(aTime,aBisector) ) ;
124
125 CGAL_POLYOFFSET_TRACE(2, " Hook not found here.") ;
126 }
127 }
128 else
129 {
130 CGAL_POLYOFFSET_TRACE(2,"Bisector is a roof peak (zero slope).");
131 }
132 }
133 else
134 {
135 CGAL_POLYOFFSET_TRACE(2,"Bisector already visited");
136 }
137 aBisector = lPrev ;
138 }
139
140 return rHook;
141 }
142
143 template<class Ss, class Gt, class Cont, class Visitor>
144 typename Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::Halfedge_const_handle
LocateSeed(FT aTime,Halfedge_const_handle aBorder)145 Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::LocateSeed( FT aTime, Halfedge_const_handle aBorder )
146 {
147 CGAL_POLYOFFSET_TRACE(2,"\nSearching for a starting seed in face " << e2str(*aBorder) ) ;
148
149 Hook_position lPos ;
150 Halfedge_const_handle rSeed = LocateHook(aTime,aBorder->prev(),false,lPos);
151 if ( handle_assigned(rSeed) )
152 {
153 if ( !IsUsedSeed(rSeed) )
154 {
155 SetIsUsedSeed(rSeed);
156
157 CGAL_postcondition( handle_assigned(rSeed->prev()) && rSeed->prev()->is_bisector() ) ;
158
159 // If a seed hook is found at a bisector's source,
160 // the next hook will be found at the previous bisector's target, which would be a mistake.
161 // So, we modify the seed to be the target() of the previous halfedge instead.
162 if ( lPos == SOURCE )
163 rSeed = rSeed->prev() ;
164 CGAL_POLYOFFSET_TRACE(2,"Pos at source switched to pos at target on " << e2str(*rSeed) ) ;
165 }
166 else
167 {
168 CGAL_POLYOFFSET_TRACE(2,"Seed already used. Discarded");
169 rSeed = Halfedge_const_handle();
170 }
171 }
172 return rSeed ;
173 }
174
175
176 template<class Ss, class Gt, class Cont, class Visitor>
177 typename Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::Halfedge_const_handle
LocateSeed(FT aTime)178 Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::LocateSeed( FT aTime )
179 {
180 CGAL_POLYOFFSET_TRACE(2,"Searching for a starting seed at " << aTime ) ;
181
182 Halfedge_const_handle rSeed ;
183
184 for ( typename Halfedge_vector::const_iterator f = mBorders.begin()
185 ; f != mBorders.end() && !handle_assigned(rSeed)
186 ; ++ f
187 )
188 rSeed = LocateSeed(aTime,*f);
189
190 CGAL_POLYOFFSET_TRACE(2,"Found seed: " << eh2str(rSeed) ) ;
191
192 return rSeed;
193 }
194
195
196 template<class Ss, class Gt, class Cont, class Visitor>
AddOffsetVertex(FT aTime,Halfedge_const_handle aHook,ContainerPtr aPoly)197 void Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::AddOffsetVertex( FT aTime
198 , Halfedge_const_handle aHook
199 , ContainerPtr aPoly
200 )
201 {
202 OptionalPoint_2 lP = Construct_offset_point(aTime,aHook);
203
204 if ( !lP )
205 lP = mVisitor.on_offset_point_overflowed(aHook) ;
206
207 CGAL_postcondition(bool(lP));
208
209 CGAL_POLYOFFSET_TRACE(1,"Found offset point p=" << p2str(*lP) << " at offset " << aTime << " along bisector " << e2str(*aHook) << " reaching " << v2str(*aHook->vertex()) ) ;
210
211 mVisitor.on_offset_point(*lP);
212
213 if ( lP != mLastPoint )
214 {
215 aPoly->push_back(*lP);
216 mLastPoint = lP ;
217 }
218 else
219 {
220 CGAL_POLYOFFSET_TRACE(1,"Duplicate point. Ignored");
221 }
222
223 CGAL_POLYOFFSET_DEBUG_CODE( ++ mStepID ) ;
224 }
225
226 template<class Ss, class Gt, class Cont, class Visitor>
227 template<class OutputIterator>
TraceOffsetPolygon(FT aTime,Halfedge_const_handle aSeed,OutputIterator aOut)228 OutputIterator Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::TraceOffsetPolygon( FT aTime, Halfedge_const_handle aSeed, OutputIterator aOut )
229 {
230 CGAL_POLYOFFSET_TRACE(1,"\nTracing new offset polygon" ) ;
231
232 ContainerPtr lPoly( new Container() ) ;
233
234 mVisitor.on_offset_contour_started();
235
236 Halfedge_const_handle lHook = aSeed ;
237 std::vector <Halfedge_const_handle > visited_hooks;
238 do
239 {
240 CGAL_POLYOFFSET_TRACE(1,"STEP " << mStepID ) ;
241
242 Halfedge_const_handle lLastHook = lHook ;
243
244 Hook_position lPos ;
245 lHook = LocateHook(aTime,lHook->prev(),true,lPos) ;
246
247 if ( handle_assigned(lHook) )
248 {
249 CGAL_POLYOFFSET_TRACE(4, "returned Hook: " << e2str(*lHook));
250
251 CGAL_assertion( lHook->slope() != ZERO );
252 AddOffsetVertex(aTime,lHook, lPoly);
253
254 Visit(lHook);
255 visited_hooks.push_back(lHook);
256
257 CGAL_POLYOFFSET_TRACE(2,"Marking hook, B" << lHook->id() << ", as visited." ) ;
258
259 lHook = lHook->opposite();
260 }
261
262 Visit(lLastHook);
263 visited_hooks.push_back(lLastHook);
264
265 CGAL_POLYOFFSET_TRACE(2,"Marking last hook, B" << lLastHook->id() << ", as visited." ) ;
266 }
267 while ( handle_assigned(lHook) && lHook != aSeed && !IsVisited(lHook)) ;
268
269 bool lComplete = ( lHook == aSeed ) ;
270
271 CGAL_POLYOFFSET_TRACE(1,"Offset polygon of " << lPoly->size() << " vertices traced." << ( lComplete ? "COMPLETE" : "INCOMPLETE" ) ) ;
272
273 // On paper, lComplete == true should imply that lPoly->size() >= 3, but since the constructions
274 // might not be exact, you can have cases where the offset points are actually duplicates
275 // and so the end polygon has size < 3. It is ignored in that case.
276 if ( lComplete && lPoly->size() < 3 )
277 lComplete = false;
278
279 mVisitor.on_offset_contour_finished( lComplete );
280
281 if ( lComplete )
282 {
283 *aOut++ = lPoly ;
284 }
285 else
286 {
287 for (std::size_t k=0;k<visited_hooks.size();++k)
288 {
289 GetBisectorData( visited_hooks[k] ).IsVisited=false;
290 }
291 }
292
293 return aOut ;
294 }
295
296 template<class Ss, class Gt, class Cont, class Visitor>
ResetBisectorData()297 void Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::ResetBisectorData()
298 {
299 std::fill(mBisectorData.begin(),mBisectorData.end(), Bisector_data() );
300 }
301
302 template<class Ss, class Gt, class Cont, class Visitor>
303 template<class OutputIterator>
construct_offset_contours(FT aTime,OutputIterator aOut)304 OutputIterator Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::construct_offset_contours( FT aTime, OutputIterator aOut )
305 {
306 CGAL_precondition( aTime > static_cast<FT>(0) ) ;
307
308 CGAL_POLYOFFSET_DEBUG_CODE( mStepID = 0 ) ;
309
310 mVisitor.on_construction_started(aTime);
311
312 mLastPoint = boost::none ;
313
314 ResetBisectorData();
315
316 CGAL_POLYOFFSET_TRACE(1,"Constructing offset polygons for offset: " << aTime ) ;
317 for ( Halfedge_const_handle lSeed = LocateSeed(aTime); handle_assigned(lSeed); lSeed = LocateSeed(aTime) )
318 aOut = TraceOffsetPolygon(aTime,lSeed,aOut);
319
320 mVisitor.on_construction_finished();
321
322 return aOut ;
323 }
324
325 template<class Ss, class Gt, class Cont, class Visitor>
326 typename Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::Trisegment_2_ptr
CreateTrisegment(Vertex_const_handle aNode)327 Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::CreateTrisegment ( Vertex_const_handle aNode ) const
328 {
329 CGAL_precondition(handle_assigned(aNode));
330
331 Trisegment_2_ptr r ;
332
333 CGAL_POLYOFFSET_TRACE(3,"Creating Trisegment for " << v2str(*aNode) ) ;
334
335 if ( aNode->is_skeleton() )
336 {
337 Triedge const& lEventTriedge = aNode->event_triedge() ;
338
339 r = CreateTrisegment(lEventTriedge) ;
340
341 CGAL_stskel_intrinsic_test_assertion
342 (
343 !CGAL_SS_i::is_possibly_inexact_distance_clearly_not_equal_to( Construct_ss_event_time_and_point_2(mTraits)(r)->get<0>()
344 , aNode->time()
345 )
346 ) ;
347
348 CGAL_POLYOFFSET_TRACE(3,"Event triedge=" << lEventTriedge ) ;
349
350 if ( r->degenerate_seed_id() == Trisegment_2::LEFT )
351 {
352 CGAL_POLYOFFSET_TRACE(3,"Left seed is degenerate." ) ;
353
354 Vertex_const_handle lLeftSeed = GetSeedVertex(aNode
355 ,aNode->primary_bisector()->prev()->opposite()
356 ,lEventTriedge.e0()
357 ,lEventTriedge.e1()
358 ) ;
359 if ( handle_assigned(lLeftSeed) )
360 r->set_child_l( CreateTrisegment(lLeftSeed) ) ; // Recursive call
361 }
362 else if ( ! aNode->is_split() && r->degenerate_seed_id() == Trisegment_2::RIGHT )
363 {
364 CGAL_POLYOFFSET_TRACE(3,"Right seed is degenerate." ) ;
365
366 Vertex_const_handle lRightSeed = GetSeedVertex(aNode
367 ,aNode->primary_bisector()->opposite()->next()
368 ,lEventTriedge.e1()
369 ,lEventTriedge.e2()
370 ) ;
371 if ( handle_assigned(lRightSeed) )
372 r->set_child_r( CreateTrisegment(lRightSeed) ) ; // Recursive call
373 }
374 }
375
376 return r ;
377 }
378
379 template<class Ss, class Gt, class Cont, class Visitor>
380 typename Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::Vertex_const_handle
GetSeedVertex(Vertex_const_handle aNode,Halfedge_const_handle aBisector,Halfedge_const_handle aEa,Halfedge_const_handle aEb)381 Polygon_offset_builder_2<Ss,Gt,Cont,Visitor>::GetSeedVertex ( Vertex_const_handle aNode
382 , Halfedge_const_handle aBisector
383 , Halfedge_const_handle aEa
384 , Halfedge_const_handle aEb
385 ) const
386 {
387 Vertex_const_handle rSeed ;
388
389 if ( Is_bisector_defined_by(aBisector,aEa,aEb) )
390 {
391 rSeed = aBisector->vertex();
392
393 CGAL_POLYOFFSET_TRACE(3,"Seed of N" << aNode->id() << " for vertex (E" << aEa->id() << ",E" << aEb->id() << ") directly found: " << v2str(*rSeed) ) ;
394 }
395 else
396 {
397 typedef typename Vertex::Halfedge_around_vertex_const_circulator Halfedge_around_vertex_const_circulator ;
398
399 Halfedge_around_vertex_const_circulator cb = aNode->halfedge_around_vertex_begin() ;
400 Halfedge_around_vertex_const_circulator c = cb ;
401 do
402 {
403 Halfedge_const_handle lBisector = *c ;
404 if ( Is_bisector_defined_by(lBisector,aEa,aEb) )
405 {
406 rSeed = lBisector->opposite()->vertex();
407 CGAL_POLYOFFSET_TRACE(3,"Seed of N" << aNode->id() << " for vertex (E" << aEa->id() << ",E" << aEb->id() << ") indirectly found: V" << rSeed->id() ) ;
408 }
409 }
410 while ( !handle_assigned(rSeed) && ++ c != cb ) ;
411 }
412
413 return rSeed ;
414 }
415
416 } // end namespace CGAL
417
418 #endif // CGAL_POLYGON_OFFSET_BUILDER_2_IMPL_H //
419 // EOF //
420