Namespace containing triangulation functionality. More...

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

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

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 int	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 >
CDT_EXPORT 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 >
CDT_EXPORT unordered_map< Edge, std::vector< VertInd > >	EdgeToSplitVertices (const unordered_map< Edge, EdgeVec > &edgeToPieces, const std::vector< V2d< T > > &vertices)

template<typename TEdgeIter , typename TGetEdgeVertexStart , typename TGetEdgeVertexEnd , typename TMakeEdgeFromStartAndEnd >
void	RemapEdges (TEdgeIter first, const 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.

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 >
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 , typename TVertexIter , typename TGetVertexCoordX , typename TGetVertexCoordY >
Box2d< T >	envelopBox (TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
	Bounding box of a collection of custom 2D points given coordinate getters.

template<typename T >
CDT_EXPORT Box2d< T >	envelopBox (const std::vector< V2d< T > > &vertices)
	Bounding box of a collection of 2D points.

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 >
Box2d< T >	envelopBox (const std::vector< V2d< T > > &vertices)
	Bounding box of a collection of 2D points.

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.

Detailed Description

Namespace containing triangulation functionality.

This Source Code Form is subject to the terms of the Mozilla Public License, v.

2.0. If a copy of the MPL was not distributed with this file, You can obtain one at https://mozilla.org/MPL/2.0/. Contribution of original implementation: Andre Fecteau andre.nosp@m..fec.nosp@m.teau1.nosp@m.@gma.nosp@m.il.co.nosp@m.m

Typedef Documentation

◆ EdgeUSet

typedef unordered_set<Edge> CDT::EdgeUSet

Hash table of edges.

Definition at line 246 of file CDTUtils.h.

◆ EdgeVec

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

Vector of edges.

Definition at line 245 of file CDTUtils.h.

◆ Index

typedef unsigned char CDT::Index

Index in triangle.

Definition at line 140 of file CDTUtils.h.

◆ IndexSizeType

typedef unsigned int CDT::IndexSizeType

Definition at line 128 of file CDTUtils.h.

◆ NeighborsArr3

typedef array<TriInd, 3> CDT::NeighborsArr3

array of three neighbors

Definition at line 157 of file CDTUtils.h.

◆ TriangleVec

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

Vector of triangles.

Definition at line 308 of file CDTUtils.h.

◆ TriDeque

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

Definition at line 22 of file Triangulation.hpp.

◆ TriInd

typedef IndexSizeType CDT::TriInd

Triangle index.

Definition at line 144 of file CDTUtils.h.

◆ TriIndUMap

typedef unordered_map<TriInd, TriInd> CDT::TriIndUMap

Triangle hash map.

Definition at line 248 of file CDTUtils.h.

◆ TriIndUSet

typedef unordered_set<TriInd> CDT::TriIndUSet

Hash table of triangles.

Definition at line 247 of file CDTUtils.h.

◆ TriIndVec

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

Vector of triangle indices.

Definition at line 155 of file CDTUtils.h.

◆ VerticesArr3

typedef array<VertInd, 3> CDT::VerticesArr3

array of three vertex indices

Definition at line 156 of file CDTUtils.h.

◆ VertInd

typedef IndexSizeType CDT::VertInd

Vertex index.

Definition at line 142 of file CDTUtils.h.

Function Documentation

◆ ccw()

CDT_INLINE_IF_HEADER_ONLY Index CDT::ccw ( Index i )

Advance vertex or neighbor index counter-clockwise.

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

◆ cw()

CDT_INLINE_IF_HEADER_ONLY Index CDT::cw ( Index i )

Advance vertex or neighbor index clockwise.

Definition at line 80 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 296 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 302 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 302 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 288 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 308 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 308 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 228 of file CDTUtils.h.

◆ edge_get_v2()

VertInd CDT::edge_get_v2 ( const Edge & e )

inline

Get edge second vertex.

Definition at line 234 of file CDTUtils.h.

◆ edge_make()

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

inline

Get edge second vertex.

Definition at line 240 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 262 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 92 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 193 of file CDTUtils.hpp.

◆ envelopBox() [1/3]

template<typename T >

CDT_EXPORT Box2d< T > CDT::envelopBox ( const std::vector< V2d< T > > & vertices )

Bounding box of a collection of 2D points.

Definition at line 33 of file CDTUtils.hpp.

◆ envelopBox() [2/3]

template<typename T >

Box2d< T > CDT::envelopBox ( const std::vector< V2d< T > > & vertices )

Bounding box of a collection of 2D points.

Definition at line 33 of file CDTUtils.hpp.

◆ envelopBox() [3/3]

template<typename T , typename TVertexIter , typename TGetVertexCoordX , typename TGetVertexCoordY >

Box2d< T > CDT::envelopBox	(	TVertexIter	first,
		TVertexIter	last,
		TGetVertexCoordX	getX,
		TGetVertexCoordY	getY )

Bounding box of a collection of custom 2D points given coordinate getters.

Definition at line 187 of file CDTUtils.h.

◆ getX_V2d()

template<typename T >

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

X- coordinate getter for V2d.

Definition at line 106 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 113 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 214 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 168 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 268 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 268 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 85 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 105 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 105 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 126 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 126 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 exactly equal.

Definition at line 120 of file CDTUtils.h.

◆ opoNbr()

CDT_INLINE_IF_HEADER_ONLY Index CDT::opoNbr ( Index vertIndex )

Opposed neighbor index from vertex index.

Definition at line 158 of file CDTUtils.hpp.

◆ opoVrt()

CDT_INLINE_IF_HEADER_ONLY Index CDT::opoVrt ( Index neighborIndex )

Opposed vertex index from neighbor index.

Definition at line 170 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 249 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 183 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 255 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 227 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 99 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 99 of file CDTUtils.hpp.

◆ RemapNoSuperTriangle()

Edge CDT::RemapNoSuperTriangle ( const Edge & e )

inline

Remap removing super-triangle: subtract 3 from vertices.

Definition at line 170 of file Triangulation.hpp.

◆ touchesSuperTriangle()

bool CDT::touchesSuperTriangle ( const Triangle & t )

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

Definition at line 313 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 238 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 279 of file CDTUtils.hpp.

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ EdgeUSet

◆ EdgeVec

◆ Index

◆ IndexSizeType

◆ NeighborsArr3

◆ TriangleVec

◆ TriDeque

◆ TriInd

◆ TriIndUMap

◆ TriIndUSet

◆ TriIndVec

◆ VerticesArr3

◆ VertInd

Function Documentation

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

◆ envelopBox() [1/3]

◆ envelopBox() [2/3]

◆ envelopBox() [3/3]

◆ getX_V2d()

◆ getY_V2d()

◆ initializeWithIrregularGrid()

◆ initializeWithRegularGrid()

◆ isInCircumcircle() [1/2]

◆ isInCircumcircle() [2/2]

◆ isOnEdge()

◆ locatePointLine() [1/2]

◆ locatePointLine() [2/2]

◆ locatePointTriangle() [1/2]

◆ locatePointTriangle() [2/2]

◆ operator==()

◆ opoNbr()

◆ opoVrt()

◆ opposedTriangle()

◆ opposedTriangleInd()

◆ opposedVertex()

◆ opposedVertexInd()

◆ orient2D() [1/2]

◆ orient2D() [2/2]

◆ RemapNoSuperTriangle()

◆ touchesSuperTriangle()

◆ verifyTopology()

◆ vertexInd()

◆ verticesShareEdge()