CDT  1.4.2
C++ library for constrained Delaunay triangulation
 
Loading...
Searching...
No Matches
CDT Namespace Reference

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  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< TriIndVecVerticesTriangles
 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< TriIndTriIndVec
 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< EdgeEdgeVec
 Vector of edges.
 
typedef unordered_set< EdgeEdgeUSet
 Hash table of edges.
 
typedef unordered_set< TriIndTriIndUSet
 Hash table of triangles.
 
typedef unordered_map< TriInd, TriIndTriIndUMap
 Triangle hash map.
 
typedef std::vector< TriangleTriangleVec
 Vector of triangles.
 
typedef std::deque< TriIndTriDeque
 

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, EdgeVecEdgeToPiecesMapping (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.
 
 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>
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>
distanceSquared (const T ax, const T ay, const T bx, const T by)
 
template<typename T>
distance (const T ax, const T ay, const T bx, const T by)
 
template<typename T>
distance (const V2d< T > &a, const V2d< T > &b)
 Distance between two 2D points.
 
template<typename 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 > &)
 

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 331 of file CDTUtils.h.

◆ EdgeVec

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

Vector of edges.

Definition at line 330 of file CDTUtils.h.

◆ Index

typedef unsigned char CDT::Index

Index in triangle.

Definition at line 189 of file CDTUtils.h.

◆ IndexSizeType

typedef unsigned int CDT::IndexSizeType

Definition at line 175 of file CDTUtils.h.

◆ NeighborsArr3

typedef array<TriInd, 3> CDT::NeighborsArr3

array of three neighbors

Definition at line 211 of file CDTUtils.h.

◆ TriangleVec

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

Vector of triangles.

Definition at line 395 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 193 of file CDTUtils.h.

◆ TriIndUMap

typedef unordered_map<TriInd, TriInd> CDT::TriIndUMap

Triangle hash map.

Definition at line 333 of file CDTUtils.h.

◆ TriIndUSet

typedef unordered_set<TriInd> CDT::TriIndUSet

Hash table of triangles.

Definition at line 332 of file CDTUtils.h.

◆ TriIndVec

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

Vector of triangle indices.

Definition at line 209 of file CDTUtils.h.

◆ VerticesArr3

typedef array<VertInd, 3> CDT::VerticesArr3

array of three vertex indices

Definition at line 210 of file CDTUtils.h.

◆ VertInd

typedef IndexSizeType CDT::VertInd

Vertex index.

Definition at line 191 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 127 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 119 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 19 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 60 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 60 of file CDTUtils.hpp.

◆ cw()

CDT_INLINE_IF_HEADER_ONLY Index CDT::cw ( Index i)

Advance vertex or neighbor index clockwise.

Definition at line 24 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 242 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 248 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 248 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 234 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 254 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 254 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 313 of file CDTUtils.h.

◆ edge_get_v2()

VertInd CDT::edge_get_v2 ( const Edge & e)
inline

Get edge second vertex.

Definition at line 319 of file CDTUtils.h.

◆ edge_make()

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

Get edge second vertex.

Definition at line 325 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 208 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 36 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 139 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 155 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 162 of file CDTUtils.h.

◆ handleException()

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

Definition at line 108 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
Ttype of vertex coordinates (e.g., float, double)
TNearPointLocatorclass providing locating near point for efficiently inserting new points.
TXCoordIteriterator dereferencing to X coordinate
TYCoordIteriterator dereferencing to Y coordinate
Parameters
xfirstbeginning of X-ticks range
xlastend of X-ticks range
yfirstbeginning of Y-ticks range
ylastend of Y-ticks range
outtriangulation 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
Ttype of vertex coordinates (e.g., float, double)
TNearPointLocatorclass providing locating near point for efficiently inserting new points.
Parameters
xminminimum X-coordinate of grid
xmaxmaximum X-coordinate of grid
yminminimum Y-coordinate of grid
ymaxmaximum Y-coordinate of grid
xresgrid X-resolution
yresgrid Y-resolution
outtriangulation 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 214 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 214 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 29 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 49 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 49 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 70 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 70 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 169 of file CDTUtils.h.

◆ opoNbr()

CDT_INLINE_IF_HEADER_ONLY Index CDT::opoNbr ( Index vertIndex)

Opposed neighbor index from vertex index.

Definition at line 102 of file CDTUtils.hpp.

◆ opoVrt()

CDT_INLINE_IF_HEADER_ONLY Index CDT::opoVrt ( Index neighborIndex)

Opposed vertex index from neighbor index.

Definition at line 115 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 195 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 129 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 201 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 173 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 43 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 43 of file CDTUtils.hpp.

◆ RemapNoSuperTriangle()

Edge CDT::RemapNoSuperTriangle ( const Edge & e)
inline

Remap removing super-triangle: subtract 3 from vertices.

Definition at line 138 of file Triangulation.hpp.

◆ to_string()

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

Definition at line 97 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 259 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
Ttype of vertex coordinates (e.g., float, double)
TNearPointLocatorclass 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 184 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 225 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.