DGtal 1.4.2
Loading...
Searching...
No Matches
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.
 
typedef std::size_t Index
 The type used for numbering half-edges (an offset an the half-edges structure).
 
typedef Index HalfEdgeIndex
 The type used for numbering half-edges (alias)
 
typedef Index VertexIndex
 The type for numbering vertices.
 
typedef Index EdgeIndex
 The type for numbering edges.
 
typedef Index FaceIndex
 The type for numbering faces.
 
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.
 
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.
 
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.
 
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.
 
std::vector< Index > myVertexHalfEdges
 
std::vector< Index > myFaceHalfEdges
 
std::vector< Index > myEdgeHalfEdges
 
Arc2Index myArc2Index
 The mapping between arcs to their half-edge index.
 

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

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

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

Definition at line 122 of file HalfEdgeDataStructure.h.

◆ Arc2Index

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

Definition at line 119 of file HalfEdgeDataStructure.h.

◆ EdgeIndex

Index DGtal::HalfEdgeDataStructure::EdgeIndex

The type for numbering edges.

Definition at line 95 of file HalfEdgeDataStructure.h.

◆ EdgeIndexRange

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

Definition at line 112 of file HalfEdgeDataStructure.h.

◆ FaceIndex

Index DGtal::HalfEdgeDataStructure::FaceIndex

The type for numbering faces.

Definition at line 97 of file HalfEdgeDataStructure.h.

◆ FaceIndexRange

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

Definition at line 113 of file HalfEdgeDataStructure.h.

◆ HalfEdgeIndex

Index DGtal::HalfEdgeDataStructure::HalfEdgeIndex

The type used for numbering half-edges (alias)

Definition at line 91 of file HalfEdgeDataStructure.h.

◆ HalfEdgeIndexRange

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

Definition at line 110 of file HalfEdgeDataStructure.h.

◆ Index

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

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

std::size_t DGtal::HalfEdgeDataStructure::Size

The type for counting elements.

Definition at line 87 of file HalfEdgeDataStructure.h.

◆ VertexIndex

Index DGtal::HalfEdgeDataStructure::VertexIndex

The type for numbering vertices.

Definition at line 93 of file HalfEdgeDataStructure.h.

◆ VertexIndexRange

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

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::IndexedDigitalSurface< TDigitalSurfaceContainer >::Euler(), DGtal::PolygonalSurface< TPoint >::Euler(), and DGtal::TriangulatedSurface< TPoint >::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

References findHalfEdgeIndexFromArc().

Referenced by findHalfEdgeIndexFromArc(), isValid(), SCENARIO(), SCENARIO(), 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

References halfEdgeIndexFromArc().

Referenced by halfEdgeIndexFromArc(), and 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(), and 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::EdgeIndex
Index EdgeIndex
The type for numbering edges.
Definition HalfEdgeDataStructure.h:95
DGtal::HalfEdgeDataStructure::FaceIndex
Index FaceIndex
The type for numbering faces.
Definition HalfEdgeDataStructure.h:97
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(), SCENARIO(), SCENARIO(), and 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(), SCENARIO(), SCENARIO(), and 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::IndexedDigitalSurface< TDigitalSurfaceContainer >::nbEdges(), DGtal::PolygonalSurface< TPoint >::nbEdges(), DGtal::TriangulatedSurface< TPoint >::nbEdges(), renumberEdge(), SCENARIO(), SCENARIO(), SCENARIO(), 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::IndexedDigitalSurface< TDigitalSurfaceContainer >::nbFaces(), DGtal::PolygonalSurface< TPoint >::nbFaces(), DGtal::TriangulatedSurface< TPoint >::nbFaces(), renumberFace(), SCENARIO(), SCENARIO(), 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::IndexedDigitalSurface< TDigitalSurfaceContainer >::nbArcs(), DGtal::PolygonalSurface< TPoint >::nbArcs(), DGtal::TriangulatedSurface< TPoint >::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::IndexedDigitalSurface< TDigitalSurfaceContainer >::nbVertices(), DGtal::PolygonalSurface< TPoint >::nbVertices(), DGtal::TriangulatedSurface< TPoint >::nbVertices(), renumberVertex(), SCENARIO(), SCENARIO(), 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(), SCENARIO(), SCENARIO(), 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: