CDT  1.4.2
C++ library for constrained Delaunay triangulation
 
Loading...
Searching...
No Matches
Triangulation.h
Go to the documentation of this file.
1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
9
10#ifndef CDT_vW1vZ0lO8rS4gY4uI4fB
11#define CDT_vW1vZ0lO8rS4gY4uI4fB
12
13#include "CDTUtils.h"
14#include "LocatorKDTree.h"
15
16#include <algorithm>
17#include <cstdlib>
18#include <iterator>
19#include <stack>
20#include <stdexcept>
21#include <string>
22#include <utility>
23#include <vector>
24
26namespace CDT
27{
28
31
38struct CDT_EXPORT VertexInsertionOrder
39{
44 enum Enum
45 {
54 };
55};
56
58struct CDT_EXPORT SuperGeometryType
59{
64 enum Enum
65 {
68 };
69};
70
75{
90};
91
97typedef unsigned short LayerDepth;
98typedef LayerDepth BoundaryOverlapCount;
99
104{
105public:
107 SourceLocation(const std::string& file, const std::string& func, int line)
108 : m_file(file)
109 , m_func(func)
110 , m_line(line)
111 {}
112
113 const std::string& file() const
114 {
115 return m_file;
116 }
117
118 const std::string& func() const
119 {
120 return m_func;
121 }
122
123 int line() const
124 {
125 return m_line;
126 }
127
128private:
129 std::string m_file;
130 std::string m_func;
131 int m_line;
132};
133
135#define CDT_SOURCE_LOCATION \
136 SourceLocation(std::string(__FILE__), std::string(__func__), __LINE__)
137
142class Error : public std::runtime_error
143{
144public:
146 Error(const std::string& description, const SourceLocation& srcLoc)
147 : std::runtime_error(
148 description + "\nin '" + srcLoc.func() + "' at " + srcLoc.file() +
149 ":" + CDT::to_string(srcLoc.line()))
150 , m_description(description)
151 , m_srcLoc(srcLoc)
152 {}
153
154 const std::string& description() const
155 {
156 return m_description;
157 }
158
160 {
161 return m_srcLoc;
162 }
163
164private:
165 std::string m_description;
166 SourceLocation m_srcLoc;
167};
168
173class FinalizedError : public Error
174{
175public:
178 : Error(
179 "Triangulation was finalized with 'erase...' method. Further "
180 "modification is not possible.",
181 srcLoc)
182 {}
183};
184
189{
190public:
193 const VertInd v1,
194 const VertInd v2,
195 const SourceLocation& srcLoc)
196 : Error(
197 "Duplicate vertex detected: #" + CDT::to_string(v1) +
198 " is a duplicate of #" + CDT::to_string(v2),
199 srcLoc)
200 , m_v1(v1)
201 , m_v2(v2)
202 {}
203
204 VertInd v1() const
205 {
206 return m_v1;
207 }
208
209 VertInd v2() const
210 {
211 return m_v2;
212 }
213
214private:
215 VertInd m_v1, m_v2;
216};
217
223{
224public:
227 const Edge& e1,
228 const Edge& e2,
229 const SourceLocation& srcLoc)
230 : Error(
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()) + ")",
235 srcLoc)
236 , m_e1(e1)
237 , m_e2(e2)
238 {}
239
240 const Edge& e1() const
241 {
242 return m_e1;
243 }
244
245 const Edge& e2() const
246 {
247 return m_e2;
248 }
249
250private:
251 Edge m_e1, m_e2;
252};
253
254#ifdef CDT_ENABLE_CALLBACK_HANDLER
255
275
279struct CDT_EXPORT TriangleChangeType
280{
290};
291
296class CDT_EXPORT ICallbackHandler
297{
298public:
301 {}
302
308 virtual void onAddSuperTriangle()
309 {}
310
321 const TriInd iRepurposedTri,
322 const TriInd iNewTri1,
323 const TriInd iNewTri2)
324 {}
325
338 const TriInd iRepurposedTri1,
339 const TriInd iRepurposedTri2,
340 const TriInd iNewTri1,
341 const TriInd iNewTri2)
342 {}
343
349 virtual void onFlipEdge(const TriInd iT, const TriInd iTopo)
350 {}
351
357 virtual void
358 onAddVertexStart(const VertInd iV, const AddVertexType::Enum vertexType)
359 {}
360
365 virtual void onAddEdgeStart(const Edge& edge)
366 {}
367
374 virtual void onReTriangulatePolygon(const std::vector<TriInd>& tris)
375 {}
376
381 virtual bool isAbortCalculation() const
382 {
383 return false;
384 };
385};
386
387#endif
388
394
403template <typename T, typename TNearPointLocator = LocatorKDTree<T> >
404class CDT_EXPORT Triangulation
405{
406public:
407 typedef std::vector<V2d<T> > V2dVec;
411
419 unordered_map<Edge, BoundaryOverlapCount> overlapCount;
420
426 unordered_map<Edge, EdgeVec> pieceToOriginals;
427
428 /*____ API _____*/
435 explicit Triangulation(VertexInsertionOrder::Enum vertexInsertionOrder);
446 VertexInsertionOrder::Enum vertexInsertionOrder,
447 IntersectingConstraintEdges::Enum intersectingEdgesStrategy,
448 T minDistToConstraintEdge);
461 VertexInsertionOrder::Enum vertexInsertionOrder,
462 const TNearPointLocator& nearPtLocator,
463 IntersectingConstraintEdges::Enum intersectingEdgesStrategy,
464 T minDistToConstraintEdge);
477 template <
478 typename TVertexIter,
479 typename TGetVertexCoordX,
480 typename TGetVertexCoordY>
481 void insertVertices(
482 TVertexIter first,
483 TVertexIter last,
484 TGetVertexCoordX getX,
485 TGetVertexCoordY getY);
490 void insertVertices(const std::vector<V2d<T> >& vertices);
520 template <
521 typename TEdgeIter,
522 typename TGetEdgeVertexStart,
523 typename TGetEdgeVertexEnd>
524 void insertEdges(
525 TEdgeIter first,
526 TEdgeIter last,
527 TGetEdgeVertexStart getStart,
528 TGetEdgeVertexEnd getEnd);
549 void insertEdges(const std::vector<Edge>& edges);
579 template <
580 typename TEdgeIter,
581 typename TGetEdgeVertexStart,
582 typename TGetEdgeVertexEnd>
583 void conformToEdges(
584 TEdgeIter first,
585 TEdgeIter last,
586 TGetEdgeVertexStart getStart,
587 TGetEdgeVertexEnd getEnd);
608 void conformToEdges(const std::vector<Edge>& edges);
616 void eraseOuterTriangles();
629
635 bool isFinalized() const;
636
650 std::vector<LayerDepth> calculateTriangleDepths() const;
651
652#ifdef CDT_ENABLE_CALLBACK_HANDLER
660 void setCallbackHandler(ICallbackHandler* callbackHandler);
661#endif
668
676 void flipEdge(TriInd iT, TriInd iTopo);
677
682 void flipEdge(
683 TriInd iT,
684 TriInd iTopo,
685 VertInd v1,
686 VertInd v2,
687 VertInd v3,
688 VertInd v4,
689 TriInd n1,
690 TriInd n2,
691 TriInd n3,
692 TriInd n4);
693
699 void removeTriangles(const TriIndUSet& removedTriangles);
700
704 const TriIndVec& VertTrisInternal() const;
706
707private:
708 /*____ Detail __*/
709 void addSuperTriangle(const Box2d<T>& box);
710 void addNewVertex(const V2d<T>& pos, TriInd iT);
711 void insertVertex(VertInd iVert);
712 void insertVertex(VertInd iVert, VertInd walkStart);
713 void ensureDelaunayByEdgeFlips(VertInd iV1, std::stack<TriInd>& triStack);
715 std::vector<Edge> insertVertex_FlipFixedEdges(VertInd iV1);
716
718 typedef tuple<IndexSizeType, IndexSizeType, TriInd, TriInd, Index>
719 TriangulatePseudoPolygonTask;
720
733 void insertEdge(
734 Edge edge,
735 Edge originalEdge,
736 EdgeVec& remaining,
737 std::vector<TriangulatePseudoPolygonTask>& tppIterations);
738
751 void insertEdgeIteration(
752 Edge edge,
753 Edge originalEdge,
754 EdgeVec& remaining,
755 std::vector<TriangulatePseudoPolygonTask>& tppIterations);
756
758 typedef tuple<Edge, EdgeVec, BoundaryOverlapCount> ConformToEdgeTask;
759
772 void conformToEdge(
773 Edge edge,
774 EdgeVec originals,
775 BoundaryOverlapCount overlaps,
776 std::vector<ConformToEdgeTask>& remaining);
777
789 void conformToEdgeIteration(
790 Edge edge,
791 const EdgeVec& originals,
792 BoundaryOverlapCount overlaps,
793 std::vector<ConformToEdgeTask>& remaining);
794
795 tuple<TriInd, VertInd, VertInd> intersectedTriangle(
796 VertInd iA,
797 const V2d<T>& a,
798 const V2d<T>& b,
799 T orientationTolerance = T(0)) const;
801 std::stack<TriInd> insertVertexInsideTriangle(VertInd v, TriInd iT);
803 std::stack<TriInd> insertVertexOnEdge(VertInd v, TriInd iT1, TriInd iT2);
804 array<TriInd, 2> trianglesAt(const V2d<T>& pos) const;
805 array<TriInd, 2>
806 walkingSearchTrianglesAt(VertInd iV, VertInd startVertex) const;
807 TriInd walkTriangles(VertInd startVertex, const V2d<T>& pos) const;
810 void edgeFlipInfo(
811 TriInd iT,
812 VertInd iV1,
813 TriInd& iTopo,
814 VertInd& iV2,
815 VertInd& iV3,
816 VertInd& iV4,
817 TriInd& n1,
818 TriInd& n2,
819 TriInd& n3,
820 TriInd& n4);
821 bool isFlipNeeded(VertInd iV1, VertInd iV2, VertInd iV3, VertInd iV4) const;
822 void changeNeighbor(TriInd iT, TriInd oldNeighbor, TriInd newNeighbor);
823 void changeNeighbor(
824 TriInd iT,
825 VertInd iVedge1,
826 VertInd iVedge2,
827 TriInd newNeighbor);
828 void triangulatePseudoPolygon(
829 const std::vector<VertInd>& poly,
830 unordered_map<Edge, TriInd>& outerTris,
831 TriInd iT,
832 TriInd iN,
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,
842 IndexSizeType iA,
843 IndexSizeType iB) const;
844 TriInd addTriangle(const Triangle& t);
845 TriInd addTriangle();
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);
869 VertInd addSplitEdgeVertex(
870 const V2d<T>& splitVert,
871 const TriInd iT,
872 const TriInd iTopo);
882 VertInd splitFixedEdgeAt(
883 const Edge& edge,
884 const V2d<T>& splitVert,
885 const TriInd iT,
886 const TriInd iTopo);
902 unordered_map<TriInd, LayerDepth> peelLayer(
903 std::stack<TriInd> seeds,
904 LayerDepth layerDepth,
905 std::vector<LayerDepth>& triDepths) const;
906
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;
911 bool hasEdge(VertInd a, VertInd b) const;
912 void setAdjacentTriangle(const VertInd v, const TriInd t);
913 void pivotVertexTriangleCW(VertInd v);
915 void tryAddVertexToLocator(const VertInd v);
918 void tryInitNearestPointLocator();
919
920 TNearPointLocator m_nearPtLocator;
921 VertInd m_nTargetVerts;
922 SuperGeometryType::Enum m_superGeomType;
923 VertexInsertionOrder::Enum m_vertexInsertionOrder;
924 IntersectingConstraintEdges::Enum m_intersectingEdgesStrategy;
925 T m_minDistToConstraintEdge;
926 TriIndVec m_vertTris;
927#ifdef CDT_ENABLE_CALLBACK_HANDLER
928 ICallbackHandler* m_callbackHandler;
929#endif
930};
931
934
935namespace detail
936{
937
940{
941 typedef unsigned long long uint64;
944 explicit SplitMix64RandGen(uint64 state)
945 : m_state(state)
946 {}
947
949 : m_state(0)
950 {}
951
953 {
954 uint64 z = (m_state += 0x9e3779b97f4a7c15);
955 z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
956 z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
957 return z ^ (z >> 31);
958 }
959};
960
962template <class RandomIt>
963void random_shuffle(RandomIt first, RandomIt last)
964{
966 typename std::iterator_traits<RandomIt>::difference_type i, n;
967 n = last - first;
968 for(i = n - 1; i > 0; --i)
969 {
970 std::swap(first[i], first[prng() % (i + 1)]);
971 }
972}
973
975template <class ForwardIt, class T>
976void iota(ForwardIt first, ForwardIt last, T value)
977{
978 while(first != last)
979 {
980 *first++ = value;
981 ++value;
982 }
983}
984
985} // namespace detail
986
987//-----------------------
988// Triangulation methods
989//-----------------------
990template <typename T, typename TNearPointLocator>
991template <
992 typename TVertexIter,
993 typename TGetVertexCoordX,
994 typename TGetVertexCoordY>
996 const TVertexIter first,
997 const TVertexIter last,
998 TGetVertexCoordX getX,
999 TGetVertexCoordY getY)
1000{
1001 if(isFinalized())
1002 handleException(FinalizedError(CDT_SOURCE_LOCATION));
1003
1004 const bool isFirstTime = vertices.empty();
1005
1006 //
1007 // performance optimization: pre-allocate triangles and vertices
1008 //
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;
1012 if(isFirstTime) // account for adding super-triangle on the first run
1013 {
1014 exactCapacityTriangles += 1;
1015 exactCapacityVertices += nSuperTriangleVertices;
1016 }
1017 std::size_t capacityTriangles = exactCapacityTriangles;
1018 std::size_t capacityVertices = exactCapacityVertices;
1019 // to avoid re-allocation and unused memory
1020 // over-allocate by a fixed factor
1021 // when constraint edge intersections are resolved and vertices are many
1022 // because vertex is added for each intersection
1023 // and total number of intersections is unknown
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)
1031 {
1032 capacityTriangles *= overAllocationFactor;
1033 capacityVertices *= overAllocationFactor;
1034 }
1035 triangles.reserve(capacityTriangles);
1036 vertices.reserve(capacityVertices);
1037 m_vertTris.reserve(capacityVertices);
1038
1039 Box2d<T> box;
1040 if(isFirstTime)
1041 {
1042 box.envelopPoints(first, last, getX, getY);
1043 addSuperTriangle(box);
1044 }
1045 tryInitNearestPointLocator();
1046 const VertInd nExistingVerts = static_cast<VertInd>(vertices.size());
1047
1048 for(TVertexIter it = first; it != last; ++it)
1049 addNewVertex(V2d<T>(getX(*it), getY(*it)), noNeighbor);
1050
1051 switch(m_vertexInsertionOrder)
1052 {
1054 insertVertices_AsProvided(nExistingVerts);
1055 break;
1057 isFirstTime ? insertVertices_KDTreeBFS(nExistingVerts, box)
1058 : insertVertices_Randomized(nExistingVerts);
1059 break;
1060 }
1061
1062// make sure pre-allocation was correct
1063#ifdef CDT_ENABLE_CALLBACK_HANDLER
1064 assert(
1065 !m_callbackHandler || m_callbackHandler->isAbortCalculation() ||
1066 (vertices.size() == exactCapacityVertices));
1067 assert(
1068 !m_callbackHandler || m_callbackHandler->isAbortCalculation() ||
1069 (triangles.size() == exactCapacityTriangles));
1070#else
1071 assert(vertices.size() == exactCapacityVertices);
1072 assert(triangles.size() == exactCapacityTriangles);
1073#endif
1074}
1075
1076template <typename T, typename TNearPointLocator>
1077template <
1078 typename TEdgeIter,
1079 typename TGetEdgeVertexStart,
1080 typename TGetEdgeVertexEnd>
1082 TEdgeIter first,
1083 const TEdgeIter last,
1084 TGetEdgeVertexStart getStart,
1085 TGetEdgeVertexEnd getEnd)
1086{
1087 if(isFinalized())
1088 handleException(FinalizedError(CDT_SOURCE_LOCATION));
1089
1090 std::vector<TriangulatePseudoPolygonTask> tppIterations;
1091 EdgeVec remaining;
1092 for(; first != last; ++first)
1093 {
1094#ifdef CDT_ENABLE_CALLBACK_HANDLER
1095 if(m_callbackHandler && m_callbackHandler->isAbortCalculation())
1096 {
1097 return;
1098 }
1099#endif
1100 // +3 to account for super-triangle vertices
1101 const Edge edge(
1102 VertInd(getStart(*first) + m_nTargetVerts),
1103 VertInd(getEnd(*first) + m_nTargetVerts));
1104 insertEdge(edge, edge, remaining, tppIterations);
1105 }
1106}
1107
1108template <typename T, typename TNearPointLocator>
1109template <
1110 typename TEdgeIter,
1111 typename TGetEdgeVertexStart,
1112 typename TGetEdgeVertexEnd>
1114 TEdgeIter first,
1115 const TEdgeIter last,
1116 TGetEdgeVertexStart getStart,
1117 TGetEdgeVertexEnd getEnd)
1118{
1119 if(isFinalized())
1120 handleException(FinalizedError(CDT_SOURCE_LOCATION));
1121
1122 tryInitNearestPointLocator();
1123 // state shared between different runs for performance gains
1124 std::vector<ConformToEdgeTask> remaining;
1125 for(; first != last; ++first)
1126 {
1127#ifdef CDT_ENABLE_CALLBACK_HANDLER
1128 if(m_callbackHandler && m_callbackHandler->isAbortCalculation())
1129 {
1130 return;
1131 }
1132#endif
1133 // +3 to account for super-triangle vertices
1134 const Edge e(
1135 VertInd(getStart(*first) + m_nTargetVerts),
1136 VertInd(getEnd(*first) + m_nTargetVerts));
1137 conformToEdge(e, EdgeVec(1, e), 0, remaining);
1138 }
1139}
1140
1141} // namespace CDT
1142
1143#ifndef CDT_USE_AS_COMPILED_LIBRARY
1144#include "Triangulation.hpp"
1145#endif
1146
1147#endif // header-guard
Utilities and helpers.
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.
Definition CDT.h:40
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.
Definition CDTUtils.h:330
unordered_set< Edge > EdgeUSet
Hash table of edges.
Definition CDTUtils.h:331
std::vector< TriInd > TriIndVec
Vector of triangle indices.
Definition CDTUtils.h:209
IndexSizeType VertInd
Vertex index.
Definition CDTUtils.h:191
unordered_set< TriInd > TriIndUSet
Hash table of triangles.
Definition CDTUtils.h:332
IndexSizeType TriInd
Triangle index.
Definition CDTUtils.h:193
std::vector< Triangle > TriangleVec
Vector of triangles.
Definition CDTUtils.h:395
What type of vertex is added to the triangulation.
Enum
The Enum itself.
@ UserInput
Original vertex from user input.
@ FixedEdgeMidpoint
During conforming triangulation edge mid-point is added.
@ FixedEdgesIntersection
Resolving fixed/constraint edges' intersection.
2D bounding box
Definition CDTUtils.h:216
Box2d< T > & envelopPoints(TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
Envelop box around a collection of custom points.
Definition CDTUtils.h:247
Edge connecting two vertices: vertex with smaller index is always first.
Definition CDTUtils.h:271
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.
Enum
The Enum itself.
@ 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)
Definition CDTUtils.h:344
2D vector
Definition CDTUtils.h:136
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.
SplitMix64RandGen()
default constructor
uint64 operator()()
functor's operator
unsigned long long uint64
uint64 type
SplitMix64RandGen(uint64 state)
constructor