1#pragma once
2
3#include <algorithm>
4#include <cassert>
5#include <cmath>
6#include <memory>
7#include <vector>
8
9namespace mapbox {
10
11namespace util {
12
13template <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); };
16};
17
18}
19
20namespace detail {
21
22template <typename N = uint32_t>
23class Earcut {
24public:
25 std::vector<N> indices;
26 std::size_t vertices = 0;
27
28 template <typename Polygon>
29 void operator()(const Polygon& points);
30
31private:
32 struct Node {
33 Node(N index, double x_, double y_) : i(index), x(x_), y(y_) {}
34 Node(const Node&) = delete;
35 Node& operator=(const Node&) = delete;
36 Node(Node&&) = delete;
37 Node& operator=(Node&&) = delete;
38
39 const N i;
40 const double x;
41 const double y;
42
43 // previous and next vertice nodes in a polygon ring
44 Node* prev = nullptr;
45 Node* next = nullptr;
46
47 // z-order curve value
48 int32_t z = 0;
49
50 // previous and next nodes in z-order
51 Node* prevZ = nullptr;
52 Node* nextZ = nullptr;
53
54 // indicates whether this is a steiner point
55 bool steiner = false;
56 };
57
58 template <typename Ring> Node* linkedList(const Ring& points, const bool clockwise);
59 Node* filterPoints(Node* start, Node* end = nullptr);
60 void earcutLinked(Node* ear, int pass = 0);
61 bool isEar(Node* ear);
62 bool isEarHashed(Node* ear);
63 Node* cureLocalIntersections(Node* start);
64 void splitEarcut(Node* start);
65 template <typename Polygon> Node* eliminateHoles(const Polygon& points, Node* outerNode);
66 void eliminateHole(Node* hole, Node* outerNode);
67 Node* findHoleBridge(Node* hole, Node* outerNode);
68 void indexCurve(Node* start);
69 Node* sortLinked(Node* list);
70 int32_t zOrder(const double x_, const double y_);
71 Node* getLeftmost(Node* start);
72 bool pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const;
73 bool isValidDiagonal(Node* a, Node* b);
74 double area(const Node* p, const Node* q, const Node* r) const;
75 bool equals(const Node* p1, const Node* p2);
76 bool intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2);
77 bool intersectsPolygon(const Node* a, const Node* b);
78 bool locallyInside(const Node* a, const Node* b);
79 bool middleInside(const Node* a, const Node* b);
80 Node* splitPolygon(Node* a, Node* b);
81 template <typename Point> Node* insertNode(std::size_t i, const Point& p, Node* last);
82 void removeNode(Node* p);
83
84 bool hashing;
85 double minX, maxX;
86 double minY, maxY;
87 double inv_size = 0;
88
89 template <typename T, typename Alloc = std::allocator<T>>
90 class ObjectPool {
91 public:
92 ObjectPool() { }
93 ObjectPool(std::size_t blockSize_) {
94 reset(newBlockSize: blockSize_);
95 }
96 ~ObjectPool() {
97 clear();
98 }
99 template <typename... Args>
100 T* construct(Args&&... args) {
101 if (currentIndex >= blockSize) {
102 currentBlock = alloc.allocate(blockSize);
103 allocations.emplace_back(currentBlock);
104 currentIndex = 0;
105 }
106 T* object = &currentBlock[currentIndex++];
107 alloc.construct(object, std::forward<Args>(args)...);
108 return object;
109 }
110 void reset(std::size_t newBlockSize) {
111 for (auto allocation : allocations) alloc.deallocate(allocation, blockSize);
112 allocations.clear();
113 blockSize = std::max<std::size_t>(a: 1, b: newBlockSize);
114 currentBlock = nullptr;
115 currentIndex = blockSize;
116 }
117 void clear() { reset(newBlockSize: blockSize); }
118 private:
119 T* currentBlock = nullptr;
120 std::size_t currentIndex = 1;
121 std::size_t blockSize = 1;
122 std::vector<T*> allocations;
123 Alloc alloc;
124 };
125 ObjectPool<Node> nodes;
126};
127
128template <typename N> template <typename Polygon>
129void Earcut<N>::operator()(const Polygon& points) {
130 // reset
131 indices.clear();
132 vertices = 0;
133
134 if (points.empty()) return;
135
136 double x;
137 double y;
138 int threshold = 80;
139 std::size_t len = 0;
140
141 for (size_t i = 0; threshold >= 0 && i < points.size(); i++) {
142 threshold -= static_cast<int>(points[i].size());
143 len += points[i].size();
144 }
145
146 //estimate size of nodes and indices
147 nodes.reset(len * 3 / 2);
148 indices.reserve(len + points[0].size());
149
150 Node* outerNode = linkedList(points[0], true);
151 if (!outerNode) return;
152
153 if (points.size() > 1) outerNode = eliminateHoles(points, outerNode);
154
155 // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox
156 hashing = threshold < 0;
157 if (hashing) {
158 Node* p = outerNode->next;
159 minX = maxX = p->x;
160 minY = maxY = p->y;
161 do {
162 x = p->x;
163 y = p->y;
164 minX = std::min<double>(a: minX, b: x);
165 minY = std::min<double>(a: minY, b: y);
166 maxX = std::max<double>(a: maxX, b: x);
167 maxY = std::max<double>(a: maxY, b: y);
168 p = p->next;
169 } while (p != outerNode);
170
171 // minX, minY and size are later used to transform coords into integers for z-order calculation
172 inv_size = std::max<double>(a: maxX - minX, b: maxY - minY);
173 inv_size = inv_size != .0 ? (1. / inv_size) : .0;
174 }
175
176 earcutLinked(ear: outerNode);
177
178 nodes.clear();
179}
180
181// create a circular doubly linked list from polygon points in the specified winding order
182template <typename N> template <typename Ring>
183typename Earcut<N>::Node*
184Earcut<N>::linkedList(const Ring& points, const bool clockwise) {
185 using Point = typename Ring::value_type;
186 double sum = 0;
187 const std::size_t len = points.size();
188 std::size_t i, j;
189 Node* last = nullptr;
190
191 // calculate original winding order of a polygon ring
192 for (i = 0, j = len > 0 ? len - 1 : 0; i < len; j = i++) {
193 const auto& p1 = points[i];
194 const auto& p2 = points[j];
195 const double p20 = util::nth<0, Point>::get(p2);
196 const double p10 = util::nth<0, Point>::get(p1);
197 const double p11 = util::nth<1, Point>::get(p1);
198 const double p21 = util::nth<1, Point>::get(p2);
199 sum += (p20 - p10) * (p11 + p21);
200 }
201
202 // link points into circular doubly-linked list in the specified winding order
203 if (clockwise == (sum > 0)) {
204 for (i = 0; i < len; i++) last = insertNode(vertices + i, points[i], last);
205 } else {
206 for (i = len; i-- > 0;) last = insertNode(vertices + i, points[i], last);
207 }
208
209 if (last && equals(p1: last, p2: last->next)) {
210 removeNode(p: last);
211 last = last->next;
212 }
213
214 vertices += len;
215
216 return last;
217}
218
219// eliminate colinear or duplicate points
220template <typename N>
221typename Earcut<N>::Node*
222Earcut<N>::filterPoints(Node* start, Node* end) {
223 if (!end) end = start;
224
225 Node* p = start;
226 bool again;
227 do {
228 again = false;
229
230 if (!p->steiner && (equals(p1: p, p2: p->next) || area(p: p->prev, q: p, r: p->next) == 0)) {
231 removeNode(p);
232 p = end = p->prev;
233
234 if (p == p->next) break;
235 again = true;
236
237 } else {
238 p = p->next;
239 }
240 } while (again || p != end);
241
242 return end;
243}
244
245// main ear slicing loop which triangulates a polygon (given as a linked list)
246template <typename N>
247void Earcut<N>::earcutLinked(Node* ear, int pass) {
248 if (!ear) return;
249
250 // interlink polygon nodes in z-order
251 if (!pass && hashing) indexCurve(start: ear);
252
253 Node* stop = ear;
254 Node* prev;
255 Node* next;
256
257 int iterations = 0;
258
259 // iterate through ears, slicing them one by one
260 while (ear->prev != ear->next) {
261 iterations++;
262 prev = ear->prev;
263 next = ear->next;
264
265 if (hashing ? isEarHashed(ear) : isEar(ear)) {
266 // cut off the triangle
267 indices.emplace_back(prev->i);
268 indices.emplace_back(ear->i);
269 indices.emplace_back(next->i);
270
271 removeNode(p: ear);
272
273 // skipping the next vertice leads to less sliver triangles
274 ear = next->next;
275 stop = next->next;
276
277 continue;
278 }
279
280 ear = next;
281
282 // if we looped through the whole remaining polygon and can't find any more ears
283 if (ear == stop) {
284 // try filtering points and slicing again
285 if (!pass) earcutLinked(ear: filterPoints(start: ear), pass: 1);
286
287 // if this didn't work, try curing all small self-intersections locally
288 else if (pass == 1) {
289 ear = cureLocalIntersections(start: ear);
290 earcutLinked(ear, pass: 2);
291
292 // as a last resort, try splitting the remaining polygon into two
293 } else if (pass == 2) splitEarcut(start: ear);
294
295 break;
296 }
297 }
298}
299
300// check whether a polygon node forms a valid ear with adjacent nodes
301template <typename N>
302bool Earcut<N>::isEar(Node* ear) {
303 const Node* a = ear->prev;
304 const Node* b = ear;
305 const Node* c = ear->next;
306
307 if (area(p: a, q: b, r: c) >= 0) return false; // reflex, can't be an ear
308
309 // now make sure we don't have other points inside the potential ear
310 Node* p = ear->next->next;
311
312 while (p != ear->prev) {
313 if (pointInTriangle(ax: a->x, ay: a->y, bx: b->x, by: b->y, cx: c->x, cy: c->y, px: p->x, py: p->y) &&
314 area(p: p->prev, q: p, r: p->next) >= 0) return false;
315 p = p->next;
316 }
317
318 return true;
319}
320
321template <typename N>
322bool Earcut<N>::isEarHashed(Node* ear) {
323 const Node* a = ear->prev;
324 const Node* b = ear;
325 const Node* c = ear->next;
326
327 if (area(p: a, q: b, r: c) >= 0) return false; // reflex, can't be an ear
328
329 // triangle bbox; min & max are calculated like this for speed
330 const double minTX = std::min<double>(a->x, std::min<double>(b->x, c->x));
331 const double minTY = std::min<double>(a->y, std::min<double>(b->y, c->y));
332 const double maxTX = std::max<double>(a->x, std::max<double>(b->x, c->x));
333 const double maxTY = std::max<double>(a->y, std::max<double>(b->y, c->y));
334
335 // z-order range for the current triangle bbox;
336 const int32_t minZ = zOrder(x_: minTX, y_: minTY);
337 const int32_t maxZ = zOrder(x_: maxTX, y_: maxTY);
338
339 // first look for points inside the triangle in increasing z-order
340 Node* p = ear->nextZ;
341
342 while (p && p->z <= maxZ) {
343 if (p != ear->prev && p != ear->next &&
344 pointInTriangle(ax: a->x, ay: a->y, bx: b->x, by: b->y, cx: c->x, cy: c->y, px: p->x, py: p->y) &&
345 area(p: p->prev, q: p, r: p->next) >= 0) return false;
346 p = p->nextZ;
347 }
348
349 // then look for points in decreasing z-order
350 p = ear->prevZ;
351
352 while (p && p->z >= minZ) {
353 if (p != ear->prev && p != ear->next &&
354 pointInTriangle(ax: a->x, ay: a->y, bx: b->x, by: b->y, cx: c->x, cy: c->y, px: p->x, py: p->y) &&
355 area(p: p->prev, q: p, r: p->next) >= 0) return false;
356 p = p->prevZ;
357 }
358
359 return true;
360}
361
362// go through all polygon nodes and cure small local self-intersections
363template <typename N>
364typename Earcut<N>::Node*
365Earcut<N>::cureLocalIntersections(Node* start) {
366 Node* p = start;
367 do {
368 Node* a = p->prev;
369 Node* b = p->next->next;
370
371 // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2])
372 if (!equals(p1: a, p2: b) && intersects(p1: a, q1: p, p2: p->next, q2: b) && locallyInside(a, b) && locallyInside(a: b, b: a)) {
373 indices.emplace_back(a->i);
374 indices.emplace_back(p->i);
375 indices.emplace_back(b->i);
376
377 // remove two nodes involved
378 removeNode(p);
379 removeNode(p: p->next);
380
381 p = start = b;
382 }
383 p = p->next;
384 } while (p != start);
385
386 return p;
387}
388
389// try splitting polygon into two and triangulate them independently
390template <typename N>
391void Earcut<N>::splitEarcut(Node* start) {
392 // look for a valid diagonal that divides the polygon into two
393 Node* a = start;
394 do {
395 Node* b = a->next->next;
396 while (b != a->prev) {
397 if (a->i != b->i && isValidDiagonal(a, b)) {
398 // split the polygon in two by the diagonal
399 Node* c = splitPolygon(a, b);
400
401 // filter colinear points around the cuts
402 a = filterPoints(start: a, end: a->next);
403 c = filterPoints(start: c, end: c->next);
404
405 // run earcut on each half
406 earcutLinked(ear: a);
407 earcutLinked(ear: c);
408 return;
409 }
410 b = b->next;
411 }
412 a = a->next;
413 } while (a != start);
414}
415
416// link every hole into the outer loop, producing a single-ring polygon without holes
417template <typename N> template <typename Polygon>
418typename Earcut<N>::Node*
419Earcut<N>::eliminateHoles(const Polygon& points, Node* outerNode) {
420 const size_t len = points.size();
421
422 std::vector<Node*> queue;
423 for (size_t i = 1; i < len; i++) {
424 Node* list = linkedList(points[i], false);
425 if (list) {
426 if (list == list->next) list->steiner = true;
427 queue.push_back(getLeftmost(start: list));
428 }
429 }
430 std::sort(queue.begin(), queue.end(), [](const Node* a, const Node* b) {
431 return a->x < b->x;
432 });
433
434 // process holes from left to right
435 for (size_t i = 0; i < queue.size(); i++) {
436 eliminateHole(hole: queue[i], outerNode);
437 outerNode = filterPoints(start: outerNode, end: outerNode->next);
438 }
439
440 return outerNode;
441}
442
443// find a bridge between vertices that connects hole with an outer ring and and link it
444template <typename N>
445void Earcut<N>::eliminateHole(Node* hole, Node* outerNode) {
446 outerNode = findHoleBridge(hole, outerNode);
447 if (outerNode) {
448 Node* b = splitPolygon(a: outerNode, b: hole);
449 filterPoints(start: b, end: b->next);
450 }
451}
452
453// David Eberly's algorithm for finding a bridge between hole and outer polygon
454template <typename N>
455typename Earcut<N>::Node*
456Earcut<N>::findHoleBridge(Node* hole, Node* outerNode) {
457 Node* p = outerNode;
458 double hx = hole->x;
459 double hy = hole->y;
460 double qx = -std::numeric_limits<double>::infinity();
461 Node* m = nullptr;
462
463 // find a segment intersected by a ray from the hole's leftmost Vertex to the left;
464 // segment's endpoint with lesser x will be potential connection Vertex
465 do {
466 if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) {
467 double x = p->x + (hy - p->y) * (p->next->x - p->x) / (p->next->y - p->y);
468 if (x <= hx && x > qx) {
469 qx = x;
470 if (x == hx) {
471 if (hy == p->y) return p;
472 if (hy == p->next->y) return p->next;
473 }
474 m = p->x < p->next->x ? p : p->next;
475 }
476 }
477 p = p->next;
478 } while (p != outerNode);
479
480 if (!m) return 0;
481
482 if (hx == qx) return m->prev;
483
484 // look for points inside the triangle of hole Vertex, segment intersection and endpoint;
485 // if there are no points found, we have a valid connection;
486 // otherwise choose the Vertex of the minimum angle with the ray as connection Vertex
487
488 const Node* stop = m;
489 double tanMin = std::numeric_limits<double>::infinity();
490 double tanCur = 0;
491
492 p = m->next;
493 double mx = m->x;
494 double my = m->y;
495
496 while (p != stop) {
497 if (hx >= p->x && p->x >= mx && hx != p->x &&
498 pointInTriangle(ax: hy < my ? hx : qx, ay: hy, bx: mx, by: my, cx: hy < my ? qx : hx, cy: hy, px: p->x, py: p->y)) {
499
500 tanCur = std::abs(hy - p->y) / (hx - p->x); // tangential
501
502 if ((tanCur < tanMin || (tanCur == tanMin && p->x > m->x)) && locallyInside(a: p, b: hole)) {
503 m = p;
504 tanMin = tanCur;
505 }
506 }
507
508 p = p->next;
509 }
510
511 return m;
512}
513
514// interlink polygon nodes in z-order
515template <typename N>
516void Earcut<N>::indexCurve(Node* start) {
517 assert(start);
518 Node* p = start;
519
520 do {
521 p->z = p->z ? p->z : zOrder(x_: p->x, y_: p->y);
522 p->prevZ = p->prev;
523 p->nextZ = p->next;
524 p = p->next;
525 } while (p != start);
526
527 p->prevZ->nextZ = nullptr;
528 p->prevZ = nullptr;
529
530 sortLinked(list: p);
531}
532
533// Simon Tatham's linked list merge sort algorithm
534// http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
535template <typename N>
536typename Earcut<N>::Node*
537Earcut<N>::sortLinked(Node* list) {
538 assert(list);
539 Node* p;
540 Node* q;
541 Node* e;
542 Node* tail;
543 int i, numMerges, pSize, qSize;
544 int inSize = 1;
545
546 for (;;) {
547 p = list;
548 list = nullptr;
549 tail = nullptr;
550 numMerges = 0;
551
552 while (p) {
553 numMerges++;
554 q = p;
555 pSize = 0;
556 for (i = 0; i < inSize; i++) {
557 pSize++;
558 q = q->nextZ;
559 if (!q) break;
560 }
561
562 qSize = inSize;
563
564 while (pSize > 0 || (qSize > 0 && q)) {
565
566 if (pSize == 0) {
567 e = q;
568 q = q->nextZ;
569 qSize--;
570 } else if (qSize == 0 || !q) {
571 e = p;
572 p = p->nextZ;
573 pSize--;
574 } else if (p->z <= q->z) {
575 e = p;
576 p = p->nextZ;
577 pSize--;
578 } else {
579 e = q;
580 q = q->nextZ;
581 qSize--;
582 }
583
584 if (tail) tail->nextZ = e;
585 else list = e;
586
587 e->prevZ = tail;
588 tail = e;
589 }
590
591 p = q;
592 }
593
594 tail->nextZ = nullptr;
595
596 if (numMerges <= 1) return list;
597
598 inSize *= 2;
599 }
600}
601
602// z-order of a Vertex given coords and size of the data bounding box
603template <typename N>
604int32_t Earcut<N>::zOrder(const double x_, const double y_) {
605 // coords are transformed into non-negative 15-bit integer range
606 int32_t x = static_cast<int32_t>(32767.0 * (x_ - minX) * inv_size);
607 int32_t y = static_cast<int32_t>(32767.0 * (y_ - minY) * inv_size);
608
609 x = (x | (x << 8)) & 0x00FF00FF;
610 x = (x | (x << 4)) & 0x0F0F0F0F;
611 x = (x | (x << 2)) & 0x33333333;
612 x = (x | (x << 1)) & 0x55555555;
613
614 y = (y | (y << 8)) & 0x00FF00FF;
615 y = (y | (y << 4)) & 0x0F0F0F0F;
616 y = (y | (y << 2)) & 0x33333333;
617 y = (y | (y << 1)) & 0x55555555;
618
619 return x | (y << 1);
620}
621
622// find the leftmost node of a polygon ring
623template <typename N>
624typename Earcut<N>::Node*
625Earcut<N>::getLeftmost(Node* start) {
626 Node* p = start;
627 Node* leftmost = start;
628 do {
629 if (p->x < leftmost->x) leftmost = p;
630 p = p->next;
631 } while (p != start);
632
633 return leftmost;
634}
635
636// check if a point lies within a convex triangle
637template <typename N>
638bool Earcut<N>::pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const {
639 return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 &&
640 (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 &&
641 (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0;
642}
643
644// check if a diagonal between two polygon nodes is valid (lies in polygon interior)
645template <typename N>
646bool Earcut<N>::isValidDiagonal(Node* a, Node* b) {
647 return a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon(a, b) &&
648 locallyInside(a, b) && locallyInside(a: b, b: a) && middleInside(a, b);
649}
650
651// signed area of a triangle
652template <typename N>
653double Earcut<N>::area(const Node* p, const Node* q, const Node* r) const {
654 return (q->y - p->y) * (r->x - q->x) - (q->x - p->x) * (r->y - q->y);
655}
656
657// check if two points are equal
658template <typename N>
659bool Earcut<N>::equals(const Node* p1, const Node* p2) {
660 return p1->x == p2->x && p1->y == p2->y;
661}
662
663// check if two segments intersect
664template <typename N>
665bool Earcut<N>::intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2) {
666 if ((equals(p1, p2: q1) && equals(p1: p2, p2: q2)) ||
667 (equals(p1, p2: q2) && equals(p1: p2, p2: q1))) return true;
668 return (area(p: p1, q: q1, r: p2) > 0) != (area(p: p1, q: q1, r: q2) > 0) &&
669 (area(p: p2, q: q2, r: p1) > 0) != (area(p: p2, q: q2, r: q1) > 0);
670}
671
672// check if a polygon diagonal intersects any polygon segments
673template <typename N>
674bool Earcut<N>::intersectsPolygon(const Node* a, const Node* b) {
675 const Node* p = a;
676 do {
677 if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i &&
678 intersects(p1: p, q1: p->next, p2: a, q2: b)) return true;
679 p = p->next;
680 } while (p != a);
681
682 return false;
683}
684
685// check if a polygon diagonal is locally inside the polygon
686template <typename N>
687bool Earcut<N>::locallyInside(const Node* a, const Node* b) {
688 return area(p: a->prev, q: a, r: a->next) < 0 ?
689 area(p: a, q: b, r: a->next) >= 0 && area(p: a, q: a->prev, r: b) >= 0 :
690 area(p: a, q: b, r: a->prev) < 0 || area(p: a, q: a->next, r: b) < 0;
691}
692
693// check if the middle Vertex of a polygon diagonal is inside the polygon
694template <typename N>
695bool Earcut<N>::middleInside(const Node* a, const Node* b) {
696 const Node* p = a;
697 bool inside = false;
698 double px = (a->x + b->x) / 2;
699 double py = (a->y + b->y) / 2;
700 do {
701 if (((p->y > py) != (p->next->y > py)) && p->next->y != p->y &&
702 (px < (p->next->x - p->x) * (py - p->y) / (p->next->y - p->y) + p->x))
703 inside = !inside;
704 p = p->next;
705 } while (p != a);
706
707 return inside;
708}
709
710// link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits
711// polygon into two; if one belongs to the outer ring and another to a hole, it merges it into a
712// single ring
713template <typename N>
714typename Earcut<N>::Node*
715Earcut<N>::splitPolygon(Node* a, Node* b) {
716 Node* a2 = nodes.construct(a->i, a->x, a->y);
717 Node* b2 = nodes.construct(b->i, b->x, b->y);
718 Node* an = a->next;
719 Node* bp = b->prev;
720
721 a->next = b;
722 b->prev = a;
723
724 a2->next = an;
725 an->prev = a2;
726
727 b2->next = a2;
728 a2->prev = b2;
729
730 bp->next = b2;
731 b2->prev = bp;
732
733 return b2;
734}
735
736// create a node and util::optionally link it with previous one (in a circular doubly linked list)
737template <typename N> template <typename Point>
738typename Earcut<N>::Node*
739Earcut<N>::insertNode(std::size_t i, const Point& pt, Node* last) {
740 Node* p = nodes.construct(static_cast<N>(i), util::nth<0, Point>::get(pt), util::nth<1, Point>::get(pt));
741
742 if (!last) {
743 p->prev = p;
744 p->next = p;
745
746 } else {
747 assert(last);
748 p->next = last->next;
749 p->prev = last;
750 last->next->prev = p;
751 last->next = p;
752 }
753 return p;
754}
755
756template <typename N>
757void Earcut<N>::removeNode(Node* p) {
758 p->next->prev = p->prev;
759 p->prev->next = p->next;
760
761 if (p->prevZ) p->prevZ->nextZ = p->nextZ;
762 if (p->nextZ) p->nextZ->prevZ = p->prevZ;
763}
764}
765
766template <typename N = uint32_t, typename Polygon>
767std::vector<N> earcut(const Polygon& poly) {
768 mapbox::detail::Earcut<N> earcut;
769 earcut(poly);
770 return std::move(earcut.indices);
771}
772}
773

source code of qtlocation/src/3rdparty/mapbox-gl-native/deps/earcut/0.12.4/include/mapbox/earcut.hpp