DGtal  1.0.0
HalfEdgeDataStructure.h
1 
17 #pragma once
18 
31 #if defined(HalfEdgeDataStructure_RECURSES)
32 #error Recursive header files inclusion detected in HalfEdgeDataStructure.h
33 #else // defined(HalfEdgeDataStructure_RECURSES)
34 
35 #define HalfEdgeDataStructure_RECURSES
36 
37 #if !defined HalfEdgeDataStructure_h
38 
39 #define HalfEdgeDataStructure_h
40 
42 // Inclusions
43 #include <iostream>
44 #include <array>
45 #include "DGtal/base/Common.h"
47 
48 namespace DGtal
49 {
50 
57  static std::size_t const HALF_EDGE_INVALID_INDEX = boost::integer_traits<std::size_t>::const_max;
58 
60  // class HalfEdgeDataStructure
87  {
88  public:
89 
91  typedef std::size_t Size;
93  typedef std::size_t Index;
97  typedef Index VertexIndex;
99  typedef Index EdgeIndex;
101  typedef Index FaceIndex;
102 
103  // Defines the invalid index.
104  // JOL: works with Apple LLVM version 8.1.0 (clang-802.0.42), but does not work with gcc 4.8.4
105  //
106  // static constexpr Index const& INVALID_INDEX = boost::integer_traits<Index>::const_max;
107  //
108  // JOL: does NOT work with Apple LLVM version 8.1.0 (clang-802.0.42)
109  // (undefined reference at link time).
110  // static constexpr Index const INVALID_INDEX = boost::integer_traits<Index>::const_max;
111  // static Index const INVALID_INDEX = boost::integer_traits<Index>::const_max;
112  // BOOST_STATIC_CONSTANT( Index, INVALID_INDEX = boost::integer_traits<Index>::const_max );
113 
114  typedef std::vector<HalfEdgeIndex> HalfEdgeIndexRange;
115  typedef std::vector<VertexIndex> VertexIndexRange;
116  typedef std::vector<EdgeIndex> EdgeIndexRange;
117  typedef std::vector<FaceIndex> FaceIndexRange;
118 
120  typedef std::pair<VertexIndex, VertexIndex> Arc;
121  // A map from an arc (a std::pair of VertexIndex's) to its
122  // half edge index (i.e. and offset into the 'halfedge' sequence).
123  typedef std::map< Arc, Index > Arc2Index;
124  // A map from an arc (a std::pair of VertexIndex's) to its face
125  // index.
126  typedef std::map< Arc, FaceIndex > Arc2FaceIndex;
127 
130  struct Edge
131  {
134 
135  VertexIndex& start() { return v[0]; }
136  const VertexIndex& start() const { return v[0]; }
137 
138  VertexIndex& end() { return v[1]; }
139  const VertexIndex& end() const { return v[1]; }
140 
142  {
143  v[0] = v[1] = -1;
144  }
146  {
147  if ( vi <= vj ) { v[0] = vi; v[1] = vj; }
148  else { v[0] = vj; v[1] = vi; }
149  }
150  bool operator<( const Edge& other ) const
151  {
152  return ( start() < other.start() )
153  || ( ( start() == other.start() ) && ( end() < other.end() ) );
154  }
155  };
156 
158  struct Triangle
159  {
161  std::array<VertexIndex,3> v;
162 
163  VertexIndex& i() { return v[0]; }
164  const VertexIndex& i() const { return v[0]; }
165 
166  VertexIndex& j() { return v[1]; }
167  const VertexIndex& j() const { return v[1]; }
168 
169  VertexIndex& k() { return v[2]; }
170  const VertexIndex& k() const { return v[2]; }
171 
173  {
174  v[0] = v[1] = v[2] = -1;
175  }
177  {
178  v[0] = v0;
179  v[1] = v1;
180  v[2] = v2;
181  }
182  };
183 
186  typedef std::vector<VertexIndex> PolygonalFace;
187 
192  struct HalfEdge
193  {
204 
208  face( HALF_EDGE_INVALID_INDEX ),
212  {}
213  };
214 
215  public:
218 
235  ( const std::vector<Triangle>& triangles, std::vector< Edge >& edges_out )
236  {
237  typedef std::set< Edge > EdgeSet;
238  typedef std::set< VertexIndex > VertexIndexSet;
239  VertexIndexSet vertexSet;
240  EdgeSet edgeSet;
241  for( const Triangle& T : triangles )
242  {
243  edgeSet.insert( Edge( T.i(), T.j() ) );
244  edgeSet.insert( Edge( T.j(), T.k() ) );
245  edgeSet.insert( Edge( T.k(), T.i() ) );
246  vertexSet.insert( T.i() );
247  vertexSet.insert( T.j() );
248  vertexSet.insert( T.k() );
249  }
250  edges_out.resize( edgeSet.size() );
251  Size e = 0;
252  for ( const Edge& edge : edgeSet )
253  {
254  edges_out.at(e) = edge;
255  ++e;
256  }
257  return vertexSet.size();
258  }
259 
276  ( const std::vector<PolygonalFace>& polygonal_faces, std::vector< Edge >& edges_out );
277 
300  bool build( const Size num_vertices,
301  const std::vector<Triangle>& triangles,
302  const std::vector<Edge>& edges );
303 
326  bool build( const Size num_vertices,
327  const std::vector<PolygonalFace>& polygonal_faces,
328  const std::vector<Edge>& edges );
329 
338  bool build( const std::vector<Triangle>& triangles )
339  {
340  std::vector<Edge> edges;
341  const Size nbVtx = getUnorderedEdgesFromTriangles( triangles, edges );
342  return build( nbVtx, triangles, edges );
343  }
344 
353  bool build( const std::vector<PolygonalFace>& polygonal_faces )
354  {
355  std::vector<Edge> edges;
356  const Size nbVtx = getUnorderedEdgesFromPolygonalFaces( polygonal_faces, edges );
357  return build( nbVtx, polygonal_faces, edges );
358  }
359 
361  void clear()
362  {
363  myHalfEdges.clear();
364  myVertexHalfEdges.clear();
365  myFaceHalfEdges.clear();
366  myEdgeHalfEdges.clear();
367  myArc2Index.clear();
368  }
369 
371  Size nbHalfEdges() const { return myHalfEdges.size(); }
372 
374  Size nbVertices() const { return myVertexHalfEdges.size(); }
375 
377  Size nbEdges() const { return myEdgeHalfEdges.size(); }
378 
380  Size nbFaces() const { return myFaceHalfEdges.size(); }
381 
383  long Euler() const
384  { return (long) nbVertices() - (long) nbEdges() + (long) nbFaces(); }
385 
388  const HalfEdge& halfEdge( const Index i ) const { return myHalfEdges.at( i ); }
389 
392  Arc arcFromHalfEdgeIndex( const Index i ) const
393  {
394  const HalfEdge& he = myHalfEdges[ i ];
395  return std::make_pair( myHalfEdges[ he.opposite ].toVertex, he.toVertex );
396  }
397 
402  { return halfEdgeIndexFromArc( std::make_pair( i, j ) ); }
403 
406  Index halfEdgeIndexFromArc( const Arc& arc ) const
407  {
408  auto result = myArc2Index.find( arc );
409  return ( result == myArc2Index.end() ) ? HALF_EDGE_INVALID_INDEX : result->second;
410  }
411 
415  { return myVertexHalfEdges[ vi ]; }
416 
420  { return myFaceHalfEdges[ fi ]; }
421 
425  { return myEdgeHalfEdges[ ei ]; }
426 
429  void getNeighboringVertices( const Index vi, VertexIndexRange& result ) const
430  {
431  result.clear();
432  const Index start_hei = halfEdgeIndexFromVertexIndex( vi );
433  Index hei = start_hei;
434  do
435  {
436  const HalfEdge& he = halfEdge( hei );
437  result.push_back( he.toVertex );
438  hei = halfEdge( he.opposite ).next;
439  }
440  while ( hei != start_hei );
441  }
442 
446  {
447  VertexIndexRange result;
448  getNeighboringVertices( vi, result );
449  return result;
450  }
451 
454  Size nbNeighboringVertices( const Index vi ) const
455  {
456  Size nb = 0;
457  const Index start_hei = halfEdgeIndexFromVertexIndex( vi );
458  Index hei = start_hei;
459  do
460  {
461  const HalfEdge& he = halfEdge( hei );
462  nb++;
463  hei = halfEdge( he.opposite ).next;
464  }
465  while ( hei != start_hei );
466  return nb;
467  }
468 
471  void getNeighboringFaces( const VertexIndex vi, FaceIndexRange& result ) const
472  {
473  result.clear();
474  const Index start_hei = halfEdgeIndexFromVertexIndex( vi );
475  Index hei = start_hei;
476  do
477  {
478  const HalfEdge& he = halfEdge( hei );
479  if( HALF_EDGE_INVALID_INDEX != he.face ) result.push_back( he.face );
480  hei = halfEdge( he.opposite ).next;
481  }
482  while ( hei != start_hei );
483  }
484 
488  {
489  FaceIndexRange result;
490  getNeighboringFaces( vi, result );
491  return result;
492  }
493 
496  bool isVertexBoundary( const VertexIndex vi ) const
497  {
499  }
500 
507  {
508  VertexIndexRange result;
509  // std::set< VertexIndex > result;
510  for( Index hei = 0; hei < myHalfEdges.size(); ++hei )
511  {
512  const HalfEdge& he = halfEdge( hei );
513  if( HALF_EDGE_INVALID_INDEX == he.face )
514  result.push_back( he.toVertex );
515  }
516  return result;
517  }
518 
522  std::vector< Index > boundaryHalfEdgeIndices() const
523  {
524  std::vector< Index > result;
525  for( Index hei = 0; hei < myHalfEdges.size(); ++hei )
526  {
527  const HalfEdge& he = halfEdge( hei );
528  if( HALF_EDGE_INVALID_INDEX == he.face )
529  result.push_back( hei );
530  }
531  return result;
532  }
536  std::vector< Arc > boundaryArcs() const
537  {
538  std::vector< Arc > result;
539  for( Index hei = 0; hei < myHalfEdges.size(); ++hei )
540  {
541  const HalfEdge& he = halfEdge( hei );
542  if( HALF_EDGE_INVALID_INDEX == he.face )
543  result.push_back( arcFromHalfEdgeIndex( hei ) );
544  }
545  return result;
546  }
547 
548  protected:
549 
551  std::vector< HalfEdge > myHalfEdges;
555  std::vector< Index > myVertexHalfEdges;
559  std::vector< Index > myFaceHalfEdges;
563  std::vector< Index > myEdgeHalfEdges;
566 
567 
568  // ----------------------- Interface --------------------------------------
569  public:
570 
575  void selfDisplay ( std::ostream & out ) const;
576 
581  bool isValid() const;
582 
583  // ------------------------- Protected Datas ------------------------------
584  private:
585  // ------------------------- Private Datas --------------------------------
586  private:
587  // ------------------------- Hidden services ------------------------------
588  protected:
589 
590  static
592  VertexIndex vi, VertexIndex vj )
593  {
594  ASSERT( !de2fi.empty() );
595 
596  Arc2FaceIndex::const_iterator it = de2fi.find( Arc( vi, vj ) );
597  // If no such directed edge exists, then there's no such face in the mesh.
598  // The edge must be a boundary edge.
599  // In this case, the reverse orientation edge must have a face.
600  if( it == de2fi.end() )
601  {
602  ASSERT( de2fi.find( Arc( vj, vi ) ) != de2fi.end() );
604  }
605  return it->second;
606  }
607 
608  }; // end of class HalfEdgeDataStructure
609 
610 
617  std::ostream&
618  operator<< ( std::ostream & out, const HalfEdgeDataStructure & object );
619 
620 } // namespace DGtal
621 
622 
624 // Includes inline functions.
625 #include "DGtal/topology/HalfEdgeDataStructure.ih"
626 
627 // //
629 
630 #endif // !defined HalfEdgeDataStructure_h
631 
632 #undef HalfEdgeDataStructure_RECURSES
633 #endif // else defined(HalfEdgeDataStructure_RECURSES)
HalfEdge()
Default constructor. The half-edge is invalid.
bool operator<(const Edge &other) const
Index FaceIndex
The type for numbering faces.
static Size getUnorderedEdgesFromTriangles(const std::vector< Triangle > &triangles, std::vector< Edge > &edges_out)
std::pair< VertexIndex, VertexIndex > Arc
An arc is a directed edge from a first vertex to a second vertex.
std::map< Arc, FaceIndex > Arc2FaceIndex
std::vector< FaceIndex > FaceIndexRange
Index halfEdgeIndexFromVertexIndex(const VertexIndex vi) const
bool build(const std::vector< Triangle > &triangles)
Index next
Index into the halfedges array.
const HalfEdge & halfEdge(const Index i) const
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
void getNeighboringFaces(const VertexIndex vi, FaceIndexRange &result) const
Arc2Index myArc2Index
The mapping between arcs to their half-edge index.
Index halfEdgeIndexFromArc(const Arc &arc) const
std::vector< HalfEdgeIndex > HalfEdgeIndexRange
void getNeighboringVertices(const Index vi, VertexIndexRange &result) const
std::vector< VertexIndex > VertexIndexRange
Edge(VertexIndex vi, VertexIndex vj)
Index halfEdgeIndexFromEdgeIndex(const EdgeIndex ei) const
Represents an unoriented triangle as three vertices.
std::vector< EdgeIndex > EdgeIndexRange
VertexIndex toVertex
The end vertex of this half-edge as an index into the vertex array.
Index halfEdgeIndexFromArc(const VertexIndex i, const VertexIndex j) const
VertexIndexRange boundaryVertices() const
EdgeIndex edge
Index into the edges array.
Index opposite
Index into the halfedges array.
static Size getUnorderedEdgesFromPolygonalFaces(const std::vector< PolygonalFace > &polygonal_faces, std::vector< Edge > &edges_out)
FaceIndex face
Index into the face array.
static FaceIndex arc2FaceIndex(const Arc2FaceIndex &de2fi, VertexIndex vi, VertexIndex vj)
std::array< VertexIndex, 3 > v
The three vertex indices.
std::vector< Index > boundaryHalfEdgeIndices() const
bool isVertexBoundary(const VertexIndex vi) const
bool build(const Size num_vertices, const std::vector< Triangle > &triangles, const std::vector< Edge > &edges)
std::vector< VertexIndex > PolygonalFace
std::ostream & operator<<(std::ostream &out, const ClosedIntegerHalfPlane< TSpace > &object)
bool build(const std::vector< PolygonalFace > &polygonal_faces)
Index HalfEdgeIndex
The type used for numbering half-edges (alias)
HalfEdgeDataStructure::Edge Edge
std::vector< Index > myVertexHalfEdges
DGtal is the top-level namespace which contains all DGtal functions and types.
std::vector< Arc > boundaryArcs() const
Aim: This class represents an half-edge data structure, which is a structure for representing the top...
Triangle(VertexIndex v0, VertexIndex v1, VertexIndex v2)
void selfDisplay(std::ostream &out) const
std::size_t Index
The type used for numbering half-edges (an offset an the half-edges structure).
HalfEdgeDataStructure()
Default constructor. The data structure is empty.
Index VertexIndex
The type for numbering vertices.
Size nbNeighboringVertices(const Index vi) const
std::size_t Size
The type for counting elements.
Arc arcFromHalfEdgeIndex(const Index i) const
static std::size_t const HALF_EDGE_INVALID_INDEX
std::map< Arc, Index > Arc2Index
void clear()
Clears the data structure.
Index EdgeIndex
The type for numbering edges.
std::vector< Index > myEdgeHalfEdges
std::vector< Index > myFaceHalfEdges
VertexIndexRange neighboringVertices(const Index vi) const
Index halfEdgeIndexFromFaceIndex(const FaceIndex fi) const
FaceIndexRange neighboringFaces(const VertexIndex vi) const