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

source code of qtlocation/src/3rdparty/earcut/earcut.hpp