straight_skeleton_builder_2_impl.h

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

// // Copyright (c) 2005, 2006 Fernando Luis Cacciola Carballal. All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Straight_skeleton_2/include/CGAL/Straight_skeleton_2/Straight_skeleton_builder_2_impl.h $
// $Id: Straight_skeleton_builder_2_impl.h 37144 2007-03-16 08:17:51Z afabri $
//
// Author(s)     : Fernando Cacciola <[e-mail]>
//
#ifndef CGAL_STRAIGHT_SKELETON_BUILDER_2_IMPL_H
#define CGAL_STRAIGHT_SKELETON_BUILDER_2_IMPL_H 1

#include <boost/bind.hpp>
#include <boost/utility.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <CGAL/Unique_hash_map.h>

#include <CGAL/Real_timer.h>

#if defined(BOOST_MSVC)
#  pragma warning(push)
#  pragma warning(disable:4355) // complaint about using 'this' to
#endif                          // initialize a member

CGAL_BEGIN_NAMESPACE

namespace {

template<class Handle> inline bool handle_assigned ( Handle const& aH )
{
  Handle null ;
  return aH != null ;
}

}


template<class Gt, class SS, class V>
Straight_skeleton_builder_2<Gt,SS,V>::Straight_skeleton_builder_2 ( Traits const& aTraits, Visitor const& aVisitor )
  :
  mTraits(aTraits)
 ,mVisitor(aVisitor)
 ,mEventCompare(this)
 ,mVertexID(0)
 ,mEdgeID(0)
 ,mEventID(0)
 ,mStepID(0)
 ,mPQ(mEventCompare)
 ,mSSkel( new SSkel() )
{
}

// This is defined out-of-class, here, just so it's easy to set a breakpoint
template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::throw_error ( char const* what ) const
{
  throw straight_skeleton_exception(what);
}

template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::InsertEventInPQ( EventPtr aEvent )
{
  mPQ.push(aEvent);
  CGAL_STSKEL_BUILDER_TRACE(2, "Main PQ: " << *aEvent);
}

template<class Gt, class SS, class V>
typename Straight_skeleton_builder_2<Gt,SS,V>::EventPtr 
Straight_skeleton_builder_2<Gt,SS,V>::PopEventFromPQ()
{
  EventPtr rR = mPQ.top(); mPQ.pop();
  return rR ;
}

// Tests whether there is an edge event between the 3 contour edges defining nodes 'aLnode' and 'aRNode'.
// If such event exits and is not in the past, it's returned. Otherwise the result is null
//
template<class Gt, class SS, class V>
typename Straight_skeleton_builder_2<Gt,SS,V>::EventPtr
Straight_skeleton_builder_2<Gt,SS,V>::FindEdgeEvent( Vertex_handle aLNode, Vertex_handle aRNode )
{
  EventPtr rResult ;
 
  Triedge lTriedge = GetTriedge(aLNode) & GetTriedge(aRNode) ;
  
  if ( lTriedge.is_valid() )
  {
    Seeded_trisegment_2 lSTrisegment = CreateSeededTrisegment(lTriedge,aLNode,aRNode);
    
    if ( ExistEvent(lSTrisegment) )
    {
      bool lAccepted = true ;

      if ( IsNewEventInThePast(lSTrisegment,aLNode) )
        lAccepted = false ;

      if ( IsNewEventInThePast(lSTrisegment,aRNode) )
        lAccepted = false ;

      if ( lAccepted )
      {
        rResult = EventPtr( new EdgeEvent( lTriedge, lSTrisegment, aLNode, aRNode ) ) ;

        mVisitor.on_edge_event_created(aLNode, aRNode) ;
        
        CGAL_STSKEL_DEBUG_CODE( SetEventTimeAndPoint(*rResult) );
      }
    }
  }
  return rResult ;
}

template<class Gt, class SS, class V>
bool Straight_skeleton_builder_2<Gt,SS,V>::IsInverseSplitEventCoincident( Vertex_handle const&        aReflexOppN 
                                                                        , Triedge const&              aEventTriedge
                                                                        , Seeded_trisegment_2 const&  aEventSTrisegment
                                                                        )
{
  Triedge lOppTriedge = GetTriedge(aReflexOppN);
  
  Triedge lOppLTriedge(lOppTriedge.e0(),lOppTriedge.e1(),aEventTriedge.e0());
  Triedge lOppRTriedge(lOppTriedge.e0(),lOppTriedge.e1(),aEventTriedge.e1());
  
  Vertex_handle null ;
  
  Seeded_trisegment_2 lOppLSTrisegment = CreateSeededTrisegment(lOppLTriedge,aReflexOppN,null);
  Seeded_trisegment_2 lOppRSTrisegment = CreateSeededTrisegment(lOppRTriedge,aReflexOppN,null);

  return (  (  lOppLSTrisegment.event().collinearity() != TRISEGMENT_COLLINEARITY_02 
            && ExistEvent(lOppLSTrisegment) 
            && AreEventsSimultaneous(aEventSTrisegment,lOppLSTrisegment) 
            )
         || (  lOppRSTrisegment.event().collinearity() != TRISEGMENT_COLLINEARITY_02 
            && ExistEvent(lOppRSTrisegment) 
            && AreEventsSimultaneous(aEventSTrisegment,lOppRSTrisegment) 
            )
         ) ;
}

template<class Gt, class SS, class V>
typename Straight_skeleton_builder_2<Gt,SS,V>::EventPtr 
Straight_skeleton_builder_2<Gt,SS,V>::IsPseudoSplitEvent( EventPtr const& aEvent, Vertex_handle aOppN )
{
  bool lIsPseudoSplitEvent = false ;
  bool lCoupleIsPrev       = false ;

  SplitEvent& lEvent = dynamic_cast<SplitEvent&>(*aEvent) ;
  
  Triedge              lEventTriedge     = lEvent.triedge();
  Seeded_trisegment_2  lEventSTrisegment = lEvent.strisegment();
  Vertex_handle        lSeedN            = lEvent.seed0();
  
  Vertex_handle lOppPrevN = GetPrevInLAV(aOppN) ;       
  
  if ( IsReflex(lOppPrevN) && IsInverseSplitEventCoincident(lOppPrevN,lEventTriedge,lEventSTrisegment) )
  {
    lIsPseudoSplitEvent = true ;
    lCoupleIsPrev       = true ;
    CGAL_STSKEL_BUILDER_TRACE(1,"Pseudo-split-event found against N" << lOppPrevN->id() ) ;
  }
  else if ( IsReflex(aOppN) && IsInverseSplitEventCoincident(aOppN,lEventTriedge,lEventSTrisegment) )
  {
    lIsPseudoSplitEvent = true ;
    lCoupleIsPrev       = false ;
    CGAL_STSKEL_BUILDER_TRACE(1,"Pseudo-split-event found against E" << aOppN->id() ) ;
  }

  EventPtr rPseudoSplitEvent ;

  if ( lIsPseudoSplitEvent )
  {
    if ( lCoupleIsPrev )
    {
      rPseudoSplitEvent = EventPtr( new PseudoSplitEvent(lEventTriedge,lEventSTrisegment,lOppPrevN,lSeedN) ) ;

      mVisitor.on_pseudo_split_event_created(lOppPrevN,lSeedN) ;
    }
    else
    {
      rPseudoSplitEvent = EventPtr( new PseudoSplitEvent(lEventTriedge, lEventSTrisegment, lSeedN, aOppN) ) ;  

      mVisitor.on_pseudo_split_event_created(lSeedN,aOppN) ;
    }

    rPseudoSplitEvent->SetTimeAndPoint(aEvent->time(),aEvent->point());
  }

  return rPseudoSplitEvent ;
}

// Tests whether there is a split event between the contour edges (aReflexLBorder,aReflexRBorder,aOppositeBorder).
// If such event exits and is not in the past, it's returned. Otherwise the result is null
// 'aReflexLBorder' and 'aReflexRBorder' are consecutive contour edges which 'aNode' as the vertex.
// 'aOppositeBorder' is some other edge in the polygon which, if the event exists, is split by the reflex wavefront.
//
// NOTE: 'aNode' can be a skeleton node (an interior split event produced by a previous vertex event). In that case,
// the 'reflex borders' are not consecutive in the input polygon but they are in the corresponding offset polygon that
// contains aNode as a vertex.
//
template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::CollectSplitEvent( Vertex_handle aNode, Triedge const& aTriedge )
{
  if ( IsOppositeEdgeFacingTheSplitSeed(aNode,aTriedge.e2()) )
  {
    Vertex_handle null ;
    
    Seeded_trisegment_2 lSTrisegment = CreateSeededTrisegment(aTriedge,aNode,null);
    
    if ( lSTrisegment.event().collinearity() != TRISEGMENT_COLLINEARITY_02 && ExistEvent(lSTrisegment) )
    {
      if ( !IsNewEventInThePast(lSTrisegment,aNode) )
      {
        EventPtr lEvent = EventPtr( new SplitEvent (aTriedge,lSTrisegment,aNode) ) ;
        
        mVisitor.on_split_event_created(aNode) ;
 
        CGAL_STSKEL_DEBUG_CODE( SetEventTimeAndPoint(*lEvent) ) ;
  
        AddSplitEvent(aNode,lEvent);      
      }
    }
  }
}

// Tests the reflex wavefront emerging from 'aNode' against the other contour edges in search for split events.
template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::CollectSplitEvents( Vertex_handle aNode )
{
  // lLBorder and lRBorder are the consecutive contour edges forming the reflex wavefront.
  Triedge lTriedge = GetTriedge(aNode);
  
  Halfedge_handle lLBorder = lTriedge.e0();
  Halfedge_handle lRBorder = lTriedge.e1();
  
  // For a strictly simple polygon, without antennas, it can be shown that the reflex wavefront cannot split 
  // the edges adjacent to it (the prev and next of each wavefront edge), so these are excluded from the search.
  // (this is NOT an optimization, they must be excluded otherwise an illegal split event could be found)
  
  Vertex_handle lPrev = GetPrevInLAV(aNode) ;
  Vertex_handle lNext = GetNextInLAV(aNode) ;

  Halfedge_handle lLBorderP = lLBorder->opposite()->next()->opposite();
  Halfedge_handle lLBorderN = lLBorder->opposite()->prev()->opposite();
  Halfedge_handle lRBorderP = lRBorder->opposite()->next()->opposite();
  Halfedge_handle lRBorderN = lRBorder->opposite()->prev()->opposite();

  CGAL_STSKEL_BUILDER_TRACE(3
                      ,"Finding SplitEvent for N" << aNode->id()
                      << " LBorder: E" << lLBorder->id() << " RBorder: E" << lRBorder->id()
                      << " LBorderP: E" << lLBorderP->id() << " LBorderN: E" << lLBorderN->id()
                      << " RBorderP: E" << lRBorderP->id() << " RBorderN: E" << lRBorderN->id()
                      );

  for ( Halfedge_handle_vector_iterator i = mContourHalfedges.begin(); i != mContourHalfedges.end(); ++ i )
  {
    Halfedge_handle lOpposite = *i ;

    if (    lOpposite != lLBorder
         && lOpposite != lRBorder
         && lOpposite != lLBorderP
         && lOpposite != lLBorderN
         && lOpposite != lRBorderP
         && lOpposite != lRBorderN
       )
      CollectSplitEvent(aNode, Triedge(lLBorder, lRBorder, lOpposite) ) ;
  }
}


// Finds and enques all the new potential events produced by the vertex wavefront emerging from 'aNode' (which can be a reflex wavefront).
// This new events are simply stored in the priority queue, not processed.
template<class Gt, class SS, class V>
void Straight_skeleton_builder_2<Gt,SS,V>::CollectNewEvents( Vertex_handle aNode )
{
  // A Straight Skeleton is the trace of the 'grassfire propagation' that corresponds to the inward move of all the vertices 
  // of a polygon along their angular bisectors.
  // Since vertices are the common endpoints of contour edges, the propagation corresponds to contour edges moving inward,
  // shrinking and expanding as neccesasry to keep the vertices along the angular bisectors.
  // At each instant in time the current location of vertices (and edges) describe the current 'Offset polygon'
  // (with at time zero corresponds to the input polygon).
  // 
  // An 'edge wavefront' is a moving contour edge.
  // A 'vertex wavefront' is the wavefront of two consecutive edge wavefronts (sharing a moving vertex).
  //
  // An 'Event' is the coallision of 2 wavefronts.
  // Each event changes the topology of the shrinking polygon; that is, at the event, the current polygon differs from the
  // inmediately previous polygon in the number of vertices.
  //
  // If 2 vertex wavefronts sharing a common edge collide, the event is called an edge event. At the time of the event, the current
  // polygon doex not have the common edge anynmore, and the two vertices become one. This new 'skeleton' vertex generates a new
  // vertex wavefront which can further collide with other wavefronts, producing for instance, more edge events.
  //
  // If a refex vertex wavefront collide with an edge wavefront, the event is called a split event. At the time of the event, the current
  // polygon is split in two unconnected polygons, each one containing a portion of the edge hit and split by the reflex wavefront.
  //
  // If 2 reflex wavefronts collide each other, the event is called a vertex event. At the time of the event, the current polygon
  // is split in two unconnected polygons. Each one contains a different combination of the colliding reflex edges. That is, if the
  // wavefront (edgea,edgeb) collides with (edgec,edged), the two resulting polygons will contain (edgea,edgec) and (edgeb,edged).
  // Furthermore, one of the new vertices can be a reflex vertex generating a reflex wavefront which can further produce more split or
  // vertex events (or edge events of course)
  // 
  // Each vertex wavefront (reflex or not) results in one and only one event from a set of possible events.
  // It can result in a edge event against the vertex wavefronts emerging from the adjacent vertices (in the current polygon, not
  // in the input polygon); or it can result in a split event (or vertex event) against any other wavefront in the rest of 
  // current polygon.

  
  // Adjacent vertices in the current polygon containing aNode (called LAV)
  Vertex_handle lPrev = GetPrevInLAV(aNode) ;
  Vertex_handle lNext = GetNextInLAV(aNode) ;

  CGAL_STSKEL_BUILDER_TRACE
    ( 2
    , "Collecting new events generated by N" << aNode->id() << " at " << aNode->point() << " (Prev: N" << lPrev->id() << " Next: N"
       << lNext->id() << ")"
    ) ;

  if ( IsReflex(aNode) )
    CollectSplitEvents(aNode) ;
    
  EventPtr lLEdgeEvent = FindEdgeEvent( lPrev , aNode ) ;
  EventPtr lREdgeEvent = FindEdgeEvent( aNode , lNext ) ;

  bool lAcceptL = !!lLEdgeEvent ;