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