Namespace containing triangulation functionality. More...

Classes
class	AccessingInvalidIndex

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

class	OptionalIndex

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

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

struct	RefinementCriterion
	Enum of strategies for triangles refinement. More...

class	SourceLocation
	Contains source location info: file, function, line. 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	Unrefined
	Counts of the refinements that Triangulation::refineTriangles was not able to perform. 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 std::queue< Edge >	EdgeQueue
	Queue of edges.

typedef std::queue< TriInd >	TriIndQueue
	Queue of triangles.

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 OptionalIndex< VertInd >	OptionalVertInd
	Optional vertex index.

typedef OptionalIndex< TriInd >	OptionalTriInd
	Optional triangle index.

typedef std::deque< TriInd >	TriDeque

Functions
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	verifyWinding (const CDT::Triangulation< T, TNearPointLocator > &cdt)
	Check that every triangle is wound counter-clockwise: degenerate and inverted triangles are topologically consistent, so verifyTopology misses them.

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_EXPORT 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_EXPORT 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>
CDT_EXPORT T	area (const V2d< T > &a, const V2d< T > &b, const V2d< T > &c)
	Surface area of a triangle ABC.

template<typename T>
CDT_EXPORT V2d< T >	circumcenter (V2d< T > a, V2d< T > b, V2d< T > c)
	Position of ABC triangle circumcenter.

template<typename T>
CDT_EXPORT T	smallestAngle (const V2d< T > &a, const V2d< T > &b, const V2d< T > &c)
	Smallest angle of triangle ABC in radians.

template<typename T>
CDT_EXPORT T	degToRad (T degrees)
	Convert an angle from degrees to radians.

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.

template<typename T>
T	area (const V2d< T > &a, const V2d< T > &b, const V2d< T > &c)
	Surface area of a triangle ABC.

template<typename T>
V2d< T >	circumcenter (V2d< T > a, V2d< T > b, V2d< T > c)
	Position of ABC triangle circumcenter.

template<typename T>
T	smallestAngle (const V2d< T > &a, const V2d< T > &b, const V2d< T > &c)
	Smallest angle of triangle ABC in radians.

template<typename T>
T	degToRad (const T degrees)
	Convert an angle from degrees to radians.

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 float	degToRad< float > (float)

template CDT_EXPORT double	degToRad< double > (double)

template CDT_EXPORT float	orient2D< float > (const V2d< float > &, const V2d< float > &, const V2d< float > &)

template CDT_EXPORT double	orient2D< double > (const V2d< double > &, const V2d< double > &, const V2d< double > &)

template CDT_EXPORT float	area< float > (const V2d< float > &, const V2d< float > &, const V2d< float > &)

template CDT_EXPORT double	area< double > (const V2d< double > &, const V2d< double > &, const V2d< double > &)

template CDT_EXPORT V2d< float >	circumcenter< float > (V2d< float >, V2d< float >, V2d< float >)

template CDT_EXPORT V2d< double >	circumcenter< double > (V2d< double >, V2d< double >, V2d< double >)

template CDT_EXPORT float	smallestAngle< float > (const V2d< float > &, const V2d< float > &, const V2d< float > &)

template CDT_EXPORT double	smallestAngle< double > (const V2d< double > &, const V2d< double > &, const V2d< double > &)

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

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

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

template CDT_EXPORT bool	verifyWinding< double > (const CDT::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

◆ EdgeQueue

typedef std::queue<Edge> CDT::EdgeQueue

Queue of edges.

Definition at line 401 of file CDTUtils.h.

◆ EdgeUSet

typedef unordered_set<Edge> CDT::EdgeUSet

Hash table of edges.

Definition at line 403 of file CDTUtils.h.

◆ EdgeVec

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

Vector of edges.

Definition at line 400 of file CDTUtils.h.

◆ Index

typedef unsigned char CDT::Index

Index in triangle.

Definition at line 252 of file CDTUtils.h.

◆ IndexSizeType

typedef unsigned int CDT::IndexSizeType

Definition at line 238 of file CDTUtils.h.

◆ NeighborsArr3

typedef array<TriInd, 3> CDT::NeighborsArr3

array of three neighbors

Definition at line 274 of file CDTUtils.h.

◆ TriangleVec

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

Vector of triangles.

Definition at line 467 of file CDTUtils.h.

◆ TriDeque

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

Definition at line 26 of file Triangulation.hpp.

◆ TriInd

typedef IndexSizeType CDT::TriInd

Triangle index.

Definition at line 256 of file CDTUtils.h.

◆ TriIndQueue

typedef std::queue<TriInd> CDT::TriIndQueue

Queue of triangles.

Definition at line 402 of file CDTUtils.h.

◆ TriIndUMap

typedef unordered_map<TriInd, TriInd> CDT::TriIndUMap

Triangle hash map.

Definition at line 405 of file CDTUtils.h.

◆ TriIndUSet

typedef unordered_set<TriInd> CDT::TriIndUSet

Hash table of triangles.

Definition at line 404 of file CDTUtils.h.

◆ TriIndVec

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

Vector of triangle indices.

Definition at line 272 of file CDTUtils.h.

◆ VerticesArr3

typedef array<VertInd, 3> CDT::VerticesArr3

array of three vertex indices

Definition at line 273 of file CDTUtils.h.

◆ VertInd

typedef IndexSizeType CDT::VertInd

Vertex index.

Definition at line 254 of file CDTUtils.h.

Function Documentation

◆ area() [1/2]

template<typename T>

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

Surface area of a triangle ABC.

Definition at line 303 of file CDTUtils.hpp.

◆ area() [2/2]

template<typename T>

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

Surface area of a triangle ABC.

Definition at line 303 of file CDTUtils.hpp.

◆ 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 183 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 175 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 23 of file CDTUtils.hpp.

◆ circumcenter() [1/2]

template<typename T>

CDT_EXPORT V2d< T > CDT::circumcenter	(	V2d< T >	a,
		V2d< T >	b,
		V2d< T >	c )

Position of ABC triangle circumcenter.

Definition at line 309 of file CDTUtils.hpp.

◆ circumcenter() [2/2]

template<typename T>

V2d< T > CDT::circumcenter	(	V2d< T >	a,
		V2d< T >	b,
		V2d< T >	c )

Position of ABC triangle circumcenter.

Definition at line 309 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 64 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 64 of file CDTUtils.hpp.

◆ cw()

CDT_INLINE_IF_HEADER_ONLY Index CDT::cw ( Index i )

Advance vertex or neighbor index clockwise.

Definition at line 28 of file CDTUtils.hpp.

◆ degToRad() [1/2]

template<typename T>

T CDT::degToRad ( const T degrees )

Convert an angle from degrees to radians.

Definition at line 330 of file CDTUtils.hpp.

◆ degToRad() [2/2]

template<typename T>

CDT_EXPORT T CDT::degToRad ( T degrees )

Convert an angle from degrees to radians.

Definition at line 330 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 245 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 251 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 251 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 237 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 257 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 257 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 99 of file VerifyTopology.h.

◆ edge_get_v1()

VertInd CDT::edge_get_v1 ( const Edge & e )

inline

Get edge first vertex.

Definition at line 383 of file CDTUtils.h.

◆ edge_get_v2()

VertInd CDT::edge_get_v2 ( const Edge & e )

inline

Get edge second vertex.

Definition at line 389 of file CDTUtils.h.

◆ edge_make()

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

inline

Get edge second vertex.

Definition at line 395 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 211 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 40 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 142 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 211 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 218 of file CDTUtils.h.

◆ handleException()

template<typename T>

void CDT::handleException ( const T & error )

Definition at line 164 of file CDTUtils.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 217 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 217 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 33 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 53 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 53 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 74 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 74 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 232 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 225 of file CDTUtils.h.

◆ opoNbr()

CDT_INLINE_IF_HEADER_ONLY Index CDT::opoNbr ( Index vertIndex )

Opposed neighbor index from vertex index.

Definition at line 105 of file CDTUtils.hpp.

◆ opoVrt()

CDT_INLINE_IF_HEADER_ONLY Index CDT::opoVrt ( Index neighborIndex )

Opposed vertex index from neighbor index.

Definition at line 118 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 198 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 132 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 204 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 176 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 47 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 47 of file CDTUtils.hpp.

◆ RemapNoSuperTriangle()

Edge CDT::RemapNoSuperTriangle ( const Edge & e )

inline

Remap removing super-triangle: subtract 3 from vertices.

Definition at line 180 of file Triangulation.hpp.

◆ smallestAngle() [1/2]

template<typename T>

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

Smallest angle of triangle ABC in radians.

Definition at line 322 of file CDTUtils.hpp.

◆ smallestAngle() [2/2]

template<typename T>

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

Smallest angle of triangle ABC in radians.

Definition at line 322 of file CDTUtils.hpp.

◆ to_string()

template<typename T>

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

Definition at line 113 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 262 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.

◆ verifyWinding()

template<typename T, typename TNearPointLocator>

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

inline

Check that every triangle is wound counter-clockwise: degenerate and inverted triangles are topologically consistent, so verifyTopology misses them.

Definition at line 81 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 187 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 228 of file CDTUtils.hpp.

Variable Documentation

◆ Box2d< double >

template struct CDT_EXPORT CDT::Box2d< double >

Definition at line 28 of file CDT.cpp.

◆ Box2d< float >

template struct CDT_EXPORT CDT::Box2d< float >

Definition at line 27 of file CDT.cpp.

◆ Triangulation< double >

template class CDT_EXPORT CDT::Triangulation< double >

Definition at line 31 of file CDT.cpp.

◆ Triangulation< float >

template class CDT_EXPORT CDT::Triangulation< float >

Definition at line 30 of file CDT.cpp.

◆ V2d< double >

template struct CDT_EXPORT CDT::V2d< double >

Definition at line 25 of file CDT.cpp.

◆ V2d< float >

template struct CDT_EXPORT CDT::V2d< float >

Definition at line 24 of file CDT.cpp.

Classes

Typedefs

Functions

Variables

Detailed Description

Typedef Documentation

◆ EdgeQueue

◆ EdgeUSet

◆ EdgeVec

◆ Index

◆ IndexSizeType

◆ NeighborsArr3

◆ TriangleVec

◆ TriDeque

◆ TriInd

◆ TriIndQueue

◆ TriIndUMap

◆ TriIndUSet

◆ TriIndVec

◆ VerticesArr3

◆ VertInd

Function Documentation

◆ area() [1/2]

◆ area() [2/2]

◆ arr3() [1/2]

◆ arr3() [2/2]

◆ BOOST_STRONG_TYPEDEF()

◆ ccw()

◆ circumcenter() [1/2]

◆ circumcenter() [2/2]

◆ classifyOrientation() [1/2]

◆ classifyOrientation() [2/2]

◆ cw()

◆ degToRad() [1/2]

◆ degToRad() [2/2]

◆ 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()

◆ 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()

◆ smallestAngle() [1/2]

◆ smallestAngle() [2/2]

◆ to_string()

◆ touchesSuperTriangle()

◆ verifyTopology()

◆ verifyWinding()

◆ vertexInd()

◆ verticesShareEdge()

Variable Documentation

◆ Box2d< double >

◆ Box2d< float >