lib/cpPlugins/Extensions/DataStructures/QuadEdge.hxx

   1 #ifndef __CPPLUGINS__EXTENSIONS__DATASTRUCTURES__QUADEDGE__HXX__
   2 #define __CPPLUGINS__EXTENSIONS__DATASTRUCTURES__QUADEDGE__HXX__
   3
   4 #include <limits>
   5
   6 // -------------------------------------------------------------------------
   7 template< typename P, typename D, bool IsPrimal >
   8 const typename cpPlugins::Extensions::DataStructures::
   9 QuadEdge< P, D, IsPrimal >::TPrimalGeometry
  10 cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
  11 NoGeometry = std::numeric_limits< P >::max( );
  12
  13 // -------------------------------------------------------------------------
  14 template< typename P, typename D, bool IsPrimal >
  15 void cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
  16 CreateRings( )
  17 {
  18   TPrimal* e = this;
  19   PtrDual r = TDual::New( );
  20   Pointer s = Self::New( );
  21   PtrDual i = TDual::New( );
  22
  23   // Create Rot ring
  24   e->m_Rot = r;
  25   r->m_Rot = s;
  26   s->m_Rot = i;
  27   i->m_Rot = e;
  28
  29   // Update Onext rings
  30   r->m_Onext = i;
  31   i->m_Onext = r;
  32 }
  33
  34 // -------------------------------------------------------------------------
  35 template< typename P, typename D, bool IsPrimal >
  36 void cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
  37 SetLnextRingGeometry( const D& v )
  38 {
  39   for( Iterator i = this->BeginLnext( ); i != this->EndLnext( ); ++i )
  40     ( *i )->SetLeft( v );
  41 }
  42
  43 // -------------------------------------------------------------------------
  44 template< typename P, typename D, bool IsPrimal >
  45 void cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
  46 UnsetLnextRingGeometry( )
  47 {
  48   this->SetLnextRingGeometry( TDual::NoGeometry );
  49 }
  50
  51 // -------------------------------------------------------------------------
  52 template< typename P, typename D, bool IsPrimal >
  53 bool cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
  54 IsEdgeInOnextRing( const TPrimal* e ) const
  55 {
  56   bool found = false;
  57   for(
  58     ConstIterator i = this->BeginOnext( );
  59     i != this->EndOnext( ) && !found;
  60     ++i
  61     )
  62     found |= ( *i == e );
  63   return( found );
  64 }
  65
  66 // -------------------------------------------------------------------------
  67 template< typename P, typename D, bool IsPrimal >
  68 bool cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
  69 IsEdgeInLnextRing( const TPrimal* e ) const
  70 {
  71   bool found = false;
  72   for(
  73     ConstIterator i = this->BeginLnext( );
  74     i != this->EndLnext( ) && !found;
  75     ++i
  76     )
  77     found |= ( *i == e );
  78   return( found );
  79 }
  80
  81 // -------------------------------------------------------------------------
  82 template< typename P, typename D, bool IsPrimal >
  83 unsigned int
  84 cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
  85 GetOnextRingSize( ) const
  86 {
  87   unsigned int count = 0;
  88   for(
  89     ConstIterator i = this->BeginOnext( );
  90     i != this->EndOnext( );
  91     ++i
  92     )
  93     count++;
  94   return( count );
  95 }
  96
  97 // -------------------------------------------------------------------------
  98 template< typename P, typename D, bool IsPrimal >
  99 unsigned int
 100 cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
 101 GetLnextRingSize( ) const
 102 {
 103   unsigned int count = 0;
 104   for(
 105     ConstIterator i = this->BeginLnext( );
 106     i != this->EndLnext( );
 107     ++i
 108     )
 109     count++;
 110   return( count );
 111 }
 112
 113 // -------------------------------------------------------------------------
 114 template< typename P, typename D, bool IsPrimal >
 115 bool cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
 116 IsAtBorder( ) const
 117 {
 118   return(
 119     (    this->IsLeftSet( )   && !( this->IsRightSet( ) ) ) ||
 120     ( !( this->IsLeftSet( ) ) &&    this->IsRightSet( )   )
 121     );
 122 }
 123
 124 // -------------------------------------------------------------------------
 125 template< typename P, typename D, bool IsPrimal >
 126 bool cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
 127 IsOriginInternal( ) const
 128 {
 129   bool internal = true;
 130   for(
 131     ConstIterator i = this->BeginOnext( );
 132     i != this->EndOnext( ) && internal;
 133     ++i
 134     )
 135     internal &= ( *i )->IsInternal( );
 136   return( internal );
 137 }
 138
 139 // -------------------------------------------------------------------------
 140 template< typename P, typename D, bool IsPrimal >
 141 typename cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
 142 TPrimal* cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
 143 GetNextBorderEdgeWithUnsetLeft( TPrimal* edge ) const
 144 {
 145   // Be sure the Onext ring isn't already full
 146   if( this->IsOriginInternal( ) )
 147     return( NULL );
 148
 149   // Update reference
 150   edge = ( edge == NULL )? const_cast< TPrimal* >( this ): edge;
 151
 152   // On efficiency purposes
 153   if( edge->IsIsolated( ) )
 154     return( edge );
 155
 156   // Ok, no more special cases
 157   const TPrimal* cedge = const_cast< const TPrimal* >( edge );
 158   ConstIterator it = cedge->BeginOnext( );
 159   TPrimal* found = NULL;
 160   for( ; it != cedge->EndOnext( ) && found == NULL; ++it )
 161     if( !( ( *it )->IsLeftSet( ) ) )
 162       found = const_cast< TPrimal* >( *it );
 163   return( found );
 164 }
 165
 166 // -------------------------------------------------------------------------
 167 template< typename P, typename D, bool IsPrimal >
 168 bool cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
 169 ReorderOnextRing( TPrimal* first, TPrimal* second )
 170 {
 171   // Making sure point adjacency is correct:
 172   if( first->GetOrigin( ) != second->GetOrigin( ) )
 173     return( false );
 174
 175   if( first->GetOnext( ) == second )
 176     return( true );
 177
 178   if( first->IsLeftSet( ) )
 179     return( false );
 180
 181   // Second is an internal edge.
 182   if( second->IsInternal( ) )
 183     return( false );
 184
 185   // Disconnect the triangles containing second:
 186   TPrimal* bsplice;
 187   if( second->IsLeftSet( ) )
 188     bsplice = second->GetNextBorderEdgeWithUnsetLeft( );
 189   else
 190     bsplice = second;
 191   TPrimal::Splice( second->GetOprev( ), bsplice );
 192
 193   // Reconnect second after first:
 194   TPrimal::Splice( first, bsplice );
 195   return( true );
 196 }
 197
 198 // -------------------------------------------------------------------------
 199 template< typename P, typename D, bool IsPrimal >
 200 void cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
 201 Splice( TPrimal* a, TPrimal* b )
 202 {
 203   // Don't waste time splicing the same edge (or non-existent)
 204   // remember: it is its own inverse!
 205   if( a != b || a == NULL || b == NULL )
 206   {
 207     TPrimal* aNext = a->m_Onext;
 208     TPrimal* bNext = b->m_Onext;
 209     TDual* al      = aNext->m_Rot;
 210     TDual* be      = bNext->m_Rot;
 211     TDual* alNext  = al->m_Onext;
 212     TDual* beNext  = be->m_Onext;
 213
 214     a->SetOnext( bNext );
 215     b->SetOnext( aNext );
 216     al->SetOnext( beNext );
 217     be->SetOnext( alNext );
 218
 219   } // fi
 220 }
 221
 222 // -------------------------------------------------------------------------
 223 template< typename P, typename D, bool IsPrimal >
 224 cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
 225 QuadEdge( )
 226   : m_Origin( Self::NoGeometry )
 227 {
 228   this->m_Onext = this;
 229   this->m_Rot = NULL;
 230 }
 231
 232 // -------------------------------------------------------------------------
 233 template< typename P, typename D, bool IsPrimal >
 234 cpPlugins::Extensions::DataStructures::QuadEdge< P, D, IsPrimal >::
 235 ~QuadEdge( )
 236 {
 237 }
 238
 239 #endif // __CPPLUGINS__EXTENSIONS__DATASTRUCTURES__QUADEDGE__HXX__
 240
 241 // eof - $RCSfile$