lib/cpm/DataStructures/QuadEdge.hxx

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