11#include "portable_nth_element.hpp"
22typedef std::deque<TriInd> TriDeque;
29array<T, 3>
arr3(
const T& v0,
const T& v1,
const T& v2)
31 const array<T, 3> out = {v0, v1, v2};
38const std::size_t nTargetVerts = 0;
44const float minDistToConstraintEdge(0);
50template <
typename T,
typename TNearPo
intLocator>
52 : m_nTargetVerts(detail::defaults::nTargetVerts)
53 , m_superGeomType(detail::defaults::superGeomType)
54 , m_vertexInsertionOrder(detail::defaults::vertexInsertionOrder)
55 , m_intersectingEdgesStrategy(detail::defaults::intersectingEdgesStrategy)
56 , m_minDistToConstraintEdge(detail::defaults::minDistToConstraintEdge)
59template <
typename T,
typename TNearPo
intLocator>
62 : m_nTargetVerts(detail::defaults::nTargetVerts)
63 , m_superGeomType(detail::defaults::superGeomType)
64 , m_vertexInsertionOrder(vertexInsertionOrder)
65 , m_intersectingEdgesStrategy(detail::defaults::intersectingEdgesStrategy)
66 , m_minDistToConstraintEdge(detail::defaults::minDistToConstraintEdge)
69template <
typename T,
typename TNearPo
intLocator>
73 const T minDistToConstraintEdge)
74 : m_nTargetVerts(detail::defaults::nTargetVerts)
75 , m_superGeomType(detail::defaults::superGeomType)
76 , m_vertexInsertionOrder(vertexInsertionOrder)
77 , m_intersectingEdgesStrategy(intersectingEdgesStrategy)
78 , m_minDistToConstraintEdge(minDistToConstraintEdge)
81template <
typename T,
typename TNearPo
intLocator>
84 const TNearPointLocator& nearPtLocator,
86 const T minDistToConstraintEdge)
87 : m_nearPtLocator(nearPtLocator)
88 , m_nTargetVerts(detail::defaults::nTargetVerts)
89 , m_superGeomType(detail::defaults::superGeomType)
90 , m_vertexInsertionOrder(vertexInsertionOrder)
91 , m_intersectingEdgesStrategy(intersectingEdgesStrategy)
92 , m_minDistToConstraintEdge(minDistToConstraintEdge)
95template <
typename T,
typename TNearPo
intLocator>
98 if(m_dummyTris.empty())
100 const TriIndUSet dummySet(m_dummyTris.begin(), m_dummyTris.end());
102 triIndMap[noNeighbor] = noNeighbor;
103 for(
TriInd iT(0), iTnew(0); iT <
TriInd(triangles.size()); ++iT)
105 if(dummySet.count(iT))
107 triIndMap[iT] = iTnew;
108 triangles[iTnew] = triangles[iT];
111 triangles.erase(triangles.end() - dummySet.size(), triangles.end());
114 for(TriIndVec::iterator iT = m_vertTris.begin(); iT != m_vertTris.end();
117 *iT = triIndMap[*iT];
120 for(TriangleVec::iterator t = triangles.begin(); t != triangles.end(); ++t)
123 for(NeighborsArr3::iterator iN = nn.begin(); iN != nn.end(); ++iN)
124 *iN = triIndMap[*iN];
127 m_dummyTris = std::vector<TriInd>();
130template <
typename T,
typename TNearPo
intLocator>
143 finalizeTriangulation(toErase);
146template <
typename T,
typename TNearPo
intLocator>
150 assert(m_vertTris[0] != noNeighbor);
151 const std::stack<TriInd> seed(std::deque<TriInd>(1, m_vertTris[0]));
152 const TriIndUSet toErase = growToBoundary(seed);
153 finalizeTriangulation(toErase);
156template <
typename T,
typename TNearPo
intLocator>
159 const std::vector<LayerDepth> triDepths = calculateTriangleDepths();
161 toErase.reserve(triangles.size());
162 for(std::size_t iT = 0; iT != triangles.size(); ++iT)
164 if(triDepths[iT] % 2 == 0)
165 toErase.insert(
static_cast<TriInd>(iT));
167 finalizeTriangulation(toErase);
176template <
typename T,
typename TNearPo
intLocator>
180 if(removedTriangles.empty())
184 for(
TriInd iT(0), iTnew(0); iT <
TriInd(triangles.size()); ++iT)
186 if(removedTriangles.count(iT))
188 triIndMap[iT] = iTnew;
189 triangles[iTnew] = triangles[iT];
192 triangles.erase(triangles.end() - removedTriangles.size(), triangles.end());
194 for(
TriInd iT(0); iT < triangles.size(); ++iT)
199 for(NeighborsArr3::iterator n = nn.begin(); n != nn.end(); ++n)
201 if(removedTriangles.count(*n))
205 else if(*n != noNeighbor)
212template <
typename T,
typename TNearPo
intLocator>
218template <
typename T,
typename TNearPo
intLocator>
227 vertices.erase(vertices.begin(), vertices.begin() + 3);
231 typedef CDT::EdgeUSet::const_iterator It;
232 for(It e = fixedEdges.begin(); e != fixedEdges.end(); ++e)
236 fixedEdges = updatedFixedEdges;
239 unordered_map<Edge, BoundaryOverlapCount> updatedOverlapCount;
240 typedef unordered_map<Edge, BoundaryOverlapCount>::const_iterator
242 for(It it = overlapCount.begin(); it != overlapCount.end(); ++it)
244 updatedOverlapCount.insert(std::make_pair(
247 overlapCount = updatedOverlapCount;
250 unordered_map<Edge, EdgeVec> updatedPieceToOriginals;
251 typedef unordered_map<Edge, EdgeVec>::const_iterator It;
252 for(It it = pieceToOriginals.begin(); it != pieceToOriginals.end();
256 for(EdgeVec::iterator eeIt = ee.begin(); eeIt != ee.end();
261 updatedPieceToOriginals.insert(
264 pieceToOriginals = updatedPieceToOriginals;
268 removeTriangles(removedTriangles);
272 for(TriangleVec::iterator t = triangles.begin(); t != triangles.end();
276 for(VerticesArr3::iterator v = vv.begin(); v != vv.end(); ++v)
284template <
typename T,
typename TNearPo
intLocator>
287 m_nearPtLocator.initialize(vertices);
288 m_nTargetVerts = vertices.size();
292template <
typename T,
typename TNearPo
intLocator>
294 std::stack<TriInd> seeds)
const
297 while(!seeds.empty())
299 const TriInd iT = seeds.top();
301 traversed.insert(iT);
306 if(fixedEdges.count(opEdge))
309 if(iN != noNeighbor && traversed.count(iN) == 0)
316template <
typename T,
typename TNearPo
intLocator>
317void Triangulation<T, TNearPointLocator>::makeDummy(
const TriInd iT)
319 m_dummyTris.push_back(iT);
322template <
typename T,
typename TNearPo
intLocator>
323TriInd Triangulation<T, TNearPointLocator>::addTriangle(
const Triangle& t)
325 if(m_dummyTris.empty())
327 triangles.push_back(t);
328 return TriInd(triangles.size() - 1);
330 const TriInd nxtDummy = m_dummyTris.back();
331 m_dummyTris.pop_back();
332 triangles[nxtDummy] = t;
336template <
typename T,
typename TNearPo
intLocator>
337TriInd Triangulation<T, TNearPointLocator>::addTriangle()
339 if(m_dummyTris.empty())
341 const Triangle dummy = {
342 {noVertex, noVertex, noVertex},
343 {noNeighbor, noNeighbor, noNeighbor}};
344 triangles.push_back(dummy);
345 return TriInd(triangles.size() - 1);
347 const TriInd nxtDummy = m_dummyTris.back();
348 m_dummyTris.pop_back();
352template <
typename T,
typename TNearPo
intLocator>
354 const std::vector<Edge>& edges)
359template <
typename T,
typename TNearPo
intLocator>
361 const std::vector<Edge>& edges)
366template <
typename T,
typename TNearPo
intLocator>
369 if(!fixedEdges.insert(edge).second)
371 ++overlapCount[edge];
379template <
typename T,
typename Allocator1>
380void insert_unique(std::vector<T, Allocator1>& to,
const T& elem)
382 if(std::find(to.begin(), to.end(), elem) == to.end())
389template <
typename T,
typename Allocator1,
typename Allocator2>
391 std::vector<T, Allocator1>& to,
392 const std::vector<T, Allocator2>& from)
394 typedef typename std::vector<T, Allocator2>::const_iterator Cit;
395 to.reserve(to.size() + from.size());
396 for(Cit cit = from.begin(); cit != from.end(); ++cit)
398 insert_unique(to, *cit);
404template <
typename T,
typename TNearPo
intLocator>
405void Triangulation<T, TNearPointLocator>::fixEdge(
407 const Edge& originalEdge)
410 if(edge != originalEdge)
411 detail::insert_unique(pieceToOriginals[edge], originalEdge);
414template <
typename T,
typename TNearPo
intLocator>
415void Triangulation<T, TNearPointLocator>::fixEdge(
417 const BoundaryOverlapCount overlaps)
419 fixedEdges.insert(edge);
420 overlapCount[edge] = overlaps;
427T lerp(
const T& a,
const T& b,
const T t)
429 return (T(1) - t) * a + t * b;
434V2d<T> intersectionPosition(
440 using namespace predicates::adaptive;
444 const T a_cd = orient2d(c.x, c.y, d.x, d.y, a.x, a.y);
445 const T b_cd = orient2d(c.x, c.y, d.x, d.y, b.x, b.y);
446 const T t = a_cd / (a_cd - b_cd);
447 return V2d<T>::make(lerp(a.x, b.x, t), lerp(a.y, b.y, t));
451 const T c_ab = orient2d(a.x, a.y, b.x, b.y, c.x, c.y);
452 const T d_ab = orient2d(a.x, a.y, b.x, b.y, d.x, d.y);
453 const T t = c_ab / (c_ab - d_ab);
454 return V2d<T>::make(lerp(c.x, d.x, t), lerp(c.y, d.y, t));
460template <
typename T,
typename TNearPo
intLocator>
461IndexSizeType Triangulation<T, TNearPointLocator>::previousEdgeEncounter(
463 const std::vector<VertInd>& poly)
const
467 if(m_vertTris[v] != noNeighbor)
470 IndexSizeType i = poly.size() - 1;
478 if(poly[i + 1] == poly.back())
483template <
typename T,
typename TNearPo
intLocator>
484void Triangulation<T, TNearPointLocator>::insertEdgeIteration(
486 const Edge originalEdge,
488 std::vector<TriangulatePseudopolygonTask>& tppIterations)
497 fixEdge(edge, originalEdge);
501 const V2d<T>& a = vertices[iA];
502 const V2d<T>& b = vertices[iB];
503 const T distanceTolerance =
504 m_minDistToConstraintEdge == T(0)
506 : m_minDistToConstraintEdge *
distance(a, b);
511 tie(iT, iVL, iVR) = intersectedTriangle(iA, a, b, distanceTolerance);
515 const Edge edgePart(iA, iVL);
516 fixEdge(edgePart, originalEdge);
517 remaining.push_back(Edge(iVL, iB));
520 Triangle t = triangles[iT];
521 std::vector<TriInd> intersected(1, iT);
522 std::vector<VertInd> polyL, polyR;
523 std::vector<TriInd> outerTrisL, outerTrisR;
526 polyL.push_back(iVL);
530 polyR.push_back(iVR);
532 removeAdjacentTriangle(iVL);
533 removeAdjacentTriangle(iVR);
536 while(!t.containsVertex(iB))
539 const Triangle& tOpo = triangles[iTopo];
543 if(m_intersectingEdgesStrategy ==
545 fixedEdges.count(Edge(iVL, iVR)))
550 const Edge splitEdge(iVL, iVR);
551 const Edge half1(iVL, iNewVert);
552 const Edge half2(iNewVert, iVR);
553 const BoundaryOverlapCount overlaps = overlapCount[splitEdge];
555 fixedEdges.erase(splitEdge);
556 overlapCount.erase(splitEdge);
558 fixEdge(half1, overlaps);
559 fixEdge(half2, overlaps);
561 EdgeVec newOriginals(1, splitEdge);
562 const unordered_map<Edge, EdgeVec>::const_iterator originalsIt =
563 pieceToOriginals.find(splitEdge);
564 if(originalsIt != pieceToOriginals.end())
566 newOriginals = originalsIt->second;
567 pieceToOriginals.erase(originalsIt);
569 detail::insert_unique(pieceToOriginals[half1], newOriginals);
570 detail::insert_unique(pieceToOriginals[half2], newOriginals);
572 for(IndexSizeType i = 0; i < outerTrisL.size(); ++i)
573 setAdjacentTriangle(polyL[i + 1], outerTrisL[i]);
574 for(IndexSizeType i = 0; i < outerTrisR.size(); ++i)
575 setAdjacentTriangle(polyR[i + 1], outerTrisR[i]);
577 const V2d<T> newV = detail::intersectionPosition(
578 vertices[iA], vertices[iB], vertices[iVL], vertices[iVR]);
579 addNewVertex(newV, noNeighbor);
580 std::stack<TriInd> triStack =
581 insertVertexOnEdge(iNewVert, iT, iTopo);
582 tryAddVertexToLocator(iNewVert);
583 ensureDelaunayByEdgeFlips(newV, iNewVert, triStack);
586 remaining.push_back(Edge(iA, iNewVert));
587 remaining.push_back(Edge(iNewVert, iB));
593 if(loc == PtLineLocation::Left)
596 const IndexSizeType prev = previousEdgeEncounter(iVopo, polyL);
597 if(prev != invalidIndex)
599 outerTrisL[prev] = noNeighbor;
600 outerTrisL.push_back(noNeighbor);
604 outerTrisL.push_back(
edgeNeighbor(tOpo, polyL.back(), iVopo));
606 polyL.push_back(iVopo);
607 removeAdjacentTriangle(iVopo);
611 else if(loc == PtLineLocation::Right)
614 const IndexSizeType prev = previousEdgeEncounter(iVopo, polyR);
615 if(prev != invalidIndex)
617 outerTrisR[prev] = noNeighbor;
618 outerTrisR.push_back(noNeighbor);
622 outerTrisR.push_back(
edgeNeighbor(tOpo, polyR.back(), iVopo));
624 polyR.push_back(iVopo);
625 removeAdjacentTriangle(iVopo);
632 intersected.push_back(iTopo);
636 outerTrisL.push_back(
edgeNeighbor(t, polyL.back(), iB));
637 outerTrisR.push_back(
edgeNeighbor(t, polyR.back(), iB));
641 assert(!intersected.empty());
644 if(m_vertTris[iA] == intersected.front())
645 pivotVertexTriangleCW(iA);
646 if(m_vertTris[iB] == intersected.back())
647 pivotVertexTriangleCW(iB);
655 typedef std::vector<TriInd>::const_iterator TriIndCit;
656 for(TriIndCit it = intersected.begin(); it != intersected.end(); ++it)
659 std::reverse(polyR.begin(), polyR.end());
660 std::reverse(outerTrisR.begin(), outerTrisR.end());
661 const TriInd iTL = addTriangle();
662 const TriInd iTR = addTriangle();
663 triangulatePseudopolygon(polyL, outerTrisL, iTL, iTR, tppIterations);
664 triangulatePseudopolygon(polyR, outerTrisR, iTR, iTL, tppIterations);
669 const Edge edgePart(iA, iB);
670 fixEdge(edgePart, originalEdge);
671 remaining.push_back(Edge(iB, edge.v2()));
676 fixEdge(edge, originalEdge);
680template <
typename T,
typename TNearPo
intLocator>
681void Triangulation<T, TNearPointLocator>::insertEdge(
683 const Edge originalEdge,
685 std::vector<TriangulatePseudopolygonTask>& tppIterations)
689 remaining.push_back(edge);
690 while(!remaining.empty())
692 edge = remaining.back();
693 remaining.pop_back();
694 insertEdgeIteration(edge, originalEdge, remaining, tppIterations);
698template <
typename T,
typename TNearPo
intLocator>
699void Triangulation<T, TNearPointLocator>::conformToEdgeIteration(
702 BoundaryOverlapCount overlaps,
703 std::vector<ConformToEdgeTask>& remaining)
712 overlaps > 0 ? fixEdge(edge, overlaps) : fixEdge(edge);
714 if(!originals.empty() && edge != originals.front())
716 detail::insert_unique(pieceToOriginals[edge], originals);
721 const V2d<T>& a = vertices[iA];
722 const V2d<T>& b = vertices[iB];
723 const T distanceTolerance =
724 m_minDistToConstraintEdge == T(0)
726 : m_minDistToConstraintEdge *
distance(a, b);
729 tie(iT, iVleft, iVright) = intersectedTriangle(iA, a, b, distanceTolerance);
733 const Edge edgePart(iA, iVleft);
734 overlaps > 0 ? fixEdge(edgePart, overlaps) : fixEdge(edgePart);
735 detail::insert_unique(pieceToOriginals[edgePart], originals);
736#ifdef CDT_CXX11_IS_SUPPORTED
737 remaining.emplace_back(Edge(iVleft, iB), originals, overlaps);
739 remaining.push_back(make_tuple(Edge(iVleft, iB), originals, overlaps));
745 Triangle t = triangles[iT];
746 while(std::find(t.vertices.begin(), t.vertices.end(), iB) ==
750 const Triangle& tOpo = triangles[iTopo];
752 const V2d<T> vOpo = vertices[iVopo];
755 if(m_intersectingEdgesStrategy ==
757 fixedEdges.count(Edge(iVleft, iVright)))
762 const Edge splitEdge(iVleft, iVright);
763 const Edge half1(iVleft, iNewVert);
764 const Edge half2(iNewVert, iVright);
766 const unordered_map<Edge, BoundaryOverlapCount>::const_iterator
767 splitEdgeOverlapsIt = overlapCount.find(splitEdge);
768 const BoundaryOverlapCount splitEdgeOverlaps =
769 splitEdgeOverlapsIt != overlapCount.end()
770 ? splitEdgeOverlapsIt->second
774 fixedEdges.erase(splitEdge);
775 if(splitEdgeOverlaps > 0)
777 overlapCount.erase(splitEdgeOverlapsIt);
778 fixEdge(half1, splitEdgeOverlaps);
779 fixEdge(half2, splitEdgeOverlaps);
787 EdgeVec newOriginals(1, splitEdge);
788 const unordered_map<Edge, EdgeVec>::const_iterator originalsIt =
789 pieceToOriginals.find(splitEdge);
790 if(originalsIt != pieceToOriginals.end())
792 newOriginals = originalsIt->second;
793 pieceToOriginals.erase(originalsIt);
795 detail::insert_unique(pieceToOriginals[half1], newOriginals);
796 detail::insert_unique(pieceToOriginals[half2], newOriginals);
799 const V2d<T> newV = detail::intersectionPosition(
804 addNewVertex(newV, noNeighbor);
805 std::stack<TriInd> triStack =
806 insertVertexOnEdge(iNewVert, iT, iTopo);
807 tryAddVertexToLocator(iNewVert);
808 ensureDelaunayByEdgeFlips(newV, iNewVert, triStack);
809#ifdef CDT_CXX11_IS_SUPPORTED
810 remaining.emplace_back(Edge(iNewVert, iB), originals, overlaps);
811 remaining.emplace_back(Edge(iA, iNewVert), originals, overlaps);
814 make_tuple(Edge(iNewVert, iB), originals, overlaps));
816 make_tuple(Edge(iA, iNewVert), originals, overlaps));
826 if(loc == PtLineLocation::Left)
831 else if(loc == PtLineLocation::Right)
843#ifdef CDT_CXX11_IS_SUPPORTED
844 remaining.emplace_back(Edge(iB, edge.v2()), originals, overlaps);
847 make_tuple(Edge(iB, edge.v2()), originals, overlaps));
853 const V2d<T>& start = vertices[iA];
854 const V2d<T>& end = vertices[iB];
856 V2d<T>::make((start.x + end.x) / T(2), (start.y + end.y) / T(2)),
858 const std::vector<Edge> flippedFixedEdges =
859 insertVertex_FlipFixedEdges(iMid);
861#ifdef CDT_CXX11_IS_SUPPORTED
862 remaining.emplace_back(Edge(iMid, iB), originals, overlaps);
863 remaining.emplace_back(Edge(iA, iMid), originals, overlaps);
865 remaining.push_back(make_tuple(Edge(iMid, iB), originals, overlaps));
866 remaining.push_back(make_tuple(Edge(iA, iMid), originals, overlaps));
871 for(std::vector<Edge>::const_iterator it = flippedFixedEdges.begin();
872 it != flippedFixedEdges.end();
875 const Edge& flippedFixedEdge = *it;
876 fixedEdges.erase(flippedFixedEdge);
878 BoundaryOverlapCount prevOverlaps = 0;
879 const unordered_map<Edge, BoundaryOverlapCount>::const_iterator
880 overlapsIt = overlapCount.find(flippedFixedEdge);
881 if(overlapsIt != overlapCount.end())
883 prevOverlaps = overlapsIt->second;
884 overlapCount.erase(overlapsIt);
887 EdgeVec prevOriginals(1, flippedFixedEdge);
888 const unordered_map<Edge, EdgeVec>::const_iterator originalsIt =
889 pieceToOriginals.find(flippedFixedEdge);
890 if(originalsIt != pieceToOriginals.end())
892 prevOriginals = originalsIt->second;
894#ifdef CDT_CXX11_IS_SUPPORTED
895 remaining.emplace_back(flippedFixedEdge, prevOriginals, prevOverlaps);
898 make_tuple(flippedFixedEdge, prevOriginals, prevOverlaps));
903template <
typename T,
typename TNearPo
intLocator>
904void Triangulation<T, TNearPointLocator>::conformToEdge(
907 BoundaryOverlapCount overlaps,
908 std::vector<ConformToEdgeTask>& remaining)
912#ifdef CDT_CXX11_IS_SUPPORTED
913 remaining.emplace_back(edge, originals, overlaps);
915 remaining.push_back(make_tuple(edge, originals, overlaps));
917 while(!remaining.empty())
919 tie(edge, originals, overlaps) = remaining.back();
920 remaining.pop_back();
921 conformToEdgeIteration(edge, originals, overlaps, remaining);
935template <
typename T,
typename TNearPo
intLocator>
936tuple<TriInd, VertInd, VertInd>
937Triangulation<T, TNearPointLocator>::intersectedTriangle(
941 const T orientationTolerance)
const
943 const TriInd startTri = m_vertTris[iA];
947 const Triangle t = triangles[iT];
950 const T orientP2 =
orient2D(vertices[iP2], a, b);
952 if(locP2 == PtLineLocation::Right)
955 const T orientP1 =
orient2D(vertices[iP1], a, b);
957 if(locP1 == PtLineLocation::OnLine)
959 return make_tuple(noNeighbor, iP1, iP1);
961 if(locP1 == PtLineLocation::Left)
963 if(orientationTolerance)
967 if(std::abs(orientP1) <= std::abs(orientP2))
969 closestOrient = orientP1;
974 closestOrient = orientP2;
978 closestOrient, orientationTolerance) ==
979 PtLineLocation::OnLine)
981 return make_tuple(noNeighbor, iClosestP, iClosestP);
984 return make_tuple(iT, iP1, iP2);
987 iT = t.next(iA).first;
988 }
while(iT != startTri);
989 throw std::runtime_error(
"Could not find vertex triangle intersected by "
990 "edge. Note: can be caused by duplicate points.");
993template <
typename T,
typename TNearPo
intLocator>
994void Triangulation<T, TNearPointLocator>::addSuperTriangle(
const Box2d<T>& box)
999 const V2d<T> center = {
1000 (box.min.x + box.max.x) / T(2), (box.min.y + box.max.y) / T(2)};
1001 const T w = box.max.x - box.min.x;
1002 const T h = box.max.y - box.min.y;
1003 T r = std::sqrt(w * w + h * h) / T(2);
1005 const T R = T(2) * r;
1006 const T shiftX = R * std::sqrt(T(3)) / T(2);
1007 const V2d<T> posV1 = {center.x - shiftX, center.y - r};
1008 const V2d<T> posV2 = {center.x + shiftX, center.y - r};
1009 const V2d<T> posV3 = {center.x, center.y + R};
1010 addNewVertex(posV1,
TriInd(0));
1011 addNewVertex(posV2,
TriInd(0));
1012 addNewVertex(posV3,
TriInd(0));
1013 const Triangle superTri = {
1015 {noNeighbor, noNeighbor, noNeighbor}};
1016 addTriangle(superTri);
1019 m_nearPtLocator.initialize(vertices);
1023template <
typename T,
typename TNearPo
intLocator>
1024void Triangulation<T, TNearPointLocator>::addNewVertex(
1028 vertices.push_back(pos);
1029 m_vertTris.push_back(iT);
1032template <
typename T,
typename TNearPo
intLocator>
1034Triangulation<T, TNearPointLocator>::insertVertex_FlipFixedEdges(
1037 std::vector<Edge> flippedFixedEdges;
1039 const V2d<T>& v1 = vertices[iV1];
1040 const VertInd startVertex = m_nearPtLocator.nearPoint(v1, vertices);
1041 array<TriInd, 2> trisAt = walkingSearchTrianglesAt(v1, startVertex);
1042 std::stack<TriInd> triStack =
1043 trisAt[1] == noNeighbor ? insertVertexInsideTriangle(iV1, trisAt[0])
1044 : insertVertexOnEdge(iV1, trisAt[0], trisAt[1]);
1046 TriInd iTopo, n1, n2, n3, n4;
1048 while(!triStack.empty())
1050 const TriInd iT = triStack.top();
1053 edgeFlipInfo(iT, iV1, iTopo, iV2, iV3, iV4, n1, n2, n3, n4);
1054 if(iTopo != noNeighbor && isFlipNeeded(v1, iV1, iV2, iV3, iV4))
1057 const Edge flippedEdge(iV2, iV4);
1058 if(!fixedEdges.empty() &&
1059 fixedEdges.find(flippedEdge) != fixedEdges.end())
1061 flippedFixedEdges.push_back(flippedEdge);
1064 flipEdge(iT, iTopo, iV1, iV2, iV3, iV4, n1, n2, n3, n4);
1066 triStack.push(iTopo);
1070 tryAddVertexToLocator(iV1);
1071 return flippedFixedEdges;
1074template <
typename T,
typename TNearPo
intLocator>
1075void Triangulation<T, TNearPointLocator>::insertVertex(
1079 const V2d<T>& v = vertices[iVert];
1080 const array<TriInd, 2> trisAt = walkingSearchTrianglesAt(v, walkStart);
1081 std::stack<TriInd> triStack =
1082 trisAt[1] == noNeighbor
1083 ? insertVertexInsideTriangle(iVert, trisAt[0])
1084 : insertVertexOnEdge(iVert, trisAt[0], trisAt[1]);
1085 ensureDelaunayByEdgeFlips(v, iVert, triStack);
1088template <
typename T,
typename TNearPo
intLocator>
1089void Triangulation<T, TNearPointLocator>::insertVertex(
const VertInd iVert)
1091 const V2d<T>& v = vertices[iVert];
1092 const VertInd walkStart = m_nearPtLocator.nearPoint(v, vertices);
1093 insertVertex(iVert, walkStart);
1094 tryAddVertexToLocator(iVert);
1097template <
typename T,
typename TNearPo
intLocator>
1098void Triangulation<T, TNearPointLocator>::ensureDelaunayByEdgeFlips(
1101 std::stack<TriInd>& triStack)
1103 TriInd iTopo, n1, n2, n3, n4;
1105 while(!triStack.empty())
1107 const TriInd iT = triStack.top();
1110 edgeFlipInfo(iT, iV1, iTopo, iV2, iV3, iV4, n1, n2, n3, n4);
1111 if(iTopo != noNeighbor && isFlipNeeded(v1, iV1, iV2, iV3, iV4))
1113 flipEdge(iT, iTopo, iV1, iV2, iV3, iV4, n1, n2, n3, n4);
1115 triStack.push(iTopo);
1133template <
typename T,
typename TNearPo
intLocator>
1134void Triangulation<T, TNearPointLocator>::edgeFlipInfo(
1151 const Triangle& t = triangles[iT];
1152 if(t.vertices[0] == iV1)
1154 iV2 = t.vertices[1];
1155 iV4 = t.vertices[2];
1156 n1 = t.neighbors[0];
1157 n3 = t.neighbors[2];
1158 iTopo = t.neighbors[1];
1160 else if(t.vertices[1] == iV1)
1162 iV2 = t.vertices[2];
1163 iV4 = t.vertices[0];
1164 n1 = t.neighbors[1];
1165 n3 = t.neighbors[0];
1166 iTopo = t.neighbors[2];
1170 iV2 = t.vertices[0];
1171 iV4 = t.vertices[1];
1172 n1 = t.neighbors[2];
1173 n3 = t.neighbors[1];
1174 iTopo = t.neighbors[0];
1176 if(iTopo == noNeighbor)
1178 const Triangle& tOpo = triangles[iTopo];
1179 if(tOpo.neighbors[0] == iT)
1181 iV3 = tOpo.vertices[2];
1182 n2 = tOpo.neighbors[1];
1183 n4 = tOpo.neighbors[2];
1185 else if(tOpo.neighbors[1] == iT)
1187 iV3 = tOpo.vertices[0];
1188 n2 = tOpo.neighbors[2];
1189 n4 = tOpo.neighbors[0];
1193 iV3 = tOpo.vertices[1];
1194 n2 = tOpo.neighbors[0];
1195 n4 = tOpo.neighbors[1];
1222template <
typename T,
typename TNearPo
intLocator>
1223bool Triangulation<T, TNearPointLocator>::isFlipNeeded(
1230 if(fixedEdges.count(Edge(iV2, iV4)))
1232 const V2d<T>& v2 = vertices[iV2];
1233 const V2d<T>& v3 = vertices[iV3];
1234 const V2d<T>& v4 = vertices[iV4];
1286template <
typename T,
typename TNearPo
intLocator>
1304 changeNeighbor(n1, iT, iTopo);
1305 changeNeighbor(n4, iTopo, iT);
1311 setAdjacentTriangle(v4, iT);
1312 setAdjacentTriangle(v2, iTopo);
1332template <
typename T,
typename TNearPo
intLocator>
1334Triangulation<T, TNearPointLocator>::insertVertexInsideTriangle(
1338 const TriInd iNewT1 = addTriangle();
1339 const TriInd iNewT2 = addTriangle();
1341 Triangle& t = triangles[iT];
1342 const array<VertInd, 3> vv = t.vertices;
1343 const array<TriInd, 3> nn = t.neighbors;
1344 const VertInd v1 = vv[0], v2 = vv[1], v3 = vv[2];
1345 const TriInd n1 = nn[0], n2 = nn[1], n3 = nn[2];
1353 setAdjacentTriangle(v, iT);
1354 setAdjacentTriangle(v3, iNewT1);
1356 changeNeighbor(n2, iT, iNewT1);
1357 changeNeighbor(n3, iT, iNewT2);
1359 std::stack<TriInd> newTriangles;
1360 newTriangles.push(iT);
1361 newTriangles.push(iNewT1);
1362 newTriangles.push(iNewT2);
1363 return newTriangles;
1379template <
typename T,
typename TNearPo
intLocator>
1380std::stack<TriInd> Triangulation<T, TNearPointLocator>::insertVertexOnEdge(
1385 const TriInd iTnew1 = addTriangle();
1386 const TriInd iTnew2 = addTriangle();
1388 Triangle& t1 = triangles[iT1];
1389 Triangle& t2 = triangles[iT2];
1391 const VertInd v1 = t1.vertices[i];
1393 const TriInd n1 = t1.neighbors[i];
1394 const TriInd n4 = t1.neighbors[
cw(i)];
1396 const VertInd v3 = t2.vertices[i];
1398 const TriInd n3 = t2.neighbors[i];
1399 const TriInd n2 = t2.neighbors[
cw(i)];
1407 setAdjacentTriangle(v, iT1);
1408 setAdjacentTriangle(v4, iTnew1);
1410 changeNeighbor(n4, iT1, iTnew1);
1411 changeNeighbor(n3, iT2, iTnew2);
1413 std::stack<TriInd> newTriangles;
1414 newTriangles.push(iT1);
1415 newTriangles.push(iTnew2);
1416 newTriangles.push(iT2);
1417 newTriangles.push(iTnew1);
1418 return newTriangles;
1421template <
typename T,
typename TNearPo
intLocator>
1423Triangulation<T, TNearPointLocator>::trianglesAt(
const V2d<T>& pos)
const
1425 array<TriInd, 2> out = {noNeighbor, noNeighbor};
1428 const Triangle& t = triangles[i];
1429 const V2d<T>& v1 = vertices[t.vertices[0]];
1430 const V2d<T>& v2 = vertices[t.vertices[1]];
1431 const V2d<T>& v3 = vertices[t.vertices[2]];
1433 if(loc == PtTriLocation::Outside)
1440 throw std::runtime_error(
"No triangle was found at position");
1443template <
typename T,
typename TNearPo
intLocator>
1444TriInd Triangulation<T, TNearPointLocator>::walkTriangles(
1446 const V2d<T>& pos)
const
1449 TriInd currTri = m_vertTris[startVertex];
1451 detail::SplitMix64RandGen prng;
1454 const Triangle& t = triangles[currTri];
1457 const Index offset(prng() % 3);
1460 const Index i((i_ + offset) % 3);
1461 const V2d<T>& vStart = vertices[t.vertices[i]];
1462 const V2d<T>& vEnd = vertices[t.vertices[
ccw(i)]];
1465 const TriInd iN = t.neighbors[i];
1466 if(edgeCheck == PtLineLocation::Right && iN != noNeighbor)
1469 currTri = t.neighbors[i];
1477template <
typename T,
typename TNearPo
intLocator>
1478array<TriInd, 2> Triangulation<T, TNearPointLocator>::walkingSearchTrianglesAt(
1480 const VertInd startVertex)
const
1482 array<TriInd, 2> out = {noNeighbor, noNeighbor};
1483 const TriInd iT = walkTriangles(startVertex, pos);
1485 const Triangle& t = triangles[iT];
1486 const V2d<T>& v1 = vertices[t.vertices[0]];
1487 const V2d<T>& v2 = vertices[t.vertices[1]];
1488 const V2d<T>& v3 = vertices[t.vertices[2]];
1490 if(loc == PtTriLocation::Outside)
1491 throw std::runtime_error(
"No triangle was found at position");
1514template <
typename T,
typename TNearPo
intLocator>
1521 const array<TriInd, 3>& triNs = t.
neighbors;
1522 const array<TriInd, 3>& triOpoNs = tOpo.
neighbors;
1523 const array<VertInd, 3>& triVs = t.
vertices;
1524 const array<VertInd, 3>& triOpoVs = tOpo.
vertices;
1529 const TriInd n1 = triNs[i];
1532 const VertInd v3 = triOpoVs[i];
1534 const TriInd n4 = triOpoNs[i];
1541 changeNeighbor(n1, iT, iTopo);
1542 changeNeighbor(n4, iTopo, iT);
1548 setAdjacentTriangle(v4, iT);
1549 setAdjacentTriangle(v2, iTopo);
1553template <
typename T,
typename TNearPo
intLocator>
1556 const TriInd oldNeighbor,
1557 const TriInd newNeighbor)
1559 if(iT == noNeighbor)
1563 nn[0] == oldNeighbor || nn[1] == oldNeighbor || nn[2] == oldNeighbor);
1564 if(nn[0] == oldNeighbor)
1565 nn[0] = newNeighbor;
1566 else if(nn[1] == oldNeighbor)
1567 nn[1] = newNeighbor;
1569 nn[2] = newNeighbor;
1572template <
typename T,
typename TNearPo
intLocator>
1573void Triangulation<T, TNearPointLocator>::changeNeighbor(
1577 const TriInd newNeighbor)
1579 assert(iT != noNeighbor);
1580 Triangle& t = triangles[iT];
1581 t.neighbors[
edgeNeighborInd(t.vertices, iVedge1, iVedge2)] = newNeighbor;
1584template <
typename T,
typename TNearPo
intLocator>
1585void Triangulation<T, TNearPointLocator>::triangulatePseudopolygon(
1586 const std::vector<VertInd>& poly,
1587 const std::vector<TriInd>& outerTris,
1590 std::vector<TriangulatePseudopolygonTask>& iterations)
1592 assert(poly.size() > 2);
1595 iterations.push_back(make_tuple(0, poly.size() - 1, iT, iN,
Index(0)));
1596 while(!iterations.empty())
1598 triangulatePseudopolygonIteration(poly, outerTris, iterations);
1602template <
typename T,
typename TNearPo
intLocator>
1603void Triangulation<T, TNearPointLocator>::triangulatePseudopolygonIteration(
1604 const std::vector<VertInd>& poly,
1605 const std::vector<TriInd>& outerTris,
1606 std::vector<TriangulatePseudopolygonTask>& iterations)
1608 IndexSizeType iA, iB;
1611 assert(!iterations.empty());
1612 tie(iA, iB, iT, iParent, iInParent) = iterations.back();
1613 iterations.pop_back();
1614 assert(iB - iA > 1 && iT != noNeighbor && iParent != noNeighbor);
1615 Triangle& t = triangles[iT];
1617 const IndexSizeType iC = findDelaunayPoint(poly, iA, iB);
1630 const TriInd iNext = addTriangle();
1631 iterations.push_back(make_tuple(iC, iB, iNext, iT,
Index(1)));
1635 const TriInd outerTri = outerTris[iC];
1636 if(outerTri != noNeighbor)
1638 assert(outerTri != iT);
1639 t.neighbors[1] = outerTri;
1640 changeNeighbor(outerTri, c, b, iT);
1646 const TriInd iNext = addTriangle();
1647 iterations.push_back(make_tuple(iA, iC, iNext, iT,
Index(2)));
1652 outerTris[iA] != noNeighbor ? outerTris[iA] : m_vertTris[c];
1653 if(outerTri != noNeighbor)
1655 assert(outerTri != iT);
1656 t.neighbors[2] = outerTri;
1657 changeNeighbor(outerTri, c, a, iT);
1663 triangles[iParent].neighbors[iInParent] = iT;
1664 t.neighbors[0] = iParent;
1665 t.vertices = detail::arr3(a, b, c);
1667 setAdjacentTriangle(c, iT);
1670template <
typename T,
typename TNearPo
intLocator>
1671IndexSizeType Triangulation<T, TNearPointLocator>::findDelaunayPoint(
1672 const std::vector<VertInd>& poly,
1673 const IndexSizeType iA,
1674 const IndexSizeType iB)
const
1676 assert(iB - iA > 1);
1677 const V2d<T>& a = vertices[poly[iA]];
1678 const V2d<T>& b = vertices[poly[iB]];
1679 IndexSizeType out = iA + 1;
1680 const V2d<T>* c = &vertices[poly[out]];
1681 for(IndexSizeType i = iA + 1; i < iB; ++i)
1683 const V2d<T>& v = vertices[poly[i]];
1690 assert(out > iA && out < iB);
1694template <
typename T,
typename TNearPo
intLocator>
1696 const std::vector<
V2d<T> >& newVertices)
1698 return insertVertices(
1699 newVertices.begin(), newVertices.end(), getX_V2d<T>, getY_V2d<T>);
1702template <
typename T,
typename TNearPo
intLocator>
1705 return m_vertTris.empty() && !vertices.empty();
1708template <
typename T,
typename TNearPo
intLocator>
1709unordered_map<TriInd, LayerDepth>
1711 std::stack<TriInd> seeds,
1713 std::vector<LayerDepth>& triDepths)
const
1715 unordered_map<TriInd, LayerDepth> behindBoundary;
1716 while(!seeds.empty())
1718 const TriInd iT = seeds.top();
1720 triDepths[iT] = layerDepth;
1721 behindBoundary.erase(iT);
1727 if(iN == noNeighbor || triDepths[iN] <= layerDepth)
1729 if(fixedEdges.count(opEdge))
1731 const unordered_map<Edge, LayerDepth>::const_iterator cit =
1732 overlapCount.find(opEdge);
1733 const LayerDepth triDepth = cit == overlapCount.end()
1735 : layerDepth + cit->second + 1;
1736 behindBoundary[iN] = triDepth;
1742 return behindBoundary;
1745template <
typename T,
typename TNearPo
intLocator>
1746std::vector<LayerDepth>
1749 std::vector<LayerDepth> triDepths(
1750 triangles.size(), std::numeric_limits<LayerDepth>::max());
1751 std::stack<TriInd> seeds(TriDeque(1, m_vertTris[0]));
1755 unordered_map<LayerDepth, TriIndUSet> seedsByDepth;
1758 const unordered_map<TriInd, LayerDepth>& newSeeds =
1759 peelLayer(seeds, layerDepth, triDepths);
1761 seedsByDepth.erase(layerDepth);
1762 typedef unordered_map<TriInd, LayerDepth>::const_iterator Iter;
1763 for(Iter it = newSeeds.begin(); it != newSeeds.end(); ++it)
1765 deepestSeedDepth = std::max(deepestSeedDepth, it->second);
1766 seedsByDepth[it->second].insert(it->first);
1768 const TriIndUSet& nextLayerSeeds = seedsByDepth[layerDepth + 1];
1769 seeds = std::stack<TriInd>(
1770 TriDeque(nextLayerSeeds.begin(), nextLayerSeeds.end()));
1772 }
while(!seeds.empty() || deepestSeedDepth > layerDepth);
1777template <
typename T,
typename TNearPo
intLocator>
1781 for(
VertInd iV = superGeomVertCount; iV < vertices.size(); ++iV)
1787template <
typename T,
typename TNearPo
intLocator>
1788void Triangulation<T, TNearPointLocator>::insertVertices_Randomized(
1791 std::size_t vertexCount = vertices.size() - superGeomVertCount;
1792 std::vector<VertInd> ii(vertexCount);
1793 detail::iota(ii.begin(), ii.end(), superGeomVertCount);
1794 detail::random_shuffle(ii.begin(), ii.end());
1795 for(std::vector<VertInd>::iterator it = ii.begin(); it != ii.end(); ++it)
1805template <
typename T>
1806inline double log2_bc(T x)
1808#ifdef CDT_CXX11_IS_SUPPORTED
1809 return std::log2(x);
1811 static double log2_constant = std::log(2.0);
1812 return std::log(
static_cast<double>(x)) / log2_constant;
1822 int filledLayerPow2 = std::floor(log2_bc(vertexCount)) - 1;
1823 std::size_t nodesInFilledTree = std::pow(2., filledLayerPow2 + 1) - 1;
1824 std::size_t nodesInLastFilledLayer = std::pow(2., filledLayerPow2);
1825 std::size_t nodesInLastLayer = vertexCount - nodesInFilledTree;
1826 return nodesInLastLayer >= nodesInLastFilledLayer
1827 ? nodesInLastFilledLayer + nodesInLastLayer -
1828 nodesInLastFilledLayer
1829 : nodesInLastFilledLayer;
1832template <
typename T>
1838 , m_front(m_vec.begin())
1839 , m_back(m_vec.begin())
1846 const T& front()
const
1854 if(m_front == m_vec.end())
1855 m_front = m_vec.begin();
1858 void push(
const T& t)
1860 assert(m_size < m_vec.size());
1863 if(m_back == m_vec.end())
1864 m_back = m_vec.begin();
1867#ifdef CDT_CXX11_IS_SUPPORTED
1868 void push(
const T&& t)
1870 assert(m_size < m_vec.size());
1873 if(m_back == m_vec.end())
1874 m_back = m_vec.begin();
1879 std::vector<T> m_vec;
1880 typename std::vector<T>::iterator m_front;
1881 typename std::vector<T>::iterator m_back;
1885template <
typename T>
1889 : vertices(vertices)
1893 return vertices[a].x < vertices[b].x;
1895 const std::vector<V2d<T> >& vertices;
1898template <
typename T>
1902 : vertices(vertices)
1906 return vertices[a].y < vertices[b].y;
1908 const std::vector<V2d<T> >& vertices;
1913template <
typename T,
typename TNearPo
intLocator>
1920 std::size_t vertexCount = vertices.size() - superGeomVertCount;
1921 std::vector<VertInd> ii(vertexCount);
1922 detail::iota(ii.begin(), ii.end(), superGeomVertCount);
1924 typedef std::vector<VertInd>::iterator It;
1926 detail::maxQueueLengthBFSKDTree(vertexCount));
1927 queue.push(make_tuple(ii.begin(), ii.end(), boxMin, boxMax,
VertInd(0)));
1930 V2d<T> newBoxMin, newBoxMax;
1936 while(!queue.empty())
1938 tie(first, last, boxMin, boxMax, parent) = queue.front();
1940 assert(first != last);
1942 const std::ptrdiff_t len = std::distance(first, last);
1945 insertVertex(*first, parent);
1948 const It midIt = first + len / 2;
1949 if(boxMax.
x - boxMin.
x >= boxMax.
y - boxMin.
y)
1951 detail::portable_nth_element(first, midIt, last, cmpX);
1953 const T split = vertices[mid].x;
1954 newBoxMin.
x = split;
1955 newBoxMin.
y = boxMin.
y;
1956 newBoxMax.
x = split;
1957 newBoxMax.
y = boxMax.
y;
1961 detail::portable_nth_element(first, midIt, last, cmpY);
1963 const T split = vertices[mid].y;
1964 newBoxMin.
x = boxMin.
x;
1965 newBoxMin.
y = split;
1966 newBoxMax.
x = boxMax.
x;
1967 newBoxMax.
y = split;
1969 insertVertex(mid, parent);
1972 queue.push(make_tuple(first, midIt, boxMin, newBoxMax, mid));
1974 if(midIt + 1 != last)
1976 queue.push(make_tuple(midIt + 1, last, newBoxMin, boxMax, mid));
1981template <
typename T,
typename TNearPo
intLocator>
1982bool Triangulation<T, TNearPointLocator>::hasEdge(
1986 const TriInd triStart = m_vertTris[a];
1987 assert(triStart != noNeighbor);
1992 const Triangle& t = triangles[iT];
1993 tie(iT, iV) = t.
next(a);
1994 assert(iT != noNeighbor);
1997 }
while(iT != triStart);
2001template <
typename T,
typename TNearPo
intLocator>
2002void Triangulation<T, TNearPointLocator>::setAdjacentTriangle(
2006 assert(t != noNeighbor);
2009 triangles[t].vertices[0] == v || triangles[t].vertices[1] == v ||
2010 triangles[t].vertices[2] == v);
2013template <
typename T,
typename TNearPo
intLocator>
2014void Triangulation<T, TNearPointLocator>::pivotVertexTriangleCW(
const VertInd v)
2016 assert(m_vertTris[v] != noNeighbor);
2017 m_vertTris[v] = triangles[m_vertTris[v]].next(v).first;
2018 assert(m_vertTris[v] != noNeighbor);
2020 triangles[m_vertTris[v]].vertices[0] == v ||
2021 triangles[m_vertTris[v]].vertices[1] == v ||
2022 triangles[m_vertTris[v]].vertices[2] == v);
2025template <
typename T,
typename TNearPo
intLocator>
2026void Triangulation<T, TNearPointLocator>::removeAdjacentTriangle(
2029 m_vertTris[v] = noNeighbor;
2032template <
typename T,
typename TNearPo
intLocator>
2033void Triangulation<T, TNearPointLocator>::tryAddVertexToLocator(
const VertInd v)
2035 if(!m_nearPtLocator.empty())
2036 m_nearPtLocator.addPoint(v, vertices);
2039template <
typename T,
typename TNearPo
intLocator>
2040void Triangulation<T, TNearPointLocator>::tryInitNearestPointLocator()
2042 if(!vertices.empty() && m_nearPtLocator.empty())
2044 m_nearPtLocator.initialize(vertices);
array< T, 3 > arr3(const T &v0, const T &v1, const T &v2)
Needed for c++03 compatibility (no uniform initialization available)
std::size_t maxQueueLengthBFSKDTree(const std::size_t vertexCount)
Since KD-tree bulk load builds a balanced tree the maximum length of a queue can be pre-calculated: i...
Data structure representing a 2D constrained Delaunay triangulation.
void eraseOuterTriangles()
Erase triangles outside of constrained boundary using growing.
void conformToEdges(TEdgeIter first, TEdgeIter last, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd)
Ensure that triangulation conforms to constraints (fixed edges)
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.
void eraseOuterTrianglesAndHoles()
Erase triangles outside of constrained boundary and auto-detected holes.
void insertEdges(TEdgeIter first, TEdgeIter last, TGetEdgeVertexStart getStart, TGetEdgeVertexEnd getEnd)
Insert constraints (custom-type fixed edges) into triangulation.
void insertVertices(TVertexIter first, TVertexIter last, TGetVertexCoordX getX, TGetVertexCoordY getY)
Insert custom point-types specified by iterator range and X/Y-getters.
void eraseSuperTriangle()
Erase triangles adjacent to super triangle.
Triangulation()
Default constructor.
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.
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.
unordered_set< Edge > EdgeUSet
Hash table of edges.
VertInd edge_get_v2(const Edge &e)
Get edge second vertex.
std::vector< TriInd > TriIndVec
Vector of triangle indices.
CDT_INLINE_IF_HEADER_ONLY Index edgeNeighborInd(const VerticesArr3 &vv, VertInd iVedge1, VertInd iVedge2)
Index of triangle's neighbor opposed to an edge.
VertInd edge_get_v1(const Edge &e)
Get edge first vertex.
CDT_EXPORT PtLineLocation::Enum classifyOrientation(T orientation, T orientationTolerance=T(0))
Classify value of orient2d predicate.
array< TriInd, 3 > NeighborsArr3
array of three neighbors
CDT_EXPORT T distance(const V2d< T > &a, const V2d< T > &b)
Distance between two 2D points.
IndexSizeType VertInd
Vertex index.
CDT_EXPORT Index cw(Index i)
Advance vertex or neighbor index clockwise.
array< VertInd, 3 > VerticesArr3
array of three vertex indices
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 vertexInd(const VerticesArr3 &vv, VertInd iV)
If triangle has a given vertex return vertex-index.
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.
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.
CDT_EXPORT T distanceSquared(const V2d< T > &a, const V2d< T > &b)
Squared distance between two 2D points.
unordered_set< TriInd > TriIndUSet
Hash table of triangles.
CDT_EXPORT Index ccw(Index i)
Advance vertex or neighbor index counter-clockwise.
CDT_EXPORT Index edgeNeighbor(PtTriLocation::Enum location)
Neighbor index from a on-edge location.
unordered_map< TriInd, TriInd > TriIndUMap
Triangle hash map.
unsigned char Index
Index in triangle.
CDT_EXPORT CDT_INLINE_IF_HEADER_ONLY TriInd opposedTriangle(const Triangle &tri, VertInd iVert)
Given triangle and a vertex find opposed triangle.
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.
Edge RemapNoSuperTriangle(const Edge &e)
Remap removing super-triangle: subtract 3 from vertices.
CDT_EXPORT bool isOnEdge(PtTriLocation::Enum location)
Check if location is classified as on any of three edges.
IndexSizeType TriInd
Triangle index.
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 opposedVertexInd(const NeighborsArr3 &nn, TriInd iTopo)
Index of triangle's vertex opposed to a triangle.
Edge connecting two vertices: vertex with smaller index is always first.
VertInd v2() const
V2 getter.
VertInd v1() const
V1 getter.
@ Ignore
constraint edge intersections are not checked
@ Resolve
constraint edge intersections are resolved
@ SuperTriangle
conventional super-triangle
@ Custom
user-specified custom geometry (e.g., grid)
Triangulation triangle (counter-clockwise winding)
VerticesArr3 vertices
triangle's three vertices
static Triangle make(const array< VertInd, 3 > &vertices, const array< TriInd, 3 > &neighbors)
Factory method.
NeighborsArr3 neighbors
triangle's three neighbors
std::pair< TriInd, VertInd > next(const VertInd i) const
Next triangle adjacent to a vertex (clockwise)
static V2d make(T x, T y)
Create vector from X and Y coordinates.
@ Auto
Automatic insertion order optimized for better performance.