vtf-logo

HalfedgeDS.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00008 #if !defined(__HalfedgeDS_h__)
00009 #define __HalfedgeDS_h__
00010 
00011 #include "../defs.h"
00012 
00013 #include "circulator.h"
00014 
00015 #include <vector>
00016 
00017 #include <cassert>
00018 
00019 BEGIN_NAMESPACE_ADS
00020   
00022 template < template<class> class Vertex, 
00023            template<class> class Halfedge, 
00024            template<class> class Face >
00025 class HalfedgeDS
00026 {
00027   //
00028   // Types
00029   //
00030 
00031 private:
00032 
00033   typedef HalfedgeDS<Vertex, Halfedge, Face> HDS;
00034 
00035 public:
00036 
00038   typedef Vertex<HDS> Vertex_type;
00040   typedef Halfedge<HDS> Halfedge_type;
00042   typedef Face<HDS> Face_type;
00043 
00044 private:
00045 
00046   typedef std::vector<Vertex_type> Vertex_container;
00047   typedef std::vector<Halfedge_type> Halfedge_container;
00048   typedef std::vector<Face_type> Face_container;
00049     
00050 public:
00051 
00053   typedef typename Vertex_container::iterator Vertex_iterator;
00055   typedef typename Halfedge_container::iterator Halfedge_iterator;
00057   typedef typename Face_container::iterator Face_iterator;
00058 
00060   typedef typename Vertex_container::const_iterator Vertex_const_iterator;
00062   typedef typename Halfedge_container::const_iterator 
00063   Halfedge_const_iterator;
00065   typedef typename Face_container::const_iterator Face_const_iterator;
00066 
00068   typedef typename Vertex_container::iterator Vertex_handle;
00070   typedef typename Halfedge_container::iterator Halfedge_handle;
00072   typedef typename Face_container::iterator Face_handle;
00073 
00075   typedef typename Vertex_container::const_iterator Vertex_const_handle;
00077   typedef typename Halfedge_container::const_iterator Halfedge_const_handle;
00079   typedef typename Face_container::const_iterator Face_const_handle;
00080 
00082   typedef typename Vertex_container::size_type size_type;
00084   typedef typename Vertex_container::difference_type difference_type;
00085 
00087   typedef Face_Halfedge_circ<Halfedge_handle> Face_Halfedge_circulator;
00089   typedef Face_Halfedge_circ<Halfedge_const_handle> 
00090   Face_Halfedge_const_circulator;
00091 
00092 private:
00093       
00094   //
00095   // Data
00096   //
00097     
00098   // Containers.
00099   Vertex_container   _vertices;
00100   Halfedge_container _halfedges;
00101   Face_container     _faces;
00102 
00103   // Null handles.
00104   Vertex_handle   _null_vertex_handle;
00105   Halfedge_handle _null_halfedge_handle;
00106   Face_handle     _null_face_handle;
00107 
00108 public:
00109 
00110   //
00111   // Constructors and Destructor
00112   //
00113 
00115   HalfedgeDS() :
00116     _vertices(),
00117     _halfedges(),
00118     _faces(),
00119     _null_vertex_handle( 0 ),
00120     _null_halfedge_handle( 0 ),
00121     _null_face_handle( 0 )
00122   {}
00123 
00125 
00128   HalfedgeDS( size_type v, size_type h, size_type f ) :
00129     _vertices(),
00130     _halfedges(),
00131     _faces(),
00132     _null_vertex_handle( 0 ),
00133     _null_halfedge_handle( 0 ),
00134     _null_face_handle( 0 )
00135   {
00136     _vertices.reserve( v );
00137     _halfedges.reserve( h );
00138     _faces.reserve( f );
00139   }
00140 
00142   HalfedgeDS( const HalfedgeDS& x );
00143 
00145   ~HalfedgeDS()
00146   {}
00147 
00149   HalfedgeDS& 
00150   operator=( const HalfedgeDS& x );
00151 
00152   //  
00153   // Accessors
00154   //
00155 
00157   Vertex_const_iterator
00158   vertices_begin() const
00159   {
00160     return _vertices.begin();
00161   }
00162 
00164   Vertex_const_iterator
00165   vertices_end() const
00166   {
00167     return _vertices.end();
00168   }
00169 
00171   Halfedge_const_iterator
00172   halfedges_begin() const
00173   {
00174     return _halfedges.begin();
00175   }
00176 
00178   Halfedge_const_iterator
00179   halfedges_end() const
00180   {
00181     return _halfedges.end();
00182   }
00183 
00185   Face_const_iterator
00186   faces_begin() const
00187   {
00188     return _faces.begin();
00189   }
00190 
00192   Face_const_iterator
00193   faces_end() const
00194   {
00195     return _faces.end();
00196   }
00197 
00199   size_type
00200   vertices_size() const
00201   {
00202     return _vertices.size();
00203   }
00204     
00206   size_type
00207   halfedges_size() const
00208   {
00209     return _halfedges.size();
00210   }
00211     
00213   size_type
00214   faces_size() const
00215   {
00216     return _faces.size();
00217   }
00218 
00219   //  
00220   // Manipulators
00221   //
00222 
00224   Vertex_iterator
00225   vertices_begin()
00226   {
00227     return _vertices.begin();
00228   }
00229 
00231   Vertex_iterator
00232   vertices_end()
00233   {
00234     return _vertices.end();
00235   }
00236 
00238   Halfedge_iterator
00239   halfedges_begin()
00240   {
00241     return _halfedges.begin();
00242   }
00243 
00245   Halfedge_iterator
00246   halfedges_end()
00247   {
00248     return _halfedges.end();
00249   }
00250 
00252   Face_iterator
00253   faces_begin()
00254   {
00255     return _faces.begin();
00256   }
00257 
00259   Face_iterator
00260   faces_end()
00261   {
00262     return _faces.end();
00263   }
00264 
00265   //
00266   // Utility
00267   //
00268 
00270 
00273   bool
00274   is_valid() const
00275   {
00276     // Check the vertices.
00277     for ( Vertex_const_iterator i = vertices_begin(); 
00278           i != vertices_end(); ++i ) {
00279       if ( ! is_valid( i->halfedge() ) ) {
00280         return false;
00281       }
00282     }
00283     // Check the halfedges.
00284     for ( Halfedge_const_iterator i = halfedges_begin(); 
00285           i != halfedges_end(); ++i ) {
00286       if ( ! ( is_valid( i->opposite() ) && 
00287                is_valid( i->prev() ) && 
00288                is_valid( i->next() ) && 
00289                is_valid( i->vertex() ) && 
00290                is_valid( i->face() ) ) ) {
00291         return false;
00292       }
00293     }
00294     // Check the faces.
00295     for ( Face_const_iterator i = faces_begin(); 
00296           i != faces_end(); ++i ) {
00297       if ( ! is_valid( i->halfedge() ) ) {
00298         return false;
00299       }
00300     }
00301     return true;
00302   }
00303     
00305   bool
00306   is_valid( Vertex_const_handle h ) const
00307   {
00308     if ( is_null( h ) || ( vertices_begin() <= h && h < vertices_end() ) ) {
00309       return true;
00310     }
00311     return false;
00312   }
00313     
00315   bool
00316   is_valid( Halfedge_const_handle h ) const
00317   {
00318     if ( is_null( h ) || ( halfedges_begin() <= h && h < halfedges_end() ) ){
00319       return true;
00320     }
00321     return false;
00322   }
00323     
00325   bool
00326   is_valid( Face_const_handle h ) const
00327   {
00328     if ( is_null( h ) || ( faces_begin() <= h && h < faces_end() ) ){
00329       return true;
00330     }
00331     return false;
00332   }
00333     
00335   difference_type
00336   index( Vertex_const_handle h ) const
00337   {
00338     if ( h == _null_vertex_handle ) {
00339       return std::distance( vertices_begin(), vertices_end() );
00340     }
00341     return std::distance( vertices_begin(), h );
00342   }
00343     
00345   difference_type
00346   index( Halfedge_const_handle h ) const
00347   {
00348     if ( h == _null_halfedge_handle ) {
00349       return std::distance( halfedges_begin(), halfedges_end() );
00350     }
00351     return std::distance( halfedges_begin(), h );
00352   }
00353     
00355   difference_type
00356   index( Face_const_handle h ) const
00357   {
00358     if ( h == _null_face_handle ) {
00359       return std::distance( faces_begin(), faces_end() );
00360     }
00361     return std::distance( faces_begin(), h );
00362   }
00363 
00365   bool
00366   is_null( Vertex_const_handle h ) const
00367   {
00368     return ( h == _null_vertex_handle );
00369   }
00370     
00372   bool
00373   is_null( Halfedge_const_handle h ) const
00374   {
00375     return ( h == _null_halfedge_handle );
00376   }
00377     
00379   bool
00380   is_null( Face_const_handle h ) const
00381   {
00382     return ( h == _null_face_handle );
00383   }
00384     
00385   //
00386   // Insert items
00387   //
00388 
00390   void
00391   reserve( size_type v, size_type h, size_type f );
00392 
00394   void
00395   clear();
00396     
00398   Vertex_handle
00399   insert_vertex();
00400     
00402   Vertex_handle
00403   insert_vertex( const Vertex_type& x );
00404     
00406 
00409   Halfedge_handle
00410   insert_halfedge();
00411     
00413   Halfedge_handle
00414   insert_halfedge( const Halfedge_type& x );
00415     
00417   Halfedge_handle
00418   insert_halfedge( const Halfedge_type& x, const Halfedge_type& y );
00419     
00421   Face_handle
00422   insert_face();
00423     
00425   Face_handle
00426   insert_face( const Face_type& x );
00427 
00428   //
00429   // I/O
00430   //
00431 
00433   void
00434   put( std::ostream& out ) const;
00435 
00437   void
00438   get( std::istream& in );
00439 
00440 private:
00441 
00442   //
00443   // private member functions
00444   //
00445 
00447   void
00448   increase_vertex_capacity();
00449 
00451   void
00452   increase_halfedge_capacity();
00453 
00455   void
00456   increase_face_capacity();
00457 
00459   void 
00460   shift_vertex_handles( difference_type d );
00461 
00463   void 
00464   shift_halfedge_handles( difference_type d );
00465 
00467   void 
00468   shift_face_handles( difference_type d );
00469 };
00470 
00471 //
00472 // Equality.
00473 //
00474 
00476 template < template<class> class Vertex, 
00477            template<class> class Halfedge, 
00478            template<class> class Face >
00479 inline
00480 bool
00481 operator==( const HalfedgeDS<Vertex,Halfedge,Face>& a,
00482             const HalfedgeDS<Vertex,Halfedge,Face>& b );
00483 
00485 template < template<class> class Vertex, 
00486            template<class> class Halfedge, 
00487            template<class> class Face >
00488 inline
00489 bool
00490 operator!=( const HalfedgeDS<Vertex,Halfedge,Face>& a,
00491             const HalfedgeDS<Vertex,Halfedge,Face>& b )
00492 {
00493   return !(a == b );
00494 }
00495 
00496 //
00497 // I/O
00498 //
00499 
00501 template < template<class> class Vertex, 
00502            template<class> class Halfedge, 
00503            template<class> class Face >
00504 inline
00505 std::ostream&
00506 operator<<( std::ostream& out, const HalfedgeDS<Vertex,Halfedge,Face>& x )
00507 {
00508   x.put( out );
00509   return out;
00510 }
00511   
00513 template < template<class> class Vertex, 
00514            template<class> class Halfedge, 
00515            template<class> class Face >
00516 inline
00517 std::istream&
00518 operator>>( std::istream& in, HalfedgeDS<Vertex,Halfedge,Face>& x )
00519 {
00520   x.get( in );
00521   return in;
00522 }
00523   
00524 END_NAMESPACE_ADS
00525 
00526 #define __HalfedgeDS_ipp__
00527 #include "HalfedgeDS.ipp"
00528 #undef __HalfedgeDS_ipp__
00529 
00530 #endif

Generated on Fri Aug 24 12:55:24 2007 for Algorithms and Data Structures Package by  doxygen 1.4.7