DGtal  0.9.4beta
Data Structures | Public Types | Public Member Functions | Static Public Member Functions | Static Protected Member Functions | Protected Attributes
DGtal::HalfEdgeDataStructure Class Reference

#include <DGtal/topology/HalfEdgeDataStructure.h>

Collaboration diagram for DGtal::HalfEdgeDataStructure:
[legend]

Data Structures

struct  Edge
 
struct  HalfEdge
 
struct  Triangle
 

Public Types

typedef std::size_t Size
 
typedef std::size_t Index
 
typedef Index HalfEdgeIndex
 
typedef Index VertexIndex
 
typedef Index EdgeIndex
 
typedef Index FaceIndex
 
typedef std::vector< HalfEdgeIndexHalfEdgeIndexRange
 
typedef std::vector< VertexIndexVertexIndexRange
 
typedef std::vector< EdgeIndexEdgeIndexRange
 
typedef std::vector< FaceIndexFaceIndexRange
 
typedef std::pair< VertexIndex, VertexIndexArc
 
typedef std::map< Arc, IndexArc2Index
 
typedef std::map< Arc, FaceIndexArc2FaceIndex
 
typedef std::vector< VertexIndexPolygonalFace
 

Public Member Functions

 HalfEdgeDataStructure ()
 
bool build (const Size num_vertices, const std::vector< Triangle > &triangles, const std::vector< Edge > &edges)
 
bool build (const Size num_vertices, const std::vector< PolygonalFace > &polygonal_faces, const std::vector< Edge > &edges)
 
bool build (const std::vector< Triangle > &triangles)
 
bool build (const std::vector< PolygonalFace > &polygonal_faces)
 
void clear ()
 
Size nbHalfEdges () const
 
Size nbVertices () const
 
Size nbEdges () const
 
Size nbFaces () const
 
long Euler () const
 
const HalfEdgehalfEdge (const Index i) const
 
Arc arcFromHalfEdgeIndex (const Index i) const
 
Index halfEdgeIndexFromArc (const VertexIndex i, const VertexIndex j) const
 
Index halfEdgeIndexFromArc (const Arc &arc) const
 
Index halfEdgeIndexFromVertexIndex (const VertexIndex vi) const
 
Index halfEdgeIndexFromFaceIndex (const FaceIndex fi) const
 
Index halfEdgeIndexFromEdgeIndex (const EdgeIndex ei) const
 
void getNeighboringVertices (const Index vi, VertexIndexRange &result) const
 
VertexIndexRange neighboringVertices (const Index vi) const
 
Size nbNeighboringVertices (const Index vi) const
 
void getNeighboringFaces (const VertexIndex vi, FaceIndexRange &result) const
 
FaceIndexRange neighboringFaces (const VertexIndex vi) const
 
bool isVertexBoundary (const VertexIndex vi) const
 
VertexIndexRange boundaryVertices () const
 
std::vector< IndexboundaryHalfEdgeIndices () const
 
std::vector< ArcboundaryArcs () const
 
void selfDisplay (std::ostream &out) const
 
bool isValid () const
 

Static Public Member Functions

static Size getUnorderedEdgesFromTriangles (const std::vector< Triangle > &triangles, std::vector< Edge > &edges_out)
 
static Size getUnorderedEdgesFromPolygonalFaces (const std::vector< PolygonalFace > &polygonal_faces, std::vector< Edge > &edges_out)
 

Static Protected Member Functions

static FaceIndex arc2FaceIndex (const Arc2FaceIndex &de2fi, VertexIndex vi, VertexIndex vj)
 

Protected Attributes

std::vector< HalfEdgemyHalfEdges
 
std::vector< IndexmyVertexHalfEdges
 
std::vector< IndexmyFaceHalfEdges
 
std::vector< IndexmyEdgeHalfEdges
 
Arc2Index myArc2Index
 

Detailed Description

Aim: This class represents an half-edge data structure, which is a structure for representing the topology of a combinatorial 2-dimensional surface or an embedding of a planar graph in the plane. It does not store any geometry. As a minimal example, these lines of code build two triangles connected by the edge {1,2}.

Description of template class 'HalfEdgeDataStructure'

std::vector< HalfEdgeDataStructure::Triangle > triangles( 2 );
triangles[0].v = { 0, 1, 2 };
triangles[1].v = { 2, 1, 3 };
mesh.build( triangles );
std::cout << mesh << std::endl;
Todo:
For now, the construction of the half-edge structure (method HalfEdgeDataStructure::build) is limited to triangles. It would be not difficult to adapt it to cellular surfaces.
Note
Large parts of this class are taken from https://github.com/yig/halfedge, written by Yotam Gingold.

Definition at line 86 of file HalfEdgeDataStructure.h.

Member Typedef Documentation

An arc is a directed edge from a first vertex to a second vertex.

Definition at line 120 of file HalfEdgeDataStructure.h.

Definition at line 126 of file HalfEdgeDataStructure.h.

Definition at line 123 of file HalfEdgeDataStructure.h.

The type for numbering edges.

Definition at line 99 of file HalfEdgeDataStructure.h.

Definition at line 116 of file HalfEdgeDataStructure.h.

The type for numbering faces.

Definition at line 101 of file HalfEdgeDataStructure.h.

Definition at line 117 of file HalfEdgeDataStructure.h.

The type used for numbering half-edges (alias)

Definition at line 95 of file HalfEdgeDataStructure.h.

Definition at line 114 of file HalfEdgeDataStructure.h.

The type used for numbering half-edges (an offset an the half-edges structure).

Definition at line 93 of file HalfEdgeDataStructure.h.

Defines an arbitrary polygonal face as a vector of vertex indices. To be valid, its size must be at least 3.

Definition at line 186 of file HalfEdgeDataStructure.h.

The type for counting elements.

Definition at line 91 of file HalfEdgeDataStructure.h.

The type for numbering vertices.

Definition at line 97 of file HalfEdgeDataStructure.h.

Definition at line 115 of file HalfEdgeDataStructure.h.

Constructor & Destructor Documentation

DGtal::HalfEdgeDataStructure::HalfEdgeDataStructure ( )
inline

Default constructor. The data structure is empty.

See also
build

Definition at line 217 of file HalfEdgeDataStructure.h.

217 {}

Member Function Documentation

static FaceIndex DGtal::HalfEdgeDataStructure::arc2FaceIndex ( const Arc2FaceIndex de2fi,
VertexIndex  vi,
VertexIndex  vj 
)
inlinestaticprotected

Definition at line 591 of file HalfEdgeDataStructure.h.

References DGtal::HALF_EDGE_INVALID_INDEX.

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  }
std::pair< VertexIndex, VertexIndex > Arc
An arc is a directed edge from a first vertex to a second vertex.
static std::size_t const HALF_EDGE_INVALID_INDEX
Arc DGtal::HalfEdgeDataStructure::arcFromHalfEdgeIndex ( const Index  i) const
inline
Parameters
iany valid half-edge index.
Returns
the corresponding directed edge as an arc (v(opp(i)), v(i)).

Definition at line 392 of file HalfEdgeDataStructure.h.

References myHalfEdges, DGtal::HalfEdgeDataStructure::HalfEdge::opposite, and DGtal::HalfEdgeDataStructure::HalfEdge::toVertex.

Referenced by boundaryArcs().

393  {
394  const HalfEdge& he = myHalfEdges[ i ];
395  return std::make_pair( myHalfEdges[ he.opposite ].toVertex, he.toVertex );
396  }
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
std::vector< Arc > DGtal::HalfEdgeDataStructure::boundaryArcs ( ) const
inline
Returns
a sequence containing the arcs lying on the boundary.
Note
O(nb half-edges) operation.
no particular order.

Definition at line 536 of file HalfEdgeDataStructure.h.

References arcFromHalfEdgeIndex(), DGtal::HalfEdgeDataStructure::HalfEdge::face, halfEdge(), and myHalfEdges.

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  }
Arc arcFromHalfEdgeIndex(const Index i) const
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
const HalfEdge & halfEdge(const Index i) const
std::size_t Index
The type used for numbering half-edges (an offset an the half-edges structure).
static std::size_t const HALF_EDGE_INVALID_INDEX
std::vector< Index > DGtal::HalfEdgeDataStructure::boundaryHalfEdgeIndices ( ) const
inline
Returns
a sequence containing the indices of half-edges lying on the boundary.
Note
O(nb half-edges) operation.
no particular order.

Definition at line 522 of file HalfEdgeDataStructure.h.

References DGtal::HalfEdgeDataStructure::HalfEdge::face, halfEdge(), and myHalfEdges.

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  }
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
const HalfEdge & halfEdge(const Index i) const
std::size_t Index
The type used for numbering half-edges (an offset an the half-edges structure).
static std::size_t const HALF_EDGE_INVALID_INDEX
VertexIndexRange DGtal::HalfEdgeDataStructure::boundaryVertices ( ) const
inline
Returns
a sequence containing the indices of the vertices lying on the boundary.
Note
O(nb half-edges) operation.
no particular order.

Definition at line 506 of file HalfEdgeDataStructure.h.

References DGtal::HalfEdgeDataStructure::HalfEdge::face, halfEdge(), myHalfEdges, and DGtal::HalfEdgeDataStructure::HalfEdge::toVertex.

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  }
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
const HalfEdge & halfEdge(const Index i) const
std::size_t Index
The type used for numbering half-edges (an offset an the half-edges structure).
static std::size_t const HALF_EDGE_INVALID_INDEX
bool DGtal::HalfEdgeDataStructure::build ( const Size  num_vertices,
const std::vector< Triangle > &  triangles,
const std::vector< Edge > &  edges 
)

Builds the half-edge data structures from the given triangles and edges. It keeps the numbering of vertices given in the input triangles as well as the numbering of triangles in the vector triangles.

Note
Parameter edges can be computed from triangles by calling getUnorderedEdgesFromTriangles() before.
Both triangles and edges are not needed after the call to build() completes and may be destroyed.
Parameters
[in]num_verticesthe number of vertices (one more than the maximal vertex index).
[in]trianglesthe vector of input triangles.
[in]edgesthe vector of input unoriented edges.
Returns
'true' if everything went well, 'false' if their was error in the given topology (for instance, three triangles sharing an edge).

Referenced by build().

bool DGtal::HalfEdgeDataStructure::build ( const Size  num_vertices,
const std::vector< PolygonalFace > &  polygonal_faces,
const std::vector< Edge > &  edges 
)

Builds the half-edge data structures from the given polygonal faces and edges. It keeps the numbering of vertices given in the input polygonal_faces as well as the numbering of faces in the vector polygonal_faces.

Note
Parameter edges can be computed from polygonal_faces by calling getUnorderedEdgesFromPolygonalFaces() before.
Both polygonal_faces and edges are not needed after the call to build() completes and may be destroyed.
Parameters
[in]num_verticesthe number of vertices (one more than the maximal vertex index).
[in]polygonal_facesthe vector of input polygonal_faces.
[in]edgesthe vector of input unoriented edges.
Returns
'true' if everything went well, 'false' if their was error in the given topology (for instance, three triangles sharing an edge).
bool DGtal::HalfEdgeDataStructure::build ( const std::vector< Triangle > &  triangles)
inline

Builds the half-edge data structure from the given triangles. It keeps the numbering of vertices given in the input triangles as well as the numbering of triangles in the vector triangles.

Parameters
[in]trianglesthe vector of input triangles.

Definition at line 338 of file HalfEdgeDataStructure.h.

References build(), and getUnorderedEdgesFromTriangles().

339  {
340  std::vector<Edge> edges;
341  const int nbVtx = getUnorderedEdgesFromTriangles( triangles, edges );
342  return build( nbVtx, triangles, edges );
343  }
static Size getUnorderedEdgesFromTriangles(const std::vector< Triangle > &triangles, std::vector< Edge > &edges_out)
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator > edges(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
bool build(const Size num_vertices, const std::vector< Triangle > &triangles, const std::vector< Edge > &edges)
bool DGtal::HalfEdgeDataStructure::build ( const std::vector< PolygonalFace > &  polygonal_faces)
inline

Builds the half-edge data structure from the given polygonal faces. It keeps the numbering of vertices given in the input polygonal_faces as well as the numbering of faces in the vector polygonal_faces.

Parameters
[in]polygonal_facesthe vector of input polygonal faces.

Definition at line 353 of file HalfEdgeDataStructure.h.

References build(), and getUnorderedEdgesFromPolygonalFaces().

354  {
355  std::vector<Edge> edges;
356  const int nbVtx = getUnorderedEdgesFromPolygonalFaces( polygonal_faces, edges );
357  return build( nbVtx, polygonal_faces, edges );
358  }
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator > edges(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
static Size getUnorderedEdgesFromPolygonalFaces(const std::vector< PolygonalFace > &polygonal_faces, std::vector< Edge > &edges_out)
bool build(const Size num_vertices, const std::vector< Triangle > &triangles, const std::vector< Edge > &edges)
void DGtal::HalfEdgeDataStructure::clear ( )
inline

Clears the data structure.

Definition at line 361 of file HalfEdgeDataStructure.h.

References myArc2Index, myEdgeHalfEdges, myFaceHalfEdges, myHalfEdges, and myVertexHalfEdges.

362  {
363  myHalfEdges.clear();
364  myVertexHalfEdges.clear();
365  myFaceHalfEdges.clear();
366  myEdgeHalfEdges.clear();
367  myArc2Index.clear();
368  }
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
Arc2Index myArc2Index
The mapping between arcs to their half-edge index.
std::vector< Index > myVertexHalfEdges
std::vector< Index > myEdgeHalfEdges
std::vector< Index > myFaceHalfEdges
long DGtal::HalfEdgeDataStructure::Euler ( ) const
inline
Returns
the euler characteristic of the corresponding combinatorial mesh.

Definition at line 383 of file HalfEdgeDataStructure.h.

References nbEdges(), nbFaces(), and nbVertices().

Referenced by DGtal::TriangulatedSurface< TPoint >::Euler(), DGtal::PolygonalSurface< TPoint >::Euler(), and DGtal::IndexedDigitalSurface< TDigitalSurfaceContainer >::Euler().

384  { return (long) nbVertices() - (long) nbEdges() + (long) nbFaces(); }
void DGtal::HalfEdgeDataStructure::getNeighboringFaces ( const VertexIndex  vi,
FaceIndexRange result 
) const
inline
Parameters
[in]viany vertex index.
[out]resultthe sequence of neighboring faces of the given vertex vi .

Definition at line 471 of file HalfEdgeDataStructure.h.

References DGtal::HalfEdgeDataStructure::HalfEdge::face, halfEdge(), halfEdgeIndexFromVertexIndex(), DGtal::HalfEdgeDataStructure::HalfEdge::next, and DGtal::HalfEdgeDataStructure::HalfEdge::opposite.

Referenced by neighboringFaces().

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  }
Index next
Index into the halfedges array.
Index halfEdgeIndexFromVertexIndex(const VertexIndex vi) const
const HalfEdge & halfEdge(const Index i) const
std::size_t Index
The type used for numbering half-edges (an offset an the half-edges structure).
static std::size_t const HALF_EDGE_INVALID_INDEX
void DGtal::HalfEdgeDataStructure::getNeighboringVertices ( const Index  vi,
VertexIndexRange result 
) const
inline
Parameters
[in]viany vertex index.
[out]resultthe sequence of vertex neighbors of the given vertex vi .

Definition at line 429 of file HalfEdgeDataStructure.h.

References halfEdge(), halfEdgeIndexFromVertexIndex(), DGtal::HalfEdgeDataStructure::HalfEdge::next, DGtal::HalfEdgeDataStructure::HalfEdge::opposite, and DGtal::HalfEdgeDataStructure::HalfEdge::toVertex.

Referenced by neighboringVertices().

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  }
Index next
Index into the halfedges array.
Index halfEdgeIndexFromVertexIndex(const VertexIndex vi) const
const HalfEdge & halfEdge(const Index i) const
std::size_t Index
The type used for numbering half-edges (an offset an the half-edges structure).
static Size DGtal::HalfEdgeDataStructure::getUnorderedEdgesFromPolygonalFaces ( const std::vector< PolygonalFace > &  polygonal_faces,
std::vector< Edge > &  edges_out 
)
static

Computes all the unoriented edges of the given polygonal faces.

Note
Method build() needs the unordered edges of the mesh. If you don't have them, call this first.
Parameters
[in]polygonal_facesthe vector of input oriented polygonal faces.
[out]edges_outthe vector of all the unoriented edges of the given triangles.
Returns
the total number of different vertices (note that the vertex numbering should be between 0 and this number minus one).

Referenced by build().

static Size DGtal::HalfEdgeDataStructure::getUnorderedEdgesFromTriangles ( const std::vector< Triangle > &  triangles,
std::vector< Edge > &  edges_out 
)
inlinestatic

Computes all the unoriented edges of the given triangles.

Note
Method build() needs the unordered edges of the mesh. If you don't have them, call this first.
Parameters
[in]trianglesthe vector of input oriented triangles.
[out]edges_outthe vector of all the unoriented edges of the given triangles.
Returns
the total number of different vertices (note that the vertex numbering should be between 0 and this number minus one).

Definition at line 235 of file HalfEdgeDataStructure.h.

Referenced by build().

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  }
Represents an unoriented triangle as three vertices.
std::size_t Size
The type for counting elements.
const HalfEdge& DGtal::HalfEdgeDataStructure::halfEdge ( const Index  i) const
inline
Parameters
iany valid half-edge index.
Returns
the half-edge of index i.

Definition at line 388 of file HalfEdgeDataStructure.h.

References myHalfEdges.

Referenced by boundaryArcs(), boundaryHalfEdgeIndices(), boundaryVertices(), getNeighboringFaces(), getNeighboringVertices(), isVertexBoundary(), and nbNeighboringVertices().

388 { return myHalfEdges.at( i ); }
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
Index DGtal::HalfEdgeDataStructure::halfEdgeIndexFromArc ( const VertexIndex  i,
const VertexIndex  j 
) const
inline
Parameters
ithe vertex index of some vertex.
jthe vertex index of some other vertex.
Returns
the index of the half-edge from i to j or HALF_EDGE_INVALID_INDEX if not found.

Definition at line 401 of file HalfEdgeDataStructure.h.

402  { return halfEdgeIndexFromArc( std::make_pair( i, j ) ); }
Index halfEdgeIndexFromArc(const VertexIndex i, const VertexIndex j) const
Index DGtal::HalfEdgeDataStructure::halfEdgeIndexFromArc ( const Arc arc) const
inline
Parameters
arcany directed edge (i,j)
Returns
the index of the half-edge from i to j or HALF_EDGE_INVALID_INDEX if not found.

Definition at line 406 of file HalfEdgeDataStructure.h.

References myArc2Index.

407  {
408  auto result = myArc2Index.find( arc );
409  return ( result == myArc2Index.end() ) ? HALF_EDGE_INVALID_INDEX : result->second;
410  }
Arc2Index myArc2Index
The mapping between arcs to their half-edge index.
static std::size_t const HALF_EDGE_INVALID_INDEX
Index DGtal::HalfEdgeDataStructure::halfEdgeIndexFromEdgeIndex ( const EdgeIndex  ei) const
inline
Parameters
[in]eiany edge index.
Returns
the index of an half-edge that borders the edge ei.

Definition at line 424 of file HalfEdgeDataStructure.h.

References myEdgeHalfEdges.

425  { return myEdgeHalfEdges[ ei ]; }
std::vector< Index > myEdgeHalfEdges
Index DGtal::HalfEdgeDataStructure::halfEdgeIndexFromFaceIndex ( const FaceIndex  fi) const
inline
Parameters
[in]fiany face index.
Returns
the index of an half-edge that borders the face fi.

Definition at line 419 of file HalfEdgeDataStructure.h.

References myFaceHalfEdges.

420  { return myFaceHalfEdges[ fi ]; }
std::vector< Index > myFaceHalfEdges
Index DGtal::HalfEdgeDataStructure::halfEdgeIndexFromVertexIndex ( const VertexIndex  vi) const
inline
Parameters
[in]viany vertex index.
Returns
the index of an half-edge originating from vi.

Definition at line 414 of file HalfEdgeDataStructure.h.

References myVertexHalfEdges.

Referenced by getNeighboringFaces(), getNeighboringVertices(), and nbNeighboringVertices().

415  { return myVertexHalfEdges[ vi ]; }
std::vector< Index > myVertexHalfEdges
bool DGtal::HalfEdgeDataStructure::isValid ( ) const

Checks the validity/consistency of the object.

Returns
'true' if the object is valid, 'false' otherwise.
bool DGtal::HalfEdgeDataStructure::isVertexBoundary ( const VertexIndex  vi) const
inline
Parameters
[in]viany vertex index.
Returns
true if and only if the vertex vi lies on the boundary.

Definition at line 496 of file HalfEdgeDataStructure.h.

References DGtal::HalfEdgeDataStructure::HalfEdge::face, halfEdge(), and myVertexHalfEdges.

497  {
499  }
FaceIndex face
Index into the face array.
const HalfEdge & halfEdge(const Index i) const
std::vector< Index > myVertexHalfEdges
static std::size_t const HALF_EDGE_INVALID_INDEX
Size DGtal::HalfEdgeDataStructure::nbEdges ( ) const
inline
Returns
the number of unoriented edges in the structure.

Definition at line 377 of file HalfEdgeDataStructure.h.

References myEdgeHalfEdges.

Referenced by Euler(), DGtal::TriangulatedSurface< TPoint >::nbEdges(), DGtal::PolygonalSurface< TPoint >::nbEdges(), and DGtal::IndexedDigitalSurface< TDigitalSurfaceContainer >::nbEdges().

377 { return myEdgeHalfEdges.size(); }
std::vector< Index > myEdgeHalfEdges
Size DGtal::HalfEdgeDataStructure::nbFaces ( ) const
inline
Size DGtal::HalfEdgeDataStructure::nbHalfEdges ( ) const
inline
Returns
the number of half edges in the structure.

Definition at line 371 of file HalfEdgeDataStructure.h.

References myHalfEdges.

Referenced by DGtal::TriangulatedSurface< TPoint >::nbArcs(), DGtal::PolygonalSurface< TPoint >::nbArcs(), and DGtal::IndexedDigitalSurface< TDigitalSurfaceContainer >::nbArcs().

371 { return myHalfEdges.size(); }
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
Size DGtal::HalfEdgeDataStructure::nbNeighboringVertices ( const Index  vi) const
inline
Parameters
[in]viany vertex index.
Returns
the number of vertex neighbors to vi.

Definition at line 454 of file HalfEdgeDataStructure.h.

References halfEdge(), halfEdgeIndexFromVertexIndex(), DGtal::HalfEdgeDataStructure::HalfEdge::next, and DGtal::HalfEdgeDataStructure::HalfEdge::opposite.

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  }
Index next
Index into the halfedges array.
Index halfEdgeIndexFromVertexIndex(const VertexIndex vi) const
const HalfEdge & halfEdge(const Index i) const
std::size_t Index
The type used for numbering half-edges (an offset an the half-edges structure).
std::size_t Size
The type for counting elements.
Size DGtal::HalfEdgeDataStructure::nbVertices ( ) const
inline
FaceIndexRange DGtal::HalfEdgeDataStructure::neighboringFaces ( const VertexIndex  vi) const
inline
Parameters
[in]viany vertex index.
Returns
the sequence of neighboring faces of the given vertex vi .

Definition at line 487 of file HalfEdgeDataStructure.h.

References getNeighboringFaces().

488  {
489  FaceIndexRange result;
490  getNeighboringFaces( vi, result );
491  return result;
492  }
std::vector< FaceIndex > FaceIndexRange
void getNeighboringFaces(const VertexIndex vi, FaceIndexRange &result) const
VertexIndexRange DGtal::HalfEdgeDataStructure::neighboringVertices ( const Index  vi) const
inline
Parameters
[in]viany vertex index.
Returns
the sequence of vertex neighbors of the given vertex vi .

Definition at line 445 of file HalfEdgeDataStructure.h.

References getNeighboringVertices().

446  {
447  VertexIndexRange result;
448  getNeighboringVertices( vi, result );
449  return result;
450  }
void getNeighboringVertices(const Index vi, VertexIndexRange &result) const
void DGtal::HalfEdgeDataStructure::selfDisplay ( std::ostream &  out) const

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.

Field Documentation

Arc2Index DGtal::HalfEdgeDataStructure::myArc2Index
protected

The mapping between arcs to their half-edge index.

Definition at line 565 of file HalfEdgeDataStructure.h.

Referenced by clear(), and halfEdgeIndexFromArc().

std::vector< Index > DGtal::HalfEdgeDataStructure::myEdgeHalfEdges
protected

Offset into the 'halfedges' sequence, one per edge (unordered pair of vertex indices). Associates to each edge index the index of an half-edge on this edge.

Definition at line 563 of file HalfEdgeDataStructure.h.

Referenced by clear(), halfEdgeIndexFromEdgeIndex(), and nbEdges().

std::vector< Index > DGtal::HalfEdgeDataStructure::myFaceHalfEdges
protected

Offset into the 'halfedges' sequence, one per face. Associates to each face index the index of an half-edge lying on the border of this face.

Definition at line 559 of file HalfEdgeDataStructure.h.

Referenced by clear(), halfEdgeIndexFromFaceIndex(), and nbFaces().

std::vector< HalfEdge > DGtal::HalfEdgeDataStructure::myHalfEdges
protected

Stores all the half-edges.

Definition at line 551 of file HalfEdgeDataStructure.h.

Referenced by arcFromHalfEdgeIndex(), boundaryArcs(), boundaryHalfEdgeIndices(), boundaryVertices(), clear(), halfEdge(), and nbHalfEdges().

std::vector< Index > DGtal::HalfEdgeDataStructure::myVertexHalfEdges
protected

Offsets into the 'halfedges' sequence, one per vertex. Associates to each vertex index the index of an half-edge originating from this vertex.

Definition at line 555 of file HalfEdgeDataStructure.h.

Referenced by clear(), halfEdgeIndexFromVertexIndex(), isVertexBoundary(), and nbVertices().


The documentation for this class was generated from the following file: