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

#include <Triangulation.h>

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

Public Member Functions
	Triangulation ()
	Default constructor.

	Triangulation (VertexInsertionOrder::Enum vertexInsertionOrder)
	Constructor.

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

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

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.

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

template<typename TEdgeIter, typename TGetEdgeVertexStart, typename TGetEdgeVertexEnd>
void	insertEdges (TEdgeIter first, TEdgeIter last, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd)
	Insert constraint edges into triangulation for Constrained Delaunay Triangulation (for example see figure below).

void	insertEdges (const std::vector< Edge > &edges)
	Insert constraint edges into triangulation for Constrained Delaunay Triangulation (for example see figure below).

template<typename TEdgeIter, typename TGetEdgeVertexStart, typename TGetEdgeVertexEnd>
void	conformToEdges (TEdgeIter first, TEdgeIter last, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd)
	Insert constraint edges into triangulation for Conforming Delaunay Triangulation (for example see figure below).

void	conformToEdges (const std::vector< Edge > &edges)
	Insert constraint edges into triangulation for Conforming Delaunay Triangulation (for example see figure below).

Unrefined	refineTriangles (VertInd maxVerticesToInsert, RefinementCriterion::Enum refinementCriterion=RefinementCriterion::SmallestAngle, T refinementThreshold=degToRad(T(20)), TriIndUSet *toEraseOrNull=NULL, T minEdgeLength=T(1e-6))
	Triangles refinement by splitting bad triangles.

EdgeVec	findEncroachedFixedEdges () const
	Find all fixed edges encroached by their opposed vertices.

TriIndVec	findUnrefinedTriangles (RefinementCriterion::Enum refinementCriterion=RefinementCriterion::SmallestAngle, T refinementThreshold=degToRad(T(20))) const
	Find triangles that don't fulfill the refinement criterion.

void	eraseSuperTriangle ()
	Erase triangles adjacent to super triangle.

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

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

TriIndUSet	collectSuperTriangle () const
	Collect triangles adjacent to super-triangle: same triangles that eraseSuperTriangle would remove.

TriIndUSet	collectOuterTriangles () const
	Collect triangles outside of constrained boundary: same triangles that eraseOuterTriangles would remove.

TriIndUSet	collectOuterTrianglesAndHoles () const
	Collect triangles outside of constrained boundary and auto-detected holes: same triangles that eraseOuterTrianglesAndHoles would remove.

void	finalizeTriangulation (const TriIndUSet &removedTriangles)
	Remove super-triangle and triangles with specified indices.

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

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

void	setCallbackHandler (ICallbackHandler *callbackHandler)
	Set user-provided callback handler.

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

void	flipEdge (TriInd iT, TriInd iTopo, VertInd v1, VertInd v2, VertInd v3, VertInd v4, TriInd n1, TriInd n2, TriInd n3, TriInd n4)
	Flip edge between two triangles given all the information such as triangle vertices and neighbors.

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

TriIndVec &	VertTrisInternal ()
	Access internal vertex adjacent triangles.

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

Public Attributes
V2dVec	vertices
	triangulation's vertices

TriangleVec	triangles
	triangulation's triangles

EdgeUSet	fixedEdges
	triangulation's constraints (fixed edges)

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

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

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 524 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 527 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 68 of file Triangulation.hpp.

◆ Triangulation() [2/4]

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

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

explicit

Constructor.

Parameters

vertexInsertionOrder strategy used for ordering vertex insertions

◆ Triangulation() [3/4]

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

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.

◆ Triangulation() [4/4]

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

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.

Member Function Documentation

◆ calculateTriangleDepths()

template<typename T, typename TNearPointLocator>

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

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 2236 of file Triangulation.hpp.

◆ collectOuterTriangles()

template<typename T, typename TNearPointLocator>

TriIndUSet CDT::Triangulation< T, TNearPointLocator >::collectOuterTriangles ( ) const

Collect triangles outside of constrained boundary: same triangles that eraseOuterTriangles would remove.

Exceptions

FinalizedError if triangulation was already finalized

Definition at line 151 of file Triangulation.hpp.

◆ collectOuterTrianglesAndHoles()

template<typename T, typename TNearPointLocator>

TriIndUSet CDT::Triangulation< T, TNearPointLocator >::collectOuterTrianglesAndHoles ( ) const

Collect triangles outside of constrained boundary and auto-detected holes: same triangles that eraseOuterTrianglesAndHoles would remove.

Exceptions

FinalizedError if triangulation was already finalized

Definition at line 163 of file Triangulation.hpp.

◆ collectSuperTriangle()

template<typename T, typename TNearPointLocator>

TriIndUSet CDT::Triangulation< T, TNearPointLocator >::collectSuperTriangle ( ) const

Collect triangles adjacent to super-triangle: same triangles that eraseSuperTriangle would remove.

Exceptions

FinalizedError if triangulation was already finalized

Definition at line 135 of file Triangulation.hpp.

◆ conformToEdges() [1/2]

template<typename T, typename TNearPointLocator>

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

Insert constraint edges into triangulation for Conforming Delaunay Triangulation (for example see figure below).

May add new vertices.

CDT show-case: constrained and
conforming triangulations, convex hulls, automatically removing holes

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

Exceptions

FinalizedError	if triangulation was already finalized
IntersectingConstraintsError	if edges intersect and intersecting constraint edges are not allowed
InvalidEdgeSplitVertex	if an edges intersection position breaks triangulation topology due to floating-point rounding

Definition at line 352 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 )

Insert constraint edges into triangulation for Conforming Delaunay Triangulation (for example see figure below).

May add new vertices.

CDT show-case: constrained and
conforming triangulations, convex hulls, automatically removing holes

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

Exceptions

FinalizedError	if triangulation was already finalized
IntersectingConstraintsError	if edges intersect and intersecting constraint edges are not allowed
InvalidEdgeSplitVertex	if an edges intersection position breaks triangulation topology due to floating-point rounding

Definition at line 1414 of file Triangulation.h.

◆ eraseOuterTriangles()

template<typename T, typename TNearPointLocator>

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

Erase triangles outside of constrained boundary using growing.

Exceptions

FinalizedError if triangulation was already finalized

Definition at line 123 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

Exceptions

FinalizedError if triangulation was already finalized

Definition at line 129 of file Triangulation.hpp.

◆ eraseSuperTriangle()

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

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

Erase triangles adjacent to super triangle.

Exceptions

FinalizedError if triangulation was already finalized

◆ finalizeTriangulation()

template<typename T, typename TNearPointLocator>

void CDT::Triangulation< T, TNearPointLocator >::finalizeTriangulation ( const TriIndUSet & removedTriangles )

Remove super-triangle and triangles with specified indices.

Adjust internal triangulation state accordingly.

Parameters

removedTriangles indices of triangles to remove

Note: pair with one of the collectXXX methods to combine erasing with refineTriangles; invalidates caller-held vertex indices and edges

Exceptions

FinalizedError if triangulation was already finalized

Definition at line 236 of file Triangulation.hpp.

◆ findEncroachedFixedEdges()

template<typename T, typename TNearPointLocator>

EdgeVec CDT::Triangulation< T, TNearPointLocator >::findEncroachedFixedEdges ( ) const

Find all fixed edges encroached by their opposed vertices.

Returns: encroached fixed edges, sorted for deterministic order

Note: can be used to scan the triangulation for the problems that refineTriangles was not able to resolve

Exceptions

FinalizedError if triangulation was already finalized: finalizing discards the vertex adjacency this relies on

Definition at line 1525 of file Triangulation.hpp.

◆ findUnrefinedTriangles()

template<typename T, typename TNearPointLocator>

TriIndVec CDT::Triangulation< T, TNearPointLocator >::findUnrefinedTriangles	(	RefinementCriterion::Enum	refinementCriterion = RefinementCriterion::SmallestAngle,
		T	refinementThreshold = degToRad(T(20)) ) const

Find triangles that don't fulfill the refinement criterion.

Parameters

refinementCriterion	refinement strategy that is used to identify bad triangles
refinementThreshold	threshold value for refinement

Returns: indices of the triangles that are still bad

Note: triangles whose smallest angle is enclosed by two fixed edges are reported as well: such an angle comes from the input and can not be refined (see Unrefined::sharpFixedCorner); can be used to scan the triangulation for the problems that refineTriangles was not able to resolve

Definition at line 1548 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 for Constrained Delaunay Triangulation (for example see figure below).

Uses only original vertices: no new verties are added

CDT show-case: constrained and
conforming triangulations, convex hulls, automatically removing holes

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

Exceptions

FinalizedError	if triangulation was already finalized
IntersectingConstraintsError	if edges intersect and intersecting constraint edges are not allowed
InvalidEdgeSplitVertex	if an edges intersection position breaks triangulation topology due to floating-point rounding

Definition at line 345 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 constraint edges into triangulation for Constrained Delaunay Triangulation (for example see figure below).

Uses only original vertices: no new verties are added

CDT show-case: constrained and
conforming triangulations, convex hulls, automatically removing holes

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

Exceptions

FinalizedError	if triangulation was already finalized
IntersectingConstraintsError	if edges intersect and intersecting constraint edges are not allowed
InvalidEdgeSplitVertex	if an edges intersection position breaks triangulation topology due to floating-point rounding

Definition at line 1382 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

Exceptions

FinalizedError	if triangulation was already finalized
DuplicateVertexError	if an inserted vertex is a duplicate

Definition at line 2184 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

Exceptions

FinalizedError	if triangulation was already finalized
DuplicateVertexError	if an inserted vertex is a duplicate

Definition at line 1296 of file Triangulation.h.

◆ isFinalized()

template<typename T, typename TNearPointLocator>

bool CDT::Triangulation< T, TNearPointLocator >::isFinalized ( ) const

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 2192 of file Triangulation.hpp.

◆ refineTriangles()

template<typename T, typename TNearPointLocator>

Unrefined CDT::Triangulation< T, TNearPointLocator >::refineTriangles	(	VertInd	maxVerticesToInsert,
		RefinementCriterion::Enum	refinementCriterion = RefinementCriterion::SmallestAngle,
		T	refinementThreshold = degToRad(T(20)),
		TriIndUSet *	toEraseOrNull = NULL,
		T	minEdgeLength = T(1e-6) )

Triangles refinement by splitting bad triangles.

Note: bad triangles don't fulfill constraints defined by the user

Parameters

maxVerticesToInsert	budget of Steiner vertices to insert
refinementCriterion	refinement strategy that is used to identify bad triangles
refinementThreshold	threshold value for refinement
toEraseOrNull	if not null, triangles in this set are skipped as refinement candidates and triangles replacing them are added to it. Must come from a `collectXXX` method; caller then passes it to finalizeTriangulation.
minEdgeLength	don't split edges/triangles already this short: acute corners and close fixed edges can otherwise force ever-shrinking splits. 0 never gives up.

Returns: refinements that could not be performed

Exceptions

FinalizedError if triangulation was already finalized

Definition at line 2609 of file Triangulation.hpp.

◆ setCallbackHandler()

template<typename T, typename TNearPointLocator>

void CDT::Triangulation< T, TNearPointLocator >::setCallbackHandler ( ICallbackHandler * callbackHandler )

Set user-provided callback handler.

Warning: callback handler must outlive the triangulation class; triangulatio does not own the callback and does not try to free it

Parameters

callbackHandler pointer to the callback handler

Definition at line 2268 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 530 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 539 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 546 of file Triangulation.h.

◆ triangles

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

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

triangulation's triangles

Definition at line 529 of file Triangulation.h.

◆ vertices

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

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

triangulation's vertices

Definition at line 528 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()

◆ collectOuterTriangles()

◆ collectOuterTrianglesAndHoles()

◆ collectSuperTriangle()

◆ conformToEdges() [1/2]

◆ conformToEdges() [2/2]

◆ eraseOuterTriangles()

◆ eraseOuterTrianglesAndHoles()

◆ eraseSuperTriangle()

◆ finalizeTriangulation()

◆ findEncroachedFixedEdges()

◆ findUnrefinedTriangles()

◆ insertEdges() [1/2]

◆ insertEdges() [2/2]

◆ insertVertices() [1/2]

◆ insertVertices() [2/2]

◆ isFinalized()

◆ refineTriangles()

◆ setCallbackHandler()

Member Data Documentation

◆ fixedEdges

◆ overlapCount

◆ pieceToOriginals

◆ triangles

◆ vertices