Namespace containing triangulation functionality. More...

Classes
struct	AddVertexType
	What type of vertex is added to the triangulation. More...

struct	Box2d
	2D bounding box More...

struct	DuplicatesInfo
	Information about removed duplicated vertices. More...

class	DuplicateVertexError
	Error thrown when duplicate vertex is detected during vertex insertion. More...

struct	Edge
	Edge connecting two vertices: vertex with smaller index is always first. More...

class	Error
	Base class for errors. More...

class	FinalizedError
	Error thrown when triangulation modification is attempted after it was finalized. More...

class	ICallbackHandler
	Interface for the callback handler that user can derive from and inject into the triangulation to monitor certain events or order aborting the calculation. More...

struct	IntersectingConstraintEdges
	Enum of strategies for treating intersecting constraint edges. More...

class	IntersectingConstraintsError
	Error thrown when intersecting constraint edges are detected, but triangulation is not configured to attempt to resolve them. More...

class	InvalidEdgeSplitVertex
	Error thrown when resolving intersecting constraints fails: floating-point rounding places the computed split vertex outside the edge's adjacent triangles, so it can not be inserted. More...

class	LocatorKDTree
	KD-tree holding points. More...

struct	PtLineLocation
	Relative location of point to a line. More...

struct	PtTriLocation
	Location of point on a triangle. More...

class	SourceLocation
	Contains source location info: file, function, line. More...

struct	SuperGeometryType
	Enum of what type of geometry used to embed triangulation into. More...

struct	Triangle
	Triangulation triangle (counter-clockwise winding) More...

struct	TriangleChangeType
	What type of triangle change happened. More...

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

struct	V2d
	2D vector More...

struct	VertexInsertionOrder
	Enum of strategies specifying order in which a range of vertices is inserted. More...

Typedefs
typedef unsigned short	LayerDepth
	Type used for storing layer depths for triangles.

typedef LayerDepth	BoundaryOverlapCount

typedef std::vector< TriIndVec >	VerticesTriangles
	Triangles by vertex index.

typedef unsigned long long	IndexSizeType

typedef unsigned char	Index
	Index in triangle.

typedef IndexSizeType	VertInd
	Vertex index.

typedef IndexSizeType	TriInd
	Triangle index.

typedef std::vector< TriInd >	TriIndVec
	Vector of triangle indices.

typedef array< VertInd, 3 >	VerticesArr3
	array of three vertex indices

typedef array< TriInd, 3 >	NeighborsArr3
	array of three neighbors

typedef std::vector< Edge >	EdgeVec
	Vector of edges.

typedef unordered_set< Edge >	EdgeUSet
	Hash table of edges.

typedef unordered_set< TriInd >	TriIndUSet
	Hash table of triangles.

typedef unordered_map< TriInd, TriInd >	TriIndUMap
	Triangle hash map.

typedef std::vector< Triangle >	TriangleVec
	Vector of triangles.

typedef std::deque< TriInd >	TriDeque

Functions
template<typename T, typename TNearPointLocator>
void	initializeWithRegularGrid (const T xmin, const T xmax, const T ymin, const T ymax, const std::size_t xres, const std::size_t yres, Triangulation< T, TNearPointLocator > &out)
	Make a triangulation that uses regular grid triangles instead of super-triangle.

template<typename T, typename TNearPointLocator, typename TXCoordIter, typename TYCoordIter>
void	initializeWithIrregularGrid (const TXCoordIter xfirst, const TXCoordIter xlast, const TYCoordIter yfirst, const TYCoordIter ylast, Triangulation< T, TNearPointLocator > &out)
	Make a triangulation that uses irregular grid triangles instead of super-triangle.

template<typename T, typename TNearPointLocator>
bool	verifyTopology (const CDT::Triangulation< T, TNearPointLocator > &cdt)
	Verify that triangulation topology is consistent.

template<typename T, typename TNearPointLocator>
bool	eachVertexHasNeighborTriangle (const CDT::Triangulation< T, TNearPointLocator > &cdt)
	Check that each vertex has a neighbor triangle.

CDT_EXPORT VerticesTriangles	calculateTrianglesByVertex (const TriangleVec &triangles, VertInd verticesSize)
	Calculate triangles adjacent to vertices (triangles by vertex index)

template<typename T, typename TVertexIter, typename TGetVertexCoordX, typename TGetVertexCoordY>
DuplicatesInfo	FindDuplicates (TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
	Find duplicates in given custom point-type range.

template<typename TVertex, typename TAllocator>
void	RemoveDuplicates (std::vector< TVertex, TAllocator > &vertices, const std::vector< std::size_t > &duplicates)
	Remove duplicates in-place from vector of custom points.

template<typename T>
CDT_EXPORT DuplicatesInfo	RemoveDuplicates (std::vector< V2d< T > > &vertices)
	Remove duplicated points in-place.

template<typename TEdgeIter, typename TGetEdgeVertexStart, typename TGetEdgeVertexEnd, typename TMakeEdgeFromStartAndEnd>
void	RemapEdges (TEdgeIter first, TEdgeIter last, const std::vector< std::size_t > &mapping, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd, TMakeEdgeFromStartAndEnd makeEdge)
	Remap vertex indices in edges (in-place) using given vertex-index mapping.

CDT_EXPORT void	RemapEdges (std::vector< Edge > &edges, const std::vector< std::size_t > &mapping)
	Remap vertex indices in edges (in-place) using given vertex-index mapping.

template<typename T, typename TVertex, typename TGetVertexCoordX, typename TGetVertexCoordY, typename TVertexAllocator, typename TEdgeIter, typename TGetEdgeVertexStart, typename TGetEdgeVertexEnd, typename TMakeEdgeFromStartAndEnd>
DuplicatesInfo	RemoveDuplicatesAndRemapEdges (std::vector< TVertex, TVertexAllocator > &vertices, TGetVertexCoordX getX, TGetVertexCoordY getY, TEdgeIter edgesFirst, TEdgeIter edgesLast, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd, TMakeEdgeFromStartAndEnd makeEdge)
	Find point duplicates, remove them from vector (in-place) and remap edges (in-place)

template<typename T>
CDT_EXPORT DuplicatesInfo	RemoveDuplicatesAndRemapEdges (std::vector< V2d< T > > &vertices, std::vector< Edge > &edges)
	Same as a chained call of CDT::RemoveDuplicates + CDT::RemapEdges.

CDT_EXPORT EdgeUSet	extractEdgesFromTriangles (const TriangleVec &triangles)
	Extract all edges of triangles.

CDT_EXPORT unordered_map< Edge, EdgeVec >	EdgeToPiecesMapping (const unordered_map< Edge, EdgeVec > &pieceToOriginals)

template<typename T>
unordered_map< Edge, std::vector< VertInd > >	EdgeToSplitVertices (const unordered_map< Edge, EdgeVec > &edgeToPieces, const std::vector< V2d< T > > &vertices)

template<typename T>
DuplicatesInfo	RemoveDuplicates (std::vector< V2d< T > > &vertices)
	Remove duplicated points in-place.

template<typename T>
DuplicatesInfo	RemoveDuplicatesAndRemapEdges (std::vector< V2d< T > > &vertices, std::vector< Edge > &edges)
	Same as a chained call of CDT::RemoveDuplicates + CDT::RemapEdges.

template<typename T>
std::string	to_string (const T &value)

template<typename T>
void	handleException (const T &error)

template<typename T>
array< T, 3 >	arr3 (const T &v0, const T &v1, const T &v2)
	Needed for c++03 compatibility (no uniform initialization available)

template<typename T>
array< T, 3 >	arr3 (const T &v)
	Needed for c++03 compatibility (no uniform initialization available)

template<typename T>
const T &	getX_V2d (const V2d< T > &v)
	X- coordinate getter for V2d.

template<typename T>
const T &	getY_V2d (const V2d< T > &v)
	Y-coordinate getter for V2d.

template<typename T>
bool	operator== (const CDT::V2d< T > &lhs, const CDT::V2d< T > &rhs)
	If two 2D vectors are exactly equal.

template<typename T>
bool	operator!= (const CDT::V2d< T > &lhs, const CDT::V2d< T > &rhs)
	If two 2D vectors are not exactly equal.

	BOOST_STRONG_TYPEDEF (unsigned char, Index)
	Index in triangle.

	BOOST_STRONG_TYPEDEF (IndexSizeType, VertInd)
	Vertex index.

VertInd	edge_get_v1 (const Edge &e)
	Get edge first vertex.

VertInd	edge_get_v2 (const Edge &e)
	Get edge second vertex.

Edge	edge_make (VertInd iV1, VertInd iV2)
	Get edge second vertex.

CDT_EXPORT Index	ccw (Index i)
	Advance vertex or neighbor index counter-clockwise.

CDT_EXPORT Index	cw (Index i)
	Advance vertex or neighbor index clockwise.

CDT_EXPORT bool	isOnEdge (PtTriLocation::Enum location)
	Check if location is classified as on any of three edges.

CDT_EXPORT Index	edgeNeighbor (PtTriLocation::Enum location)
	Neighbor index from a on-edge location.

template<typename T>
CDT_EXPORT T	orient2D (const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2)
	Orient p against line v1-v2 2D: robust geometric predicate.

template<typename T>
CDT_EXPORT PtLineLocation::Enum	locatePointLine (const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2, T orientationTolerance=T(0))
	Check if point lies to the left of, to the right of, or on a line.

template<typename T>
CDT_EXPORT PtLineLocation::Enum	classifyOrientation (T orientation, T orientationTolerance=T(0))
	Classify value of orient2d predicate.

template<typename T>
CDT_EXPORT PtTriLocation::Enum	locatePointTriangle (const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2, const V2d< T > &v3)
	Check if point a lies inside of, outside of, or on an edge of a triangle.

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index	opoNbr (Index vertIndex)
	Opposed neighbor index from vertex index.

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index	opoVrt (Index neighborIndex)
	Opposed vertex index from neighbor index.

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index	opposedTriangleInd (const VerticesArr3 &vv, VertInd iVert)
	Index of triangle's neighbor opposed to a vertex.

CDT_INLINE_IF_HEADER_ONLY Index	edgeNeighborInd (const VerticesArr3 &vv, VertInd iVedge1, VertInd iVedge2)
	Index of triangle's neighbor opposed to an edge.

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index	opposedVertexInd (const NeighborsArr3 &nn, TriInd iTopo)
	Index of triangle's vertex opposed to a triangle.

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY Index	vertexInd (const VerticesArr3 &vv, VertInd iV)
	If triangle has a given vertex return vertex-index.

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY TriInd	opposedTriangle (const Triangle &tri, VertInd iVert)
	Given triangle and a vertex find opposed triangle.

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY TriInd	edgeNeighbor (const Triangle &tri, VertInd iVedge1, VertInd iVedge2)
	Given triangle and an edge find neighbor sharing the edge.

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY VertInd	opposedVertex (const Triangle &tri, TriInd iTopo)
	Given two triangles, return vertex of first triangle opposed to the second.

template<typename T>
CDT_EXPORT bool	isInCircumcircle (const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2, const V2d< T > &v3)
	Test if point lies in a circumscribed circle of a triangle.

CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY bool	verticesShareEdge (const TriIndVec &aTris, const TriIndVec &bTris)
	Test if two vertices share at least one common triangle.

template<typename T>
CDT_EXPORT T	distance (const V2d< T > &a, const V2d< T > &b)
	Distance between two 2D points.

template<typename T>
CDT_EXPORT T	distanceSquared (const V2d< T > &a, const V2d< T > &b)
	Squared distance between two 2D points.

CDT_INLINE_IF_HEADER_ONLY bool	touchesSuperTriangle (const Triangle &t)
	Check if any of triangle's vertices belongs to a super-triangle.

template<typename T>
T	orient2D (const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2)
	Orient p against line v1-v2 2D: robust geometric predicate.

template<typename T>
PtLineLocation::Enum	locatePointLine (const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2, const T orientationTolerance)
	Check if point lies to the left of, to the right of, or on a line.

template<typename T>
PtLineLocation::Enum	classifyOrientation (const T orientation, const T orientationTolerance)
	Classify value of orient2d predicate.

template<typename T>
PtTriLocation::Enum	locatePointTriangle (const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2, const V2d< T > &v3)
	Check if point a lies inside of, outside of, or on an edge of a triangle.

template<typename T>
bool	isInCircumcircle (const V2d< T > &p, const V2d< T > &v1, const V2d< T > &v2, const V2d< T > &v3)
	Test if point lies in a circumscribed circle of a triangle.

template<typename T>
T	distanceSquared (const T ax, const T ay, const T bx, const T by)

template<typename T>
T	distance (const T ax, const T ay, const T bx, const T by)

template<typename T>
T	distance (const V2d< T > &a, const V2d< T > &b)
	Distance between two 2D points.

template<typename T>
T	distanceSquared (const V2d< T > &a, const V2d< T > &b)
	Squared distance between two 2D points.

Edge	RemapNoSuperTriangle (const Edge &e)
	Remap removing super-triangle: subtract 3 from vertices.

template CDT_EXPORT DuplicatesInfo	RemoveDuplicates< float > (std::vector< V2d< float > > &)

template CDT_EXPORT DuplicatesInfo	RemoveDuplicates< double > (std::vector< V2d< double > > &)

template CDT_EXPORT DuplicatesInfo	RemoveDuplicatesAndRemapEdges< float > (std::vector< V2d< float > > &, std::vector< Edge > &)

template CDT_EXPORT DuplicatesInfo	RemoveDuplicatesAndRemapEdges< double > (std::vector< V2d< double > > &, std::vector< Edge > &)

template CDT_EXPORT bool	verifyTopology< float > (const CDT::Triangulation< float > &)

template CDT_EXPORT bool	verifyTopology< double > (const CDT::Triangulation< double > &)

template CDT_EXPORT void	initializeWithRegularGrid< float > (float, float, float, float, std::size_t, std::size_t, Triangulation< float > &)

template CDT_EXPORT void	initializeWithRegularGrid< double > (double, double, double, double, std::size_t, std::size_t, Triangulation< double > &)

template CDT_EXPORT float	distance (const V2d< float > &a, const V2d< float > &b)

template CDT_EXPORT double	distance (const V2d< double > &a, const V2d< double > &b)

template CDT_EXPORT float	distanceSquared (const V2d< float > &a, const V2d< float > &b)

template CDT_EXPORT double	distanceSquared (const V2d< double > &a, const V2d< double > &b)

Variables
template struct CDT_EXPORT	V2d< float >

template struct CDT_EXPORT	V2d< double >

template struct CDT_EXPORT	Box2d< float >

template struct CDT_EXPORT	Box2d< double >

template class CDT_EXPORT	Triangulation< float >

template class CDT_EXPORT	Triangulation< double >

Detailed Description

Namespace containing triangulation functionality.

Typedef Documentation

◆ EdgeUSet

typedef unordered_set<Edge> CDT::EdgeUSet

Hash table of edges.

Definition at line 347 of file CDTUtils.h.

◆ EdgeVec

typedef std::vector<Edge> CDT::EdgeVec

Vector of edges.

Definition at line 346 of file CDTUtils.h.

◆ Index

typedef unsigned char CDT::Index

Index in triangle.

Definition at line 205 of file CDTUtils.h.

◆ IndexSizeType

typedef unsigned int CDT::IndexSizeType

Definition at line 191 of file CDTUtils.h.

◆ NeighborsArr3

typedef array<TriInd, 3> CDT::NeighborsArr3

array of three neighbors

Definition at line 227 of file CDTUtils.h.

◆ TriangleVec

typedef std::vector<Triangle> CDT::TriangleVec

Vector of triangles.

Definition at line 411 of file CDTUtils.h.

◆ TriDeque

typedef std::deque<TriInd> CDT::TriDeque

Definition at line 24 of file Triangulation.hpp.

◆ TriInd

typedef IndexSizeType CDT::TriInd

Triangle index.

Definition at line 209 of file CDTUtils.h.

◆ TriIndUMap

typedef unordered_map<TriInd, TriInd> CDT::TriIndUMap

Triangle hash map.

Definition at line 349 of file CDTUtils.h.

◆ TriIndUSet

typedef unordered_set<TriInd> CDT::TriIndUSet

Hash table of triangles.

Definition at line 348 of file CDTUtils.h.

◆ TriIndVec

typedef std::vector<TriInd> CDT::TriIndVec

Vector of triangle indices.

Definition at line 225 of file CDTUtils.h.

◆ VerticesArr3

typedef array<VertInd, 3> CDT::VerticesArr3

array of three vertex indices

Definition at line 226 of file CDTUtils.h.

◆ VertInd

typedef IndexSizeType CDT::VertInd

Vertex index.

Definition at line 207 of file CDTUtils.h.

Function Documentation

◆ arr3() [1/2]

template<typename T>

array< T, 3 > CDT::arr3 ( const T & v )

Needed for c++03 compatibility (no uniform initialization available)

Definition at line 136 of file CDTUtils.h.

◆ arr3() [2/2]

template<typename T>

array< T, 3 > CDT::arr3	(	const T &	v0,
		const T &	v1,
		const T &	v2 )

Needed for c++03 compatibility (no uniform initialization available)

Definition at line 128 of file CDTUtils.h.

◆ BOOST_STRONG_TYPEDEF()

CDT::BOOST_STRONG_TYPEDEF	(	IndexSizeType	,
		VertInd	)

Vertex index.

Triangle index.

◆ ccw()

CDT_INLINE_IF_HEADER_ONLY Index CDT::ccw ( Index i )

Advance vertex or neighbor index counter-clockwise.

Definition at line 21 of file CDTUtils.hpp.

◆ classifyOrientation() [1/2]

template<typename T>

PtLineLocation::Enum CDT::classifyOrientation	(	const T	orientation,
		const T	orientationTolerance )

Classify value of orient2d predicate.

Definition at line 62 of file CDTUtils.hpp.

◆ classifyOrientation() [2/2]

template<typename T>

CDT_EXPORT PtLineLocation::Enum CDT::classifyOrientation	(	T	orientation,
		T	orientationTolerance = T(0) )

Classify value of orient2d predicate.

Definition at line 62 of file CDTUtils.hpp.

◆ cw()

CDT_INLINE_IF_HEADER_ONLY Index CDT::cw ( Index i )

Advance vertex or neighbor index clockwise.

Definition at line 26 of file CDTUtils.hpp.

◆ distance() [1/3]

template<typename T>

T CDT::distance	(	const T	ax,
		const T	ay,
		const T	bx,
		const T	by )

Definition at line 244 of file CDTUtils.hpp.

◆ distance() [2/3]

template<typename T>

CDT_EXPORT T CDT::distance	(	const V2d< T > &	a,
		const V2d< T > &	b )

Distance between two 2D points.

Definition at line 250 of file CDTUtils.hpp.

◆ distance() [3/3]

template<typename T>

T CDT::distance	(	const V2d< T > &	a,
		const V2d< T > &	b )

Distance between two 2D points.

Definition at line 250 of file CDTUtils.hpp.

◆ distanceSquared() [1/3]

template<typename T>

T CDT::distanceSquared	(	const T	ax,
		const T	ay,
		const T	bx,
		const T	by )

Definition at line 236 of file CDTUtils.hpp.

◆ distanceSquared() [2/3]

template<typename T>

CDT_EXPORT T CDT::distanceSquared	(	const V2d< T > &	a,
		const V2d< T > &	b )

Squared distance between two 2D points.

Definition at line 256 of file CDTUtils.hpp.

◆ distanceSquared() [3/3]

template<typename T>

T CDT::distanceSquared	(	const V2d< T > &	a,
		const V2d< T > &	b )

Squared distance between two 2D points.

Definition at line 256 of file CDTUtils.hpp.

◆ eachVertexHasNeighborTriangle()

template<typename T, typename TNearPointLocator>

bool CDT::eachVertexHasNeighborTriangle ( const CDT::Triangulation< T, TNearPointLocator > & cdt )

inline

Check that each vertex has a neighbor triangle.

Definition at line 79 of file VerifyTopology.h.

◆ edge_get_v1()

VertInd CDT::edge_get_v1 ( const Edge & e )

inline

Get edge first vertex.

Definition at line 329 of file CDTUtils.h.

◆ edge_get_v2()

VertInd CDT::edge_get_v2 ( const Edge & e )

inline

Get edge second vertex.

Definition at line 335 of file CDTUtils.h.

◆ edge_make()

Edge CDT::edge_make	(	VertInd	iV1,
		VertInd	iV2 )

inline

Get edge second vertex.

Definition at line 341 of file CDTUtils.h.

◆ edgeNeighbor() [1/2]

CDT_INLINE_IF_HEADER_ONLY TriInd CDT::edgeNeighbor	(	const Triangle &	tri,
		VertInd	iVedge1,
		VertInd	iVedge2 )

Given triangle and an edge find neighbor sharing the edge.

Definition at line 210 of file CDTUtils.hpp.

◆ edgeNeighbor() [2/2]

CDT_INLINE_IF_HEADER_ONLY Index CDT::edgeNeighbor ( PtTriLocation::Enum location )

Neighbor index from a on-edge location.

Note: Call only if located on the edge!

Definition at line 38 of file CDTUtils.hpp.

◆ edgeNeighborInd()

CDT_INLINE_IF_HEADER_ONLY Index CDT::edgeNeighborInd	(	const VerticesArr3 &	vv,
		VertInd	iVedge1,
		VertInd	iVedge2 )

Index of triangle's neighbor opposed to an edge.

Definition at line 141 of file CDTUtils.hpp.

◆ getX_V2d()

template<typename T>

const T & CDT::getX_V2d ( const V2d< T > & v )

X- coordinate getter for V2d.

Definition at line 164 of file CDTUtils.h.

◆ getY_V2d()

template<typename T>

const T & CDT::getY_V2d ( const V2d< T > & v )

Y-coordinate getter for V2d.

Definition at line 171 of file CDTUtils.h.

◆ handleException()

template<typename T>

void CDT::handleException ( const T & error )

Definition at line 117 of file CDTUtils.h.

◆ initializeWithIrregularGrid()

template<typename T, typename TNearPointLocator, typename TXCoordIter, typename TYCoordIter>

void CDT::initializeWithIrregularGrid	(	const TXCoordIter	xfirst,
		const TXCoordIter	xlast,
		const TYCoordIter	yfirst,
		const TYCoordIter	ylast,
		Triangulation< T, TNearPointLocator > &	out )

Make a triangulation that uses irregular grid triangles instead of super-triangle.

Irregular grid is given by collections of X- and Y-ticks

Template Parameters

T	type of vertex coordinates (e.g., float, double)
TNearPointLocator	class providing locating near point for efficiently inserting new points.
TXCoordIter	iterator dereferencing to X coordinate
TYCoordIter	iterator dereferencing to Y coordinate

Parameters

xfirst	beginning of X-ticks range
xlast	end of X-ticks range
yfirst	beginning of Y-ticks range
ylast	end of Y-ticks range
out	triangulation to initialize with grid super-geometry

Definition at line 211 of file InitializeWithGrid.h.

◆ initializeWithRegularGrid()

template<typename T, typename TNearPointLocator>

void CDT::initializeWithRegularGrid	(	const T	xmin,
		const T	xmax,
		const T	ymin,
		const T	ymax,
		const std::size_t	xres,
		const std::size_t	yres,
		Triangulation< T, TNearPointLocator > &	out )

Make a triangulation that uses regular grid triangles instead of super-triangle.

Template Parameters

T	type of vertex coordinates (e.g., float, double)
TNearPointLocator	class providing locating near point for efficiently inserting new points.

Parameters

xmin	minimum X-coordinate of grid
xmax	maximum X-coordinate of grid
ymin	minimum Y-coordinate of grid
ymax	maximum Y-coordinate of grid
xres	grid X-resolution
yres	grid Y-resolution
out	triangulation to initialize with grid super-geometry

Definition at line 165 of file InitializeWithGrid.h.

◆ isInCircumcircle() [1/2]

template<typename T>

CDT_EXPORT bool CDT::isInCircumcircle	(	const V2d< T > &	p,
		const V2d< T > &	v1,
		const V2d< T > &	v2,
		const V2d< T > &	v3 )

Test if point lies in a circumscribed circle of a triangle.

Definition at line 216 of file CDTUtils.hpp.

◆ isInCircumcircle() [2/2]

template<typename T>

bool CDT::isInCircumcircle	(	const V2d< T > &	p,
		const V2d< T > &	v1,
		const V2d< T > &	v2,
		const V2d< T > &	v3 )

Test if point lies in a circumscribed circle of a triangle.

Definition at line 216 of file CDTUtils.hpp.

◆ isOnEdge()

CDT_INLINE_IF_HEADER_ONLY bool CDT::isOnEdge ( PtTriLocation::Enum location )

Check if location is classified as on any of three edges.

Definition at line 31 of file CDTUtils.hpp.

◆ locatePointLine() [1/2]

template<typename T>

PtLineLocation::Enum CDT::locatePointLine	(	const V2d< T > &	p,
		const V2d< T > &	v1,
		const V2d< T > &	v2,
		const T	orientationTolerance )

Check if point lies to the left of, to the right of, or on a line.

Definition at line 51 of file CDTUtils.hpp.

◆ locatePointLine() [2/2]

template<typename T>

CDT_EXPORT PtLineLocation::Enum CDT::locatePointLine	(	const V2d< T > &	p,
		const V2d< T > &	v1,
		const V2d< T > &	v2,
		T	orientationTolerance = T(0) )

Check if point lies to the left of, to the right of, or on a line.

Definition at line 51 of file CDTUtils.hpp.

◆ locatePointTriangle() [1/2]

template<typename T>

CDT_EXPORT PtTriLocation::Enum CDT::locatePointTriangle	(	const V2d< T > &	p,
		const V2d< T > &	v1,
		const V2d< T > &	v2,
		const V2d< T > &	v3 )

Check if point a lies inside of, outside of, or on an edge of a triangle.

Definition at line 72 of file CDTUtils.hpp.

◆ locatePointTriangle() [2/2]

template<typename T>

PtTriLocation::Enum CDT::locatePointTriangle	(	const V2d< T > &	p,
		const V2d< T > &	v1,
		const V2d< T > &	v2,
		const V2d< T > &	v3 )

Check if point a lies inside of, outside of, or on an edge of a triangle.

Definition at line 72 of file CDTUtils.hpp.

◆ operator!=()

template<typename T>

bool CDT::operator!=	(	const CDT::V2d< T > &	lhs,
		const CDT::V2d< T > &	rhs )

If two 2D vectors are not exactly equal.

Definition at line 185 of file CDTUtils.h.

◆ operator==()

template<typename T>

bool CDT::operator==	(	const CDT::V2d< T > &	lhs,
		const CDT::V2d< T > &	rhs )

If two 2D vectors are exactly equal.

Definition at line 178 of file CDTUtils.h.

◆ opoNbr()

CDT_INLINE_IF_HEADER_ONLY Index CDT::opoNbr ( Index vertIndex )

Opposed neighbor index from vertex index.

Definition at line 104 of file CDTUtils.hpp.

◆ opoVrt()

CDT_INLINE_IF_HEADER_ONLY Index CDT::opoVrt ( Index neighborIndex )

Opposed vertex index from neighbor index.

Definition at line 117 of file CDTUtils.hpp.

◆ opposedTriangle()

CDT_INLINE_IF_HEADER_ONLY TriInd CDT::opposedTriangle	(	const Triangle &	tri,
		VertInd	iVert )

Given triangle and a vertex find opposed triangle.

Definition at line 197 of file CDTUtils.hpp.

◆ opposedTriangleInd()

CDT_INLINE_IF_HEADER_ONLY Index CDT::opposedTriangleInd	(	const VerticesArr3 &	vv,
		VertInd	iVert )

Index of triangle's neighbor opposed to a vertex.

Definition at line 131 of file CDTUtils.hpp.

◆ opposedVertex()

CDT_INLINE_IF_HEADER_ONLY VertInd CDT::opposedVertex	(	const Triangle &	tri,
		TriInd	iTopo )

Given two triangles, return vertex of first triangle opposed to the second.

Definition at line 203 of file CDTUtils.hpp.

◆ opposedVertexInd()

CDT_INLINE_IF_HEADER_ONLY Index CDT::opposedVertexInd	(	const NeighborsArr3 &	nn,
		TriInd	iTopo )

Index of triangle's vertex opposed to a triangle.

Definition at line 175 of file CDTUtils.hpp.

◆ orient2D() [1/2]

template<typename T>

CDT_EXPORT T CDT::orient2D	(	const V2d< T > &	p,
		const V2d< T > &	v1,
		const V2d< T > &	v2 )

Orient p against line v1-v2 2D: robust geometric predicate.

Definition at line 45 of file CDTUtils.hpp.

◆ orient2D() [2/2]

template<typename T>

T CDT::orient2D	(	const V2d< T > &	p,
		const V2d< T > &	v1,
		const V2d< T > &	v2 )

Orient p against line v1-v2 2D: robust geometric predicate.

Definition at line 45 of file CDTUtils.hpp.

◆ RemapNoSuperTriangle()

Edge CDT::RemapNoSuperTriangle ( const Edge & e )

inline

Remap removing super-triangle: subtract 3 from vertices.

Definition at line 140 of file Triangulation.hpp.

◆ to_string()

template<typename T>

std::string CDT::to_string ( const T & value )

Definition at line 106 of file CDTUtils.h.

◆ touchesSuperTriangle()

bool CDT::touchesSuperTriangle ( const Triangle & t )

Check if any of triangle's vertices belongs to a super-triangle.

Definition at line 261 of file CDTUtils.hpp.

◆ verifyTopology()

template<typename T, typename TNearPointLocator>

bool CDT::verifyTopology ( const CDT::Triangulation< T, TNearPointLocator > & cdt )

inline

Verify that triangulation topology is consistent.

Checks:

for each vertex adjacent triangles contain the vertex
each triangle's neighbor in turn has triangle as its neighbor
each of triangle's vertices has triangle as adjacent

Template Parameters

T	type of vertex coordinates (e.g., float, double)
TNearPointLocator	class providing locating near point for efficiently

Definition at line 32 of file VerifyTopology.h.

◆ vertexInd()

CDT_INLINE_IF_HEADER_ONLY Index CDT::vertexInd	(	const VerticesArr3 &	vv,
		VertInd	iV )

If triangle has a given vertex return vertex-index.

Definition at line 186 of file CDTUtils.hpp.

◆ verticesShareEdge()

CDT_INLINE_IF_HEADER_ONLY bool CDT::verticesShareEdge	(	const TriIndVec &	aTris,
		const TriIndVec &	bTris )

Test if two vertices share at least one common triangle.

Definition at line 227 of file CDTUtils.hpp.

Variable Documentation

◆ Box2d< double >

template struct CDT_EXPORT CDT::Box2d< double >

Definition at line 29 of file CDT.cpp.

◆ Box2d< float >

template struct CDT_EXPORT CDT::Box2d< float >

Definition at line 28 of file CDT.cpp.

◆ Triangulation< double >

template class CDT_EXPORT CDT::Triangulation< double >

Definition at line 32 of file CDT.cpp.

◆ Triangulation< float >

template class CDT_EXPORT CDT::Triangulation< float >

Definition at line 31 of file CDT.cpp.

◆ V2d< double >

template struct CDT_EXPORT CDT::V2d< double >

Definition at line 26 of file CDT.cpp.

◆ V2d< float >

template struct CDT_EXPORT CDT::V2d< float >

Definition at line 25 of file CDT.cpp.

Classes

Typedefs

Functions

Variables

Detailed Description

Typedef Documentation

◆ EdgeUSet

◆ EdgeVec

◆ Index

◆ IndexSizeType

◆ NeighborsArr3

◆ TriangleVec

◆ TriDeque

◆ TriInd

◆ TriIndUMap

◆ TriIndUSet

◆ TriIndVec

◆ VerticesArr3

◆ VertInd

Function Documentation

◆ arr3() [1/2]

◆ arr3() [2/2]

◆ BOOST_STRONG_TYPEDEF()

◆ ccw()

◆ classifyOrientation() [1/2]

◆ classifyOrientation() [2/2]

◆ cw()

◆ distance() [1/3]

◆ distance() [2/3]

◆ distance() [3/3]

◆ distanceSquared() [1/3]

◆ distanceSquared() [2/3]

◆ distanceSquared() [3/3]

◆ eachVertexHasNeighborTriangle()

◆ edge_get_v1()

◆ edge_get_v2()

◆ edge_make()

◆ edgeNeighbor() [1/2]

◆ edgeNeighbor() [2/2]

◆ edgeNeighborInd()

◆ getX_V2d()

◆ getY_V2d()

◆ handleException()

◆ initializeWithIrregularGrid()

◆ initializeWithRegularGrid()

◆ isInCircumcircle() [1/2]

◆ isInCircumcircle() [2/2]

◆ isOnEdge()

◆ locatePointLine() [1/2]

◆ locatePointLine() [2/2]

◆ locatePointTriangle() [1/2]

◆ locatePointTriangle() [2/2]

◆ operator!=()

◆ operator==()

◆ opoNbr()

◆ opoVrt()

◆ opposedTriangle()

◆ opposedTriangleInd()

◆ opposedVertex()

◆ opposedVertexInd()

◆ orient2D() [1/2]

◆ orient2D() [2/2]

◆ RemapNoSuperTriangle()

◆ to_string()

◆ touchesSuperTriangle()

◆ verifyTopology()

◆ vertexInd()

◆ verticesShareEdge()

Variable Documentation

◆ Box2d< double >

◆ Box2d< float >

◆ Triangulation< double >

◆ Triangulation< float >

◆ V2d< double >

◆ V2d< float >