Mercurial > ldforge2 / file comparison

comparison: src/algorithm/earcut.h

src/algorithm/earcut.h

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

Mercurial Repository: ldforge2

mercurial