// Copyright (c) 2006-2008 Fernando Luis Cacciola Carballal. All rights reserved. // // This file is part of CGAL (www.cgal.org). // // $URL: https://github.com/CGAL/cgal/blob/v5.2/Straight_skeleton_2/include/CGAL/Straight_skeleton_builder_2.h $ // $Id: Straight_skeleton_builder_2.h 7d311d3 2020-11-27T13:54:22+01:00 Mael Rouxel-Labbé // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial // // Author(s) : Fernando Cacciola // #ifndef CGAL_STRAIGHT_SKELETON_BUILDER_2_H #define CGAL_STRAIGHT_SKELETON_BUILDER_2_H 1 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace CGAL { template struct Dummy_straight_skeleton_builder_2_visitor { typedef SSkel_ SSkel ; typedef typename SSkel::Halfedge_const_handle Halfedge_const_handle ; typedef typename SSkel::Vertex_const_handle Vertex_const_handle ; void on_contour_edge_entered ( Halfedge_const_handle const& ) const {} void on_initialization_started( std::size_t /* size_of_vertices */ ) const {} void on_initial_events_collected( Vertex_const_handle const& , bool /* is_reflex */, bool /*is_degenerate*/ ) const {} void on_edge_event_created( Vertex_const_handle const& /* lnode */ , Vertex_const_handle const& /* rnode */ ) const {} void on_split_event_created( Vertex_const_handle const& ) const {} void on_pseudo_split_event_created( Vertex_const_handle const& /* lnode */ , Vertex_const_handle const& /* rnode */ ) const {} void on_initialization_finished() const {} void on_propagation_started() const {} void on_anihiliation_event_processed ( Vertex_const_handle const& /* node0 */ , Vertex_const_handle const& /* node1 */ ) const {} void on_edge_event_processed( Vertex_const_handle const& /* lseed */ , Vertex_const_handle const& /* rseed */ , Vertex_const_handle const& /* node */ ) const {} void on_split_event_processed( Vertex_const_handle const& /* seed */ , Vertex_const_handle const& /* node0 */ , Vertex_const_handle const& /* node1 */ ) const {} void on_pseudo_split_event_processed( Vertex_const_handle const& /* lseed */ , Vertex_const_handle const& /* rseed */ , Vertex_const_handle const& /* node0 */ , Vertex_const_handle const& /* node1 */ ) const {} void on_vertex_processed( Vertex_const_handle const& ) const {} void on_propagation_finished() const {} void on_cleanup_started() const {} void on_cleanup_finished() const {} void on_algorithm_finished ( bool /* finished_ok */ ) const {} void on_error( char const* ) const {} } ; template > class Straight_skeleton_builder_2 { public: typedef Traits_ Traits ; typedef SSkel_ SSkel ; typedef Visitor_ Visitor ; typedef boost::shared_ptr SSkelPtr ; private : typedef typename Traits::Kernel K ; typedef typename Traits::FT FT ; typedef typename Traits::Point_2 Point_2 ; typedef typename Traits::Vector_2 Vector_2 ; typedef typename Traits::Direction_2 Direction_2 ; typedef typename Traits::Segment_2 Segment_2 ; typedef typename Traits::Trisegment_2 Trisegment_2 ; typedef typename Traits::Trisegment_2_ptr Trisegment_2_ptr ; typedef typename SSkel::Vertex Vertex ; typedef typename SSkel::Halfedge Halfedge ; typedef typename SSkel::Face Face ; typedef typename SSkel::Vertex_const_handle Vertex_const_handle ; typedef typename SSkel::Halfedge_const_handle Halfedge_const_handle ; typedef typename SSkel::Face_const_handle Face_const_handle ; typedef typename SSkel::Vertex_const_iterator Vertex_const_iterator ; typedef typename SSkel::Halfedge_const_iterator Halfedge_const_iterator ; typedef typename SSkel::Face_const_iterator Face_const_iterator ; typedef typename SSkel::Vertex_handle Vertex_handle ; typedef typename SSkel::Halfedge_handle Halfedge_handle ; typedef typename SSkel::Face_handle Face_handle ; typedef typename SSkel::Vertex_iterator Vertex_iterator ; typedef typename SSkel::Halfedge_iterator Halfedge_iterator ; typedef typename SSkel::Face_iterator Face_iterator ; typedef typename Vertex::Halfedge_around_vertex_circulator Halfedge_around_vertex_circulator ; typedef typename SSkel::size_type size_type ; typedef CGAL_SS_i::Triedge Triedge ; typedef CGAL_SS_i::Event_2 Event ; typedef CGAL_SS_i::Edge_event_2 EdgeEvent ; typedef CGAL_SS_i::Split_event_2 SplitEvent ; typedef CGAL_SS_i::Pseudo_split_event_2 PseudoSplitEvent ; typedef boost::intrusive_ptr EventPtr ; typedef std::pair Vertex_handle_pair ; typedef std::vector EventPtr_Vector ; typedef std::vector Halfedge_handle_vector ; typedef std::vector Vertex_handle_vector ; typedef std::vector Vertex_handle_pair_vector ; typedef typename Halfedge_handle_vector ::iterator Halfedge_handle_vector_iterator ; typedef typename Vertex_handle_vector ::iterator Vertex_handle_vector_iterator ; typedef typename Vertex_handle_pair_vector::iterator Vertex_handle_pair_vector_iterator ; typedef typename EventPtr_Vector::const_iterator event_const_iterator ; typedef Straight_skeleton_builder_2 Self ; typedef typename Halfedge::Base_base HBase_base ; typedef typename Halfedge::Base HBase ; typedef typename Vertex::Base VBase ; typedef typename Face::Base FBase ; enum Site { AT_SOURCE = -1 , INSIDE = 0, AT_TARGET = +1 } ; struct Multinode : public Ref_counted_base { Multinode ( Halfedge_handle b, Halfedge_handle e ) : begin(b) ,end (e) ,v (b->vertex()) ,size (0) {} Halfedge_handle begin ; Halfedge_handle end ; Vertex_handle v ; std::size_t size ; Halfedge_handle_vector bisectors_to_relink ; Halfedge_handle_vector bisectors_to_remove ; Vertex_handle_vector nodes_to_remove ; } ; typedef boost::intrusive_ptr MultinodePtr ; struct MultinodeComparer { bool operator() ( MultinodePtr const& x, MultinodePtr const& y ) { return x->size > y->size ; } } ; typedef std::vector MultinodeVector ; struct Halfedge_ID_compare : CGAL::cpp98::binary_function { bool operator() ( Halfedge_handle const& aA, Halfedge_handle const& aB ) const { return aA->id() < aB->id() ; } } ; public: Straight_skeleton_builder_2 ( boost::optional aMaxTime = boost::none, Traits const& = Traits(), Visitor const& aVisitor = Visitor() ) ; SSkelPtr construct_skeleton( bool aNull_if_failed = true ) ; private : // Only used to debug double ComputeApproximateAngle ( Vector_2 const& u, Vector_2 const& v) const { typename K::Compute_scalar_product_2 sp = K().compute_scalar_product_2_object(); double product = CGAL::sqrt(to_double(sp(u,u)) * to_double(sp(v,v))); if(product == FT(0)) return 0; // cosine double dot = to_double(sp(u,v)); double cosine = dot / product; if(cosine > 1.) cosine = 1.; if(cosine < -1.) cosine = -1.; return std::acos(cosine) * 180. / CGAL_PI; } // Only used to debug double ComputeSupportsAngleSplit ( EventPtr const& aEvent ) { SplitEvent& lEvent = dynamic_cast(*aEvent) ; Vector_2 lV1 ( aEvent->point(), lEvent.seed0()->point() ); Vector_2 lV2 ( aEvent->point(), aEvent->point() + CreateVector(aEvent->triedge().e2()) ) ; return ComputeApproximateAngle(lV1, lV2) ; } // Only used to debug double ComputeSupportsAnglePseudoSplit ( EventPtr const& aEvent ) { PseudoSplitEvent& lEvent = dynamic_cast(*aEvent) ; Vector_2 lV1 ; Vector_2 lV2 ; if(lEvent.is_at_source_vertex()) { // is_at_source_vertex <=> opposite node is seed0 lV1 = Vector_2( aEvent->point(), lEvent.seed1()->point() ); lV2 = Vector_2( aEvent->point(), aEvent->point() + CreateVector(aEvent->triedge().e2()) ) ; } else { lV1 = Vector_2( aEvent->point(), lEvent.seed0()->point() ); lV2 = Vector_2( aEvent->point(), aEvent->point() - CreateVector(aEvent->triedge().e2()) ) ; } return ComputeApproximateAngle(lV1, lV2) ; } // Only used to debug double ComputeSupportsAngle ( EventPtr const& aEvent ) { if ( aEvent->type() == Event::cSplitEvent ) { Halfedge_handle lOppEdge = aEvent->triedge().e2() ; Site lSite; Vertex_handle_pair lOpp = LookupOnSLAV(lOppEdge,aEvent,lSite); if ( handle_assigned(lOpp.first) ) { EventPtr lPseudoSplitEvent = IsPseudoSplitEvent(aEvent,lOpp,lSite); if ( lPseudoSplitEvent ) return ComputeSupportsAnglePseudoSplit ( lPseudoSplitEvent ) ; else return ComputeSupportsAngleSplit ( aEvent ) ; } else { return 2 * CGAL_PI; // event isn't valid anymore } } else { CGAL_assertion ( aEvent->type() == Event::cPseudoSplitEvent ); return ComputeSupportsAngleSplit ( aEvent ) ; } } // Real stuff Comparison_result CompareEventsSupportAnglesSplitSplit ( EventPtr const& aA, EventPtr const& aB ) { CGAL_precondition ( aA->triedge().e0() == aB->triedge().e0() && aA->triedge().e1() == aB->triedge().e1() ) ; return Compare_ss_event_angles_2(mTraits)( CreateVector(aA->triedge().e0()), CreateVector(aA->triedge().e1()), CreateVector(aA->triedge().e2()), CreateVector(aB->triedge().e2()) ); } Comparison_result CompareEventsSupportAnglesSplitPseudoSplit ( EventPtr const& aA, EventPtr const& aB ) { CGAL_precondition ( aA->triedge().e0() == aB->triedge().e0() && aA->triedge().e1() == aB->triedge().e1() ) ; PseudoSplitEvent& lPSEvent = dynamic_cast(*aB) ; if(lPSEvent.is_at_source_vertex()) { return Compare_ss_event_angles_2(mTraits)( CreateVector(aA->triedge().e0()), CreateVector(aA->triedge().e1()), CreateVector(aA->triedge().e2()), CreateVector(aB->triedge().e2()) ); } else { return Compare_ss_event_angles_2(mTraits)( CreateVector(aA->triedge().e0()), CreateVector(aA->triedge().e1()), CreateVector(aA->triedge().e2()), K().construct_opposite_vector_2_object()( CreateVector(aB->triedge().e2())) ); } } Comparison_result CompareEventsSupportAnglesPseudoSplitPseudoSplit ( EventPtr const& aA, EventPtr const& aB ) { CGAL_precondition ( aA->triedge().e0() == aB->triedge().e0() && aA->triedge().e1() == aB->triedge().e1() ) ; PseudoSplitEvent& lPSEventA = dynamic_cast(*aA) ; PseudoSplitEvent& lPSEventB = dynamic_cast(*aB) ; if(lPSEventA.is_at_source_vertex()) { if(lPSEventB.is_at_source_vertex()) { return Compare_ss_event_angles_2(mTraits)( CreateVector(aA->triedge().e0()), CreateVector(aA->triedge().e1()), CreateVector(aA->triedge().e2()), CreateVector(aB->triedge().e2()) ); } else { return Compare_ss_event_angles_2(mTraits)( CreateVector(aA->triedge().e0()), CreateVector(aA->triedge().e1()), CreateVector(aA->triedge().e2()), K().construct_opposite_vector_2_object()( CreateVector(aB->triedge().e2())) ); } } else // aA is a Pseudo-split Event at the target { if(lPSEventB.is_at_source_vertex()) { return Compare_ss_event_angles_2(mTraits)( CreateVector(aA->triedge().e0()), CreateVector(aA->triedge().e1()), K().construct_opposite_vector_2_object()( CreateVector(aA->triedge().e2()) ), CreateVector(aB->triedge().e2()) ); } else { return Compare_ss_event_angles_2(mTraits)( CreateVector(aA->triedge().e0()), CreateVector(aA->triedge().e1()), K().construct_opposite_vector_2_object()( CreateVector(aA->triedge().e2())), K().construct_opposite_vector_2_object()( CreateVector(aB->triedge().e2())) ); } } } Comparison_result CompareEventsSupportAnglesSplitX ( EventPtr const& aA, EventPtr const& aB ) { if ( aB->type() == Event::cSplitEvent ) { Halfedge_handle lOppEdge = aB->triedge().e2() ; Site lSite; Vertex_handle_pair lOpp = LookupOnSLAV(lOppEdge,aB,lSite); if ( handle_assigned(lOpp.first) ) { EventPtr lPseudoSplitEvent = IsPseudoSplitEvent(aB,lOpp,lSite); if ( lPseudoSplitEvent ) return CompareEventsSupportAnglesSplitPseudoSplit ( aA,lPseudoSplitEvent ) ; else return CompareEventsSupportAnglesSplitSplit ( aA,aB ) ; } else { // Event B does not exist, so give it the lower priority by returning SMALLER // (meaning, operator() == false and A has higher priority than B) return CGAL::SMALLER; } } else { CGAL_assertion ( aB->type() == Event::cPseudoSplitEvent ); return CompareEventsSupportAnglesSplitPseudoSplit ( aA,aB ) ; } } Comparison_result CompareEventsSupportAnglesPseudoSplitX ( EventPtr const& aA, EventPtr const& aB ) { if ( aB->type() == Event::cSplitEvent ) { Halfedge_handle lOppEdge = aB->triedge().e2() ; Site lSite; Vertex_handle_pair lOpp = LookupOnSLAV(lOppEdge,aB,lSite); if ( handle_assigned(lOpp.first) ) { EventPtr lPseudoSplitEvent = IsPseudoSplitEvent(aB,lOpp,lSite); if ( lPseudoSplitEvent ) { return CompareEventsSupportAnglesPseudoSplitPseudoSplit ( aA,lPseudoSplitEvent ) ; } else { Comparison_result lRes = CompareEventsSupportAnglesSplitPseudoSplit ( aB,aA ) ; if ( lRes == LARGER ) return SMALLER ; else if ( lRes == SMALLER ) return LARGER ; else return EQUAL ; } } else { // Event B does not exist, so give it the lower priority by returning SMALLER // (meaning, operator() == false and A has higher priority than B) return CGAL::SMALLER; } } else { CGAL_assertion ( aB->type() == Event::cPseudoSplitEvent ); return CompareEventsSupportAnglesPseudoSplitPseudoSplit ( aA,aB ) ; } } // @todo Should split events always have lower priority than split events? Comparison_result CompareEventsSupportAngles ( EventPtr const& aA, EventPtr const& aB ) { CGAL_precondition ( aA->type() != Event::cEdgeEvent && aB->type() != Event::cEdgeEvent ) ; if(aA->triedge() == aB->triedge()) return EQUAL; if ( aA->type() == Event::cSplitEvent ) { Halfedge_handle lOppEdge = aA->triedge().e2() ; Site lSite; Vertex_handle_pair lOpp = LookupOnSLAV(lOppEdge,aA,lSite); if ( handle_assigned(lOpp.first) ) { EventPtr lPseudoSplitEvent = IsPseudoSplitEvent(aA,lOpp,lSite); if ( lPseudoSplitEvent ) return CompareEventsSupportAnglesPseudoSplitX ( lPseudoSplitEvent,aB ) ; else return CompareEventsSupportAnglesSplitX ( aA,aB ) ; } else { // Event A does not exist, so give it the lower priority by returning LARGER // (meaning, operator() == true and A has lower priority than B) // // Exception: event B also is a pseudo split that does not exist... if ( aB->type() == Event::cSplitEvent ) { Halfedge_handle lOppEdgeB = aB->triedge().e2() ; Site lSiteB; Vertex_handle_pair lOppB = LookupOnSLAV(lOppEdgeB,aB,lSiteB); if ( !handle_assigned(lOppB.first) ) return EQUAL; } return LARGER; } } else { CGAL_assertion ( aA->type() == Event::cPseudoSplitEvent ); return CompareEventsSupportAnglesPseudoSplitX ( aA,aB ) ; } } public: // Event compare for the main queue class Event_compare : public CGAL::cpp98::binary_function { public: Event_compare ( Self* aBuilder ) : mBuilder(aBuilder) {} bool operator() ( EventPtr const& aA, EventPtr const& aB ) const { return mBuilder->CompareEvents(aA,aB) == LARGER ; } private: Self* mBuilder ; } ; // Event compare for the local queues // // Special ordering for simultaneous split events (i.e. both (pseudo)splits + same time + same point) // to prevent impossible-to-untangle knots class Split_event_compare : public CGAL::cpp98::binary_function { public: Split_event_compare ( Self* aBuilder, Vertex_handle aV ) : mBuilder(aBuilder), mV(aV) {} bool operator() ( EventPtr const& aA, EventPtr const& aB ) const { CGAL_precondition( aA->type() != Event::cEdgeEvent || aB->type() != Event::cEdgeEvent ) ; if ( ! mBuilder->AreEventsSimultaneous(aA,aB) ) { Comparison_result res = mBuilder->CompareEvents(aA,aB); if ( res == EQUAL ) return aA < aB; return ( res == LARGER ) ; } // There are simultaneous events, we will need to refresh the queue before calling top() // see PopNextSplitEvent() mBuilder->GetVertexData(mV).mHasSimultaneousEvents = true ; // Priority queue comparison: `A` has higher priority than `B` if `operator()(A, B)` is `false`. // We want to give priority to smaller angles, so we must return `false` if the angle is smaller // i.e. `true` if the angle is larger Comparison_result res = mBuilder->CompareEventsSupportAngles(aA, aB); if ( res == EQUAL ) return aA < aB; return ( res == LARGER ) ; } private: Self* mBuilder ; const Vertex_handle mV ; } ; typedef std::priority_queue,Split_event_compare> SplitPQ ; struct Vertex_data : public Ref_counted_base { Vertex_data ( Vertex_handle aVertex, Split_event_compare const& aComparer ) : mVertex(aVertex) , mIsReflex(false) , mIsDegenerate(false) , mIsProcessed(false) , mIsExcluded(false) , mPrevInLAV(-1) , mNextInLAV(-1) , mNextSplitEventInMainPQ(false) , mHasSimultaneousEvents(false) , mSplitEvents(aComparer) {} Vertex_handle mVertex ; bool mIsReflex ; bool mIsDegenerate ; bool mIsProcessed ; bool mIsExcluded ; int mPrevInLAV ; int mNextInLAV ; bool mNextSplitEventInMainPQ ; bool mHasSimultaneousEvents ; SplitPQ mSplitEvents ; Triedge mTriedge ; // Here, E0,E1 corresponds to the vertex (unlike *event* triedges) Trisegment_2_ptr mTrisegment ; // Skeleton nodes cache the full trisegment tree that defines the originating event } ; typedef boost::intrusive_ptr Vertex_data_ptr ; typedef std::priority_queue,Event_compare> PQ ; private : Halfedge_handle validate( Halfedge_handle aH ) const ; Vertex_handle validate( Vertex_handle aH ) const ; std::list& GetHalfedgeLAVList(Halfedge_handle aH) { return mLAVLists[aH->id()]; } Halfedge_handle SSkelEdgesPushBack(const Halfedge& aH1, const Halfedge& aH2) { mLAVLists.resize(aH2.id()+1); return mSSkel->SSkel::Base::edges_push_back (aH1, aH2); } void InitVertexData( Vertex_handle aV ) { mVertexData.push_back( Vertex_data_ptr( new Vertex_data(aV, Split_event_compare(this, aV) ) ) ) ; } Vertex_data const& GetVertexData( Vertex_const_handle aV ) const { CGAL_precondition( handle_assigned(aV) ) ; return *mVertexData[aV->id()]; } Vertex_data& GetVertexData( Vertex_const_handle aV ) { CGAL_precondition( handle_assigned(aV) ) ; return *mVertexData[aV->id()]; } Vertex_handle GetVertex ( int aIdx ) { CGAL_precondition(aIdx>=0); return mVertexData[aIdx]->mVertex ; } // Null if aV is a contour or infinite node Trisegment_2_ptr const& GetTrisegment ( Vertex_handle aV ) const { return GetVertexData(aV).mTrisegment ; } void SetTrisegment ( Vertex_handle aV, Trisegment_2_ptr const& aTrisegment ) { GetVertexData(aV).mTrisegment = aTrisegment ; } // Null if aV is a contour node Triedge const& GetVertexTriedge ( Vertex_handle aV ) const { return GetVertexData(aV).mTriedge ; } void SetVertexTriedge ( Vertex_handle aV, Triedge const& aTriedge ) { GetVertexData(aV).mTriedge = aTriedge ; GetHalfedgeLAVList(aTriedge.e0()).push_back(aV); } void GLAV_push_back ( Vertex_handle /* aV */ ) {} void GLAV_remove ( Vertex_handle aV ) { GetHalfedgeLAVList(GetVertexData(aV).mTriedge.e0()).remove(aV); } typename K::Segment_2 CreateRawSegment ( Halfedge_const_handle aH ) const { Point_2 s = aH->opposite()->vertex()->point() ; Point_2 t = aH->vertex()->point() ; return K().construct_segment_2_object()(s,t); } template // actually just equal to 'Traits', but gotta template for SFINAE to work Segment_2 CreateSegment ( Halfedge_const_handle aH, typename std::enable_if< ! CGAL_SS_i::has_Segment_2_with_ID::value>::type* = nullptr ) const { return Segment_2(CreateRawSegment(aH)) ; } template // actually just equal to 'Traits', but gotta template for SFINAE to work Segment_2 CreateSegment ( Halfedge_const_handle aH, typename std::enable_if< CGAL_SS_i::has_Segment_2_with_ID::value>::type* = nullptr ) const { return Segment_2(CreateRawSegment(aH), aH->id()); } Vector_2 CreateVector ( Halfedge_const_handle aH ) const { Point_2 s = aH->opposite()->vertex()->point() ; Point_2 t = aH->vertex()->point() ; return K().construct_vector_2_object()(s,t); } Direction_2 CreateDirection ( Halfedge_const_handle aH ) const { return K().construct_direction_2_object()( CreateVector(aH) ); } Trisegment_2_ptr CreateTrisegment ( Triedge const& aTriedge ) const { CGAL_precondition(aTriedge.is_valid() && aTriedge.is_skeleton()); Trisegment_2_ptr r = Construct_ss_trisegment_2(mTraits)(CreateSegment(aTriedge.e0()) ,CreateSegment(aTriedge.e1()) ,CreateSegment(aTriedge.e2()) ); CGAL_STSKEL_BUILDER_TRACE(5,"Trisegment for " << aTriedge << ":" << r ) ; CGAL_postcondition_msg((r!= Trisegment_2_ptr()), "Unable to determine edges collinearity"); return r ; } Trisegment_2_ptr CreateTrisegment ( Triedge const& aTriedge, Vertex_handle aLSeed ) const { Trisegment_2_ptr r = CreateTrisegment( aTriedge ) ; r->set_child_l( GetTrisegment(aLSeed) ) ; return r ; } Trisegment_2_ptr CreateTrisegment ( Triedge const& aTriedge, Vertex_handle aLSeed, Vertex_handle aRSeed ) const { Trisegment_2_ptr r = CreateTrisegment( aTriedge ) ; r->set_child_l( GetTrisegment(aLSeed) ) ; r->set_child_r( GetTrisegment(aRSeed) ) ; return r ; } Vertex_handle GetPrevInLAV ( Vertex_handle aV ) { return GetVertex ( GetVertexData(aV).mPrevInLAV ) ; } Vertex_handle GetNextInLAV ( Vertex_handle aV ) { return GetVertex ( GetVertexData(aV).mNextInLAV ) ; } void SetPrevInLAV ( Vertex_handle aV, Vertex_handle aPrev ) { GetVertexData(aV).mPrevInLAV = aPrev->id(); } void SetNextInLAV ( Vertex_handle aV, Vertex_handle aPrev ) { GetVertexData(aV).mNextInLAV = aPrev->id(); } Halfedge_handle GetEdgeEndingAt ( Vertex_handle aV ) { return GetVertexTriedge(aV).e0(); } Halfedge_handle GetEdgeStartingAt ( Vertex_handle aV ) { return GetEdgeEndingAt( GetNextInLAV(aV) ) ; } void Exclude ( Vertex_handle aV ) { GetVertexData(aV).mIsExcluded = true ; } bool IsExcluded ( Vertex_const_handle aV ) const { return GetVertexData(aV).mIsExcluded ; } void SetIsReflex ( Vertex_handle aV ) { GetVertexData(aV).mIsReflex = true ; } bool IsReflex ( Vertex_handle aV ) { return GetVertexData(aV).mIsReflex ; } void SetIsDegenerate ( Vertex_handle aV ) { GetVertexData(aV).mIsDegenerate = true ; } bool IsDegenerate ( Vertex_handle aV ) { return GetVertexData(aV).mIsDegenerate ; } void SetIsProcessed ( Vertex_handle aV ) { GetVertexData(aV).mIsProcessed = true ; mVisitor.on_vertex_processed(aV); } bool IsConvex ( Vertex_handle aV ) { Vertex_data const& lData = GetVertexData(aV) ; return !lData.mIsReflex && !lData.mIsDegenerate ; } bool IsProcessed ( Vertex_handle aV ) { return GetVertexData(aV).mIsProcessed ; } void AddSplitEvent ( Vertex_handle aV, EventPtr const& aEvent ) { CGAL_STSKEL_BUILDER_TRACE(2, "V" << aV->id() << " PQ: " << *aEvent); GetVertexData(aV).mSplitEvents.push(aEvent); } EventPtr PopNextSplitEvent ( Vertex_handle aV ) { EventPtr rEvent ; Vertex_data& lData = GetVertexData(aV) ; if ( !lData.mNextSplitEventInMainPQ ) { SplitPQ& lPQ = lData.mSplitEvents ; if ( !lPQ.empty() ) { // When there are simultaneous split events, we sort them to handle nearby pseudo split events // together as to avoid multiple fronts crossing each other without seeing // and creating an invalid SLS. // // Unfortunately, the way that this sorting is performed requires knowing whether an event // is a pseudo split, and requires looking into the LAV tree. More annoyingly, whether an event // exists or not (see calls to handle_assigned(lOpp) and such) can change, which will // change the position of the item in the split priority queue (as an invalid event is // at the bottom of the priority queue). // // Consequently, when a simultaneous event has been detected, we need to refresh the queue // to get the real top. // // In practice, things are usually fine with a roughly-correct priority queue because an // invalid event being popped will just be ignored, but MSVC 2015-Debug is a very zealous // compiler that checks that the full queue is sane when it pops() and will detect this kind // of unimportant inconsistencies... if ( lData.mHasSimultaneousEvents ) { std::make_heap(const_cast(&lPQ.top()), const_cast(&lPQ.top()) + lPQ.size(), Split_event_compare(this, aV)); } rEvent = lPQ.top(); lPQ.pop(); lData.mNextSplitEventInMainPQ = true ; } } return rEvent ; } void AllowNextSplitEvent ( Vertex_handle aV ) { GetVertexData(aV).mNextSplitEventInMainPQ = false ; } void InsertEventInPQ( EventPtr aEvent ) ; EventPtr PopEventFromPQ() ; bool ExistEvent ( Trisegment_2_ptr const& aS ) { return Do_ss_event_exist_2(mTraits)(aS,mMaxTime); } bool IsOppositeEdgeFacingTheSplitSeed( Vertex_handle aSeed, Halfedge_handle aOpposite ) const { if ( aSeed->is_skeleton() ) return Is_edge_facing_ss_node_2(mTraits)( GetTrisegment(aSeed), CreateSegment(aOpposite) ) ; else return Is_edge_facing_ss_node_2(mTraits)( aSeed->point() , CreateSegment(aOpposite) ) ; } Oriented_side EventPointOrientedSide( Event const& aEvent , Halfedge_const_handle aE0 , Halfedge_const_handle aE1 , Vertex_handle aV01 , bool aE0isPrimary ) const { return Oriented_side_of_event_point_wrt_bisector_2(mTraits)( aEvent.trisegment() , CreateSegment(aE0) , CreateSegment(aE1) , GetTrisegment(aV01) // Can be null , aE0isPrimary ) ; } Comparison_result CompareEvents ( Trisegment_2_ptr const& aA, Trisegment_2_ptr const& aB ) const { return Compare_ss_event_times_2(mTraits)(aA,aB) ; } Comparison_result CompareEvents ( EventPtr const& aA, EventPtr const& aB ) const { return aA->triedge() != aB->triedge() ? CompareEvents( aA->trisegment(), aB->trisegment() ) : EQUAL ; } Comparison_result CompareEvents( Trisegment_2_ptr const& aTrisegment, Vertex_handle aSeedNode ) const { return aSeedNode->is_skeleton() ? aSeedNode->has_infinite_time() ? SMALLER : CompareEvents( aTrisegment, GetTrisegment(aSeedNode) ) : LARGER ; } Comparison_result CompareEvents( Vertex_handle aLNode, Vertex_handle aRNode ) const { if ( aLNode->is_skeleton() ) { if ( aRNode->is_skeleton() ) { if ( aLNode->has_infinite_time() && aRNode->has_infinite_time() ) return EQUAL ; else if ( aLNode->has_infinite_time() ) return LARGER ; else if ( aRNode->has_infinite_time() ) return SMALLER ; else return CompareEvents ( GetTrisegment(aLNode), GetTrisegment(aRNode) ) ; } else // left skeleton, right not skeleton { return LARGER ; } } else // left not skeleton { if ( aRNode->is_skeleton() ) return SMALLER ; else // both not skeleton return EQUAL ; } } bool AreEventsSimultaneous( Trisegment_2_ptr const& x, Trisegment_2_ptr const& y ) const { return Are_ss_events_simultaneous_2(mTraits)(x,y) ; } bool AreEventsSimultaneous( EventPtr const& x, EventPtr const& y ) const { return AreEventsSimultaneous(x->trisegment(),y->trisegment()); } bool AreContourNodesCoincident( Vertex_handle aX, Vertex_handle aY ) const { CGAL_precondition( aX->is_contour() ); CGAL_precondition( aY->is_contour() ); return CGAL::compare_xy(aX->point(),aY->point()) == EQUAL ; } bool AreSkeletonNodesCoincident( Vertex_handle aX, Vertex_handle aY ) const { CGAL_precondition( aX->is_skeleton() ); CGAL_precondition( aY->is_skeleton() ); CGAL_precondition( !aX->has_infinite_time() ); CGAL_precondition( !aY->has_infinite_time() ); return AreEventsSimultaneous( GetTrisegment(aX), GetTrisegment(aY) ) ; } void SetBisectorSlope ( Halfedge_handle aBisector, Sign aSlope ) { aBisector->HBase_base::set_slope(aSlope); } void SetBisectorSlope ( Vertex_handle aA, Vertex_handle aB ) { Halfedge_handle lOBisector = aA->primary_bisector(); Halfedge_handle lIBisector = lOBisector->opposite(); CGAL_precondition( !aA->is_contour() || !aB->is_contour() ) ; if ( aA->is_contour() ) { SetBisectorSlope(lOBisector,POSITIVE); SetBisectorSlope(lIBisector,NEGATIVE); } else if ( aB->is_contour()) { SetBisectorSlope(lOBisector,NEGATIVE); SetBisectorSlope(lIBisector,POSITIVE); } else { if ( aA->has_infinite_time() ) { CGAL_precondition( !aB->has_infinite_time()); SetBisectorSlope(lOBisector,NEGATIVE); SetBisectorSlope(lIBisector,POSITIVE); } else if ( aB->has_infinite_time()) { CGAL_precondition( !aA->has_infinite_time()); SetBisectorSlope(lOBisector,NEGATIVE); SetBisectorSlope(lIBisector,POSITIVE); } else { CGAL_precondition( !aA->has_infinite_time()); CGAL_precondition( !aB->has_infinite_time()); Sign lSlope = CompareEvents(GetTrisegment(aB),GetTrisegment(aA)); SetBisectorSlope(lOBisector,lSlope); SetBisectorSlope(lIBisector,opposite(lSlope)); } } } boost::tuple ConstructEventTimeAndPoint( Trisegment_2_ptr const& aS ) const { boost::optional< boost::tuple > r = Construct_ss_event_time_and_point_2(mTraits)(aS); CGAL_postcondition_msg(!!r, "Unable to compute skeleton node coordinates"); return *r ; } void SetEventTimeAndPoint( Event& aE ) { FT lTime ; Point_2 lP ; boost::tie(lTime,lP) = ConstructEventTimeAndPoint(aE.trisegment()); aE.SetTimeAndPoint(lTime,lP); } void EraseBisector( Halfedge_handle aB ) { CGAL_STSKEL_BUILDER_TRACE(1,"Dangling B" << aB->id() << " and B" << aB->opposite()->id() << " removed."); mSSkel->SSkel::Base::edges_erase(aB); } #ifdef CGAL_STSKEL_TRACE_ON std::string wavefront2str( Vertex_handle v ) { std::ostringstream ss ; ss << "N" << GetPrevInLAV(v)->id() << "->N" << v->id() << "->N" << GetNextInLAV(v)->id() << " E" << GetVertexTriedge(v).e0()->id() << "->E" << GetVertexTriedge(v).e1()->id() ; return ss.str() ; } #endif void Link( Halfedge_handle aH, Face_handle aF ) { aH->HBase_base::set_face(aF); } void Link( Halfedge_handle aH, Vertex_handle aV ) { aH->HBase_base::set_vertex(aV); } void Link( Vertex_handle aV, Halfedge_handle aH ) { aV->VBase::set_halfedge(aH); } void CrossLinkFwd( Halfedge_handle aPrev, Halfedge_handle aNext ) { aPrev->HBase_base::set_next(aNext); aNext->HBase_base::set_prev(aPrev); } void CrossLink( Halfedge_handle aH, Vertex_handle aV ) { Link(aH,aV); Link(aV,aH); } Triedge GetCommonTriedge( Vertex_handle aA, Vertex_handle aB ) ; bool AreBisectorsCoincident ( Halfedge_const_handle aA, Halfedge_const_handle aB ) const ; EventPtr IsPseudoSplitEvent( EventPtr const& aEvent, Vertex_handle_pair aOpp, Site const& aSite ) ; void CollectSplitEvent( Vertex_handle aNode, Triedge const& aTriedge ) ; void CollectSplitEvents( Vertex_handle aNode, Triedge const& aPrevEventTriedge ) ; EventPtr FindEdgeEvent( Vertex_handle aLNode, Vertex_handle aRNode, Triedge const& aPrevEventTriedge ) ; void HandleSimultaneousEdgeEvent( Vertex_handle aA, Vertex_handle aB ) ; void CollectNewEvents( Vertex_handle aNode, Triedge const& aPrevEventTriedge ) ; void UpdatePQ( Vertex_handle aV, Triedge const& aPrevEventTriedge ) ; void CreateInitialEvents(); void CreateContourBisectors(); void HarmonizeSpeeds(boost::mpl::bool_) { } void HarmonizeSpeeds(boost::mpl::bool_); // @fixme This function can create an inconsistency between the skeleton and the offset // when caching is used: this function will harmonize values in the cache used by the skeleton // builder, but not the values in the cache used in the offset builder (actually, no_cache is used // for the offset builder, at the moment). It is difficult to harmonize between caches as one might // wish to build the skeleton and the offset in completely different moments and independent functions... void HarmonizeSpeeds() { // Harmonize speed only if we have a segment type with id and a not exact square root return HarmonizeSpeeds( boost::mpl::bool_< CGAL_SS_i::has_Segment_2_with_ID::value && ( !is_same_or_derived::Algebraic_category >::value || std::is_floating_point::value) >() ); } void InitPhase(); void SetupNewNode( Vertex_handle aNode ); Vertex_handle_pair LookupOnSLAV ( Halfedge_handle aOBorder, EventPtr const& aEvent, Site& rSite ) ; Vertex_handle ConstructEdgeEventNode ( EdgeEvent& aEvent ) ; Vertex_handle_pair ConstructSplitEventNodes ( SplitEvent& aEvent, Vertex_handle aOppR ) ; Vertex_handle_pair ConstructPseudoSplitEventNodes ( PseudoSplitEvent& aEvent ) ; bool IsValidEvent ( EventPtr aEvent ) ; bool IsValidEdgeEvent ( EdgeEvent const& aEvent ) ; bool IsValidSplitEvent ( SplitEvent const& aEvent ) ; bool IsValidPseudoSplitEvent ( PseudoSplitEvent const& aEvent ) ; void HandleEdgeEvent ( EventPtr aEvent ) ; void HandleSplitEvent ( EventPtr aEvent, Vertex_handle_pair aOpp ) ; void HandlePseudoSplitEvent ( EventPtr aEvent ) ; void HandleSplitOrPseudoSplitEvent ( EventPtr aEvent ) ; void InsertNextSplitEventInPQ( Vertex_handle v ) ; void InsertNextSplitEventsInPQ() ; bool IsProcessed( EventPtr aEvent ) ; void Propagate(); void EraseNode ( Vertex_handle aNode ) ; void MergeSplitNodes ( Vertex_handle_pair aSplitNodes ) ; void RelinkBisectorsAroundMultinode( Vertex_handle const& v0, Halfedge_handle_vector& aLinks ) ; void PreprocessMultinode( Multinode& aMN ) ; void ProcessMultinode( Multinode& aMN, Halfedge_handle_vector& rHalfedgesToRemove , Vertex_handle_vector& rNodesToRemove ) ; MultinodePtr CreateMultinode( Halfedge_handle begin, Halfedge_handle end ) ; // returns 'true' if something was merged bool MergeCoincidentNodes() ; bool FinishUp(); bool Run(); private: //Input Traits mTraits ; Visitor const& mVisitor ; std::vector mVertexData ; std::vector> mLAVLists; Vertex_handle_vector mReflexVertices ; Halfedge_handle_vector mDanglingBisectors ; Halfedge_handle_vector mContourHalfedges ; Vertex_handle_pair_vector mSplitNodes ; Event_compare mEventCompare ; int mVertexID ; int mEdgeID ; int mFaceID ; int mEventID ; int mStepID ; boost::optional mMaxTime ; PQ mPQ ; //Output SSkelPtr mSSkel ; private : template void enter_valid_contour ( InputPointIterator aBegin, InputPointIterator aEnd, Converter const& cvt ) { CGAL_STSKEL_BUILDER_TRACE(0,"Inserting Connected Component of the Boundary...."); Halfedge_handle lFirstCCWBorder ; Halfedge_handle lPrevCCWBorder ; Halfedge_handle lNextCWBorder ; Vertex_handle lFirstVertex ; Vertex_handle lPrevVertex ; InputPointIterator lCurr = aBegin ; // InputPointIterator lPrev = aBegin ; int c = 0 ; while ( lCurr != aEnd ) { Halfedge_handle lCCWBorder = SSkelEdgesPushBack( Halfedge(mEdgeID),Halfedge(mEdgeID+1) ); Halfedge_handle lCWBorder = lCCWBorder->opposite(); mEdgeID += 2 ; mContourHalfedges.push_back(lCCWBorder); Vertex_handle lVertex = mSSkel->SSkel::Base::vertices_push_back( Vertex(mVertexID++,cvt(*lCurr)) ) ; CGAL_STSKEL_BUILDER_TRACE(1,"Vertex: V" << lVertex->id() << " at " << lVertex->point() ); InitVertexData(lVertex); Face_handle lFace = mSSkel->SSkel::Base::faces_push_back( Face(mFaceID++) ) ; ++ c ; lCCWBorder->HBase_base::set_face(lFace); lFace ->FBase ::set_halfedge(lCCWBorder); lVertex ->VBase ::set_halfedge(lCCWBorder); lCCWBorder->HBase_base::set_vertex(lVertex); if ( lCurr == aBegin ) { lFirstVertex = lVertex ; lFirstCCWBorder = lCCWBorder ; } else { SetPrevInLAV(lVertex ,lPrevVertex); SetNextInLAV(lPrevVertex,lVertex ); SetVertexTriedge(lPrevVertex, Triedge(lPrevCCWBorder,lCCWBorder) ) ; lCWBorder->HBase_base::set_vertex(lPrevVertex); lCCWBorder ->HBase_base::set_prev(lPrevCCWBorder); lPrevCCWBorder->HBase_base::set_next(lCCWBorder); lNextCWBorder->HBase_base::set_prev(lCWBorder); lCWBorder ->HBase_base::set_next(lNextCWBorder); CGAL_STSKEL_BUILDER_TRACE(1,"CCW Border: E" << lCCWBorder->id() << ' ' << lPrevVertex->point() << " -> " << lVertex ->point()); CGAL_STSKEL_BUILDER_TRACE(1,"CW Border: E" << lCWBorder ->id() << ' ' << lVertex ->point() << " -> " << lPrevVertex->point() ); mVisitor.on_contour_edge_entered(lCCWBorder); } // lPrev = lCurr ; ++ lCurr ; lPrevVertex = lVertex ; lPrevCCWBorder = lCCWBorder ; lNextCWBorder = lCWBorder ; } SetPrevInLAV(lFirstVertex,lPrevVertex ); SetNextInLAV(lPrevVertex ,lFirstVertex); SetVertexTriedge( lPrevVertex, Triedge(lPrevCCWBorder,lFirstCCWBorder) ) ; lFirstCCWBorder->opposite()->HBase_base::set_vertex(lPrevVertex); lFirstCCWBorder->HBase_base::set_prev(lPrevCCWBorder); lPrevCCWBorder ->HBase_base::set_next(lFirstCCWBorder); lPrevCCWBorder ->opposite()->HBase_base::set_prev(lFirstCCWBorder->opposite()); lFirstCCWBorder->opposite()->HBase_base::set_next(lPrevCCWBorder ->opposite()); CGAL_precondition_msg(c >=3, "The contour must have at least 3 _distinct_ vertices" ) ; CGAL_STSKEL_BUILDER_TRACE(1 , "CCW Border: E" << lFirstCCWBorder->id() << ' ' << lPrevVertex ->point() << " -> " << lFirstVertex->point() << '\n' << "CW Border: E" << lFirstCCWBorder->opposite()->id() << ' ' << lFirstVertex->point() << " -> " << lPrevVertex ->point() ); mVisitor.on_contour_edge_entered(lFirstCCWBorder); } // internal function to filter split event in case the traits is Filtered bool CanSafelyIgnoreSplitEventImpl(const EventPtr&, boost::mpl::bool_) const { return false; } bool CanSafelyIgnoreSplitEventImpl(const EventPtr& lEvent, boost::mpl::bool_) const { return mTraits.CanSafelyIgnoreSplitEvent(lEvent); } bool CanSafelyIgnoreSplitEvent(const EventPtr& lEvent) const { return CanSafelyIgnoreSplitEventImpl(lEvent, typename CGAL_SS_i::has_Filters_split_events_tag::type()); } void ComputeUpperBoundForValidSplitEventsImpl(Vertex_handle, Vertex_handle, Vertex_handle, Halfedge_handle_vector_iterator, Halfedge_handle_vector_iterator, boost::mpl::bool_) const { } void ComputeUpperBoundForValidSplitEventsImpl(Vertex_handle lPrev, Vertex_handle aNode, Vertex_handle lNext, Halfedge_handle_vector_iterator contour_halfedges_begin, Halfedge_handle_vector_iterator contour_halfedges_end, boost::mpl::bool_) const { return mTraits.ComputeFilteringBound(lPrev, aNode, lNext, contour_halfedges_begin, contour_halfedges_end); } void ComputeUpperBoundForValidSplitEvents(Vertex_handle lPrev, Vertex_handle aNode, Vertex_handle lNext, Halfedge_handle_vector_iterator contour_halfedges_begin, Halfedge_handle_vector_iterator contour_halfedges_end) const { return ComputeUpperBoundForValidSplitEventsImpl(lPrev, aNode, lNext, contour_halfedges_begin, contour_halfedges_end, typename CGAL_SS_i::has_Filters_split_events_tag::type()); } public: // This compares INPUT vertices so there is no need to filter it. struct AreVerticesEqual { template bool operator() ( P const&x, P const& y ) const { return CGAL::compare_xy(x,y) == EQUAL ; } } ; template Straight_skeleton_builder_2& enter_contour ( InputPointIterator aBegin , InputPointIterator aEnd , Converter const& cvt , bool aCheckValidity = true ) { if ( aCheckValidity ) { typedef typename std::iterator_traits::value_type Input_point; typedef std::vector Input_point_vector ; // Remove coincident consecutive vertices Input_point_vector lList; std::unique_copy(aBegin,aEnd,std::back_inserter(lList),AreVerticesEqual()); while ( lList.size() > 0 && CGAL::compare_xy(lList.front(),lList.back()) == EQUAL ) lList.pop_back(); if ( lList.size() >= 3 ) { enter_valid_contour(lList.begin(),lList.end(),cvt); } else { CGAL_STSKEL_BUILDER_TRACE(0,"Degenerate contour (less than 3 non-degenerate vertices)."); } } else { enter_valid_contour(aBegin,aEnd,cvt); } return *this ; } template Straight_skeleton_builder_2& enter_contour ( InputPointIterator aBegin , InputPointIterator aEnd , bool aCheckValidity = true ) { return enter_contour(aBegin, aEnd, Cartesian_converter(), aCheckValidity); } } ; } // end namespace CGAL #include #endif // CGAL_STRAIGHT_SKELETON_BUILDER_2_H // // EOF //