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 | |
33 | namespace qt_mapbox { |
34 | |
35 | namespace util { |
36 | |
37 | template <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 | |
44 | namespace detail { |
45 | |
46 | template <typename N = uint32_t> |
47 | class Earcut { |
48 | public: |
49 | std::vector<N> indices; |
50 | std::size_t vertices = 0; |
51 | |
52 | template <typename Polygon> |
53 | void operator()(const Polygon& points); |
54 | |
55 | private: |
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 = ¤tBlock[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 | |
158 | template <typename N> template <typename Polygon> |
159 | void 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 |
212 | template <typename N> template <typename Ring> |
213 | typename Earcut<N>::Node* |
214 | Earcut<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 |
250 | template <typename N> |
251 | typename Earcut<N>::Node* |
252 | Earcut<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) |
276 | template <typename N> |
277 | void 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 |
331 | template <typename N> |
332 | bool 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 | |
351 | template <typename N> |
352 | bool 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 |
393 | template <typename N> |
394 | typename Earcut<N>::Node* |
395 | Earcut<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 |
420 | template <typename N> |
421 | void 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 |
447 | template <typename N> template <typename Polygon> |
448 | typename Earcut<N>::Node* |
449 | Earcut<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 |
474 | template <typename N> |
475 | void 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 |
484 | template <typename N> |
485 | typename Earcut<N>::Node* |
486 | Earcut<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 |
546 | template <typename N> |
547 | bool 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 |
552 | template <typename N> |
553 | void 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 |
572 | template <typename N> |
573 | typename Earcut<N>::Node* |
574 | Earcut<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 |
640 | template <typename N> |
641 | int32_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 |
660 | template <typename N> |
661 | typename Earcut<N>::Node* |
662 | Earcut<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 |
675 | template <typename N> |
676 | bool 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) |
683 | template <typename N> |
684 | bool 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 |
692 | template <typename N> |
693 | double 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 |
698 | template <typename N> |
699 | bool 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 |
704 | template <typename N> |
705 | bool 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 |
722 | template <typename N> |
723 | bool 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 | |
730 | template <typename N> |
731 | int 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 |
736 | template <typename N> |
737 | bool 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 |
749 | template <typename N> |
750 | bool 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 |
757 | template <typename N> |
758 | bool 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 |
776 | template <typename N> |
777 | typename Earcut<N>::Node* |
778 | Earcut<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) |
800 | template <typename N> template <typename Point> |
801 | typename Earcut<N>::Node* |
802 | Earcut<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 | |
819 | template <typename N> |
820 | void 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 | |
829 | template <typename N = uint32_t, typename Polygon> |
830 | std::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 | |