straight_skeleton_builder_2_impl.h

很多二维 三维几何计算算法 C++ 类库

  bool lAcceptR = !!lREdgeEvent ;

  // Altough one and only one of the potential events actually happens, the ocurrence of a particular candidate is
  // determined by all the previous events. That is, at this point we may find that the vertex wavefront collides, for instance,
  // with both adjacent vertex wavefronts, thus encountering 2 potential edge events; however, we cannot rule out one of these
  // potential edge events based on the other because it is, precisely, potential. 
  // IOW, if event A happens before event B (for both A and B correspoding to the same wavefront), then for sure B won't happen; 
  // but at this point we can't tell whether A will actually ocurr so we can't discard B just yet. 
  // Both must be placed in the queue; if A is effectively processed, then B will naturally by ignored when it's pop off the queue.
  
  
  // But there is one exception to the "don't discard B yet" rule:
  // If A and B are coincident in time, their relative ordering in the queue is undetermined. Thus, 
  // the 'wrong' event could be pop off and processed first.
  // In this case, and only this case, we rule out B (the event that can't ocurr if A does)
  // TODO: This may be incorrect still... the priority queue should resolve the "second level" ordering in case of time coincidence.
  if ( lLEdgeEvent && lREdgeEvent )
  {
    Comparison_result lRel = CompareEvents(lLEdgeEvent,lREdgeEvent) ;
    if ( lRel == EQUAL )
    {
      if ( CompareEventsDistanceToSeed(aNode,lLEdgeEvent,lREdgeEvent) == LARGER )
           lAcceptL = false ;
      else lAcceptR = false ; 
    
      CGAL_STSKEL_BUILDER_TRACE(3,"Both Left and Right Edge Events found with the same time:"
                               << "LEvent:" << *lLEdgeEvent << '\n'
                               << "REvent:" << *lREdgeEvent << '\n'
                               << "Selecting the one closer to the seed: " << (lAcceptL ? "Left" : "Right") 
                               );
    }
  }
    
  if ( lAcceptL )
    InsertEventInPQ(lLEdgeEvent);
    
  if ( lAcceptR )
    InsertEventInPQ(lREdgeEvent);
}

// Handles the special case of two simultaneous edge events, that is, two edges
// collapsing along the line/point were they meet at the same time.
// This ocurrs when the bisector emerging from vertex 'aA' is defined by the same pair of 
// contour edges as the bisector emerging from vertex 'aB' (but in opposite order).
//
template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::HandleSimultaneousEdgeEvent( Vertex_handle aA, Vertex_handle aB )
{
  CGAL_STSKEL_BUILDER_TRACE ( 2, "Handling simultaneous EdgeEvent between N" << aA ->id() << " and N"  << aB ->id() ) ;

  mVisitor.on_anihiliation_event_processed(aA,aB) ;

  Halfedge_handle lOA = aA->primary_bisector() ;
  Halfedge_handle lOB = aB->primary_bisector() ;
  Halfedge_handle lIA = lOA->opposite();
  Halfedge_handle lIB = lOB->opposite();

  CGAL_STSKEL_BUILDER_TRACE ( 2
                            ,    "OA: B" << lOA->id() << '\n'
                              << "IA: B" << lIA->id() << '\n'
                              << "OB: B" << lOB->id() << '\n'
                              << "IB: B" << lIB->id()
                            ) ;

  SetIsProcessed(aA) ;
  SetIsProcessed(aB) ;
  mSLAV.remove(aA);
  mSLAV.remove(aB);

  CGAL_STSKEL_BUILDER_TRACE ( 3, 'N' << aA->id() << " processed\nN" << aB->id() << " processed" ) ;

  Halfedge_handle lOA_Prev = lOA->prev() ;
  Halfedge_handle lIA_Next = lIA->next() ;

  Halfedge_handle lOB_Prev = lOB->prev() ;
  Halfedge_handle lIB_Next = lIB->next() ;

  CGAL_STSKEL_BUILDER_TRACE ( 2
                            ,   "OA_Prev: B" << lOA_Prev->id() << '\n'
                              << "IA_Next: B" << lIA_Next->id() << '\n'
                              << "OB_Prev: B" << lOB_Prev->id() << '\n'
                              << "IB_Next: B" << lIB_Next->id()
                           ) ;

  lOB     ->HBase_base::set_next( lIA_Next );
  lIA_Next->HBase_base::set_prev( lOB      );
  lIB     ->HBase_base::set_prev( lOA_Prev );
  lOA_Prev->HBase_base::set_next( lIB      );

  lOB->HBase_base::set_vertex  (aA);

  CGAL_STSKEL_BUILDER_TRACE ( 1, "B" << lOA->id() << " and B" << lIA->id() << " erased." ) ;
  mDanglingBisectors.push_back(lOA);

  //
  // The code above corrects the links for vertices aA/aB to the erased halfedges lOA and lIA.
  // However, any of these vertices (aA/aB) maybe one of the twin vertices of a split event.
  // If that's the case, the erased halfedge maybe be linked to a 'couple' of those vertices.
  // This situation is corrected below:

  if ( handle_assigned(lOA->vertex()) && lOA->vertex() != aA && lOA->vertex() != aB )
  {
    lOA->vertex()->VBase::set_halfedge(lIB);
    
    CGAL_STSKEL_BUILDER_TRACE ( 1, "N" << lOA->vertex()->id() << " has B" << lOA->id() 
                              << " as it's halfedge. Replacing it with B" << lIB->id() 
                              ) ;
  }
  if ( handle_assigned(lIA->vertex()) && lIA->vertex() != aA && lIA->vertex() != aB )
  {
    lIA->vertex()->VBase::set_halfedge(lOB);
    
    CGAL_STSKEL_BUILDER_TRACE ( 1, "N" << lIA->vertex()->id() << " has B" << lIA->id() 
                              << " as it's halfedge. Replacing it with B" << lOB->id() 
                              ) ;
  }

  CGAL_STSKEL_BUILDER_TRACE ( 2, "N" << aA->id() << " halfedge: B" << aA->halfedge()->id() ) ;
  CGAL_STSKEL_BUILDER_TRACE ( 2, "N" << aB->id() << " halfedge: B" << aB->halfedge()->id() ) ;

  CGAL_assertion( aA->primary_bisector() == lIB ) ;
}

// Returns true if the skeleton edges 'aA' and 'aB' are defined by the same pair of contour edges (but possibly in reverse order)
//
template<class Gt, class SS, class V>
bool Straight_skeleton_builder_2<Gt,SS,V>::AreBisectorsCoincident ( Halfedge_const_handle aA, Halfedge_const_handle aB  ) const
{
  CGAL_STSKEL_BUILDER_TRACE ( 3, "Testing for simultaneous EdgeEvents between B" << aA->id() << " and B" << aB->id() ) ;

  Halfedge_const_handle lA_LBorder = aA->defining_contour_edge();
  Halfedge_const_handle lA_RBorder = aA->opposite()->defining_contour_edge();
  Halfedge_const_handle lB_LBorder = aB->defining_contour_edge();
  Halfedge_const_handle lB_RBorder = aB->opposite()->defining_contour_edge();

  return    ( lA_LBorder == lB_LBorder && lA_RBorder == lB_RBorder )
         || ( lA_LBorder == lB_RBorder && lA_RBorder == lB_LBorder ) ;
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::UpdatePQ( Vertex_handle aNode )
{
  Vertex_handle lPrev = GetPrevInLAV(aNode) ;
  Vertex_handle lNext = GetNextInLAV(aNode) ;

  CGAL_STSKEL_BUILDER_TRACE ( 3, "Updating PQ for N" << aNode->id() << " Prev N" << lPrev->id() << " Next N" << lNext->id() ) ;

  Halfedge_handle lOBisector_P = lPrev->primary_bisector() ;
  Halfedge_handle lOBisector_C = aNode->primary_bisector() ;
  Halfedge_handle lOBisector_N = lNext->primary_bisector() ;

  if ( AreBisectorsCoincident(lOBisector_C,lOBisector_P) )
    HandleSimultaneousEdgeEvent( aNode, lPrev ) ;
  else
  if ( AreBisectorsCoincident(lOBisector_C,lOBisector_N) )
    HandleSimultaneousEdgeEvent( aNode, lNext ) ;
  else
     CollectNewEvents(aNode);
}
template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::CreateInitialEvents()
{
  CGAL_STSKEL_BUILDER_TRACE(0, "Creating initial events...");
  for ( Vertex_iterator v = mSSkel->vertices_begin(); v != mSSkel->vertices_end(); ++ v )
  {
    UpdatePQ(v);
    mVisitor.on_initial_events_collected(v,IsReflex(v),IsDegenerate(v)) ;
  }
}


template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::CreateContourBisectors()
{
  CGAL_STSKEL_BUILDER_TRACE(0, "Creating contour bisectors...");
  for ( Vertex_iterator v = mSSkel->vertices_begin(); v != mSSkel->vertices_end(); ++ v )
  {
    mSLAV.push_back(static_cast<Vertex_handle>(v));
    Vertex_handle lPrev = GetPrevInLAV(v) ;
    Vertex_handle lNext = GetNextInLAV(v) ;

    Orientation lOrientation = CGAL::orientation(lPrev->point(),v->point(),lNext->point()); 
    if ( lOrientation == COLLINEAR )
    {
      SetIsDegenerate(v);
      CGAL_STSKEL_BUILDER_TRACE(1, "COLLINEAR vertex: N" << v->id() );
    }
    else if ( lOrientation == RIGHT_TURN )
    {
      mReflexVertices.push_back(v);
      SetIsReflex(v);
      CGAL_STSKEL_BUILDER_TRACE(1,"Reflex vertex: N" << v->id() );
    }

    Halfedge lOB(mEdgeID++), lIB(mEdgeID++);
    Halfedge_handle lOBisector = mSSkel->SSkel::Base::edges_push_back (lOB, lIB);
    Halfedge_handle lIBisector = lOBisector->opposite();
    lOBisector->HBase_base::set_face(v->halfedge()->face());
    lIBisector->HBase_base::set_face(v->halfedge()->next()->face());
    lIBisector->HBase_base::set_vertex(v);

    Halfedge_handle lIBorder = v->halfedge() ;
    Halfedge_handle lOBorder = v->halfedge()->next() ;
    lIBorder  ->HBase_base::set_next(lOBisector);
    lOBisector->HBase_base::set_prev(lIBorder);
    lOBorder  ->HBase_base::set_prev(lIBisector);
    lIBisector->HBase_base::set_next(lOBorder);
    CGAL_STSKEL_BUILDER_TRACE(3
                             ,"Adding Contour Bisector at N:" << v->id() << "\n B" << lOBisector->id()
                             << " (Out)\n B" << lIBisector->id() << " (In)"
                             ) ;
  }
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::InitPhase()
{
  mVisitor.on_initialization_started(mSSkel->size_of_vertices());
  CreateContourBisectors();
  CreateInitialEvents();
  mVisitor.on_initialization_finished();
}

template<class Gt, class SS, class V>
typename Straight_skeleton_builder_2<Gt,SS,V>::Vertex_handle
Straight_skeleton_builder_2<Gt,SS,V>::ConstructEdgeEventNode( EdgeEvent& aEvent )
{
  CGAL_STSKEL_BUILDER_TRACE ( 2, "Creating EdgeEvent Node" ) ;

  Vertex_handle lLSeed = aEvent.seed0() ;
  Vertex_handle lRSeed = aEvent.seed1() ;

  Vertex_handle lNewNode = mSSkel->SSkel::Base::vertices_push_back( Vertex( mVertexID++, aEvent.point(), aEvent.time()) ) ;
  mSLAV.push_back(lNewNode);

  InitVertexData(lNewNode);
  SetSeededTrisegment(lNewNode,aEvent.strisegment());
  
  Halfedge_handle lLOBisector = lLSeed->primary_bisector();
  Halfedge_handle lROBisector = lRSeed->primary_bisector();
  Halfedge_handle lLIBisector = lLOBisector->opposite();
  Halfedge_handle lRIBisector = lROBisector->opposite();

  lNewNode->VBase::set_halfedge(lLOBisector);
  lLOBisector->HBase_base::set_vertex(lNewNode);
  lROBisector->HBase_base::set_vertex(lNewNode);

  lLIBisector->HBase_base::set_prev( lROBisector ) ;
  lROBisector->HBase_base::set_next( lLIBisector ) ;

  CGAL_STSKEL_BUILDER_TRACE
  ( 3
  ,    "LSeed: N" << lLSeed->id() << " proccesed\n"
    << "RSeed: N" << lRSeed->id() << " proccesed"
  ) ;

  SetIsProcessed(lLSeed) ;
  SetIsProcessed(lRSeed) ;
  mSLAV.remove(lLSeed);
  mSLAV.remove(lRSeed);

  Vertex_handle lLPrev = GetPrevInLAV(lLSeed) ;
  Vertex_handle lRNext = GetNextInLAV(lRSeed) ;

  SetPrevInLAV(lNewNode, lLPrev ) ;
  SetNextInLAV(lLPrev  , lNewNode  ) ;

  SetNextInLAV(lNewNode, lRNext ) ;
  SetPrevInLAV(lRNext  , lNewNode  ) ;

  CGAL_STSKEL_BUILDER_TRACE
  ( 2
  ,    "LO: B" << lLOBisector->id() << " LI: B" << lLIBisector->id() << " RO: B" << lROBisector->id() << " RI: B" << lRIBisector->id() << '\n'
    << "New Node: N" << lNewNode->id() << " at " << lNewNode->point() << '\n'
    << "New Links: B" << lROBisector->id() << "->B" << lLIBisector->id() << '\n'
    << 'N' << lNewNode->id() << " inserted into LAV: N" << lLPrev->id() << "->N" << lNewNode->id() << "->N" << lRNext->id() << std::endl
    << 'N' << lLSeed->id() << " removed from LAV\n"
    << 'N' << lRSeed->id() << " removed from LAV"
  );


  return lNewNode ;
}


 template<class Gt, class SS, class V>
typename Straight_skeleton_builder_2<Gt,SS,V>::Vertex_handle
Straight_skeleton_builder_2<Gt,SS,V>::LookupOnSLAV ( Halfedge_handle aBorder, EventPtr const& aEvent )
{
  Vertex_handle rResult ;

  CGAL_STSKEL_BUILDER_TRACE ( 3, "Looking up for E" << aBorder->id() << " on SLAV. P=" << aEvent->point() ) ;

  CGAL_STSKEL_DEBUG_CODE( bool lFound = false ; )

  for ( typename std::list<Vertex_handle>::const_iterator vi = mSLAV.begin(); vi != mSLAV.end(); ++ vi )
  {
    Vertex_handle v = *vi;
 
    Triedge lTriedge = GetTriedge(v);
       
    if (  handle_assigned(GetPrevInLAV(v))
       && handle_assigned(GetNextInLAV(v))
       && lTriedge.e0() == aBorder
       )
    {
      CGAL_STSKEL_DEBUG_CODE( lFound = true ; )

      Vertex_handle lPrev = GetPrevInLAV(v);
      Vertex_handle lNext = GetNextInLAV(v);
      
      Halfedge_handle lPrevBorder = GetTriedge(lPrev).e0();
      Halfedge_handle lNextBorder = GetTriedge(lNext).e0();
      
      CGAL_assertion(handle_assigned(lPrevBorder));
      CGAL_assertion(handle_assigned(lNextBorder));
      
      CGAL_STSKEL_BUILDER_TRACE ( 3
                                , "Subedge found in SLAV: N" << lPrev->id() << "->N" << v->id()
                                  << " (E" << lPrevBorder->id() << "->E" << aBorder->id() << "->E" << lNextBorder->id() << ")"
                                ) ;
                                
      if ( IsSplitEventInsideOffsetZone( aEvent, Triedge(lPrevBorder, aBorder, lNextBorder), lPrev, v ) )
      {
        rResult = v ;
        CGAL_STSKEL_BUILDER_TRACE ( 3, "That's the correct subedge. Found") ;
        break ;
      }
    }
  }
  
#ifdef CGAL_STRAIGHT_SKELETON_ENABLE_TRACE