13 template <std::
size_t I,
typename T>
struct nth {
14 inline static typename std::tuple_element<I, T>::type
15 get(
const T& t) {
return std::get<I>(t); };
22 template <
typename N = u
int32_t>
28 template <
typename Polygon>
33 Node(N index,
double x_,
double y_) :
i(index),
x(x_),
y(y_) {}
58 template <
typename Ring>
Node*
linkedList(
const Ring& points,
const bool clockwise);
71 int32_t
zOrder(
const double x_,
const double y_);
73 bool pointInTriangle(
double ax,
double ay,
double bx,
double by,
double cx,
double cy,
double px,
double py)
const;
92 template <
typename T,
typename Alloc = std::allocator<T>>
102 template <
typename... Args>
110 alloc_traits::construct(
alloc,
object, std::forward<Args>(args)...);
113 void reset(std::size_t newBlockSize) {
118 blockSize = std::max<std::size_t>(1, newBlockSize);
134 template <
typename N>
template <
typename Polygon>
140 if (points.empty())
return;
147 for (
size_t i = 0; threshold >= 0 && i < points.size(); i++) {
148 threshold -=
static_cast<int>(points[i].size());
149 len += points[i].size();
153 nodes.reset(len * 3 / 2);
154 indices.reserve(len + points[0].size());
156 Node* outerNode = linkedList(points[0],
true);
157 if (!outerNode || outerNode->
prev == outerNode->
next)
return;
159 if (points.size() > 1) outerNode = eliminateHoles(points, outerNode);
162 hashing = threshold < 0;
165 minX = maxX = outerNode->
x;
166 minY = maxY = outerNode->
y;
170 minX = std::min<double>(minX,
x);
171 minY = std::min<double>(minY,
y);
172 maxX = std::max<double>(maxX,
x);
173 maxY = std::max<double>(maxY,
y);
175 }
while (p != outerNode);
178 inv_size = std::max<double>(maxX - minX, maxY - minY);
179 inv_size = inv_size != .0 ? (1. / inv_size) : .0;
182 earcutLinked(outerNode);
188 template <
typename N>
template <
typename Ring>
191 using Point =
typename Ring::value_type;
193 const std::size_t len = points.size();
195 Node* last =
nullptr;
198 for (i = 0, j = len > 0 ? len - 1 : 0; i < len; j = i++) {
199 const auto& p1 = points[i];
200 const auto& p2 = points[j];
205 sum += (p20 - p10) * (p11 + p21);
209 if (clockwise == (sum > 0)) {
210 for (i = 0; i < len; i++) last = insertNode(vertices + i, points[i], last);
213 for (i = len; i-- > 0;) last = insertNode(vertices + i, points[i], last);
216 if (last && equals(last, last->
next)) {
227 template <
typename N>
230 if (!end) end = start;
241 if (p == p->
next)
break;
248 }
while (again || p != end);
254 template <
typename N>
259 if (!pass && hashing) indexCurve(ear);
273 if (hashing ? isEarHashed(ear) : isEar(ear)) {
275 indices.emplace_back(prev->
i);
276 indices.emplace_back(ear->
i);
277 indices.emplace_back(next->
i);
293 if (!pass) earcutLinked(filterPoints(ear), 1);
296 else if (pass == 1) {
297 ear = cureLocalIntersections(filterPoints(ear));
298 earcutLinked(ear, 2);
302 else if (pass == 2) splitEarcut(ear);
310 template <
typename N>
316 if (area(a, b, c) >= 0)
return false;
321 while (p != ear->
prev) {
322 if (pointInTriangle(a->
x, a->
y, b->
x, b->
y, c->
x, c->
y, p->
x, p->
y) &&
323 area(p->
prev, p, p->
next) >= 0)
return false;
330 template <
typename N>
336 if (area(a, b, c) >= 0)
return false;
339 const double minTX = std::min<double>(a->
x, std::min<double>(b->
x, c->
x));
340 const double minTY = std::min<double>(a->
y, std::min<double>(b->
y, c->
y));
341 const double maxTX = std::max<double>(a->
x, std::max<double>(b->
x, c->
x));
342 const double maxTY = std::max<double>(a->
y, std::max<double>(b->
y, c->
y));
345 const int32_t minZ = zOrder(minTX, minTY);
346 const int32_t maxZ = zOrder(maxTX, maxTY);
351 while (p && p->
z <= maxZ) {
352 if (p != ear->
prev && p != ear->
next &&
353 pointInTriangle(a->
x, a->
y, b->
x, b->
y, c->
x, c->
y, p->
x, p->
y) &&
354 area(p->
prev, p, p->
next) >= 0)
return false;
361 while (p && p->
z >= minZ) {
362 if (p != ear->
prev && p != ear->
next &&
363 pointInTriangle(a->
x, a->
y, b->
x, b->
y, c->
x, c->
y, p->
x, p->
y) &&
364 area(p->
prev, p, p->
next) >= 0)
return false;
372 template <
typename N>
381 if (!equals(a, b) && intersects(a, p, p->
next, b) && locallyInside(a, b) && locallyInside(b, a)) {
382 indices.emplace_back(a->
i);
383 indices.emplace_back(p->
i);
384 indices.emplace_back(b->
i);
393 }
while (p != start);
395 return filterPoints(p);
399 template <
typename N>
405 while (b != a->
prev) {
406 if (a->
i != b->
i && isValidDiagonal(a, b)) {
408 Node* c = splitPolygon(a, b);
411 a = filterPoints(a, a->
next);
412 c = filterPoints(c, c->
next);
422 }
while (a != start);
426 template <
typename N>
template <
typename Polygon>
429 const size_t len = points.size();
431 std::vector<Node*> queue;
432 for (
size_t i = 1; i < len; i++) {
433 Node* list = linkedList(points[i],
false);
436 queue.push_back(getLeftmost(list));
439 std::sort(queue.begin(), queue.end(), [](
const Node* a,
const Node* b) {
444 for (
size_t i = 0; i < queue.size(); i++) {
445 eliminateHole(queue[i], outerNode);
446 outerNode = filterPoints(outerNode, outerNode->
next);
453 template <
typename N>
455 outerNode = findHoleBridge(hole, outerNode);
457 Node* b = splitPolygon(outerNode, hole);
460 filterPoints(outerNode, outerNode->
next);
461 filterPoints(b, b->
next);
466 template <
typename N>
472 double qx = -std::numeric_limits<double>::infinity();
478 if (hy <= p->
y && hy >= p->
next->
y && p->
next->
y != p->
y) {
479 double x = p->
x + (hy - p->
y) * (p->
next->
x - p->
x) / (p->
next->
y - p->
y);
480 if (x <= hx && x > qx) {
483 if (hy == p->
y)
return p;
490 }
while (p != outerNode);
494 if (hx == qx)
return m;
500 const Node* stop = m;
501 double tanMin = std::numeric_limits<double>::infinity();
509 if (hx >= p->
x && p->
x >= mx && hx != p->
x &&
510 pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p->
x, p->
y)) {
512 tanCur = std::abs(hy - p->
y) / (hx - p->
x);
514 if (locallyInside(p, hole) &&
515 (tanCur < tanMin || (tanCur == tanMin && (p->
x > m->
x || sectorContainsSector(m, p))))) {
528 template <
typename N>
534 template <
typename N>
540 p->
z = p->
z ? p->
z : zOrder(p->
x, p->
y);
544 }
while (p != start);
554 template <
typename N>
562 int i, numMerges, pSize, qSize;
575 for (i = 0; i < inSize; i++) {
583 while (pSize > 0 || (qSize > 0 && q)) {
590 else if (qSize == 0 || !q) {
595 else if (p->
z <= q->
z) {
606 if (tail) tail->
nextZ = e;
616 tail->
nextZ =
nullptr;
618 if (numMerges <= 1)
return list;
625 template <
typename N>
628 int32_t
x =
static_cast<int32_t
>(32767.0 * (x_ - minX) * inv_size);
629 int32_t
y =
static_cast<int32_t
>(32767.0 * (y_ - minY) * inv_size);
631 x = (
x | (
x << 8)) & 0x00FF00FF;
632 x = (
x | (
x << 4)) & 0x0F0F0F0F;
633 x = (
x | (
x << 2)) & 0x33333333;
634 x = (
x | (
x << 1)) & 0x55555555;
636 y = (
y | (
y << 8)) & 0x00FF00FF;
637 y = (
y | (
y << 4)) & 0x0F0F0F0F;
638 y = (
y | (
y << 2)) & 0x33333333;
639 y = (
y | (
y << 1)) & 0x55555555;
645 template <
typename N>
649 Node* leftmost = start;
651 if (p->
x < leftmost->
x || (p->
x == leftmost->
x && p->
y < leftmost->
y))
654 }
while (p != start);
660 template <
typename N>
662 return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 &&
663 (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 &&
664 (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0;
668 template <
typename N>
670 return a->
next->
i != b->
i && a->
prev->
i != b->
i && !intersectsPolygon(a, b) &&
671 ((locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b) &&
672 (area(a->
prev, a, b->
prev) != 0.0 || area(a, b->
prev, b) != 0.0)) ||
673 (equals(a, b) && area(a->
prev, a, a->
next) > 0 && area(b->
prev, b, b->
next) > 0));
677 template <
typename N>
679 return (q->
y - p->
y) * (r->
x - q->
x) - (q->
x - p->
x) * (r->
y - q->
y);
683 template <
typename N>
685 return p1->
x == p2->
x && p1->
y == p2->
y;
689 template <
typename N>
691 int o1 = sign(area(p1, q1, p2));
692 int o2 = sign(area(p1, q1, q2));
693 int o3 = sign(area(p2, q2, p1));
694 int o4 = sign(area(p2, q2, q1));
696 if (o1 != o2 && o3 != o4)
return true;
698 if (o1 == 0 && onSegment(p1, p2, q1))
return true;
699 if (o2 == 0 && onSegment(p1, q2, q1))
return true;
700 if (o3 == 0 && onSegment(p2, p1, q2))
return true;
701 if (o4 == 0 && onSegment(p2, q1, q2))
return true;
707 template <
typename N>
709 return q->
x <= std::max<double>(p->
x, r->
x) &&
710 q->
x >= std::min<double>(p->
x, r->
x) &&
711 q->
y <= std::max<double>(p->
y, r->
y) &&
712 q->
y >= std::min<double>(p->
y, r->
y);
715 template <
typename N>
717 return (0.0 < val) - (val < 0.0);
721 template <
typename N>
725 if (p->
i != a->
i && p->
next->
i != a->
i && p->
i != b->
i && p->
next->
i != b->
i &&
726 intersects(p, p->
next, a, b))
return true;
734 template <
typename N>
736 return area(a->
prev, a, a->
next) < 0 ?
737 area(a, b, a->
next) >= 0 && area(a, a->
prev, b) >= 0 :
738 area(a, b, a->
prev) < 0 || area(a, a->
next, b) < 0;
742 template <
typename N>
746 double px = (a->
x + b->
x) / 2;
747 double py = (a->
y + b->
y) / 2;
749 if (((p->
y > py) != (p->
next->
y > py)) && p->
next->
y != p->
y &&
750 (px < (p->
next->
x - p->
x) * (py - p->
y) / (p->
next->
y - p->
y) + p->
x))
761 template <
typename N>
764 Node* a2 = nodes.construct(a->
i, a->
x, a->
y);
765 Node* b2 = nodes.construct(b->
i, b->
x, b->
y);
785 template <
typename N>
template <
typename Po
int>
805 template <
typename N>
815 template <
typename N = u
int32_t,
typename Polygon>
816 std::vector<N>
earcut(
const Polygon& poly) {
819 return std::move(
earcut.indices);
Definition: triangulation.hpp:93
T * construct(Args &&... args)
Definition: triangulation.hpp:103
~ObjectPool()
Definition: triangulation.hpp:99
Alloc alloc
Definition: triangulation.hpp:128
std::size_t currentIndex
Definition: triangulation.hpp:125
std::size_t blockSize
Definition: triangulation.hpp:126
std::allocator_traits< Alloc > alloc_traits
Definition: triangulation.hpp:129
T * currentBlock
Definition: triangulation.hpp:124
ObjectPool()
Definition: triangulation.hpp:95
void reset(std::size_t newBlockSize)
Definition: triangulation.hpp:113
void clear()
Definition: triangulation.hpp:122
ObjectPool(std::size_t blockSize_)
Definition: triangulation.hpp:96
std::vector< T * > allocations
Definition: triangulation.hpp:127
Definition: triangulation.hpp:23
int sign(double val)
Definition: triangulation.hpp:716
bool isEarHashed(Node *ear)
Definition: triangulation.hpp:331
bool isEar(Node *ear)
Definition: triangulation.hpp:311
Node * cureLocalIntersections(Node *start)
Definition: triangulation.hpp:374
Node * eliminateHoles(const Polygon &points, Node *outerNode)
Definition: triangulation.hpp:428
bool onSegment(const Node *p, const Node *q, const Node *r)
Definition: triangulation.hpp:708
double minY
Definition: triangulation.hpp:89
double inv_size
Definition: triangulation.hpp:90
Node * splitPolygon(Node *a, Node *b)
Definition: triangulation.hpp:763
bool middleInside(const Node *a, const Node *b)
Definition: triangulation.hpp:743
double area(const Node *p, const Node *q, const Node *r) const
Definition: triangulation.hpp:678
bool intersectsPolygon(const Node *a, const Node *b)
Definition: triangulation.hpp:722
double maxX
Definition: triangulation.hpp:88
void eliminateHole(Node *hole, Node *outerNode)
Definition: triangulation.hpp:454
void splitEarcut(Node *start)
Definition: triangulation.hpp:400
Node * sortLinked(Node *list)
Definition: triangulation.hpp:556
double minX
Definition: triangulation.hpp:88
void indexCurve(Node *start)
Definition: triangulation.hpp:535
bool isValidDiagonal(Node *a, Node *b)
Definition: triangulation.hpp:669
bool pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const
Definition: triangulation.hpp:661
double maxY
Definition: triangulation.hpp:89
std::size_t vertices
Definition: triangulation.hpp:26
bool locallyInside(const Node *a, const Node *b)
Definition: triangulation.hpp:735
void operator()(const Polygon &points)
Definition: triangulation.hpp:135
bool hashing
Definition: triangulation.hpp:87
bool sectorContainsSector(const Node *m, const Node *p)
Definition: triangulation.hpp:529
Node * findHoleBridge(Node *hole, Node *outerNode)
Definition: triangulation.hpp:468
ObjectPool< Node > nodes
Definition: triangulation.hpp:131
Node * getLeftmost(Node *start)
Definition: triangulation.hpp:647
void removeNode(Node *p)
Definition: triangulation.hpp:806
void earcutLinked(Node *ear, int pass=0)
Definition: triangulation.hpp:255
Node * insertNode(std::size_t i, const Point &p, Node *last)
Definition: triangulation.hpp:787
bool equals(const Node *p1, const Node *p2)
Definition: triangulation.hpp:684
int32_t zOrder(const double x_, const double y_)
Definition: triangulation.hpp:626
std::vector< N > indices
Definition: triangulation.hpp:25
bool intersects(const Node *p1, const Node *q1, const Node *p2, const Node *q2)
Definition: triangulation.hpp:690
Node * filterPoints(Node *start, Node *end=nullptr)
Definition: triangulation.hpp:229
Node * linkedList(const Ring &points, const bool clockwise)
Definition: triangulation.hpp:190
#define y
Definition: functions.hpp:41
#define x
Definition: functions.hpp:40
Definition: triangulation.hpp:9
std::vector< N > earcut(const Polygon &poly)
Definition: triangulation.hpp:816
Definition: triangulation.hpp:32
int32_t z
Definition: triangulation.hpp:48
Node * nextZ
Definition: triangulation.hpp:52
Node & operator=(Node &&)=delete
Node(const Node &)=delete
Node * prev
Definition: triangulation.hpp:44
Node & operator=(const Node &)=delete
bool steiner
Definition: triangulation.hpp:55
const double x
Definition: triangulation.hpp:40
Node * next
Definition: triangulation.hpp:45
Node(N index, double x_, double y_)
Definition: triangulation.hpp:33
const double y
Definition: triangulation.hpp:41
Node * prevZ
Definition: triangulation.hpp:51
const N i
Definition: triangulation.hpp:39
Definition: triangulation.hpp:13
static std::tuple_element< I, T >::type get(const T &t)
Definition: triangulation.hpp:15