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

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}. More...

#include <DGtal/topology/HalfEdgeDataStructure.h>

Collaboration diagram for DGtal::HalfEdgeDataStructure:
[legend]

Data Structures

struct  Edge
 
struct  HalfEdge
 
struct  Triangle
 Represents an unoriented triangle as three vertices. More...
 

Public Types

typedef std::size_t Size
 The type for counting elements. More...
 
typedef std::size_t Index
 The type used for numbering half-edges (an offset an the half-edges structure). More...
 
typedef Index HalfEdgeIndex
 The type used for numbering half-edges (alias) More...
 
typedef Index VertexIndex
 The type for numbering vertices. More...
 
typedef Index EdgeIndex
 The type for numbering edges. More...
 
typedef Index FaceIndex
 The type for numbering faces. More...
 
typedef std::vector< HalfEdgeIndexHalfEdgeIndexRange
 
typedef std::vector< VertexIndexVertexIndexRange
 
typedef std::vector< EdgeIndexEdgeIndexRange
 
typedef std::vector< FaceIndexFaceIndexRange
 
typedef std::pair< VertexIndex, VertexIndexArc
 An arc is a directed edge from a first vertex to a second vertex. More...
 
typedef std::map< Arc, IndexArc2Index
 
typedef std::map< Arc, FaceIndexArc2FaceIndex
 
typedef std::vector< VertexIndexPolygonalFace
 

Public Member Functions

 HalfEdgeDataStructure ()
 Default constructor. The data structure is empty. More...
 
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 ()
 Clears the data structure. More...
 
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
 Stores all the half-edges. More...
 
std::vector< IndexmyVertexHalfEdges
 
std::vector< IndexmyFaceHalfEdges
 
std::vector< IndexmyEdgeHalfEdges
 
Arc2Index myArc2Index
 The mapping between arcs to their half-edge index. More...
 

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

◆ Arc

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

Definition at line 120 of file HalfEdgeDataStructure.h.

◆ Arc2FaceIndex

Definition at line 126 of file HalfEdgeDataStructure.h.

◆ Arc2Index

Definition at line 123 of file HalfEdgeDataStructure.h.

◆ EdgeIndex

The type for numbering edges.

Definition at line 99 of file HalfEdgeDataStructure.h.

◆ EdgeIndexRange

Definition at line 116 of file HalfEdgeDataStructure.h.

◆ FaceIndex

The type for numbering faces.

Definition at line 101 of file HalfEdgeDataStructure.h.

◆ FaceIndexRange

Definition at line 117 of file HalfEdgeDataStructure.h.

◆ HalfEdgeIndex

The type used for numbering half-edges (alias)

Definition at line 95 of file HalfEdgeDataStructure.h.

◆ HalfEdgeIndexRange

Definition at line 114 of file HalfEdgeDataStructure.h.

◆ Index

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

Definition at line 93 of file HalfEdgeDataStructure.h.

◆ PolygonalFace

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.

◆ Size

The type for counting elements.

Definition at line 91 of file HalfEdgeDataStructure.h.

◆ VertexIndex

The type for numbering vertices.

Definition at line 97 of file HalfEdgeDataStructure.h.

◆ VertexIndexRange

Definition at line 115 of file HalfEdgeDataStructure.h.

Constructor & Destructor Documentation

◆ HalfEdgeDataStructure()

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

◆ arc2FaceIndex()

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

Definition at line 591 of file HalfEdgeDataStructure.h.

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

References DGtal::HALF_EDGE_INVALID_INDEX.

◆ arcFromHalfEdgeIndex()

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.

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.

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

Referenced by boundaryArcs().

◆ boundaryArcs()

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.

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  }
const HalfEdge & halfEdge(const Index i) const
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
std::size_t Index
The type used for numbering half-edges (an offset an the half-edges structure).
Arc arcFromHalfEdgeIndex(const Index i) const
static std::size_t const HALF_EDGE_INVALID_INDEX

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

Referenced by SCENARIO().

◆ boundaryHalfEdgeIndices()

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.

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  }
const HalfEdge & halfEdge(const Index i) const
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
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

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

◆ boundaryVertices()

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.

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  }
const HalfEdge & halfEdge(const Index i) const
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
std::size_t Index
The type used for numbering half-edges (an offset an the half-edges structure).
HalfEdgeDataStructure::VertexIndexRange VertexIndexRange
static std::size_t const HALF_EDGE_INVALID_INDEX

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

Referenced by SCENARIO().

◆ build() [1/4]

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(), makeBox(), makeCube(), makePyramid(), makeRibbonWithHole(), makeTetrahedron(), makeThreeTriangles(), makeTriangulatedDisk(), and makeTwoTriangles().

◆ build() [2/4]

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).

◆ build() [3/4]

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.

339  {
340  std::vector<Edge> edges;
341  const Size 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)
std::size_t Size
The type for counting elements.

References build(), and getUnorderedEdgesFromTriangles().

◆ build() [4/4]

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.

354  {
355  std::vector<Edge> edges;
356  const Size 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)
std::size_t Size
The type for counting elements.

References build(), and getUnorderedEdgesFromPolygonalFaces().

◆ clear()

void DGtal::HalfEdgeDataStructure::clear ( )
inline

Clears the data structure.

Definition at line 361 of file HalfEdgeDataStructure.h.

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

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

◆ Euler()

long DGtal::HalfEdgeDataStructure::Euler ( ) const
inline
Returns
the euler characteristic of the corresponding combinatorial mesh.

Definition at line 383 of file HalfEdgeDataStructure.h.

384  { return (long) nbVertices() - (long) nbEdges() + (long) nbFaces(); }

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

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

◆ getNeighboringFaces()

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.

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 halfEdgeIndexFromVertexIndex(const VertexIndex vi) const
Index next
Index into the halfedges array.
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

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

Referenced by neighboringFaces().

◆ getNeighboringVertices()

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.

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 halfEdgeIndexFromVertexIndex(const VertexIndex vi) const
Index next
Index into the halfedges array.
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).

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

Referenced by neighboringVertices(), and SCENARIO().

◆ getUnorderedEdgesFromPolygonalFaces()

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().

◆ getUnorderedEdgesFromTriangles()

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.

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.
HalfEdgeDataStructure::Edge Edge
std::size_t Size
The type for counting elements.

Referenced by build(), makeRibbonWithHole(), and makeTriangulatedDisk().

◆ halfEdge()

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.

388 { return myHalfEdges.at( i ); }
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.

References myHalfEdges.

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

◆ halfEdgeIndexFromArc() [1/2]

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

◆ halfEdgeIndexFromArc() [2/2]

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.

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

References DGtal::HALF_EDGE_INVALID_INDEX, and myArc2Index.

◆ halfEdgeIndexFromEdgeIndex()

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.

425  { return myEdgeHalfEdges[ ei ]; }
std::vector< Index > myEdgeHalfEdges

References myEdgeHalfEdges.

◆ halfEdgeIndexFromFaceIndex()

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.

420  { return myFaceHalfEdges[ fi ]; }
std::vector< Index > myFaceHalfEdges

References myFaceHalfEdges.

◆ halfEdgeIndexFromVertexIndex()

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.

415  { return myVertexHalfEdges[ vi ]; }
std::vector< Index > myVertexHalfEdges

References myVertexHalfEdges.

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

◆ isValid()

bool DGtal::HalfEdgeDataStructure::isValid ( ) const

Checks the validity/consistency of the object.

Returns
'true' if the object is valid, 'false' otherwise.

◆ isVertexBoundary()

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.

497  {
499  }
const HalfEdge & halfEdge(const Index i) const
FaceIndex face
Index into the face array.
std::vector< Index > myVertexHalfEdges
static std::size_t const HALF_EDGE_INVALID_INDEX

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

◆ nbEdges()

Size DGtal::HalfEdgeDataStructure::nbEdges ( ) const
inline

◆ nbFaces()

Size DGtal::HalfEdgeDataStructure::nbFaces ( ) const
inline

◆ nbHalfEdges()

Size DGtal::HalfEdgeDataStructure::nbHalfEdges ( ) const
inline
Returns
the number of half edges in the structure.

Definition at line 371 of file HalfEdgeDataStructure.h.

371 { return myHalfEdges.size(); }
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.

References myHalfEdges.

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

◆ nbNeighboringVertices()

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.

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 halfEdgeIndexFromVertexIndex(const VertexIndex vi) const
Index next
Index into the halfedges array.
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.

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

◆ nbVertices()

Size DGtal::HalfEdgeDataStructure::nbVertices ( ) const
inline

◆ neighboringFaces()

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.

488  {
489  FaceIndexRange result;
490  getNeighboringFaces( vi, result );
491  return result;
492  }
std::vector< FaceIndex > FaceIndexRange
void getNeighboringFaces(const VertexIndex vi, FaceIndexRange &result) const

References getNeighboringFaces().

◆ neighboringVertices()

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.

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

References getNeighboringVertices().

◆ selfDisplay()

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

◆ myArc2Index

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().

◆ myEdgeHalfEdges

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().

◆ myFaceHalfEdges

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().

◆ myHalfEdges

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().

◆ myVertexHalfEdges

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: