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

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.

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

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 404 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 407 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 43 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 1828 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

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

Definition at line 1113 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 115 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 124 of file Triangulation.hpp.

◆ eraseSuperTriangle()

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

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

Erase triangles adjacent to super triangle.

Note: does nothing if custom geometry is used

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

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

Definition at line 1081 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 1776 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 995 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 1784 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 1860 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 410 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 419 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 426 of file Triangulation.h.

◆ triangles

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

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

triangulation's triangles

Definition at line 409 of file Triangulation.h.

◆ vertices

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

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

triangulation's vertices

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

◆ setCallbackHandler()

Member Data Documentation

◆ fixedEdges

◆ overlapCount

◆ pieceToOriginals

◆ triangles

◆ vertices