10#ifndef CDT_vW1vZ0lO8rS4gY4uI4fB
11#define CDT_vW1vZ0lO8rS4gY4uI4fB
113 const std::string&
file()
const
118 const std::string&
func()
const
135#define CDT_SOURCE_LOCATION \
136 SourceLocation(std::string(__FILE__), std::string(__func__), __LINE__)
142class Error :
public std::runtime_error
147 : std::runtime_error(
148 description +
"\nin '" + srcLoc.func() +
"' at " + srcLoc.file() +
149 ":" +
CDT::to_string(srcLoc.line()))
156 return m_description;
165 std::string m_description;
179 "Triangulation was finalized with 'erase...' method. Further "
180 "modification is not possible.",
197 "Duplicate vertex detected: #" +
CDT::to_string(
v1) +
198 " is a duplicate of #" +
CDT::to_string(
v2),
231 "Intersecting constraint edges detected: (" +
232 CDT::to_string(
e1.v1()) +
", " +
CDT::to_string(
e1.v2()) +
233 ") intersects (" +
CDT::to_string(
e2.v1()) +
", " +
234 CDT::to_string(
e2.v2()) +
")",
254#ifdef CDT_ENABLE_CALLBACK_HANDLER
321 const TriInd iRepurposedTri,
338 const TriInd iRepurposedTri1,
339 const TriInd iRepurposedTri2,
403template <
typename T,
typename TNearPo
intLocator = LocatorKDTree<T> >
448 T minDistToConstraintEdge);
462 const TNearPointLocator& nearPtLocator,
464 T minDistToConstraintEdge);
478 typename TVertexIter,
479 typename TGetVertexCoordX,
480 typename TGetVertexCoordY>
484 TGetVertexCoordX getX,
485 TGetVertexCoordY getY);
522 typename TGetEdgeVertexStart,
523 typename TGetEdgeVertexEnd>
527 TGetEdgeVertexStart getStart,
528 TGetEdgeVertexEnd getEnd);
581 typename TGetEdgeVertexStart,
582 typename TGetEdgeVertexEnd>
586 TGetEdgeVertexStart getStart,
587 TGetEdgeVertexEnd getEnd);
652#ifdef CDT_ENABLE_CALLBACK_HANDLER
709 void addSuperTriangle(
const Box2d<T>& box);
711 void insertVertex(
VertInd iVert);
713 void ensureDelaunayByEdgeFlips(
VertInd iV1, std::stack<TriInd>& triStack);
715 std::vector<Edge> insertVertex_FlipFixedEdges(
VertInd iV1);
718 typedef tuple<IndexSizeType, IndexSizeType, TriInd, TriInd, Index>
719 TriangulatePseudoPolygonTask;
737 std::vector<TriangulatePseudoPolygonTask>& tppIterations);
751 void insertEdgeIteration(
755 std::vector<TriangulatePseudoPolygonTask>& tppIterations);
758 typedef tuple<Edge, EdgeVec, BoundaryOverlapCount> ConformToEdgeTask;
775 BoundaryOverlapCount overlaps,
776 std::vector<ConformToEdgeTask>& remaining);
789 void conformToEdgeIteration(
792 BoundaryOverlapCount overlaps,
793 std::vector<ConformToEdgeTask>& remaining);
795 tuple<TriInd, VertInd, VertInd> intersectedTriangle(
799 T orientationTolerance = T(0))
const;
801 std::stack<TriInd> insertVertexInsideTriangle(
VertInd v,
TriInd iT);
804 array<TriInd, 2> trianglesAt(
const V2d<T>& pos)
const;
828 void triangulatePseudoPolygon(
829 const std::vector<VertInd>& poly,
830 unordered_map<Edge, TriInd>& outerTris,
833 std::vector<TriInd>& trianglesToReuse,
834 std::vector<TriangulatePseudoPolygonTask>& iterations);
835 void triangulatePseudoPolygonIteration(
836 const std::vector<VertInd>& poly,
837 unordered_map<Edge, TriInd>& outerTris,
838 std::vector<TriInd>& trianglesToReuse,
839 std::vector<TriangulatePseudoPolygonTask>& iterations);
840 IndexSizeType findDelaunayPoint(
841 const std::vector<VertInd>& poly,
843 IndexSizeType iB)
const;
851 void finalizeTriangulation(
const TriIndUSet& removedTriangles);
852 TriIndUSet growToBoundary(std::stack<TriInd> seeds)
const;
853 void fixEdge(
const Edge& edge);
854 void fixEdge(
const Edge& edge,
const Edge& originalEdge);
860 void splitFixedEdge(
const Edge& edge,
const VertInd iSplitVert);
902 unordered_map<TriInd, LayerDepth> peelLayer(
903 std::stack<TriInd> seeds,
905 std::vector<LayerDepth>& triDepths)
const;
907 void insertVertices_AsProvided(
VertInd superGeomVertCount);
908 void insertVertices_Randomized(
VertInd superGeomVertCount);
909 void insertVertices_KDTreeBFS(
VertInd superGeomVertCount,
Box2d<T> box);
910 std::pair<TriInd, TriInd> edgeTriangles(
VertInd a,
VertInd b)
const;
913 void pivotVertexTriangleCW(
VertInd v);
915 void tryAddVertexToLocator(
const VertInd v);
918 void tryInitNearestPointLocator();
920 TNearPointLocator m_nearPtLocator;
925 T m_minDistToConstraintEdge;
927#ifdef CDT_ENABLE_CALLBACK_HANDLER
955 z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
956 z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
957 return z ^ (z >> 31);
962template <
class RandomIt>
966 typename std::iterator_traits<RandomIt>::difference_type i, n;
968 for(i = n - 1; i > 0; --i)
970 std::swap(first[i], first[prng() % (i + 1)]);
975template <
class ForwardIt,
class T>
976void iota(ForwardIt first, ForwardIt last, T value)
990template <
typename T,
typename TNearPo
intLocator>
992 typename TVertexIter,
993 typename TGetVertexCoordX,
994 typename TGetVertexCoordY>
996 const TVertexIter first,
997 const TVertexIter last,
998 TGetVertexCoordX getX,
999 TGetVertexCoordY getY)
1004 const bool isFirstTime =
vertices.empty();
1009 const std::size_t nNewVertices = std::distance(first, last);
1010 std::size_t exactCapacityTriangles =
triangles.size() + 2 * nNewVertices;
1011 std::size_t exactCapacityVertices =
vertices.size() + nNewVertices;
1014 exactCapacityTriangles += 1;
1015 exactCapacityVertices += nSuperTriangleVertices;
1017 std::size_t capacityTriangles = exactCapacityTriangles;
1018 std::size_t capacityVertices = exactCapacityVertices;
1024 const VertInd overAllocationVerticesThreshold(1000);
1025 const T overAllocationFactor(1.1);
1026 const bool isOverPreAllocated =
1027 m_intersectingEdgesStrategy ==
1029 VertInd(nNewVertices) >= overAllocationVerticesThreshold;
1030 if(isOverPreAllocated)
1032 capacityTriangles *= overAllocationFactor;
1033 capacityVertices *= overAllocationFactor;
1036 vertices.reserve(capacityVertices);
1037 m_vertTris.reserve(capacityVertices);
1043 addSuperTriangle(box);
1045 tryInitNearestPointLocator();
1048 for(TVertexIter it = first; it != last; ++it)
1049 addNewVertex(
V2d<T>(getX(*it), getY(*it)), noNeighbor);
1051 switch(m_vertexInsertionOrder)
1054 insertVertices_AsProvided(nExistingVerts);
1057 isFirstTime ? insertVertices_KDTreeBFS(nExistingVerts, box)
1058 : insertVertices_Randomized(nExistingVerts);
1063#ifdef CDT_ENABLE_CALLBACK_HANDLER
1065 !m_callbackHandler || m_callbackHandler->isAbortCalculation() ||
1066 (
vertices.size() == exactCapacityVertices));
1068 !m_callbackHandler || m_callbackHandler->isAbortCalculation() ||
1069 (
triangles.size() == exactCapacityTriangles));
1071 assert(
vertices.size() == exactCapacityVertices);
1072 assert(
triangles.size() == exactCapacityTriangles);
1076template <
typename T,
typename TNearPo
intLocator>
1079 typename TGetEdgeVertexStart,
1080 typename TGetEdgeVertexEnd>
1083 const TEdgeIter last,
1084 TGetEdgeVertexStart getStart,
1085 TGetEdgeVertexEnd getEnd)
1090 std::vector<TriangulatePseudoPolygonTask> tppIterations;
1092 for(; first != last; ++first)
1094#ifdef CDT_ENABLE_CALLBACK_HANDLER
1095 if(m_callbackHandler && m_callbackHandler->isAbortCalculation())
1102 VertInd(getStart(*first) + m_nTargetVerts),
1103 VertInd(getEnd(*first) + m_nTargetVerts));
1104 insertEdge(edge, edge, remaining, tppIterations);
1108template <
typename T,
typename TNearPo
intLocator>
1111 typename TGetEdgeVertexStart,
1112 typename TGetEdgeVertexEnd>
1115 const TEdgeIter last,
1116 TGetEdgeVertexStart getStart,
1117 TGetEdgeVertexEnd getEnd)
1122 tryInitNearestPointLocator();
1124 std::vector<ConformToEdgeTask> remaining;
1125 for(; first != last; ++first)
1127#ifdef CDT_ENABLE_CALLBACK_HANDLER
1128 if(m_callbackHandler && m_callbackHandler->isAbortCalculation())
1135 VertInd(getStart(*first) + m_nTargetVerts),
1136 VertInd(getEnd(*first) + m_nTargetVerts));
1137 conformToEdge(e,
EdgeVec(1, e), 0, remaining);
1143#ifndef CDT_USE_AS_COMPILED_LIBRARY
Adapter between for KDTree and CDT.
void random_shuffle(RandomIt first, RandomIt last)
backport from c++11
void iota(ForwardIt first, ForwardIt last, T value)
backport from c++11
Triangulation class - implementation.
VertInd v2() const
second duplicate
VertInd v1() const
first duplicate
DuplicateVertexError(const VertInd v1, const VertInd v2, const SourceLocation &srcLoc)
Constructor.
const SourceLocation & sourceLocation() const
Get source location from where the error was thrown.
Error(const std::string &description, const SourceLocation &srcLoc)
Constructor.
const std::string & description() const
Get error description.
Error thrown when triangulation modification is attempted after it was finalized.
FinalizedError(const SourceLocation &srcLoc)
Constructor.
Interface for the callback handler that user can derive from and inject into the triangulation to mon...
virtual void onAddSuperTriangle()
Called when super-triangle is added.
virtual void onInsertVertexOnEdge(const TriInd iRepurposedTri1, const TriInd iRepurposedTri2, const TriInd iNewTri1, const TriInd iNewTri2)
Called when inserted vertex is on an edge.
virtual bool isAbortCalculation() const
Tells whether the user wants to abort the triangulation at the earliest opportunity.
virtual ~ICallbackHandler()
Virtual destructor.
virtual void onReTriangulatePolygon(const std::vector< TriInd > &tris)
Called when inserting a constraint edge causes polygon containing triangles to be re-triangulated @tr...
virtual void onFlipEdge(const TriInd iT, const TriInd iTopo)
Called just before an edge between tro triangles is flipped.
virtual void onInsertVertexInsideTriangle(const TriInd iRepurposedTri, const TriInd iNewTri1, const TriInd iNewTri2)
Called when inserted vertex is inside a triangle.
virtual void onAddEdgeStart(const Edge &edge)
Called at the start of adding a constraint edge to the triangulation.
virtual void onAddVertexStart(const VertInd iV, const AddVertexType::Enum vertexType)
Called at the start of adding new vertex to the triangulation.
const Edge & e1() const
first intersecting constraint
const Edge & e2() const
second intersecting constraint
IntersectingConstraintsError(const Edge &e1, const Edge &e2, const SourceLocation &srcLoc)
Constructor.
Contains source location info: file, function, line.
SourceLocation(const std::string &file, const std::string &func, int line)
Constructor.
const std::string & func() const
source function
int line() const
source line
const std::string & file() const
source file
EdgeUSet fixedEdges
triangulation's constraints (fixed edges)
void eraseOuterTriangles()
Erase triangles outside of constrained boundary using growing.
void conformToEdges(TEdgeIter first, TEdgeIter last, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd)
Insert constraint edges into triangulation for Conforming Delaunay Triangulation (for example see fig...
std::vector< V2d< T > > V2dVec
Vertices vector.
std::vector< LayerDepth > calculateTriangleDepths() const
Calculate depth of each triangle in constraint triangulation.
bool isFinalized() const
Check if the triangulation was finalized with erase... method and super-triangle was removed.
Triangulation(VertexInsertionOrder::Enum vertexInsertionOrder)
Constructor.
void eraseOuterTrianglesAndHoles()
Erase triangles outside of constrained boundary and auto-detected holes.
V2dVec vertices
triangulation's vertices
void insertEdges(TEdgeIter first, TEdgeIter last, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd)
Insert constraint edges into triangulation for Constrained Delaunay Triangulation (for example see fi...
void insertVertices(TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
Insert custom point-types specified by iterator range and X/Y-getters.
Triangulation(VertexInsertionOrder::Enum vertexInsertionOrder, IntersectingConstraintEdges::Enum intersectingEdgesStrategy, T minDistToConstraintEdge)
Constructor.
void eraseSuperTriangle()
Erase triangles adjacent to super triangle.
unordered_map< Edge, EdgeVec > pieceToOriginals
Stores list of original edges represented by a given fixed edge.
Triangulation(VertexInsertionOrder::Enum vertexInsertionOrder, const TNearPointLocator &nearPtLocator, IntersectingConstraintEdges::Enum intersectingEdgesStrategy, T minDistToConstraintEdge)
Constructor.
unordered_map< Edge, BoundaryOverlapCount > overlapCount
Stores count of overlapping boundaries for a fixed edge.
TriangleVec triangles
triangulation's triangles
Triangulation()
Default constructor.
void setCallbackHandler(ICallbackHandler *callbackHandler)
Set user-provided callback handler.
void initializedWithCustomSuperGeometry()
Call this method after directly setting custom super-geometry via vertices and triangles members.
unsigned short LayerDepth
Type used for storing layer depths for triangles.
void flipEdge(TriInd iT, TriInd iTopo)
Flip an edge between two triangle.
TriIndVec & VertTrisInternal()
Access internal vertex adjacent triangles.
void removeTriangles(const TriIndUSet &removedTriangles)
Remove triangles with specified indices.
Namespace containing triangulation functionality.
std::vector< Edge > EdgeVec
Vector of edges.
unordered_set< Edge > EdgeUSet
Hash table of edges.
std::vector< TriInd > TriIndVec
Vector of triangle indices.
IndexSizeType VertInd
Vertex index.
unordered_set< TriInd > TriIndUSet
Hash table of triangles.
IndexSizeType TriInd
Triangle index.
std::vector< Triangle > TriangleVec
Vector of triangles.
What type of vertex is added to the triangulation.
@ UserInput
Original vertex from user input.
@ FixedEdgeMidpoint
During conforming triangulation edge mid-point is added.
@ FixedEdgesIntersection
Resolving fixed/constraint edges' intersection.
Box2d< T > & envelopPoints(TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
Envelop box around a collection of custom points.
Edge connecting two vertices: vertex with smaller index is always first.
Enum of strategies for treating intersecting constraint edges.
@ TryResolve
attempt to resolve constraint edge intersections
@ NotAllowed
constraint edge intersections are not allowed
@ DontCheck
No checks: slightly faster but less safe.
Enum of what type of geometry used to embed triangulation into.
@ SuperTriangle
conventional super-triangle
@ Custom
user-specified custom geometry (e.g., grid)
What type of triangle change happened.
@ AddedNew
new triangle added to the triangulation
@ ModifiedExisting
existing triangle was modified
Triangulation triangle (counter-clockwise winding)
Enum of strategies specifying order in which a range of vertices is inserted.
@ AsProvided
insert vertices in same order they are provided
@ Auto
Automatic insertion order optimized for better performance.
SplitMix64 pseudo-random number generator.
uint64 m_state
PRNG's state.
SplitMix64RandGen()
default constructor
uint64 operator()()
functor's operator
unsigned long long uint64
uint64 type
SplitMix64RandGen(uint64 state)
constructor