straight_skeleton_builder_2_impl.h

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

      << "New Bisector OR:\nB" << lNOBisector_R->id()
      << "[E" << lNOBisector_R            ->defining_contour_edge()->id()
      << ",E" << lNOBisector_R->opposite()->defining_contour_edge()->id() << "]"
      << " (Out: Prev: B" << lNOBisector_R->prev()->id() << ")\n"
      << "New Bisector IR:\nB" << lNIBisector_R->id()
      << "[E" << lNIBisector_R            ->defining_contour_edge()->id()
      << ",E" << lNIBisector_R->opposite()->defining_contour_edge()->id()
      << "] (In: Next: B" << lNIBisector_R->next()->id() << ")\n"
      << "N" << lNewNode_L->id() << " halfedge: " << lNewNode_L->halfedge()->id()
      << " primary bisector: B" << lNewNode_L->primary_bisector()->id() << '\n'
      << "N" << lNewNode_R->id() << " halfedge: " << lNewNode_R->halfedge()->id()
      << " primary bisector: B" << lNewNode_R->primary_bisector()->id()
    ) ;

  UpdatePQ(lNewNode_L);
  UpdatePQ(lNewNode_R);

  mVisitor.on_split_event_processed(lSeed,lNewNode_L,lNewNode_R) ;
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::SetupPseudoSplitEventNode( Vertex_handle   aNode
                                                                    , Halfedge_handle aDefiningBorderA
                                                                    , Halfedge_handle aDefiningBorderB
                                                                    )
{
  Point_2 p = aDefiningBorderA->opposite()->vertex()->point() ;
  Point_2 q = aDefiningBorderA->opposite()->prev()->vertex()->point() ;
  Point_2 r = aDefiningBorderB->opposite()->prev()->vertex()->point() ;

  Orientation lOrientation = CGAL::orientation(p,q,r) ;
  if ( lOrientation == COLLINEAR )
  {
    SetIsDegenerate(aNode);
    CGAL_STSKEL_BUILDER_TRACE(1, "COLLINEAR *NEW* vertex: N" << aNode->id() );
  }
  else if ( lOrientation == RIGHT_TURN )
  {
    mReflexVertices.push_back(aNode);
    SetIsReflex(aNode);
    CGAL_STSKEL_BUILDER_TRACE(1, "Reflex *NEW* vertex: N" << aNode->id() );
  }
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::HandlePseudoSplitEvent( EventPtr aEvent )
{
  
  PseudoSplitEvent& lEvent = dynamic_cast<PseudoSplitEvent&>(*aEvent) ;
  
  Vertex_handle lLSeed = lEvent.seed0() ;
  Vertex_handle lRSeed = lEvent.seed1() ;

  Vertex_handle lNewNode_L, lNewNode_R ;
  boost::tie(lNewNode_L,lNewNode_R) = ConstructPseudoSplitEventNodes(lEvent);

  Halfedge_handle lNBisector_LO = mSSkel->SSkel::Base::edges_push_back ( Halfedge(mEdgeID++),Halfedge(mEdgeID++) );
  Halfedge_handle lNBisector_RO = mSSkel->SSkel::Base::edges_push_back ( Halfedge(mEdgeID++),Halfedge(mEdgeID++) );
  Halfedge_handle lNBisector_LI = lNBisector_LO->opposite();
  Halfedge_handle lNBisector_RI = lNBisector_RO->opposite();

  Halfedge_handle lSBisector_LO = lLSeed->primary_bisector() ;
  Halfedge_handle lSBisector_LI = lSBisector_LO->opposite();

  Halfedge_handle lSBisector_RO = lRSeed->primary_bisector() ;
  Halfedge_handle lSBisector_RI = lSBisector_RO->opposite();

  lNBisector_LO->HBase_base::set_face(lSBisector_LO->face());
  lNBisector_LI->HBase_base::set_face(lSBisector_RI->face());
  lNBisector_RO->HBase_base::set_face(lSBisector_RO->face());
  lNBisector_RI->HBase_base::set_face(lSBisector_LI->face());

  lNBisector_LI->HBase_base::set_vertex(lNewNode_L);
  lNBisector_RI->HBase_base::set_vertex(lNewNode_R);

  lSBisector_LO->HBase_base::set_next(lNBisector_LO);
  lNBisector_LO->HBase_base::set_prev(lSBisector_LO);

  lSBisector_LI->HBase_base::set_prev(lNBisector_RI);
  lNBisector_RI->HBase_base::set_next(lSBisector_LI);

  lSBisector_RI->HBase_base::set_prev(lNBisector_LI);
  lNBisector_LI->HBase_base::set_next(lSBisector_RI);

  lSBisector_RO->HBase_base::set_next(lNBisector_RO);
  lNBisector_RO->HBase_base::set_prev(lSBisector_RO);

  lNewNode_L->VBase::set_halfedge(lSBisector_LO);
  lNewNode_R->VBase::set_halfedge(lSBisector_RO);

  Halfedge_handle lNewNode_L_DefiningBorderA = lNewNode_L->halfedge()->face()->halfedge();
  Halfedge_handle lNewNode_L_DefiningBorderB = lNewNode_L->halfedge()->next()->opposite()->face()->halfedge();
  Halfedge_handle lNewNode_L_DefiningBorderC = lNewNode_L->halfedge()->opposite()->prev()->face()->halfedge();
  Halfedge_handle lNewNode_R_DefiningBorderA = lNewNode_R->halfedge()->face()->halfedge();
  Halfedge_handle lNewNode_R_DefiningBorderB = lNewNode_R->halfedge()->next()->opposite()->face()->halfedge();
  Halfedge_handle lNewNode_R_DefiningBorderC = lNewNode_R->halfedge()->opposite()->prev()->face()->halfedge();

  SetTriedge(lNewNode_L, Triedge(lNewNode_L_DefiningBorderA, lNewNode_L_DefiningBorderB, lNewNode_L_DefiningBorderC) )  ;
  SetTriedge(lNewNode_R, Triedge(lNewNode_R_DefiningBorderA, lNewNode_R_DefiningBorderB, lNewNode_R_DefiningBorderC) )  ;

  CGAL_STSKEL_BUILDER_TRACE
    (2
    ,    "New Node L: N" << lNewNode_L->id() << " at " << lNewNode_L->point()
      << " defining borders: E" << lNewNode_L_DefiningBorderA->id()
      << ",E" << lNewNode_L_DefiningBorderB->id()
      << ",E" << lNewNode_L_DefiningBorderC->id() << '\n'
      << "New Node R: N" << lNewNode_R->id() << " at " << lNewNode_R->point()
      << " defining borders: E" << lNewNode_R_DefiningBorderA->id()
      << ",E" << lNewNode_R_DefiningBorderB->id()
      << ",E" << lNewNode_R_DefiningBorderC->id() << '\n'
      << "New Bisector LO: B" << lNBisector_LO->id()
      << "[E"  << lNBisector_LO            ->defining_contour_edge()->id()
      << ",E" << lNBisector_LO->opposite()->defining_contour_edge()->id() << "]\n"
      << "New Bisector LI: B" << lNBisector_LI->id()
      << "[E" << lNBisector_LI            ->defining_contour_edge()->id()
      << ",E" << lNBisector_LI->opposite()->defining_contour_edge()->id() << "]\n"
      << "New Bisector RO: B" << lNBisector_RO->id()
      << "[E" << lNBisector_RO            ->defining_contour_edge()->id()
      << ",E" << lNBisector_RO->opposite()->defining_contour_edge()->id() << "]\n"
      << "New Bisector RI: B" << lNBisector_RI->id()
      << "[E" << lNBisector_RI            ->defining_contour_edge()->id()
      << ",E" << lNBisector_RI->opposite()->defining_contour_edge()->id() << "]\n"
      << "N" << lNewNode_L->id() << " halfedge: " << lNewNode_L->halfedge()->id()
      << " primary bisector: B" << lNewNode_L->primary_bisector()->id() << '\n'
      << "N" << lNewNode_R->id() << " halfedge: " << lNewNode_R->halfedge()->id()
      << " primary bisector: B" << lNewNode_R->primary_bisector()->id()
    ) ;

  SetupPseudoSplitEventNode(lNewNode_L,lNewNode_L_DefiningBorderA,lNewNode_L_DefiningBorderB) ;
  SetupPseudoSplitEventNode(lNewNode_R,lNewNode_R_DefiningBorderA,lNewNode_R_DefiningBorderB) ;

  
  UpdatePQ(lNewNode_L);
  UpdatePQ(lNewNode_R);
  

  mVisitor.on_pseudo_split_event_processed(lLSeed,lRSeed,lNewNode_L,lNewNode_R) ;
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::HandleSplitOrPseudoSplitEvent( EventPtr aEvent )
{
  Vertex_handle lOppR = LookupOnSLAV(aEvent->triedge().e2(),aEvent);
  if ( handle_assigned(lOppR) )
  {
    EventPtr lPseudoSplitEvent = IsPseudoSplitEvent(aEvent,lOppR);
    if ( lPseudoSplitEvent )
         HandlePseudoSplitEvent(lPseudoSplitEvent);
    else HandleSplitEvent      (aEvent,lOppR);  
  }
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::InsertNextSplitEventInPQ( Vertex_handle v )
{
  EventPtr lSplitEvent = PopNextSplitEvent(v);
  if ( !!lSplitEvent )
    InsertEventInPQ(lSplitEvent);
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::InsertNextSplitEventsInPQ()
{
  for ( typename Vertex_handle_vector::iterator v = mReflexVertices.begin(), ev = mReflexVertices.end(); v != ev ; ++ v )
    if ( !IsProcessed(*v) )
      InsertNextSplitEventInPQ(*v);
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::Propagate()
{
  CGAL_STSKEL_BUILDER_TRACE(0,"Propagating events...");
  mVisitor.on_propagation_started();

  while ( !mPQ.empty() )
  {
    InsertNextSplitEventsInPQ();
       
    EventPtr lEvent = PopEventFromPQ();

    if ( lEvent->type() != Event::cEdgeEvent )    
      AllowNextSplitEvent(lEvent->seed0());

    if ( !IsProcessed(lEvent) )
    {
      CGAL_STSKEL_BUILDER_TRACE (1,"\nS" << mStepID << " Event: " << *lEvent ) ;

      SetEventTimeAndPoint(*lEvent) ;
      
      switch ( lEvent->type() )
      {
        case Event::cEdgeEvent       : HandleEdgeEvent              (lEvent) ; break ;
        case Event::cSplitEvent      : HandleSplitOrPseudoSplitEvent(lEvent) ; break ;
        case Event::cPseudoSplitEvent: HandlePseudoSplitEvent       (lEvent) ; break ; 
      }

      ++ mStepID ;
    }
  }
  
  mVisitor.on_propagation_finished();
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::MergeSplitNodes ( Vertex_handle_pair aSplitNodes )
{
  Vertex_handle lLNode, lRNode ;
  boost::tie(lLNode,lRNode)=aSplitNodes;

  Halfedge_handle lIBisectorL1 = lLNode->primary_bisector()->opposite();
  Halfedge_handle lIBisectorR1 = lRNode->primary_bisector()->opposite();
  Halfedge_handle lIBisectorL2 = lIBisectorL1->next()->opposite();
  Halfedge_handle lIBisectorR2 = lIBisectorR1->next()->opposite();
  
  CGAL_STSKEL_BUILDER_TRACE(2
                      ,"Merging SplitNodes: (L) N" << lLNode->id() << " and (R) N" << lRNode->id() << ".\n"
                       << "  LOut: B" << lLNode->primary_bisector()->id() << '\n'
                       << "  ROut: B" << lRNode->primary_bisector()->id() << '\n'
                       << "  LIn1: B" << lIBisectorL1->id() << '\n'
                       << "  RIn1: B" << lIBisectorR1->id() << '\n'
                       << "  LIn2: B" << lIBisectorL2->id() << '\n'
                       << "  RIn2: B" << lIBisectorR2->id() 
                       );

  if ( lIBisectorL1->vertex() == lRNode )
    lIBisectorL1->HBase_base::set_vertex(lLNode);

  if ( lIBisectorR1->vertex() == lRNode )
    lIBisectorR1->HBase_base::set_vertex(lLNode);

  if ( lIBisectorL2->vertex() == lRNode )
    lIBisectorL2->HBase_base::set_vertex(lLNode);

  if ( lIBisectorR2->vertex() == lRNode )
    lIBisectorR2->HBase_base::set_vertex(lLNode);

  CGAL_STSKEL_BUILDER_TRACE(2
                      ,   "  N" << lRNode->id() << " excluded.\n"
                       << "  LIn1 B" << lIBisectorL1->id() << " now linked to N" << lIBisectorL1->vertex()->id() << '\n'
                       << "  RIn1 B" << lIBisectorR1->id() << " now linked to N" << lIBisectorR1->vertex()->id() << '\n'
                       << "  LIn2 B" << lIBisectorL2->id() << " now linked to N" << lIBisectorL2->vertex()->id() << '\n'
                       << "  RIn2 B" << lIBisectorR2->id() << " now linked to N" << lIBisectorR2->vertex()->id()
                       );

  mSSkel->SSkel::Base::vertices_erase(lRNode);

}


#ifdef CGAL_STRAIGHT_SKELETON_ENABLE_TRACE
template<class Halfedge_handle>
void TraceMultinode( char const* t, Halfedge_handle b, Halfedge_handle e )
{
  std::ostringstream ss ;
  ss << t ;
  
  do
  {
    ss << "B" << b->id() << " N" << b->vertex()->id() << " " ;
  }
  while ( b = b->next(), b != e ) ;
  
  std::string s = ss.str();
  CGAL_STSKEL_BUILDER_TRACE(0, s);
}


template<class Point>
double angle_wrt_X ( Point const& a, Point const& b )
{
  double dx = to_double(b.x() - a.x() ) ;
  double dy = to_double(b.y() - a.y() ) ;
  double atan = std::atan2(dy,dx);
  double rad  = atan >= 0.0 ? atan : 2.0 * 3.141592 + atan ;
  double deg  = rad * 180.0 / 3.141592 ;
  return deg ;
}

template<class Vertex_handle, class Halfedge_around_vertex_circulator>
void TraceFinalBisectors( Vertex_handle v, Halfedge_around_vertex_circulator cb )
{
  Halfedge_around_vertex_circulator c = cb ;

  do
  {
    double phi = angle_wrt_X((*c)->vertex()->point(),(*c)->opposite()->vertex()->point());
    
    CGAL_STSKEL_BUILDER_TRACE(2, "  N" << v->id() << " in=B" << (*c)->id() 
                        << " E" << (*c)->defining_contour_edge()->id() 
                        << " out=B" << (*c)->opposite()->id() 
                        << " E" << (*c)->opposite()->defining_contour_edge()->id() 
                        << " phi=" << phi
                        );
    
    ++ c ;
  }
  while( c != cb ) ;
  
}
#endif

template<class Vertex_handle, class Halfedge_around_vertex_circulator>
bool ValidateFinalBisectorsAfterMerge( Vertex_handle /* v */, Halfedge_around_vertex_circulator cb )
{
  bool rOK = true ;
  
  Halfedge_around_vertex_circulator c = cb ;

  do
  {
    if ( (*c)->defining_contour_edge() != (*c)->prev()->defining_contour_edge() )
      rOK = false ;
      
    ++ c ;
  }
  while( rOK && c != cb ) ;
  
  return rOK ;
  
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::RelinkBisectorsAroundMultinode( Vertex_handle const& v0, Halfedge_handle_vector& aLinks )
{
  CGAL_assertion( aLinks.size() > 0 ) ;
  
  CGAL_STSKEL_BUILDER_TRACE(4, "Relinking " << aLinks.size() << " bisectors around N" << v0->id() ) ;
  
  // Connect the bisectors with each other following the CCW ordering
  
  Halfedge_handle first_he = aLinks.front();        
  Halfedge_handle prev_he  = first_he ;