straight_skeleton_builder_2_impl.h

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

  
  first_he->HBase_base::set_vertex(v0);
  
  for ( typename Halfedge_handle_vector::iterator i = successor(aLinks.begin()), ei = aLinks.end(); i != ei ; ++ i )
  {
    Halfedge_handle he = *i ;

    he->HBase_base::set_vertex(v0);
            
    Halfedge_handle prev_he_opp = prev_he->opposite();
    
    he         ->HBase_base::set_next(prev_he_opp);
    prev_he_opp->HBase_base::set_prev(he);

    CGAL_STSKEL_BUILDER_TRACE(4, "Relinking B" << he->id() << "->B" << prev_he_opp->id() ) ;
    
    prev_he = he ;
  }

  Halfedge_handle prev_he_opp = prev_he->opposite();
    
  first_he   ->HBase_base::set_next(prev_he_opp);
  prev_he_opp->HBase_base::set_prev(first_he);

  CGAL_STSKEL_BUILDER_TRACE(4, "Relinking B" << first_he->id() << "->B" << prev_he_opp->id() ) ;
  
  // Reset the main halfedge for v0  
  v0->VBase::set_halfedge(first_he) ;
  
  CGAL_STSKEL_DEBUG_CODE( TraceFinalBisectors(v0,v0->halfedge_around_vertex_begin()); )

  CGAL_postcondition( ValidateFinalBisectorsAfterMerge(v0,v0->halfedge_around_vertex_begin()) ) ;
}


template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::PreprocessMultinode( Multinode& aMN )
{
  //
  // A Multinode is a run of coincident nodes along a face.
  // Its represented by a pair of halfedges describing a linear profile.
  // The first halfedge in the pair points to the first node in the multinode.
  // Each ->next() halfedge in the profile points to a subsequent node.
  // The second halfedge in the pair is past-the-end (it points to the first node around the face that IS NOT part of the multinode)
  //
  
  Halfedge_handle oend = validate(aMN.end->opposite());
  
  Halfedge_handle h = aMN.begin ;
 
  aMN.bisectors_to_relink.push_back(h);
  
  // Traverse the profile collecting:
  //  The nodes to be removed from the HDS (all but the first)
  //  The bisectors to be removed from the HDS (each bisector pointing to the next node in the multinode)
  //  The bisectors around each node that must be relinked to the first node (which will be kept in place of the multinode)
  do
  {
    ++ aMN.size ;
    Halfedge_handle nx = validate(h->next());
    if ( nx != aMN.end )
      aMN.bisectors_to_remove.push_back(nx);

    // Since each halfedge "h" in this lineal profile corresponds to a single face, all the bisectors around
    // each node which must be relinked are those found ccw between h and h->next()
    Halfedge_handle ccw = h ;
    Halfedge_handle ccw_end = validate(h->next()->opposite());
    for(;;)
    {
      ccw = validate(ccw->opposite()->prev()) ;
      if ( ccw != ccw_end )
           aMN.bisectors_to_relink.push_back(ccw);
      else break ;  
    }    
    if ( h != aMN.begin )
      aMN.nodes_to_remove.push_back(h->vertex());
      
    h = nx;
  }
  while ( h != aMN.end ) ;
  
  aMN.bisectors_to_relink.push_back(aMN.end->opposite());
  
  CGAL_STSKEL_DEBUG_CODE( TraceMultinode("Preprocessing multinode: ", aMN.begin,aMN.end) ) ;
}

//
// Replaces a run of coincident nodes with a single one by removing all but the first, remvong node-to-node bisectors and
// relinking the other bisectors.
//
template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::ProcessMultinode( Multinode&              aMN 
                                                           , Halfedge_handle_vector& rBisectorsToRemove 
                                                           , Vertex_handle_vector&   rNodesToRemove
                                                           )
{
  bool lSomeNodeAlreadyProcessed = false ;
  
  Halfedge_handle h = aMN.begin ;

  do
  {
    if ( IsExcluded(h->vertex()))
      lSomeNodeAlreadyProcessed = true ;
  }
  while ( h = h->next(), !lSomeNodeAlreadyProcessed && h != aMN.end ) ;
  
  if ( !lSomeNodeAlreadyProcessed )
  {
    CGAL_STSKEL_DEBUG_CODE( TraceMultinode("Processing multinode: ", aMN.begin,aMN.end) ) ;
    
    Halfedge_handle h = aMN.begin ;
    do
    {
      Exclude(h->vertex());
    }
    while ( h = h->next(), h != aMN.end ) ;

    std::copy(aMN.bisectors_to_remove.begin(), aMN.bisectors_to_remove.end(), std::back_inserter(rBisectorsToRemove));
    std::copy(aMN.nodes_to_remove    .begin(), aMN.nodes_to_remove    .end(), std::back_inserter(rNodesToRemove));
     
    RelinkBisectorsAroundMultinode(aMN.v,aMN.bisectors_to_relink);    
  }
}


template<class Gt, class SS, class V>
typename Straight_skeleton_builder_2<Gt,SS,V>::MultinodePtr
Straight_skeleton_builder_2<Gt,SS,V>::CreateMultinode( Halfedge_handle begin, Halfedge_handle end )
{
  return MultinodePtr( new Multinode(begin,end) );
}


//
// Finds coincident skeleton nodes and merge them
//
// If moving edges Ei,Ej collide with moving edge Ek causing Ej to collapse, Ei and Ek becomes consecutive and a new
// polygon vertex (Ei,Ek) appears in the wavefront.
// If moving edges Ei,Ej collide with moving edge Ek causing Ek to be split in two halves, L(Ek) amd R(Ek) resp, two new 
// polygon vertices appears in the wavefront; namely: (Ei,R(Ek)) and (L(Ek),Ej))
// If moving edge Ei,Ej collide with both Ek,El simultaneously causing the edges to cross-connect, two new vertices
// (Ei,Ek) and (El,Ej) appear in the wavefront.
//
// In all those 3 cases, each new polygon vertex is represented in the straight skeleton as a skeleton node.
// Every skeleton node is describing the coallision of at least 3 edges (called the "defining edges" of the node)
// and it has at least 3 incident bisectors, each one pairing 2 out of the total number of defining egdes. 
// 
// Any skeleton node has a degree of at least 3, but if more than 3 edges collide simultaneously, the corresponding
// skeleton node has a higher degree. (the degree of the node is exactly the number of colliding edges)
//
// However, the algorithm handles the coallison of 3 edges at a time so each skeleton node initially created
// has degree exactly 3 so this function which detects higher degree nodes and merge them into a single node
// of the proper degree is needed.
//
// Two skeleton nodes are "coincident" IFF they have 2 defining edges in common and each triedge of edges collide
// at the same time and point. IOW, 2 nodes are coincident if they represent the simultaneous 
// coallison of exactly 4 edges (the union of 2 triedges with 2 common elements is a set of 4).
//
template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::MergeCoincidentNodes()
{
  //
  // NOTE: This code might be executed on a topologically incosistent HDS, thus the need to check
  // the structure along the way.
  //

  CGAL_STSKEL_BUILDER_TRACE(0, "Merging coincident nodes...");

  // ALGORITHM DESCRIPTION:
  //
  // While circulating the bisectors along the face for edge Ei we find all those edges E* which
  // are or become consecutive to Ei during the wavefront propagation. Each bisector along the face:
  // (Ei,Ea), (Ei,Eb), (Ei,Ec), etcc pairs Ei with such other edge.
  // Between one bisector (Ei,Ea) and the next (Ei,Eb) there is skeleton node which represents
  // the coallision between the 3 edges (Ei,Ea,Eb).
  // It follows from the pairing that any skeleton node Ni, for example (Ei,Ea,Eb), neccesarily
  // shares two edges (Ei and Eb precisely) with any next skeleton node Ni+1 around the face.
  // That is, the triedge of defining edges that correspond to each skeleton node around the face follow this
  // sequence: (Ei,Ea,Eb), (Ei,Eb,Ec), (Ei,Ec,Ed), ...
  //
  // Any 2_ consecutive_ skeleton nodes around a face share 2 out of the 3 defining edges, which is one of the 
  // neccesary conditions for "coincidence". Therefore, coincident nodes can only come as consecutive along a face
  //

  MultinodeVector lMultinodes ;

  for( Face_iterator fit = mSSkel->SSkel::Base::faces_begin(); fit != mSSkel->SSkel::Base::faces_end(); ++fit)
  {
    // 'h' is the first (CCW) skeleton halfedge.
    Halfedge_handle h = validate(validate(fit->halfedge())->next());

    CGAL_assertion ( h->is_bisector() ) ;

    // 'last' is the last (CCW) skeleton halfedge
    Halfedge_handle last = validate(fit->halfedge()->prev()) ;

    CGAL_assertion ( last->is_bisector() ) ;
    CGAL_assertion ( last->vertex()->is_contour() ) ;

    Halfedge_handle h0 = h ;
    Vertex_handle   v0 = validate(h0->vertex()) ;

    CGAL_assertion ( v0->is_skeleton() ) ;

    h = validate(h->next()) ;

    while ( h != last )
    {
      Vertex_handle v = validate(h->vertex());

      CGAL_assertion ( v->is_skeleton() ) ;

      if ( !AreSkeletonNodesCoincident(v0,v) )
      {
        if ( h0->next() != h )
          lMultinodes.push_back( CreateMultinode(h0,h) );

        v0 = v ;
        h0 = h ;
      }

      h = validate(h->next());
    } 

    if ( h0->next() != h )
      lMultinodes.push_back( CreateMultinode(h0,h) );
  }

  //
  // The merging loop removes all but one of the coincident skeleton nodes and the halfedges between them.
  // But it can't physically erase those from the HDS while looping, so the nodes/bisector to erase 
  // are collected in these sequences are erased after the merging loop.
  // 
  Halfedge_handle_vector lBisectorsToRemove ;
  Vertex_handle_vector   lNodesToRemove ;

  for ( typename MultinodeVector::iterator it = lMultinodes.begin(), eit = lMultinodes.end() ; it != eit ; ++ it )
    PreprocessMultinode(**it);
    
  std::sort(lMultinodes.begin(), lMultinodes.end(), MultinodeComparer());
    
  for ( typename MultinodeVector::iterator it = lMultinodes.begin(), eit = lMultinodes.end() ; it != eit ; ++ it )
    ProcessMultinode(**it,lBisectorsToRemove,lNodesToRemove);
  
  for( Halfedge_handle_vector_iterator hi = lBisectorsToRemove.begin(), ehi = lBisectorsToRemove.end() ; hi != ehi ; ++ hi )
  {
    CGAL_STSKEL_BUILDER_TRACE(1, "B" << (*hi)->id() << " removed.");
    mSSkel->SSkel::Base::edges_erase(*hi);    
  }
    
  for( Vertex_handle_vector_iterator vi = lNodesToRemove.begin(), evi = lNodesToRemove.end() ; vi != evi ; ++ vi )
  {
    CGAL_STSKEL_BUILDER_TRACE(1, "N" << (*vi)->id() << " removed.");
    mSSkel->SSkel::Base::vertices_erase(*vi);    
  }  

}



template<class Gt, class SS, class V>
bool Straight_skeleton_builder_2<Gt,SS,V>::FinishUp()
{
  CGAL_STSKEL_BUILDER_TRACE(0, "\n\nFinishing up...");

  mVisitor.on_cleanup_started();
  
  std::for_each( mSplitNodes.begin()
                ,mSplitNodes.end  ()
                ,boost::bind(&Straight_skeleton_builder_2<Gt,SS,V>::MergeSplitNodes,this,_1)
               ) ;
  
  std::for_each( mDanglingBisectors.begin()
                ,mDanglingBisectors.end  ()
                ,boost::bind(&Straight_skeleton_builder_2<Gt,SS,V>::EraseBisector,this,_1)
               ) ;
               
  MergeCoincidentNodes();             

  mVisitor.on_cleanup_finished();

  return mSSkel->is_valid() ;
}

template<class Gt, class SS, class V>
bool Straight_skeleton_builder_2<Gt,SS,V>::Run()
{
  InitPhase();
  Propagate();
  return FinishUp();
}

template<class Gt, class SS, class V>
typename Straight_skeleton_builder_2<Gt,SS,V>::SSkelPtr Straight_skeleton_builder_2<Gt,SS,V>::construct_skeleton()
{
  bool ok = false ;
  
  try
  {
    ok = Run() ;
  }
  catch( std::exception const& e ) 
  {
    mVisitor.on_error ( e.what() ) ;
    CGAL_STSKEL_BUILDER_TRACE(0,"EXCEPTION THROWN (" << e.what() << ") during straight skeleton construction.");
 }

  if ( !ok ) 
  {
    CGAL_STSKEL_BUILDER_TRACE(0,"Invalid result.");
    mSSkel = SSkelPtr() ; 
  }

  mVisitor.on_algorithm_finished(ok);
  
  return mSSkel ;
}

CGAL_END_NAMESPACE

#if defined(BOOST_MSVC)
#  pragma warning(pop)
#endif

#endif // CGAL_STRAIGHT_SKELETON_BUILDER_2_IMPL_H //
// EOF //