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