DGtal  1.5.beta
Data Structures | Public Types | Public Member Functions | Static Public Member Functions | Protected 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>

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< HalfEdgeIndex > HalfEdgeIndexRange
 
typedef std::vector< VertexIndex > VertexIndexRange
 
typedef std::vector< EdgeIndex > EdgeIndexRange
 
typedef std::vector< FaceIndex > FaceIndexRange
 
typedef std::pair< VertexIndex, VertexIndex > Arc
 An arc is a directed edge from a first vertex to a second vertex. More...
 
typedef std::map< Arc, Index > Arc2Index
 
typedef std::map< Arc, FaceIndex > Arc2FaceIndex
 
typedef std::vector< VertexIndex > PolygonalFace
 

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 HalfEdge & halfEdge (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 findHalfEdgeIndexFromArc (const VertexIndex i, const VertexIndex j) const
 
Index findHalfEdgeIndexFromArc (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 VertexIndex vi, VertexIndexRange &result) const
 
VertexIndexRange neighboringVertices (const VertexIndex 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< Index > boundaryHalfEdgeIndices () const
 
std::vector< Arc > boundaryArcs () const
 
Size nbSides (Index hei) const
 
Size nbSidesOfFace (const FaceIndex f) const
 
VertexIndexRange verticesOfFace (const FaceIndex f) const
 
bool isFlippable (const Index hei) const
 
void flip (const Index hei, bool update_arc2index=true)
 
VertexIndex split (const Index i, bool update_arc2index=true)
 
bool isMergeable (const Index hei) const
 
VertexIndex merge (const Index hei, bool update_arc2index=true)
 
bool isValid (bool check_arc2index=true) const
 
bool isValidTriangulation () const
 
void selfDisplay (std::ostream &out) 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)
 

Protected Member Functions

void renumberVertex (const VertexIndex vi, bool update_arc2index=true)
 
void renumberEdge (const EdgeIndex ei)
 
void renumberFace (const FaceIndex fi)
 
void renumberHalfEdge (const Index i, bool update_arc2index=true)
 

Static Protected Member Functions

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

Protected Attributes

std::vector< HalfEdge > myHalfEdges
 Stores all the half-edges. More...
 
std::vector< Index > myVertexHalfEdges
 
std::vector< Index > myFaceHalfEdges
 
std::vector< Index > myEdgeHalfEdges
 
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 };
HalfEdgeDataStructure mesh;
mesh.build( triangles );
std::cout << mesh << std::endl;
DGtal::HalfEdgeDataStructure::HalfEdgeDataStructure
HalfEdgeDataStructure()
Default constructor. The data structure is empty.
Definition: HalfEdgeDataStructure.h:213
Note
Large parts of this class are taken from https://github.com/yig/halfedge, written by Yotam Gingold.

Definition at line 82 of file HalfEdgeDataStructure.h.

Member Typedef Documentation

◆ Arc

typedef std::pair<VertexIndex, VertexIndex> DGtal::HalfEdgeDataStructure::Arc

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

Definition at line 116 of file HalfEdgeDataStructure.h.

◆ Arc2FaceIndex

typedef std::map< Arc, FaceIndex > DGtal::HalfEdgeDataStructure::Arc2FaceIndex

Definition at line 122 of file HalfEdgeDataStructure.h.

◆ Arc2Index

typedef std::map< Arc, Index > DGtal::HalfEdgeDataStructure::Arc2Index

Definition at line 119 of file HalfEdgeDataStructure.h.

◆ EdgeIndex

typedef Index DGtal::HalfEdgeDataStructure::EdgeIndex

The type for numbering edges.

Definition at line 95 of file HalfEdgeDataStructure.h.

◆ EdgeIndexRange

typedef std::vector<EdgeIndex> DGtal::HalfEdgeDataStructure::EdgeIndexRange

Definition at line 112 of file HalfEdgeDataStructure.h.

◆ FaceIndex

typedef Index DGtal::HalfEdgeDataStructure::FaceIndex

The type for numbering faces.

Definition at line 97 of file HalfEdgeDataStructure.h.

◆ FaceIndexRange

typedef std::vector<FaceIndex> DGtal::HalfEdgeDataStructure::FaceIndexRange

Definition at line 113 of file HalfEdgeDataStructure.h.

◆ HalfEdgeIndex

typedef Index DGtal::HalfEdgeDataStructure::HalfEdgeIndex

The type used for numbering half-edges (alias)

Definition at line 91 of file HalfEdgeDataStructure.h.

◆ HalfEdgeIndexRange

typedef std::vector<HalfEdgeIndex> DGtal::HalfEdgeDataStructure::HalfEdgeIndexRange

Definition at line 110 of file HalfEdgeDataStructure.h.

◆ Index

typedef std::size_t DGtal::HalfEdgeDataStructure::Index

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

Definition at line 89 of file HalfEdgeDataStructure.h.

◆ PolygonalFace

typedef std::vector<VertexIndex> DGtal::HalfEdgeDataStructure::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 182 of file HalfEdgeDataStructure.h.

◆ Size

typedef std::size_t DGtal::HalfEdgeDataStructure::Size

The type for counting elements.

Definition at line 87 of file HalfEdgeDataStructure.h.

◆ VertexIndex

typedef Index DGtal::HalfEdgeDataStructure::VertexIndex

The type for numbering vertices.

Definition at line 93 of file HalfEdgeDataStructure.h.

◆ VertexIndexRange

typedef std::vector<VertexIndex> DGtal::HalfEdgeDataStructure::VertexIndexRange

Definition at line 111 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 213 of file HalfEdgeDataStructure.h.

213 {}

Member Function Documentation

◆ arc2FaceIndex()

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

Definition at line 1413 of file HalfEdgeDataStructure.h.

1415  {
1416  ASSERT( !de2fi.empty() );
1417 
1418  Arc2FaceIndex::const_iterator it = de2fi.find( Arc( vi, vj ) );
1419  // If no such directed edge exists, then there's no such face in the mesh.
1420  // The edge must be a boundary edge.
1421  // In this case, the reverse orientation edge must have a face.
1422  if( it == de2fi.end() )
1423  {
1424  ASSERT( de2fi.find( Arc( vj, vi ) ) != de2fi.end() );
1425  return HALF_EDGE_INVALID_INDEX;
1426  }
1427  return it->second;
1428  }
DGtal::HalfEdgeDataStructure::Arc
std::pair< VertexIndex, VertexIndex > Arc
An arc is a directed edge from a first vertex to a second vertex.
Definition: HalfEdgeDataStructure.h:116
DGtal::HALF_EDGE_INVALID_INDEX
static std::size_t const HALF_EDGE_INVALID_INDEX
Definition: HalfEdgeDataStructure.h:57

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 388 of file HalfEdgeDataStructure.h.

389  {
390  const HalfEdge& he = myHalfEdges[ i ];
391  return std::make_pair( myHalfEdges[ he.opposite ].toVertex, he.toVertex );
392  }
DGtal::HalfEdgeDataStructure::myHalfEdges
std::vector< HalfEdge > myHalfEdges
Stores all the half-edges.
Definition: HalfEdgeDataStructure.h:1379

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 566 of file HalfEdgeDataStructure.h.

567  {
568  std::vector< Arc > result;
569  for( Index hei = 0; hei < myHalfEdges.size(); ++hei )
570  {
571  const HalfEdge& he = halfEdge( hei );
572  if( HALF_EDGE_INVALID_INDEX == he.face )
573  result.push_back( arcFromHalfEdgeIndex( hei ) );
574  }
575  return result;
576  }
DGtal::HalfEdgeDataStructure::halfEdge
const HalfEdge & halfEdge(const Index i) const
Definition: HalfEdgeDataStructure.h:384
DGtal::HalfEdgeDataStructure::arcFromHalfEdgeIndex
Arc arcFromHalfEdgeIndex(const Index i) const
Definition: HalfEdgeDataStructure.h:388
Index
SMesh::Index Index
Definition: fullConvexitySphereGeodesics.cpp:117

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 552 of file HalfEdgeDataStructure.h.

553  {
554  std::vector< Index > result;
555  for( Index hei = 0; hei < myHalfEdges.size(); ++hei )
556  {
557  const HalfEdge& he = halfEdge( hei );
558  if( HALF_EDGE_INVALID_INDEX == he.face )
559  result.push_back( hei );
560  }
561  return result;
562  }

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 536 of file HalfEdgeDataStructure.h.

537  {
538  VertexIndexRange result;
539  // std::set< VertexIndex > result;
540  for( Index hei = 0; hei < myHalfEdges.size(); ++hei )
541  {
542  const HalfEdge& he = halfEdge( hei );
543  if( HALF_EDGE_INVALID_INDEX == he.face )
544  result.push_back( he.toVertex );
545  }
546  return result;
547  }
VertexIndexRange
HalfEdgeDataStructure::VertexIndexRange VertexIndexRange
Definition: testHalfEdgeDataStructure.cpp:49

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

Referenced by isValid(), and SCENARIO().

◆ build() [1/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() [2/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(), makeOctahedron(), makePyramid(), makeRibbonWithHole(), makeTetrahedron(), makeThreeTriangles(), makeTriangulatedDisk(), and makeTwoTriangles().

◆ build() [3/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 349 of file HalfEdgeDataStructure.h.

350  {
351  std::vector<Edge> edges;
352  const Size nbVtx = getUnorderedEdgesFromPolygonalFaces( polygonal_faces, edges );
353  return build( nbVtx, polygonal_faces, edges );
354  }
DGtal::HalfEdgeDataStructure::getUnorderedEdgesFromPolygonalFaces
static Size getUnorderedEdgesFromPolygonalFaces(const std::vector< PolygonalFace > &polygonal_faces, std::vector< Edge > &edges_out)
DGtal::HalfEdgeDataStructure::build
bool build(const Size num_vertices, const std::vector< Triangle > &triangles, const std::vector< Edge > &edges)
boost::edges
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator > edges(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Definition: DigitalSurfaceBoostGraphInterface.h:503
Size
HalfEdgeDataStructure::Size Size
Definition: testHalfEdgeDataStructure.cpp:50

References build(), and getUnorderedEdgesFromPolygonalFaces().

◆ build() [4/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 334 of file HalfEdgeDataStructure.h.

335  {
336  std::vector<Edge> edges;
337  const Size nbVtx = getUnorderedEdgesFromTriangles( triangles, edges );
338  return build( nbVtx, triangles, edges );
339  }
DGtal::HalfEdgeDataStructure::getUnorderedEdgesFromTriangles
static Size getUnorderedEdgesFromTriangles(const std::vector< Triangle > &triangles, std::vector< Edge > &edges_out)
Definition: HalfEdgeDataStructure.h:231

References build(), and getUnorderedEdgesFromTriangles().

◆ clear()

void DGtal::HalfEdgeDataStructure::clear ( )
inline

Clears the data structure.

Definition at line 357 of file HalfEdgeDataStructure.h.

358  {
359  myHalfEdges.clear();
360  myVertexHalfEdges.clear();
361  myFaceHalfEdges.clear();
362  myEdgeHalfEdges.clear();
363  myArc2Index.clear();
364  }
DGtal::HalfEdgeDataStructure::myArc2Index
Arc2Index myArc2Index
The mapping between arcs to their half-edge index.
Definition: HalfEdgeDataStructure.h:1393
DGtal::HalfEdgeDataStructure::myVertexHalfEdges
std::vector< Index > myVertexHalfEdges
Definition: HalfEdgeDataStructure.h:1383

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 379 of file HalfEdgeDataStructure.h.

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

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

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

◆ findHalfEdgeIndexFromArc() [1/2]

Index DGtal::HalfEdgeDataStructure::findHalfEdgeIndexFromArc ( const Arc &  arc) const
inline
Note
In opposition with halfEdgeIndexFromArc, this method does not use the map myArc2Index to find the half-edge associated with arc (v1,v2), but rather gets an half-edge originating from v1, and turn around to find the one pointing to v2. This method is useful if you do not update myArc2Index when flipping.
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 430 of file HalfEdgeDataStructure.h.

431  {
432  const Index s = halfEdgeIndexFromVertexIndex( arc.first );
433  Index i = s;
434  do {
435  const HalfEdge& he = myHalfEdges[ i ];
436  if ( he.toVertex == arc.second ) return i;
437  i = halfEdge( he.opposite ).next;
438  } while ( i != s );
439  return HALF_EDGE_INVALID_INDEX;
440  }
DGtal::HalfEdgeDataStructure::halfEdgeIndexFromVertexIndex
Index halfEdgeIndexFromVertexIndex(const VertexIndex vi) const
Definition: HalfEdgeDataStructure.h:444
DGtal::HalfEdgeDataStructure::HalfEdge::next
Index next
Index into the halfedges array.
Definition: HalfEdgeDataStructure.h:199

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

◆ findHalfEdgeIndexFromArc() [2/2]

Index DGtal::HalfEdgeDataStructure::findHalfEdgeIndexFromArc ( const VertexIndex  i,
const VertexIndex  j 
) const
inline
Note
In opposition with halfEdgeIndexFromArc, this method does not use the map myArc2Index to find the half-edge associated with arc (v1,v2), but rather gets an half-edge originating from v1, and turn around to find the one pointing to v2. This method is useful if you do not update myArc2Index when flipping.
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 418 of file HalfEdgeDataStructure.h.

419  { return findHalfEdgeIndexFromArc( std::make_pair( i, j ) ); }
DGtal::HalfEdgeDataStructure::findHalfEdgeIndexFromArc
Index findHalfEdgeIndexFromArc(const VertexIndex i, const VertexIndex j) const
Definition: HalfEdgeDataStructure.h:418

Referenced by isValid(), and SCENARIO().

◆ flip()

void DGtal::HalfEdgeDataStructure::flip ( const Index  hei,
bool  update_arc2index = true 
)
inline

Tries to flip the edge containing hei.

Parameters
heiany valid half-edge index.
update_arc2index(optimisation parameter), when 'true' updates everything consistently; when 'false' do not update myArc2Index map, which means you cannot get an half edge from two vertices afterwards. Use 'false' only if you know that you never use this mapping (e.g. no call to halfEdgeIndexFromArc)
Precondition
the edge must be flippable, isFlippable( hei ) == true
See also
isFlippable
Note
Time complexity is O(1) if update_arc2index is false, otherwise it is O(log n) is n is the number of arcs.

Definition at line 664 of file HalfEdgeDataStructure.h.

665  {
666  const Index i1 = hei;
667  HalfEdge& he1 = myHalfEdges[ i1 ];
668  const Index i2 = he1.opposite;
669  HalfEdge& he2 = myHalfEdges[ i2 ];
670  const VertexIndex v2 = he1.toVertex;
671  const VertexIndex v1 = he2.toVertex;
672  const Index i1_next = he1.next;
673  const Index i2_next = he2.next;
674  HalfEdge& he1_next = myHalfEdges[ i1_next ];
675  HalfEdge& he2_next = myHalfEdges[ i2_next ];
676  const Index i1_next2 = he1_next.next;
677  const Index i2_next2 = he2_next.next;
678  myHalfEdges[ i1_next2 ].next = i2_next;
679  myHalfEdges[ i2_next2 ].next = i1_next;
680  he2_next.next = i1;
681  he1_next.next = i2;
682  he2_next.face = he1.face;
683  he1_next.face = he2.face;
684  he1.next = i1_next2;
685  he2.next = i2_next2;
686  he1.toVertex = he1_next.toVertex;
687  he2.toVertex = he2_next.toVertex;
688  // Reassign the mapping vertex v -> index of half edge starting from v
689  // (JOL): must check before reassign for boundary vertices.
690  if ( myVertexHalfEdges[ v1 ] == i1 ) myVertexHalfEdges[ v1 ] = i2_next;
691  if ( myVertexHalfEdges[ v2 ] == i2 ) myVertexHalfEdges[ v2 ] = i1_next;
692  // Reassign the mapping face f -> index of half edge contained in f
693  myFaceHalfEdges[ he1.face ] = i1;
694  myFaceHalfEdges[ he2.face ] = i2;
695  // No need to reassign edge... it has just changed of vertices
696  // but is still based on half-edges i1 and i2
697  // Now taking care of mapping (vertex,vertex) -> half-edge.
698  if ( update_arc2index )
699  {
700  myArc2Index.erase( Arc( v1, v2 ) );
701  myArc2Index.erase( Arc( v2, v1 ) );
702  const VertexIndex v2p = he1.toVertex;
703  const VertexIndex v1p = he2.toVertex;
704  myArc2Index[ Arc( v1p, v2p ) ] = i1;
705  myArc2Index[ Arc( v2p, v1p ) ] = i2;
706  }
707  }
DGtal::HalfEdgeDataStructure::VertexIndex
Index VertexIndex
The type for numbering vertices.
Definition: HalfEdgeDataStructure.h:93

References DGtal::HalfEdgeDataStructure::HalfEdge::face, myArc2Index, myFaceHalfEdges, myHalfEdges, myVertexHalfEdges, DGtal::HalfEdgeDataStructure::HalfEdge::next, DGtal::HalfEdgeDataStructure::HalfEdge::opposite, and DGtal::HalfEdgeDataStructure::HalfEdge::toVertex.

Referenced by SCENARIO().

◆ 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 501 of file HalfEdgeDataStructure.h.

502  {
503  result.clear();
504  const Index start_hei = halfEdgeIndexFromVertexIndex( vi );
505  Index hei = start_hei;
506  do
507  {
508  const HalfEdge& he = halfEdge( hei );
509  if( HALF_EDGE_INVALID_INDEX != he.face ) result.push_back( he.face );
510  hei = halfEdge( he.opposite ).next;
511  }
512  while ( hei != start_hei );
513  }

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 VertexIndex  vi,
VertexIndexRange &  result 
) const
inline
Parameters
[in]viany vertex index.
[out]resultthe sequence of vertex neighbors of the given vertex vi (clockwise if triangles were given ccw).

Definition at line 459 of file HalfEdgeDataStructure.h.

460  {
461  result.clear();
462  const Index start_hei = halfEdgeIndexFromVertexIndex( vi );
463  Index hei = start_hei;
464  do
465  {
466  const HalfEdge& he = halfEdge( hei );
467  result.push_back( he.toVertex );
468  hei = halfEdge( he.opposite ).next;
469  }
470  while ( hei != start_hei );
471  }

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 230 of file HalfEdgeDataStructure.h.

232  {
233  typedef std::set< Edge > EdgeSet;
234  typedef std::set< VertexIndex > VertexIndexSet;
235  VertexIndexSet vertexSet;
236  EdgeSet edgeSet;
237  for( const Triangle& T : triangles )
238  {
239  edgeSet.insert( Edge( T.i(), T.j() ) );
240  edgeSet.insert( Edge( T.j(), T.k() ) );
241  edgeSet.insert( Edge( T.k(), T.i() ) );
242  vertexSet.insert( T.i() );
243  vertexSet.insert( T.j() );
244  vertexSet.insert( T.k() );
245  }
246  edges_out.resize( edgeSet.size() );
247  Size e = 0;
248  for ( const Edge& edge : edgeSet )
249  {
250  edges_out.at(e) = edge;
251  ++e;
252  }
253  return vertexSet.size();
254  }
DGtal::HalfEdgeDataStructure::Triangle
Represents an unoriented triangle as three vertices.
Definition: HalfEdgeDataStructure.h:155
Edge
HalfEdgeDataStructure::Edge Edge
Definition: testHalfEdgeDataStructure.cpp:47

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 384 of file HalfEdgeDataStructure.h.

384 { return myHalfEdges.at( i ); }

References myHalfEdges.

Referenced by boundaryArcs(), boundaryHalfEdgeIndices(), boundaryVertices(), findHalfEdgeIndexFromArc(), getNeighboringFaces(), getNeighboringVertices(), isFlippable(), isMergeable(), isValid(), isValidTriangulation(), isVertexBoundary(), merge(), nbNeighboringVertices(), nbSides(), renumberHalfEdge(), renumberVertex(), and verticesOfFace().

◆ halfEdgeIndexFromArc() [1/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 402 of file HalfEdgeDataStructure.h.

403  {
404  auto result = myArc2Index.find( arc );
405  return ( result == myArc2Index.end() ) ? HALF_EDGE_INVALID_INDEX : result->second;
406  }

References DGtal::HALF_EDGE_INVALID_INDEX, and myArc2Index.

◆ halfEdgeIndexFromArc() [2/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 397 of file HalfEdgeDataStructure.h.

398  { return halfEdgeIndexFromArc( std::make_pair( i, j ) ); }
DGtal::HalfEdgeDataStructure::halfEdgeIndexFromArc
Index halfEdgeIndexFromArc(const VertexIndex i, const VertexIndex j) const
Definition: HalfEdgeDataStructure.h:397

Referenced by SCENARIO().

◆ 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 454 of file HalfEdgeDataStructure.h.

455  { return myEdgeHalfEdges[ ei ]; }

References myEdgeHalfEdges.

Referenced by SCENARIO().

◆ 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 449 of file HalfEdgeDataStructure.h.

450  { return myFaceHalfEdges[ fi ]; }

References myFaceHalfEdges.

Referenced by nbSidesOfFace(), and verticesOfFace().

◆ 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 444 of file HalfEdgeDataStructure.h.

445  { return myVertexHalfEdges[ vi ]; }

References myVertexHalfEdges.

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

◆ isFlippable()

bool DGtal::HalfEdgeDataStructure::isFlippable ( const Index  hei) const
inline

An edge is (topologically) flippable iff: (1) it does not lie on the boundary, (2) it is bordered by two triangles, (3) the two other vertices of the quad are not already neighbors.

Parameters
heiany valid half-edge index.
Returns
'true' if the edge containing hei is topologically flippable.
Note
Time complexity is O(1).

Definition at line 628 of file HalfEdgeDataStructure.h.

629  {
630  ASSERT( hei != HALF_EDGE_INVALID_INDEX );
631  const HalfEdge& he = halfEdge( hei );
632  const Index hei2 = he.opposite;
633  const HalfEdge& he2 = halfEdge( hei2 );
634  // check if hei borders an infinite face.
635  if ( he.face == HALF_EDGE_INVALID_INDEX ) return false;
636  // check if hei2 borders an infinite face.
637  if ( he2.face == HALF_EDGE_INVALID_INDEX ) return false;
638  // Checks that he1 and he2 border a triangle.
639  if ( ( nbSides( hei ) != 3 ) || ( nbSides( hei2 ) != 3 ) ) return false;
640  // Checks that the two other vertices of the two surrounding
641  // triangles are not already neighbors
642  const VertexIndex v1 = halfEdge( he.next ).toVertex;
643  const VertexIndex v2 = halfEdge( he2.next ).toVertex;
644  const auto neighb_v1 = neighboringVertices( v1 );
645  const auto it_v2 = std::find( neighb_v1.cbegin(), neighb_v1.cend(), v2 );
646  return it_v2 == neighb_v1.cend();
647  }
DGtal::HalfEdgeDataStructure::neighboringVertices
VertexIndexRange neighboringVertices(const VertexIndex vi) const
Definition: HalfEdgeDataStructure.h:475
DGtal::HalfEdgeDataStructure::HalfEdge::toVertex
VertexIndex toVertex
The end vertex of this half-edge as an index into the vertex array.
Definition: HalfEdgeDataStructure.h:191

References DGtal::HalfEdgeDataStructure::HalfEdge::face, DGtal::HALF_EDGE_INVALID_INDEX, halfEdge(), nbSides(), neighboringVertices(), DGtal::HalfEdgeDataStructure::HalfEdge::next, DGtal::HalfEdgeDataStructure::HalfEdge::opposite, and DGtal::HalfEdgeDataStructure::HalfEdge::toVertex.

Referenced by SCENARIO().

◆ isMergeable()

bool DGtal::HalfEdgeDataStructure::isMergeable ( const Index  hei) const
inline

An edge is (topologically) mergeable iff: (1) it is bordered by two triangles, (2) there is no boundary vertex in the two triangles bordering the edge.

Parameters
heiany valid half-edge index.
Returns
'true' if the edge containing hei is topologically mergeable.
Note
Time complexity is O(1).

Definition at line 827 of file HalfEdgeDataStructure.h.

827  {
828  ASSERT( hei != HALF_EDGE_INVALID_INDEX );
829  const HalfEdge& he = halfEdge( hei );
830  const Index hei2 = he.opposite;
831  const HalfEdge& he2 = halfEdge( hei2 );
832  // check if hei borders an infinite face.
833  if ( ( he.face == HALF_EDGE_INVALID_INDEX )
834  || ( he2.face == HALF_EDGE_INVALID_INDEX ) )
835  return false;
836  // Checks that he1 and he2 border a triangle.
837  if ( ( nbSides( hei ) != 3 ) || ( nbSides( hei2 ) != 3) )
838  return false;
839  // Checks that no vertices around lie on the boundary.
840  return ( ! isVertexBoundary( he.toVertex ) )
841  && ( ! isVertexBoundary( he2.toVertex ) )
842  && ( ! isVertexBoundary( halfEdge( he.next ).toVertex ) )
843  && ( ! isVertexBoundary( halfEdge( he2.next ).toVertex ) );
844  }
DGtal::HalfEdgeDataStructure::isVertexBoundary
bool isVertexBoundary(const VertexIndex vi) const
Definition: HalfEdgeDataStructure.h:526

References DGtal::HalfEdgeDataStructure::HalfEdge::face, DGtal::HALF_EDGE_INVALID_INDEX, halfEdge(), isVertexBoundary(), nbSides(), DGtal::HalfEdgeDataStructure::HalfEdge::next, DGtal::HalfEdgeDataStructure::HalfEdge::opposite, and DGtal::HalfEdgeDataStructure::HalfEdge::toVertex.

Referenced by SCENARIO().

◆ isValid()

bool DGtal::HalfEdgeDataStructure::isValid ( bool  check_arc2index = true) const
inline

Checks the whole half-edge structure for consistency. Complexity is at O(n log n) if n in the number of half-edges.

Parameters
check_arc2index(optimisation parameter), when 'true' checks everything, otherwise does not check that the mapping myArc2Index is correct. This is used in conjunction with flip method when using the optimisation.
Returns
'true' iff all checks have passed.
See also
flip

Definition at line 1109 of file HalfEdgeDataStructure.h.

1110  {
1111  bool ok = true;
1112  // Checks that indices are within range
1113  for ( Index i = 0; i < nbHalfEdges(); i++ )
1114  {
1115  const HalfEdge& he = myHalfEdges[ i ];
1116  if ( he.next >= nbHalfEdges() ) {
1117  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1118  << "half-edge " << i
1119  << " has invalid next half-edge " << he.next
1120  << std::endl;
1121  ok = false;
1122  }
1123  if ( he.opposite >= nbHalfEdges() ) {
1124  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1125  << "half-edge " << i
1126  << " has invalid opposite half-edge " << he.opposite
1127  << std::endl;
1128  ok = false;
1129  }
1130  if ( he.toVertex >= nbVertices() ) {
1131  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1132  << "half-edge " << i
1133  << " has invalid toVertex " << he.toVertex
1134  << std::endl;
1135  ok = false;
1136  }
1137  if ( he.face >= nbFaces() && he.face != HALF_EDGE_INVALID_INDEX ) {
1138  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1139  << "half-edge " << i
1140  << " has invalid face " << he.face
1141  << std::endl;
1142  ok = false;
1143  }
1144  }
1145  // Checks that opposite are correct
1146  for ( Index i = 0; i < nbHalfEdges(); i++ )
1147  {
1148  const Index j = myHalfEdges[ i ].opposite;
1149  if ( j == HALF_EDGE_INVALID_INDEX ) {
1150  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1151  << "half-edge " << i << " has invalid opposite half-edge." << std::endl;
1152  ok = false;
1153  }
1154  if ( myHalfEdges[ j ].opposite != i ) {
1155  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1156  << "half-edge " << i << " has opposite half-edge " << j
1157  << " but the latter has opposite half-edge " << myHalfEdges[ j ].opposite << std::endl;
1158  ok = false;
1159  }
1160  const VertexIndex vi = myHalfEdges[ i ].toVertex;
1161  const VertexIndex vj = myHalfEdges[ j ].toVertex;
1162  if ( vi == vj ) {
1163  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1164  << "half-edge " << i << " and its opposite half-edge " << j
1165  << " have the same toVertex " << vi << std::endl;
1166  ok = false;
1167  }
1168  if ( vi >= nbVertices() ) {
1169  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1170  << "half-edge " << i
1171  << " points to an invalid vertex " << vi << std::endl;
1172  ok = false;
1173  }
1174  if ( vj >= nbVertices() ) {
1175  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1176  << "opposite half-edge " << j
1177  << " points to an invalid vertex " << vj << std::endl;
1178  ok = false;
1179  }
1180  }
1181  // Checks that vertices have a correct starting half-edge.
1182  for ( VertexIndex i = 0; i < nbVertices(); i++ )
1183  {
1184  const Index j = myVertexHalfEdges[ i ];
1185  const Index jopp = myHalfEdges[ j ].opposite;
1186  const VertexIndex ip = myHalfEdges[ jopp ].toVertex;
1187  if ( ip != i ) {
1188  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1189  << "vertex " << i << " is associated to half-edge " << j
1190  << " but its opposite half-edge " << jopp << " points to vertex " << ip << std::endl;
1191  ok = false;
1192  }
1193  }
1194  // Checks that faces have a correct bordering half-edge.
1195  for ( FaceIndex f = 0; f < nbFaces(); f++ )
1196  {
1197  const Index i = myFaceHalfEdges[ f ];
1198  if ( myHalfEdges[ i ].face != f ) {
1199  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1200  << "face " << f << " is associated to half-edge " << i
1201  << " but its associated face is " << myHalfEdges[ i ].face << std::endl;
1202  ok = false;
1203  }
1204  }
1205  // Checks that following next half-edges turns around the same face.
1206  for ( FaceIndex f = 0; f < nbFaces(); f++ )
1207  {
1208  Index i = myFaceHalfEdges[ f ];
1209  const Index start = i;
1210  do {
1211  const HalfEdge& he = halfEdge( i );
1212  if ( he.face != f ) {
1213  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1214  << "when turning around face " << f << ", half-edge " << i
1215  << " is associated to face " << he.face << std::endl;
1216  ok = false;
1217  }
1218  i = he.next;
1219  }
1220  while ( i != start );
1221  }
1222  // Checks that turning around a vertex gives half-edges associated to this vertex.
1223  for ( VertexIndex v = 0; v < nbVertices(); v++ )
1224  {
1225  const Index s = halfEdgeIndexFromVertexIndex( v );
1226  Index i = s;
1227  do
1228  {
1229  const HalfEdge& he = halfEdge( i );
1230  const VertexIndex w = halfEdge( he.opposite ).toVertex;
1231  if ( v != w ) {
1232  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1233  << "when turning around vertex " << v << ", some opposite half-edge "
1234  << he.opposite << " points to " << w << std::endl;
1235  ok = false;
1236  }
1237  i = halfEdge( he.opposite ).next;
1238  }
1239  while ( i != s );
1240  }
1241 
1242  // Checks that boundary vertices have specific associated half-edges.
1243  VertexIndexRange bdryV = boundaryVertices();
1244  for ( VertexIndex i : bdryV ) {
1245  const Index j = myVertexHalfEdges[ i ];
1246  if ( halfEdge( j ).face != HALF_EDGE_INVALID_INDEX ) {
1247  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1248  << "boundary vertex " << i << " is associated to the half-edge " << j
1249  << " that does not lie on the boundary but on face " << halfEdge( j ).face
1250  << std::endl;
1251  ok = false;
1252  }
1253  }
1254 
1255  // Checks that that we can find arcs.
1256  for ( Index i = 0; i < nbHalfEdges(); i++ ) {
1257  const HalfEdge& he = halfEdge( i );
1258  const VertexIndex v2 = he.toVertex;
1259  const VertexIndex v1 = halfEdge( he.opposite ).toVertex;
1260  const Index j = findHalfEdgeIndexFromArc( v1, v2 );
1261  const HalfEdge& he2 = halfEdge( j );
1262  if ( he2.toVertex != v2 ) {
1263  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1264  << "arc (" << v1 << "," << v2 << ") was found to be half-edge " << j
1265  << " but it should be half-edge " << i << std::endl;
1266  ok = false;
1267  }
1268  }
1269 
1270  // Checks that edges have two correct associated half-edges.
1271  for ( EdgeIndex ei = 0; ei < nbEdges(); ei++ ) {
1272  const Index i = myEdgeHalfEdges[ ei ];
1273  const HalfEdge& hei = halfEdge( i );
1274  const Index j = hei.opposite;
1275  const HalfEdge& hej = halfEdge( j );
1276  if ( hei.edge != ei ) {
1277  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1278  << "edge " << ei << " is associated to half-edge " << i
1279  << " but its edge is " << hei.edge << std::endl;
1280  ok = false;
1281  }
1282  if ( hej.edge != ei ) {
1283  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1284  << "edge " << ei << " is associated to half-edge " << i
1285  << " of opposite half-edge " << j
1286  << " but its edge is " << hej.edge << std::endl;
1287  ok = false;
1288  }
1289  }
1290 
1291  // Checks that arcs have a correct associated half-edge.
1292  if ( check_arc2index )
1293  {
1294  for ( auto arc2idx : myArc2Index )
1295  {
1296  const VertexIndex v1 = arc2idx.first.first;
1297  const VertexIndex v2 = arc2idx.first.second;
1298  const Index i = arc2idx.second;
1299  if ( myHalfEdges[ i ].toVertex != v2 ) {
1300  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1301  << "arc (" << v1 << "," << v2 << ") is associated to half-edge " << i
1302  << " but it points to vertex " << myHalfEdges[ i ].toVertex << std::endl;
1303  ok = false;
1304  }
1305  const Index i2 = myHalfEdges[ i ].opposite;
1306  if ( myHalfEdges[ i2 ].toVertex != v1 ) {
1307  trace.warning() << "[HalfEdgeDataStructure::isValid] "
1308  << "arc (" << v1 << "," << v2 << ") is associated to half-edge " << i
1309  << " but its opposite half-edge " << i2 << " points to vertex " << myHalfEdges[ i2 ].toVertex
1310  << std::endl;
1311  ok = false;
1312  }
1313  }
1314  }
1315  return ok;
1316  }
DGtal::HalfEdgeDataStructure::FaceIndex
Index FaceIndex
The type for numbering faces.
Definition: HalfEdgeDataStructure.h:97
DGtal::HalfEdgeDataStructure::EdgeIndex
Index EdgeIndex
The type for numbering edges.
Definition: HalfEdgeDataStructure.h:95
DGtal::HalfEdgeDataStructure::boundaryVertices
VertexIndexRange boundaryVertices() const
Definition: HalfEdgeDataStructure.h:536
DGtal::Trace::warning
std::ostream & warning()
DGtal::trace
Trace trace
Definition: Common.h:153
DGtal::HalfEdgeDataStructure::HalfEdge::face
FaceIndex face
Index into the face array.
Definition: HalfEdgeDataStructure.h:193

References boundaryVertices(), DGtal::HalfEdgeDataStructure::HalfEdge::edge, DGtal::HalfEdgeDataStructure::HalfEdge::face, findHalfEdgeIndexFromArc(), DGtal::HALF_EDGE_INVALID_INDEX, halfEdge(), halfEdgeIndexFromVertexIndex(), myArc2Index, myEdgeHalfEdges, myFaceHalfEdges, myHalfEdges, myVertexHalfEdges, nbEdges(), nbFaces(), nbHalfEdges(), nbVertices(), DGtal::HalfEdgeDataStructure::HalfEdge::next, DGtal::HalfEdgeDataStructure::HalfEdge::opposite, DGtal::HalfEdgeDataStructure::HalfEdge::toVertex, DGtal::trace, and DGtal::Trace::warning().

Referenced by SCENARIO().

◆ isValidTriangulation()

bool DGtal::HalfEdgeDataStructure::isValidTriangulation ( ) const
inline

Specific checks that are meaningful only for a triangulation (i.e. faces have three vertices).

Returns
'true' if all checks have passed.

Definition at line 1322 of file HalfEdgeDataStructure.h.

1323  {
1324  bool ok = true;
1325  // Checks that indices are within range
1326  // Checks that following next half-edges turns around the same face.
1327  for ( FaceIndex f = 0; f < nbFaces(); f++ )
1328  {
1329  Index i = myFaceHalfEdges[ f ];
1330  const Index start = i;
1331  int nbv = 0;
1332  std::set<VertexIndex> V;
1333  std::set<EdgeIndex> E;
1334  do {
1335  const HalfEdge& he = halfEdge( i );
1336  if ( he.face != f ) {
1337  trace.warning() << "[HalfEdgeDataStructure::isValidTriangulation] "
1338  << "when turning around face " << f
1339  << ", half-edge " << i
1340  << " is associated to face " << he.face
1341  << std::endl;
1342  ok = false;
1343  }
1344  V.insert( he.toVertex );
1345  E.insert( he.edge );
1346  nbv++;
1347  i = he.next;
1348  }
1349  while ( i != start );
1350  if ( nbv != 3 ) {
1351  trace.warning() << "[HalfEdgeDataStructure::isValidTriangulation] "
1352  << "when turning around face " << f
1353  << ", we had to visit " << nbv
1354  << " half-edges to loop (instead of 3)" << std::endl;
1355  ok = false;
1356  }
1357  if ( V.size() != 3 ) {
1358  trace.warning() << "[HalfEdgeDataStructure::isValidTriangulation] "
1359  << "when turning around face " << f
1360  << ", the set of vertices has not a size 3:";
1361  for ( auto v : V ) trace.warning() << " " << v;
1362  trace.warning() << std::endl;
1363  ok = false;
1364  }
1365  if ( E.size() != 3 ) {
1366  trace.warning() << "[HalfEdgeDataStructure::isValidTriangulation] "
1367  << "when turning around face " << f
1368  << ", the set of edges has not a size 3:";
1369  for ( auto e : E ) trace.warning() << " " << e;
1370  trace.warning() << std::endl;
1371  ok = false;
1372  }
1373  }
1374  return ok;
1375  }

References DGtal::HalfEdgeDataStructure::HalfEdge::edge, DGtal::HalfEdgeDataStructure::HalfEdge::face, halfEdge(), myFaceHalfEdges, nbFaces(), DGtal::HalfEdgeDataStructure::HalfEdge::next, DGtal::HalfEdgeDataStructure::HalfEdge::toVertex, DGtal::trace, and DGtal::Trace::warning().

Referenced by SCENARIO().

◆ 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 526 of file HalfEdgeDataStructure.h.

527  {
528  return HALF_EDGE_INVALID_INDEX == halfEdge( myVertexHalfEdges[ vi ] ).face;
529  }

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

Referenced by isMergeable().

◆ merge()

VertexIndex DGtal::HalfEdgeDataStructure::merge ( const Index  hei,
bool  update_arc2index = true 
)
inline

Merges the edge specified by the half-edge hei.

Parameters
heiany valid half-edge index.
update_arc2index(optimisation parameter), when 'true' updates everything consistently; when 'false' do not update myArc2Index map, which means you cannot get an half edge from two vertices afterwards. Use 'false' only if you know that you never use this mapping (e.g. no call to halfEdgeIndexFromArc)
Returns
the index of the merged vertex.
Precondition
the edge must be mergeable, isMergeable( hei ) == true
See also
isMergeable
Note
Time complexity is O(1) if update_arc2index is false, otherwise it is O(log n) is n is the number of arcs.
Todo:
We could also merge boundary triangles or more general faces.

Definition at line 865 of file HalfEdgeDataStructure.h.

865  {
866  const Index i1 = hei; // arc (v1,v2)
867  const HalfEdge& he1 = halfEdge( i1 );
868  const Index i1n = he1.next;
869  const HalfEdge& he1n = halfEdge( i1n );
870  const Index i1nn = he1n.next;
871  const Index i2 = he1.opposite; // arc (v2,v1)
872  const HalfEdge& he2 = halfEdge( i2 );
873  const Index i2n = he2.next;
874  const HalfEdge& he2n = halfEdge( i2n );
875  const Index i2nn = he2n.next;
876  const Index iext1nn = halfEdge( i1nn ).opposite;
877  const Index iext1n = halfEdge( i1n ).opposite;
878  const Index iext2nn = halfEdge( i2nn ).opposite;
879  const Index iext2n = halfEdge( i2n ).opposite;
880  const VertexIndex v1 = he2.toVertex;
881  // Storing v2 the deleted vertex.
882  const VertexIndex v2 = he1.toVertex;
883  const VertexIndex v3 = he1n.toVertex;
884  const VertexIndex v4 = he2n.toVertex;
885  // Storing deleted face indices f1 and f2
886  const FaceIndex f1 = he1.face;
887  const FaceIndex f2 = he2.face;
888  // Storing deleted edge indices (v1,v2), (v2,v3) and (v2,v3').
889  const EdgeIndex e1 = he1.edge;
890  const EdgeIndex e2 = he1n.edge;
891  const EdgeIndex e3 = halfEdge( i2nn ).edge;
892  const EdgeIndex ev13 = halfEdge( iext1nn ).edge;
893  const EdgeIndex ev14 = halfEdge( iext2n ).edge;
894  // For debug
895  auto nbV1 = nbNeighboringVertices( v1 );
896  auto nbV2 = nbNeighboringVertices( v2 );
897  auto nbV3 = nbNeighboringVertices( v3 );
898  auto nbV4 = nbNeighboringVertices( v4 );
899  // Changes toVertex field of half-edges pointing to v2
900  std::vector<VertexIndex> outer_v; // stores vertices around v2
901  std::vector<Index> inner_he; // stores half-edges from v2
902  std::vector<Index> outer_he; // stores half-edges toward v2
903  Index i = i1n;
904  do {
905  const HalfEdge& he = halfEdge( i );
906  const Index iopp = he.opposite;
907  outer_v. push_back( he.toVertex );
908  inner_he.push_back( i );
909  outer_he.push_back( iopp );
910  HalfEdge& heopp = myHalfEdges[ iopp ];
911  ASSERT( heopp.toVertex == v2 );
912  heopp.toVertex = v1;
913  i = heopp.next;
914  } while ( i != i1n ); // i2 precedes i1n around the vertex v2.
915  // std::cout << "#outer_v=" << outer_v.size() << std::endl;
916  // Gluing arcs around the two triangles
917  // std::cout << "Gluing arcs around the two triangles" << std::endl;
918  myHalfEdges[ iext1nn ].opposite = iext1n;
919  myHalfEdges[ iext1n ].opposite = iext1nn;
920  myHalfEdges[ iext2nn ].opposite = iext2n;
921  myHalfEdges[ iext2n ].opposite = iext2nn;
922  // Changing edges of merged edges
923  // std::cout << "Changing edges of merged edges" << std::endl;
924  myHalfEdges[ iext1n ].edge = ev13;
925  myHalfEdges[ iext2nn ].edge = ev14;
926  // Taking care of look-up tables.
927  // (1) myVertexHalfEdges
928  // std::cout << "(1) myVertexHalfEdges" << std::endl;
929  myVertexHalfEdges[ v1 ] = iext1nn;
930  if ( myVertexHalfEdges[ v3 ] == i1nn )
931  myVertexHalfEdges[ v3 ] = iext1n;
932  if ( myVertexHalfEdges[ v4 ] == i2nn )
933  myVertexHalfEdges[ v4 ] = iext2n;
934  // (2) myFaceHalfEdges -> nothing to do.
935  // (3) myEdgeHalfEdges
936  // std::cout << "(3) myEdgeHalfEdges" << std::endl;
937  myEdgeHalfEdges[ ev13 ] = iext1nn;
938  myEdgeHalfEdges[ ev14 ] = iext2n;
939  // (4) myArc2Index only if asked
940  if ( update_arc2index ) {
941  for ( std::size_t j = 0; j < outer_v.size(); ++j ) {
942  myArc2Index.erase( Arc( v2, outer_v[ j ] ) );
943  myArc2Index.erase( Arc( outer_v[ j ], v2 ) );
944  }
945  for ( std::size_t j = 1; j < ( outer_v.size() - 2 ); ++j ) {
946  myArc2Index[ Arc( v1, outer_v[ j ] ) ] = inner_he[ j ];
947  myArc2Index[ Arc( outer_v[ j ], v1 ) ] = outer_he[ j ];
948  }
949  myArc2Index[ Arc( v3, v1 ) ] = iext1n;
950  myArc2Index[ Arc( v1, v4 ) ] = iext2nn;
951  }
952  // Debug
953  auto new_nbV1 = nbNeighboringVertices( v1 );
954  auto new_nbV3 = nbNeighboringVertices( v3 );
955  auto new_nbV4 = nbNeighboringVertices( v4 );
956  if ( ( new_nbV1 != nbV1+nbV2-4 )
957  || ( new_nbV3 != nbV3 -1 )
958  || ( new_nbV4 != nbV4 -1 ) )
959  trace.warning() << "Invalid nb of neighbors: "
960  << " nbV1=" << nbV1
961  << " nbV2=" << nbV2
962  << " nbV3=" << nbV3
963  << " nbV4=" << nbV4 << std::endl
964  << " new_nbV1=" << new_nbV1
965  << " new_nbV3=" << new_nbV3
966  << " new_nbV4=" << new_nbV4 << std::endl;
967 
968  // Renumbering of 1 vertex, 3 edges, 2 faces, 6 half-edges
969  renumberVertex( v2, update_arc2index );
970  std::array< EdgeIndex, 3 > E = { e1, e2, e3 };
971  std::sort( E.begin(), E.end(), std::greater<EdgeIndex>() );
972  for ( Index e : E ) {
973  renumberEdge( e );
974  }
975  std::array< FaceIndex, 2 > F = { f1, f2 };
976  std::sort( F.begin(), F.end(), std::greater<FaceIndex>() );
977  for ( Index f : F ) {
978  renumberFace( f );
979  }
980  std::array< Index, 6 > T = { i1, i1n, i1nn, i2, i2n, i2nn };
981  std::sort( T.begin(), T.end(), std::greater<Index>() );
982  for ( Index t : T ) {
983  renumberHalfEdge( t );
984  }
985  return v1;
986  }
DGtal::HalfEdgeDataStructure::renumberFace
void renumberFace(const FaceIndex fi)
Definition: HalfEdgeDataStructure.h:1042
DGtal::HalfEdgeDataStructure::renumberEdge
void renumberEdge(const EdgeIndex ei)
Definition: HalfEdgeDataStructure.h:1023
DGtal::HalfEdgeDataStructure::renumberVertex
void renumberVertex(const VertexIndex vi, bool update_arc2index=true)
Definition: HalfEdgeDataStructure.h:994
DGtal::HalfEdgeDataStructure::renumberHalfEdge
void renumberHalfEdge(const Index i, bool update_arc2index=true)
Definition: HalfEdgeDataStructure.h:1061
DGtal::HalfEdgeDataStructure::nbNeighboringVertices
Size nbNeighboringVertices(const Index vi) const
Definition: HalfEdgeDataStructure.h:484
DGtal::HalfEdgeDataStructure::HalfEdge::edge
EdgeIndex edge
Index into the edges array.
Definition: HalfEdgeDataStructure.h:195
DGtal::HalfEdgeDataStructure::HalfEdge::opposite
Index opposite
Index into the halfedges array.
Definition: HalfEdgeDataStructure.h:197

References DGtal::HalfEdgeDataStructure::HalfEdge::edge, DGtal::HalfEdgeDataStructure::HalfEdge::face, halfEdge(), myArc2Index, myEdgeHalfEdges, myHalfEdges, myVertexHalfEdges, nbNeighboringVertices(), DGtal::HalfEdgeDataStructure::HalfEdge::next, DGtal::HalfEdgeDataStructure::HalfEdge::opposite, renumberEdge(), renumberFace(), renumberHalfEdge(), renumberVertex(), DGtal::HalfEdgeDataStructure::HalfEdge::toVertex, DGtal::trace, and DGtal::Trace::warning().

Referenced by SCENARIO().

◆ nbEdges()

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

Definition at line 373 of file HalfEdgeDataStructure.h.

373 { return myEdgeHalfEdges.size(); }

References myEdgeHalfEdges.

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

◆ nbFaces()

Size DGtal::HalfEdgeDataStructure::nbFaces ( ) const
inline
Returns
the number of faces in the structure.

Definition at line 376 of file HalfEdgeDataStructure.h.

376 { return myFaceHalfEdges.size(); }

References myFaceHalfEdges.

Referenced by Euler(), isValid(), isValidTriangulation(), DGtal::PolygonalSurface< TPoint >::nbFaces(), DGtal::TriangulatedSurface< TPoint >::nbFaces(), DGtal::IndexedDigitalSurface< TDigitalSurfaceContainer >::nbFaces(), renumberFace(), and SCENARIO().

◆ nbHalfEdges()

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

Definition at line 367 of file HalfEdgeDataStructure.h.

367 { return myHalfEdges.size(); }

References myHalfEdges.

Referenced by isValid(), DGtal::PolygonalSurface< TPoint >::nbArcs(), DGtal::TriangulatedSurface< TPoint >::nbArcs(), DGtal::IndexedDigitalSurface< TDigitalSurfaceContainer >::nbArcs(), renumberHalfEdge(), 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 484 of file HalfEdgeDataStructure.h.

485  {
486  Size nb = 0;
487  const Index start_hei = halfEdgeIndexFromVertexIndex( vi );
488  Index hei = start_hei;
489  do
490  {
491  const HalfEdge& he = halfEdge( hei );
492  nb++;
493  hei = halfEdge( he.opposite ).next;
494  }
495  while ( hei != start_hei );
496  return nb;
497  }

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

Referenced by merge().

◆ nbSides()

Size DGtal::HalfEdgeDataStructure::nbSides ( Index  hei) const
inline
Parameters
heiany valid half-edge index.
Returns
the number of sides of the face that contains the half-edge hei.

Definition at line 580 of file HalfEdgeDataStructure.h.

581  {
582  ASSERT( hei != HALF_EDGE_INVALID_INDEX );
583  Size nb = 0;
584  const Index start = hei;
585  do {
586  hei = halfEdge( hei ).next;
587  nb++;
588  }
589  while ( hei != start );
590  return nb;
591  }

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

Referenced by isFlippable(), isMergeable(), and nbSidesOfFace().

◆ nbSidesOfFace()

Size DGtal::HalfEdgeDataStructure::nbSidesOfFace ( const FaceIndex  f) const
inline
Parameters
fany valid face index.
Returns
the number of sides of the face f.

Definition at line 595 of file HalfEdgeDataStructure.h.

596  {
597  return nbSides( halfEdgeIndexFromFaceIndex( f ) );
598  }
DGtal::HalfEdgeDataStructure::halfEdgeIndexFromFaceIndex
Index halfEdgeIndexFromFaceIndex(const FaceIndex fi) const
Definition: HalfEdgeDataStructure.h:449

References halfEdgeIndexFromFaceIndex(), and nbSides().

◆ nbVertices()

Size DGtal::HalfEdgeDataStructure::nbVertices ( ) const
inline
Returns
the number of vertices in the structure.

Definition at line 370 of file HalfEdgeDataStructure.h.

370 { return myVertexHalfEdges.size(); }

References myVertexHalfEdges.

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

◆ 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 517 of file HalfEdgeDataStructure.h.

518  {
519  FaceIndexRange result;
520  getNeighboringFaces( vi, result );
521  return result;
522  }
DGtal::HalfEdgeDataStructure::getNeighboringFaces
void getNeighboringFaces(const VertexIndex vi, FaceIndexRange &result) const
Definition: HalfEdgeDataStructure.h:501
DGtal::HalfEdgeDataStructure::FaceIndexRange
std::vector< FaceIndex > FaceIndexRange
Definition: HalfEdgeDataStructure.h:113

References getNeighboringFaces().

◆ neighboringVertices()

VertexIndexRange DGtal::HalfEdgeDataStructure::neighboringVertices ( const VertexIndex  vi) const
inline
Parameters
[in]viany vertex index.
Returns
the sequence of vertex neighbors of the given vertex vi (clockwise if triangles were given ccw).

Definition at line 475 of file HalfEdgeDataStructure.h.

476  {
477  VertexIndexRange result;
478  getNeighboringVertices( vi, result );
479  return result;
480  }
DGtal::HalfEdgeDataStructure::getNeighboringVertices
void getNeighboringVertices(const VertexIndex vi, VertexIndexRange &result) const
Definition: HalfEdgeDataStructure.h:459

References getNeighboringVertices().

Referenced by isFlippable(), and SCENARIO().

◆ renumberEdge()

void DGtal::HalfEdgeDataStructure::renumberEdge ( const EdgeIndex  ei)
inlineprotected

Renumber the last edge of the triangulated surface as edge ei (this replaces it). The number of edges of the data structure is decreased by 1.

Definition at line 1023 of file HalfEdgeDataStructure.h.

1023  {
1024  const EdgeIndex ej = nbEdges() - 1;
1025  if ( ei != ej ) {
1026  const Index j = myEdgeHalfEdges[ ej ];
1027  HalfEdge& hej = myHalfEdges[ j ];
1028  const Index jopp = hej.opposite;
1029  HalfEdge& hejopp = myHalfEdges[ jopp ];
1030  ASSERT( hej.edge == ej );
1031  ASSERT( hejopp.edge == ej );
1032  hej.edge = ei;
1033  hejopp.edge = ei;
1034  myEdgeHalfEdges[ ei ] = j;
1035  }
1036  myEdgeHalfEdges.pop_back();
1037  }

References DGtal::HalfEdgeDataStructure::HalfEdge::edge, myEdgeHalfEdges, myHalfEdges, nbEdges(), and DGtal::HalfEdgeDataStructure::HalfEdge::opposite.

Referenced by merge().

◆ renumberFace()

void DGtal::HalfEdgeDataStructure::renumberFace ( const FaceIndex  fi)
inlineprotected

Renumber the last face of the triangulated surface as face fi (this replaces it). The number of faces of the data structure is decreased by 1.

Definition at line 1042 of file HalfEdgeDataStructure.h.

1042  {
1043  const FaceIndex fj = nbFaces() - 1;
1044  if ( fi != fj ) {
1045  const Index j = myFaceHalfEdges[ fj ];
1046  Index k = j;
1047  do {
1048  HalfEdge& hek = myHalfEdges[ k ];
1049  ASSERT( hek.face == fj );
1050  hek.face = fi;
1051  k = hek.next;
1052  } while ( k != j );
1053  myFaceHalfEdges[ fi ] = j;
1054  }
1055  myFaceHalfEdges.pop_back();
1056  }

References DGtal::HalfEdgeDataStructure::HalfEdge::face, myFaceHalfEdges, myHalfEdges, nbFaces(), and DGtal::HalfEdgeDataStructure::HalfEdge::next.

Referenced by merge().

◆ renumberHalfEdge()

void DGtal::HalfEdgeDataStructure::renumberHalfEdge ( const Index  i,
bool  update_arc2index = true 
)
inlineprotected

Renumber the last half-edge of the triangulated surface as half-edge i (this replaces it). The number of half-edges of the data structure is decreased by 1.

Definition at line 1061 of file HalfEdgeDataStructure.h.

1061  {
1062  const Index j = nbHalfEdges() - 1;
1063  if ( i != j ) {
1064  // std::cout << "renumberHalfEdge j=" << j << std::endl;
1065  const HalfEdge& hej = halfEdge( j );
1066  const Index jopp = hej.opposite;
1067  // std::cout << "renumberHalfEdge jopp=" << jopp << std::endl;
1068  HalfEdge& hejopp = myHalfEdges[ jopp ];
1069  const VertexIndex vj = hejopp.toVertex; // hej corresponds to (vj,vk)
1070  const VertexIndex vk = hej.toVertex; // hejopp corresponds to (vk,vj)
1071  // Update opposite and previous
1072  Index k = hej.next;
1073  while ( halfEdge( k ).next != j ) k = halfEdge( k ).next;
1074  myHalfEdges[ k ].next = i;
1075  hejopp.opposite = i;
1076  // Take care of look-up tables
1077  // std::cout << "myVertexHalfEdges[" << vj << "]" << std::endl;
1078  if ( myVertexHalfEdges[ vj ] == j )
1079  myVertexHalfEdges[ vj ] = i;
1080  // std::cout << "myEdgeHalfEdges[" << hej.edge << "]" << std::endl;
1081  if ( myEdgeHalfEdges[ hej.edge ] == j )
1082  myEdgeHalfEdges[ hej.edge ] = i;
1083  // std::cout << "myFaceHalfEdges[" << hej.face << "]" << std::endl;
1084  if ( myFaceHalfEdges[ hej.face ] == j )
1085  myFaceHalfEdges[ hej.face ] = i;
1086  // std::cout << "myArc2Index[" << vj << "," << vk << "]" << std::endl;
1087  if ( update_arc2index ) {
1088  myArc2Index[ Arc( vj, vk ) ] = i;
1089  }
1090  // Copy last half-edge into i-th half-edge.
1091  myHalfEdges[ i ] = hej;
1092  }
1093  myHalfEdges.pop_back();
1094  }

References DGtal::HalfEdgeDataStructure::HalfEdge::edge, DGtal::HalfEdgeDataStructure::HalfEdge::face, halfEdge(), myArc2Index, myEdgeHalfEdges, myFaceHalfEdges, myHalfEdges, myVertexHalfEdges, nbHalfEdges(), DGtal::HalfEdgeDataStructure::HalfEdge::next, DGtal::HalfEdgeDataStructure::HalfEdge::opposite, and DGtal::HalfEdgeDataStructure::HalfEdge::toVertex.

Referenced by merge().

◆ renumberVertex()

void DGtal::HalfEdgeDataStructure::renumberVertex ( const VertexIndex  vi,
bool  update_arc2index = true 
)
inlineprotected

Renumber the last vertex of the triangulated surface as vertex i (this replaces it). The number of vertices of the data structure is decreased by 1.

Definition at line 994 of file HalfEdgeDataStructure.h.

994  {
995  // Vertex j becomes vertex i
996  const VertexIndex vj = nbVertices() - 1;
997  if ( vi != vj ) {
998  const Index j = myVertexHalfEdges[ vj ];
999  Index k = j;
1000  // Turns around vertex vj to modify toVertex fields.
1001  do {
1002  const HalfEdge& hek = halfEdge( k );
1003  const Index kopp = hek.opposite;
1004  HalfEdge& hekopp = myHalfEdges[ kopp ];
1005  ASSERT( hekopp.toVertex == vj );
1006  hekopp.toVertex = vi;
1007  if ( update_arc2index ) {
1008  myArc2Index.erase( Arc( vj, hek.toVertex ) );
1009  myArc2Index.erase( Arc( hek.toVertex, vj ) );
1010  myArc2Index[ Arc( vi, hek.toVertex ) ] = k;
1011  myArc2Index[ Arc( hek.toVertex, vi ) ] = kopp;
1012  }
1013  k = hekopp.next;
1014  } while ( k != j );
1015  myVertexHalfEdges[ vi ] = j;
1016  }
1017  myVertexHalfEdges.pop_back();
1018  }

References halfEdge(), myArc2Index, myHalfEdges, myVertexHalfEdges, nbVertices(), DGtal::HalfEdgeDataStructure::HalfEdge::next, DGtal::HalfEdgeDataStructure::HalfEdge::opposite, and DGtal::HalfEdgeDataStructure::HalfEdge::toVertex.

Referenced by merge().

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

◆ split()

VertexIndex DGtal::HalfEdgeDataStructure::split ( const Index  i,
bool  update_arc2index = true 
)
inline

Splits the edge specified by the half-edge i.

Parameters
iany valid half-edge index.
update_arc2index(optimisation parameter), when 'true' updates everything consistently; when 'false' do not update myArc2Index map, which means you cannot get an half edge from two vertices afterwards. Use 'false' only if you know that you never use this mapping (e.g. no call to halfEdgeIndexFromArc)
Returns
the index of the created vertex.
Precondition
the edge must be flippable, isFlippable( i ) == true
See also
isFlippable
Todo:
We could also split boundary triangles or more general faces.
Note
Time complexity is O(1) if update_arc2index is false, otherwise it is O(log n) is n is the number of arcs.

Definition at line 727 of file HalfEdgeDataStructure.h.

728  {
729  Index new_hei = myHalfEdges.size();
730  VertexIndex new_vtxi = myVertexHalfEdges.size();
731  EdgeIndex new_edgei = myEdgeHalfEdges.size();
732  FaceIndex new_facei = myFaceHalfEdges.size();
733  myHalfEdges.resize( new_hei + 6 );
734  myVertexHalfEdges.push_back( new_hei );
735  HalfEdge& hei = myHalfEdges[ i ];
736  HalfEdge& hei_next = myHalfEdges[ hei.next ];
737  Index j = hei.opposite;
738  HalfEdge& hej = myHalfEdges[ j ];
739  HalfEdge& hej_next = myHalfEdges[ hej.next ];
740  HalfEdge& he0 = myHalfEdges[ new_hei ];
741  HalfEdge& he1 = myHalfEdges[ new_hei + 1 ];
742  HalfEdge& he2 = myHalfEdges[ new_hei + 2 ];
743  HalfEdge& he3 = myHalfEdges[ new_hei + 3 ];
744  HalfEdge& he4 = myHalfEdges[ new_hei + 4 ];
745  HalfEdge& he5 = myHalfEdges[ new_hei + 5 ];
746  // HalfEdge = { toVertex, face, edge, opposite, next }
747  // Taking care of new half-edges
748  he0.toVertex = hei_next.toVertex;
749  he0.face = hei.face;
750  he0.edge = new_edgei;
751  he0.opposite = new_hei + 1;
752  he0.next = hei_next.next;
753  he1.toVertex = new_vtxi;
754  he1.face = new_facei;
755  he1.edge = new_edgei;
756  he1.opposite = new_hei;
757  he1.next = new_hei + 2;
758  he2.toVertex = hei.toVertex;
759  he2.face = new_facei;
760  he2.edge = new_edgei + 1;
761  he2.opposite = j;
762  he2.next = hei.next;
763  he3.toVertex = hej_next.toVertex;
764  he3.face = hej.face;
765  he3.edge = new_edgei + 2;
766  he3.opposite = new_hei + 4;
767  he3.next = hej_next.next;
768  he4.toVertex = new_vtxi;
769  he4.face = new_facei + 1;
770  he4.edge = new_edgei + 2;
771  he4.opposite = new_hei + 3;
772  he4.next = new_hei + 5;
773  he5.toVertex = hej.toVertex;
774  he5.face = new_facei + 1;
775  he5.edge = hei.edge;
776  he5.opposite = i;
777  he5.next = hej.next;
778  // Updating existing half-edges
779  hei.toVertex = new_vtxi;
780  hei.opposite = new_hei + 5;
781  hei.next = new_hei;
782  hej.toVertex = new_vtxi;
783  hej.edge = new_edgei + 1;
784  hej.opposite = new_hei + 2;
785  hej.next = new_hei + 3;
786  hei_next.face = new_facei;
787  hei_next.next = new_hei + 1;
788  hej_next.face = new_facei + 1;
789  hej_next.next = new_hei + 4;
790  // Updating other arrays
791  myEdgeHalfEdges.push_back( new_hei );
792  myEdgeHalfEdges.push_back( j );
793  myEdgeHalfEdges.push_back( new_hei + 3 );
794  myFaceHalfEdges.push_back( new_hei + 1 );
795  myFaceHalfEdges.push_back( new_hei + 4 );
796  myFaceHalfEdges[ hei.face ] = i;
797  myFaceHalfEdges[ hej.face ] = j;
798  myEdgeHalfEdges[ hei.edge ] = i;
799  if ( update_arc2index )
800  {
801  const VertexIndex vi = he5.toVertex;
802  const VertexIndex vk = hei_next.toVertex;
803  const VertexIndex vj = he2.toVertex;
804  const VertexIndex vl = hej_next.toVertex;
805  myArc2Index.erase( Arc( vi, vj ) );
806  myArc2Index.erase( Arc( vj, vi ) );
807  myArc2Index[ Arc( vi, new_vtxi ) ] = i;
808  myArc2Index[ Arc( new_vtxi, vi ) ] = new_hei + 5;
809  myArc2Index[ Arc( vj, new_vtxi ) ] = j;
810  myArc2Index[ Arc( new_vtxi, vj ) ] = new_hei + 2;
811  myArc2Index[ Arc( vk, new_vtxi ) ] = new_hei + 1;
812  myArc2Index[ Arc( new_vtxi, vk ) ] = new_hei;
813  myArc2Index[ Arc( vl, new_vtxi ) ] = new_hei + 4;
814  myArc2Index[ Arc( new_vtxi, vl ) ] = new_hei + 3;
815  }
816  return new_vtxi;
817  }

References DGtal::HalfEdgeDataStructure::HalfEdge::edge, DGtal::HalfEdgeDataStructure::HalfEdge::face, myArc2Index, myEdgeHalfEdges, myFaceHalfEdges, myHalfEdges, myVertexHalfEdges, DGtal::HalfEdgeDataStructure::HalfEdge::next, DGtal::HalfEdgeDataStructure::HalfEdge::opposite, and DGtal::HalfEdgeDataStructure::HalfEdge::toVertex.

Referenced by SCENARIO().

◆ verticesOfFace()

VertexIndexRange DGtal::HalfEdgeDataStructure::verticesOfFace ( const FaceIndex  f) const
inline
Parameters
fany valid face index.
Returns
the sequence of vertices of the face f.

Definition at line 602 of file HalfEdgeDataStructure.h.

603  {
604  VertexIndexRange result;
605  result.reserve( 3 );
606  Index hei = halfEdgeIndexFromFaceIndex( f );
607  const Index start = hei;
608  do {
609  const HalfEdge& he = halfEdge( hei );
610  result.push_back( he.toVertex );
611  hei = he.next;
612  }
613  while ( hei != start );
614  return result;
615  }

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

Field Documentation

◆ myArc2Index

Arc2Index DGtal::HalfEdgeDataStructure::myArc2Index
protected

The mapping between arcs to their half-edge index.

Definition at line 1393 of file HalfEdgeDataStructure.h.

Referenced by clear(), flip(), halfEdgeIndexFromArc(), isValid(), merge(), renumberHalfEdge(), renumberVertex(), and split().

◆ 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 1391 of file HalfEdgeDataStructure.h.

Referenced by clear(), halfEdgeIndexFromEdgeIndex(), isValid(), merge(), nbEdges(), renumberEdge(), renumberHalfEdge(), and split().

◆ 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 1387 of file HalfEdgeDataStructure.h.

Referenced by clear(), flip(), halfEdgeIndexFromFaceIndex(), isValid(), isValidTriangulation(), nbFaces(), renumberFace(), renumberHalfEdge(), and split().

◆ myHalfEdges

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

Stores all the half-edges.

Definition at line 1379 of file HalfEdgeDataStructure.h.

Referenced by arcFromHalfEdgeIndex(), boundaryArcs(), boundaryHalfEdgeIndices(), boundaryVertices(), clear(), findHalfEdgeIndexFromArc(), flip(), halfEdge(), isValid(), merge(), nbHalfEdges(), renumberEdge(), renumberFace(), renumberHalfEdge(), renumberVertex(), and split().

◆ 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 1383 of file HalfEdgeDataStructure.h.

Referenced by clear(), flip(), halfEdgeIndexFromVertexIndex(), isValid(), isVertexBoundary(), merge(), nbVertices(), renumberHalfEdge(), renumberVertex(), and split().

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