CDT::Triangulation< T, TNearPointLocator > Class Template Reference

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

#include <Triangulation.h>

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

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	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)
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 258 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 261 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

(

)

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

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

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 916 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 146 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 156 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 291 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

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 359 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

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 889 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 1720 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 843 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 1728 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 264 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 273 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 280 of file Triangulation.h.

triangles

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

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

triangulation's triangles

Definition at line 263 of file Triangulation.h.

vertices

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

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

triangulation's vertices

Definition at line 262 of file Triangulation.h.

---

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

• include/Triangulation.h
• include/Triangulation.hpp