Data structure representing a 2D constrained Delaunay triangulation. More...

#include <Triangulation.h>

Collaboration diagram for CDT::Triangulation< T, TNearPointLocator >:

[legend]

Public Types
typedef std::vector< V2d< T > >	V2dVec
	Vertices vector. More...

Public Member Functions
	Triangulation ()
	Default constructor. More...

	Triangulation (VertexInsertionOrder::Enum vertexInsertionOrder)
	Constructor. More...

	Triangulation (VertexInsertionOrder::Enum vertexInsertionOrder, IntersectingConstraintEdges::Enum intersectingEdgesStrategy, T minDistToConstraintEdge)
	Constructor. More...

	Triangulation (VertexInsertionOrder::Enum vertexInsertionOrder, const TNearPointLocator &nearPtLocator, IntersectingConstraintEdges::Enum intersectingEdgesStrategy, T minDistToConstraintEdge)
	Constructor. More...

template<typename TVertexIter , typename TGetVertexCoordX , typename TGetVertexCoordY >
void	insertVertices (TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
	Insert custom point-types specified by iterator range and X/Y-getters. More...

void	insertVertices (const std::vector< V2d< T > > &vertices)
	Insert vertices into triangulation. More...

template<typename TEdgeIter , typename TGetEdgeVertexStart , typename TGetEdgeVertexEnd >
void	insertEdges (TEdgeIter first, TEdgeIter last, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd)
	Insert constraints (custom-type fixed edges) into triangulation. More...

void	insertEdges (const std::vector< Edge > &edges)
	Insert constraint edges into triangulation. More...

template<typename TEdgeIter , typename TGetEdgeVertexStart , typename TGetEdgeVertexEnd >
void	conformToEdges (TEdgeIter first, TEdgeIter last, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd)
	Ensure that triangulation conforms to constraints (fixed edges) More...

void	conformToEdges (const std::vector< Edge > &edges)
	Ensure that triangulation conforms to constraints (fixed edges) More...

void	eraseSuperTriangle ()
	Erase triangles adjacent to super triangle. More...

void	eraseOuterTriangles ()
	Erase triangles outside of constrained boundary using growing. More...

void	eraseOuterTrianglesAndHoles ()
	Erase triangles outside of constrained boundary and auto-detected holes. More...

void	initializedWithCustomSuperGeometry ()
	Call this method after directly setting custom super-geometry via vertices and triangles members. More...

bool	isFinalized () const
	Check if the triangulation was finalized with `erase...` method and super-triangle was removed. More...

std::vector< LayerDepth >	calculateTriangleDepths () const
	Calculate depth of each triangle in constraint triangulation. More...

void	flipEdge (TriInd iT, TriInd iTopo)
	Flip an edge between two triangle. More...

void	flipEdge (TriInd iT, TriInd iTopo, VertInd v1, VertInd v2, VertInd v3, VertInd v4, TriInd n1, TriInd n2, TriInd n3, TriInd n4)

void	removeTriangles (const TriIndUSet &removedTriangles)
	Remove triangles with specified indices. More...

TriIndVec &	VertTrisInternal ()
	Access internal vertex adjacent triangles. More...

Public Attributes
V2dVec	vertices
	triangulation's vertices More...

TriangleVec	triangles
	triangulation's triangles More...

EdgeUSet	fixedEdges
	triangulation's constraints (fixed edges) More...

unordered_map< Edge, BoundaryOverlapCount >	overlapCount
	Stores count of overlapping boundaries for a fixed edge. More...

unordered_map< Edge, EdgeVec >	pieceToOriginals
	Stores list of original edges represented by a given fixed edge. More...

Detailed Description

template<typename T, typename TNearPointLocator = LocatorKDTree<T>>
class CDT::Triangulation< T, TNearPointLocator >

Data structure representing a 2D constrained Delaunay triangulation.

Template Parameters

T	type of vertex coordinates (e.g., float, double)
TNearPointLocator	class providing locating near point for efficiently inserting new points. Provides methods: 'addPoint(vPos, iV)' and 'nearPoint(vPos) -> iV'

Definition at line 109 of file Triangulation.h.

Member Typedef Documentation

◆ V2dVec

template<typename T , typename TNearPointLocator = LocatorKDTree<T>>

typedef std::vector<V2d<T> > CDT::Triangulation< T, TNearPointLocator >::V2dVec

Vertices vector.

Definition at line 112 of file Triangulation.h.

Constructor & Destructor Documentation

◆ Triangulation() [1/4]

template<typename T , typename TNearPointLocator >

CDT::Triangulation< T, TNearPointLocator >::Triangulation

Default constructor.

Definition at line 51 of file Triangulation.hpp.

◆ Triangulation() [2/4]

template<typename T , typename TNearPointLocator >

CDT::Triangulation< T, TNearPointLocator >::Triangulation ( VertexInsertionOrder::Enum vertexInsertionOrder )

explicit

Constructor.

Parameters

vertexInsertionOrder strategy used for ordering vertex insertions

Definition at line 60 of file Triangulation.hpp.

◆ Triangulation() [3/4]

template<typename T , typename TNearPointLocator >

CDT::Triangulation< T, TNearPointLocator >::Triangulation	(	VertexInsertionOrder::Enum	vertexInsertionOrder,
		IntersectingConstraintEdges::Enum	intersectingEdgesStrategy,
		T	minDistToConstraintEdge
	)

Constructor.

Parameters

vertexInsertionOrder	strategy used for ordering vertex insertions
intersectingEdgesStrategy	strategy for treating intersecting constraint edges
minDistToConstraintEdge	distance within which point is considered to be lying on a constraint edge. Used when adding constraints to the triangulation.

Definition at line 70 of file Triangulation.hpp.

◆ Triangulation() [4/4]

template<typename T , typename TNearPointLocator >

CDT::Triangulation< T, TNearPointLocator >::Triangulation	(	VertexInsertionOrder::Enum	vertexInsertionOrder,
		const TNearPointLocator &	nearPtLocator,
		IntersectingConstraintEdges::Enum	intersectingEdgesStrategy,
		T	minDistToConstraintEdge
	)

Constructor.

Parameters

vertexInsertionOrder	strategy used for ordering vertex insertions
nearPtLocator	class providing locating near point for efficiently inserting new points
intersectingEdgesStrategy	strategy for treating intersecting constraint edges
minDistToConstraintEdge	distance within which point is considered to be lying on a constraint edge. Used when adding constraints to the triangulation.

Definition at line 82 of file Triangulation.hpp.

Member Function Documentation

◆ calculateTriangleDepths()

template<typename T , typename TNearPointLocator >

std::vector< LayerDepth > CDT::Triangulation< T, TNearPointLocator >::calculateTriangleDepths

Calculate depth of each triangle in constraint triangulation.

Supports overlapping boundaries.

Perform depth peeling from super triangle to outermost boundary, then to next boundary and so on until all triangles are traversed.
For example depth is:

0 for triangles outside outermost boundary
1 for triangles inside boundary but outside hole
2 for triangles in hole
3 for triangles in island and so on...
Returns
vector where element at index i stores depth of i-th triangle

Definition at line 1747 of file Triangulation.hpp.

◆ conformToEdges() [1/2]

template<typename T , typename TNearPointLocator >

void CDT::Triangulation< T, TNearPointLocator >::conformToEdges ( const std::vector< Edge > & edges )

Ensure that triangulation conforms to constraints (fixed edges)

Note: For each fixed edge that is not present in the triangulation its midpoint is recursively added until the original edge is represented by a sequence of its pieces. New vertices are inserted.; If some edge appears more than once the input this means that multiple boundaries overlap at the edge and impacts how hole detection algorithm of Triangulation::eraseOuterTrianglesAndHoles works. Make sure there are no erroneous duplicates.

Template Parameters

edges edges to conform to

Definition at line 360 of file Triangulation.hpp.

◆ conformToEdges() [2/2]

template<typename T , typename TNearPointLocator >

template<typename TEdgeIter , typename TGetEdgeVertexStart , typename TGetEdgeVertexEnd >

void CDT::Triangulation< T, TNearPointLocator >::conformToEdges	(	TEdgeIter	first,
		TEdgeIter	last,
		TGetEdgeVertexStart	getStart,
		TGetEdgeVertexEnd	getEnd
	)

Ensure that triangulation conforms to constraints (fixed edges)

Note: For each fixed edge that is not present in the triangulation its midpoint is recursively added until the original edge is represented by a sequence of its pieces. New vertices are inserted.; If some edge appears more than once the input this means that multiple boundaries overlap at the edge and impacts how hole detection algorithm of Triangulation::eraseOuterTrianglesAndHoles works. Make sure there are no erroneous duplicates.

Template Parameters

TEdgeIter	iterator that dereferences to custom edge type
TGetEdgeVertexStart	function object getting start vertex index from an edge. Getter signature: const TEdgeIter::value_type& -> CDT::VertInd
TGetEdgeVertexEnd	function object getting end vertex index from an edge. Getter signature: const TEdgeIter::value_type& -> CDT::VertInd

Parameters

first	beginning of the range of edges to add
last	end of the range of edges to add
getStart	getter of edge start vertex index
getEnd	getter of edge end vertex index

Definition at line 720 of file Triangulation.h.

◆ eraseOuterTriangles()

template<typename T , typename TNearPointLocator >

void CDT::Triangulation< T, TNearPointLocator >::eraseOuterTriangles

Erase triangles outside of constrained boundary using growing.

Definition at line 147 of file Triangulation.hpp.

◆ eraseOuterTrianglesAndHoles()

template<typename T , typename TNearPointLocator >

void CDT::Triangulation< T, TNearPointLocator >::eraseOuterTrianglesAndHoles

Erase triangles outside of constrained boundary and auto-detected holes.

Note: detecting holes relies on layer peeling based on layer depth; supports overlapping or touching boundaries

Definition at line 157 of file Triangulation.hpp.

◆ eraseSuperTriangle()

template<typename T , typename TNearPointLocator >

void CDT::Triangulation< T, TNearPointLocator >::eraseSuperTriangle

Erase triangles adjacent to super triangle.

Note: does nothing if custom geometry is used

Definition at line 131 of file Triangulation.hpp.

◆ initializedWithCustomSuperGeometry()

template<typename T , typename TNearPointLocator >

void CDT::Triangulation< T, TNearPointLocator >::initializedWithCustomSuperGeometry

Call this method after directly setting custom super-geometry via vertices and triangles members.

Definition at line 285 of file Triangulation.hpp.

◆ insertEdges() [1/2]

template<typename T , typename TNearPointLocator >

void CDT::Triangulation< T, TNearPointLocator >::insertEdges ( const std::vector< Edge > & edges )

Insert constraint edges into triangulation.

Note: Each fixed edge is inserted by deleting the triangles it crosses, followed by the triangulation of the polygons on each side of the edge. No new vertices are inserted.; If some edge appears more than once in the input this means that multiple boundaries overlap at the edge and impacts how hole detection algorithm of Triangulation::eraseOuterTrianglesAndHoles works. Make sure there are no erroneous duplicates.

Template Parameters

edges constraint edges

Definition at line 353 of file Triangulation.hpp.

◆ insertEdges() [2/2]

template<typename T , typename TNearPointLocator >

template<typename TEdgeIter , typename TGetEdgeVertexStart , typename TGetEdgeVertexEnd >

void CDT::Triangulation< T, TNearPointLocator >::insertEdges	(	TEdgeIter	first,
		TEdgeIter	last,
		TGetEdgeVertexStart	getStart,
		TGetEdgeVertexEnd	getEnd
	)

Insert constraints (custom-type fixed edges) into triangulation.

Note: Each fixed edge is inserted by deleting the triangles it crosses, followed by the triangulation of the polygons on each side of the edge. No new vertices are inserted.; If some edge appears more than once in the input this means that multiple boundaries overlap at the edge and impacts how hole detection algorithm of Triangulation::eraseOuterTrianglesAndHoles works. Make sure there are no erroneous duplicates.

Template Parameters

TEdgeIter	iterator that dereferences to custom edge type
TGetEdgeVertexStart	function object getting start vertex index from an edge. Getter signature: const TEdgeIter::value_type& -> CDT::VertInd
TGetEdgeVertexEnd	function object getting end vertex index from an edge. Getter signature: const TEdgeIter::value_type& -> CDT::VertInd

Parameters

first	beginning of the range of edges to add
last	end of the range of edges to add
getStart	getter of edge start vertex index
getEnd	getter of edge end vertex index

Definition at line 689 of file Triangulation.h.

◆ insertVertices() [1/2]

template<typename T , typename TNearPointLocator >

void CDT::Triangulation< T, TNearPointLocator >::insertVertices ( const std::vector< V2d< T > > & vertices )

Insert vertices into triangulation.

Parameters

vertices vector of vertices to insert

Definition at line 1695 of file Triangulation.hpp.

◆ insertVertices() [2/2]

template<typename T , typename TNearPointLocator >

template<typename TVertexIter , typename TGetVertexCoordX , typename TGetVertexCoordY >

void CDT::Triangulation< T, TNearPointLocator >::insertVertices	(	TVertexIter	first,
		TVertexIter	last,
		TGetVertexCoordX	getX,
		TGetVertexCoordY	getY
	)

Insert custom point-types specified by iterator range and X/Y-getters.

Template Parameters

TVertexIter	iterator that dereferences to custom point type
TGetVertexCoordX	function object getting x coordinate from vertex. Getter signature: const TVertexIter::value_type& -> T
TGetVertexCoordY	function object getting y coordinate from vertex. Getter signature: const TVertexIter::value_type& -> T

Parameters

first	beginning of the range of vertices to add
last	end of the range of vertices to add
getX	getter of X-coordinate
getY	getter of Y-coordinate

Definition at line 641 of file Triangulation.h.

◆ isFinalized()

template<typename T , typename TNearPointLocator >

bool CDT::Triangulation< T, TNearPointLocator >::isFinalized

Check if the triangulation was finalized with erase... method and super-triangle was removed.

Returns: true if triangulation is finalized, false otherwise

Definition at line 1703 of file Triangulation.hpp.

Member Data Documentation

◆ fixedEdges

template<typename T , typename TNearPointLocator = LocatorKDTree<T>>

EdgeUSet CDT::Triangulation< T, TNearPointLocator >::fixedEdges

triangulation's constraints (fixed edges)

Definition at line 115 of file Triangulation.h.

◆ overlapCount

template<typename T , typename TNearPointLocator = LocatorKDTree<T>>

unordered_map<Edge, BoundaryOverlapCount> CDT::Triangulation< T, TNearPointLocator >::overlapCount

Stores count of overlapping boundaries for a fixed edge.

If no entry is present for an edge: no boundaries overlap.

Note: map only has entries for fixed for edges that represent overlapping boundaries; needed for handling depth calculations and hole-removel in case of overlapping boundaries

Definition at line 124 of file Triangulation.h.

◆ pieceToOriginals

template<typename T , typename TNearPointLocator = LocatorKDTree<T>>

unordered_map<Edge, EdgeVec> CDT::Triangulation< T, TNearPointLocator >::pieceToOriginals

Stores list of original edges represented by a given fixed edge.

Note: map only has entries for edges where multiple original fixed edges overlap or where a fixed edge is a part of original edge created by conforming Delaunay triangulation vertex insertion

Definition at line 131 of file Triangulation.h.

◆ triangles

template<typename T , typename TNearPointLocator = LocatorKDTree<T>>

TriangleVec CDT::Triangulation< T, TNearPointLocator >::triangles

triangulation's triangles

Definition at line 114 of file Triangulation.h.

◆ vertices

template<typename T , typename TNearPointLocator = LocatorKDTree<T>>

V2dVec CDT::Triangulation< T, TNearPointLocator >::vertices

triangulation's vertices

Definition at line 113 of file Triangulation.h.

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

include/Triangulation.h
include/Triangulation.hpp

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

◆ V2dVec

Constructor & Destructor Documentation

◆ Triangulation() [1/4]

◆ Triangulation() [2/4]

◆ Triangulation() [3/4]

◆ Triangulation() [4/4]

Member Function Documentation

◆ calculateTriangleDepths()

◆ conformToEdges() [1/2]

◆ conformToEdges() [2/2]

◆ eraseOuterTriangles()

◆ eraseOuterTrianglesAndHoles()

◆ eraseSuperTriangle()

◆ initializedWithCustomSuperGeometry()

◆ insertEdges() [1/2]

◆ insertEdges() [2/2]

◆ insertVertices() [1/2]

◆ insertVertices() [2/2]

◆ isFinalized()

Member Data Documentation

◆ fixedEdges

◆ overlapCount

◆ pieceToOriginals

◆ triangles

◆ vertices