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 = ¤tBlock[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 } |
|