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