changeset
Move earcut.h outside src/ directory
Tue, 28 Jun 2022 19:49:45 +0300
- author
- Teemu Piippo <teemu.s.piippo@gmail.com>
- date
- Tue, 28 Jun 2022 19:49:45 +0300
- changeset 301
- 8ccd6fdb30dc
- parent 300
- 3a4b132b8353
- child 302
- d59cb01d8031
Move earcut.h outside src/ directory
| CMakeLists.txt | file | annotate | diff | comparison | revisions | |
| src/algorithm/earcut.h | file | annotate | diff | comparison | revisions | |
| src/layers/edittools.cpp | file | annotate | diff | comparison | revisions | |
| thirdparty/earcut.h | file | annotate | diff | comparison | revisions |
--- a/CMakeLists.txt Tue Jun 28 19:47:34 2022 +0300 +++ b/CMakeLists.txt Tue Jun 28 19:49:45 2022 +0300 @@ -110,7 +110,6 @@ src/uiutilities.h src/version.h src/vertexmap.h - src/algorithm/earcut.h src/gl/basicshaderprogram.h src/gl/common.h src/gl/compiler.h @@ -126,6 +125,7 @@ src/ui/objecteditor.h src/widgets/colorindexinput.h src/widgets/colorselectdialog.h + thirdparty/earcut.h ) set(FORM_FILES src/about.ui
--- a/src/algorithm/earcut.h Tue Jun 28 19:47:34 2022 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,828 +0,0 @@ -#pragma once - -#include <algorithm> -#include <cassert> -#include <cmath> -#include <cstddef> -#include <limits> -#include <memory> -#include <utility> -#include <vector> - -namespace mapbox { - -namespace util { - -template <std::size_t I, typename T> struct nth { - inline static typename std::tuple_element<I, T>::type - get(const T& t) { return std::get<I>(t); } -}; - -} - -namespace detail { - -template <typename N = uint32_t> -class Earcut { -public: - std::vector<N> indices; - std::size_t vertices = 0; - - template <typename Polygon> - void operator()(const Polygon& points); - -private: - struct Node { - Node(N index, double x_, double y_) : i(index), x(x_), y(y_) {} - Node(const Node&) = delete; - Node& operator=(const Node&) = delete; - Node(Node&&) = delete; - Node& operator=(Node&&) = delete; - - const N i; - const double x; - const double y; - - // previous and next vertice nodes in a polygon ring - Node* prev = nullptr; - Node* next = nullptr; - - // z-order curve value - int32_t z = 0; - - // previous and next nodes in z-order - Node* prevZ = nullptr; - Node* nextZ = nullptr; - - // indicates whether this is a steiner point - bool steiner = false; - }; - - template <typename Ring> Node* linkedList(const Ring& points, const bool clockwise); - Node* filterPoints(Node* start, Node* end = nullptr); - void earcutLinked(Node* ear, int pass = 0); - bool isEar(Node* ear); - bool isEarHashed(Node* ear); - Node* cureLocalIntersections(Node* start); - void splitEarcut(Node* start); - template <typename Polygon> Node* eliminateHoles(const Polygon& points, Node* outerNode); - Node* eliminateHole(Node* hole, Node* outerNode); - Node* findHoleBridge(Node* hole, Node* outerNode); - bool sectorContainsSector(const Node* m, const Node* p); - void indexCurve(Node* start); - Node* sortLinked(Node* list); - int32_t zOrder(const double x_, const double y_); - Node* getLeftmost(Node* start); - bool pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const; - bool isValidDiagonal(Node* a, Node* b); - double area(const Node* p, const Node* q, const Node* r) const; - bool equals(const Node* p1, const Node* p2); - bool intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2); - bool onSegment(const Node* p, const Node* q, const Node* r); - int sign(double val); - bool intersectsPolygon(const Node* a, const Node* b); - bool locallyInside(const Node* a, const Node* b); - bool middleInside(const Node* a, const Node* b); - Node* splitPolygon(Node* a, Node* b); - template <typename Point> Node* insertNode(std::size_t i, const Point& p, Node* last); - void removeNode(Node* p); - - bool hashing; - double minX, maxX; - double minY, maxY; - double inv_size = 0; - - template <typename T, typename Alloc = std::allocator<T>> - class ObjectPool { - public: - ObjectPool() { } - ObjectPool(std::size_t blockSize_) { - reset(blockSize_); - } - ~ObjectPool() { - clear(); - } - template <typename... Args> - T* construct(Args&&... args) { - if (currentIndex >= blockSize) { - currentBlock = alloc_traits::allocate(alloc, blockSize); - allocations.emplace_back(currentBlock); - currentIndex = 0; - } - T* object = ¤tBlock[currentIndex++]; - alloc_traits::construct(alloc, object, std::forward<Args>(args)...); - return object; - } - void reset(std::size_t newBlockSize) { - for (auto allocation : allocations) { - alloc_traits::deallocate(alloc, allocation, blockSize); - } - allocations.clear(); - blockSize = std::max<std::size_t>(1, newBlockSize); - currentBlock = nullptr; - currentIndex = blockSize; - } - void clear() { reset(blockSize); } - private: - T* currentBlock = nullptr; - std::size_t currentIndex = 1; - std::size_t blockSize = 1; - std::vector<T*> allocations; - Alloc alloc; - typedef typename std::allocator_traits<Alloc> alloc_traits; - }; - ObjectPool<Node> nodes; -}; - -template <typename N> template <typename Polygon> -void Earcut<N>::operator()(const Polygon& points) { - // reset - indices.clear(); - vertices = 0; - - if (points.empty()) return; - - double x; - double y; - int threshold = 80; - std::size_t len = 0; - - for (size_t i = 0; threshold >= 0 && i < points.size(); i++) { - threshold -= static_cast<int>(points[i].size()); - len += points[i].size(); - } - - //estimate size of nodes and indices - nodes.reset(len * 3 / 2); - indices.reserve(len + points[0].size()); - - Node* outerNode = linkedList(points[0], true); - if (!outerNode || outerNode->prev == outerNode->next) return; - - if (points.size() > 1) outerNode = eliminateHoles(points, outerNode); - - // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox - hashing = threshold < 0; - if (hashing) { - Node* p = outerNode->next; - minX = maxX = outerNode->x; - minY = maxY = outerNode->y; - do { - x = p->x; - y = p->y; - minX = std::min<double>(minX, x); - minY = std::min<double>(minY, y); - maxX = std::max<double>(maxX, x); - maxY = std::max<double>(maxY, y); - p = p->next; - } while (p != outerNode); - - // minX, minY and size are later used to transform coords into integers for z-order calculation - inv_size = std::max<double>(maxX - minX, maxY - minY); - inv_size = inv_size != .0 ? (1. / inv_size) : .0; - } - - earcutLinked(outerNode); - - nodes.clear(); -} - -// create a circular doubly linked list from polygon points in the specified winding order -template <typename N> template <typename Ring> -typename Earcut<N>::Node* -Earcut<N>::linkedList(const Ring& points, const bool clockwise) { - using Point = typename Ring::value_type; - double sum = 0; - const std::size_t len = points.size(); - std::size_t i, j; - Node* last = nullptr; - - // calculate original winding order of a polygon ring - for (i = 0, j = len > 0 ? len - 1 : 0; i < len; j = i++) { - const auto& p1 = points[i]; - const auto& p2 = points[j]; - const double p20 = util::nth<0, Point>::get(p2); - const double p10 = util::nth<0, Point>::get(p1); - const double p11 = util::nth<1, Point>::get(p1); - const double p21 = util::nth<1, Point>::get(p2); - sum += (p20 - p10) * (p11 + p21); - } - - // link points into circular doubly-linked list in the specified winding order - if (clockwise == (sum > 0)) { - for (i = 0; i < len; i++) last = insertNode(vertices + i, points[i], last); - } else { - for (i = len; i-- > 0;) last = insertNode(vertices + i, points[i], last); - } - - if (last && equals(last, last->next)) { - removeNode(last); - last = last->next; - } - - vertices += len; - - return last; -} - -// eliminate colinear or duplicate points -template <typename N> -typename Earcut<N>::Node* -Earcut<N>::filterPoints(Node* start, Node* end) { - if (!end) end = start; - - Node* p = start; - bool again; - do { - again = false; - - if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) { - removeNode(p); - p = end = p->prev; - - if (p == p->next) break; - again = true; - - } else { - p = p->next; - } - } while (again || p != end); - - return end; -} - -// main ear slicing loop which triangulates a polygon (given as a linked list) -template <typename N> -void Earcut<N>::earcutLinked(Node* ear, int pass) { - if (!ear) return; - - // interlink polygon nodes in z-order - if (!pass && hashing) indexCurve(ear); - - Node* stop = ear; - Node* prev; - Node* next; - - int iterations = 0; - - // iterate through ears, slicing them one by one - while (ear->prev != ear->next) { - iterations++; - prev = ear->prev; - next = ear->next; - - if (hashing ? isEarHashed(ear) : isEar(ear)) { - // cut off the triangle - indices.emplace_back(prev->i); - indices.emplace_back(ear->i); - indices.emplace_back(next->i); - - removeNode(ear); - - // skipping the next vertice leads to less sliver triangles - ear = next->next; - stop = next->next; - - continue; - } - - ear = next; - - // if we looped through the whole remaining polygon and can't find any more ears - if (ear == stop) { - // try filtering points and slicing again - if (!pass) earcutLinked(filterPoints(ear), 1); - - // if this didn't work, try curing all small self-intersections locally - else if (pass == 1) { - ear = cureLocalIntersections(filterPoints(ear)); - earcutLinked(ear, 2); - - // as a last resort, try splitting the remaining polygon into two - } else if (pass == 2) splitEarcut(ear); - - break; - } - } -} - -// check whether a polygon node forms a valid ear with adjacent nodes -template <typename N> -bool Earcut<N>::isEar(Node* ear) { - const Node* a = ear->prev; - const Node* b = ear; - const Node* c = ear->next; - - if (area(a, b, c) >= 0) return false; // reflex, can't be an ear - - // now make sure we don't have other points inside the potential ear - Node* p = ear->next->next; - - while (p != ear->prev) { - if (pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && - area(p->prev, p, p->next) >= 0) return false; - p = p->next; - } - - return true; -} - -template <typename N> -bool Earcut<N>::isEarHashed(Node* ear) { - const Node* a = ear->prev; - const Node* b = ear; - const Node* c = ear->next; - - if (area(a, b, c) >= 0) return false; // reflex, can't be an ear - - // triangle bbox; min & max are calculated like this for speed - const double minTX = std::min<double>(a->x, std::min<double>(b->x, c->x)); - const double minTY = std::min<double>(a->y, std::min<double>(b->y, c->y)); - const double maxTX = std::max<double>(a->x, std::max<double>(b->x, c->x)); - const double maxTY = std::max<double>(a->y, std::max<double>(b->y, c->y)); - - // z-order range for the current triangle bbox; - const int32_t minZ = zOrder(minTX, minTY); - const int32_t maxZ = zOrder(maxTX, maxTY); - - // first look for points inside the triangle in increasing z-order - Node* p = ear->nextZ; - - while (p && p->z <= maxZ) { - if (p != ear->prev && p != ear->next && - pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && - area(p->prev, p, p->next) >= 0) return false; - p = p->nextZ; - } - - // then look for points in decreasing z-order - p = ear->prevZ; - - while (p && p->z >= minZ) { - if (p != ear->prev && p != ear->next && - pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && - area(p->prev, p, p->next) >= 0) return false; - p = p->prevZ; - } - - return true; -} - -// go through all polygon nodes and cure small local self-intersections -template <typename N> -typename Earcut<N>::Node* -Earcut<N>::cureLocalIntersections(Node* start) { - Node* p = start; - do { - Node* a = p->prev; - Node* b = p->next->next; - - // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2]) - if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) { - indices.emplace_back(a->i); - indices.emplace_back(p->i); - indices.emplace_back(b->i); - - // remove two nodes involved - removeNode(p); - removeNode(p->next); - - p = start = b; - } - p = p->next; - } while (p != start); - - return filterPoints(p); -} - -// try splitting polygon into two and triangulate them independently -template <typename N> -void Earcut<N>::splitEarcut(Node* start) { - // look for a valid diagonal that divides the polygon into two - Node* a = start; - do { - Node* b = a->next->next; - while (b != a->prev) { - if (a->i != b->i && isValidDiagonal(a, b)) { - // split the polygon in two by the diagonal - Node* c = splitPolygon(a, b); - - // filter colinear points around the cuts - a = filterPoints(a, a->next); - c = filterPoints(c, c->next); - - // run earcut on each half - earcutLinked(a); - earcutLinked(c); - return; - } - b = b->next; - } - a = a->next; - } while (a != start); -} - -// link every hole into the outer loop, producing a single-ring polygon without holes -template <typename N> template <typename Polygon> -typename Earcut<N>::Node* -Earcut<N>::eliminateHoles(const Polygon& points, Node* outerNode) { - const size_t len = points.size(); - - std::vector<Node*> queue; - for (size_t i = 1; i < len; i++) { - Node* list = linkedList(points[i], false); - if (list) { - if (list == list->next) list->steiner = true; - queue.push_back(getLeftmost(list)); - } - } - std::sort(queue.begin(), queue.end(), [](const Node* a, const Node* b) { - return a->x < b->x; - }); - - // process holes from left to right - for (size_t i = 0; i < queue.size(); i++) { - outerNode = eliminateHole(queue[i], outerNode); - outerNode = filterPoints(outerNode, outerNode->next); - } - - return outerNode; -} - -// find a bridge between vertices that connects hole with an outer ring and and link it -template <typename N> -typename Earcut<N>::Node* -Earcut<N>::eliminateHole(Node* hole, Node* outerNode) { - Node* bridge = findHoleBridge(hole, outerNode); - if (!bridge) { - return outerNode; - } - - Node* bridgeReverse = splitPolygon(bridge, hole); - - // filter collinear points around the cuts - Node* filteredBridge = filterPoints(bridge, bridge->next); - filterPoints(bridgeReverse, bridgeReverse->next); - - // Check if input node was removed by the filtering - return outerNode == bridge ? filteredBridge : outerNode; -} - -// David Eberly's algorithm for finding a bridge between hole and outer polygon -template <typename N> -typename Earcut<N>::Node* -Earcut<N>::findHoleBridge(Node* hole, Node* outerNode) { - Node* p = outerNode; - double hx = hole->x; - double hy = hole->y; - double qx = -std::numeric_limits<double>::infinity(); - Node* m = nullptr; - - // find a segment intersected by a ray from the hole's leftmost Vertex to the left; - // segment's endpoint with lesser x will be potential connection Vertex - do { - if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) { - double x = p->x + (hy - p->y) * (p->next->x - p->x) / (p->next->y - p->y); - if (x <= hx && x > qx) { - qx = x; - if (x == hx) { - if (hy == p->y) return p; - if (hy == p->next->y) return p->next; - } - m = p->x < p->next->x ? p : p->next; - } - } - p = p->next; - } while (p != outerNode); - - if (!m) return 0; - - if (hx == qx) return m; // hole touches outer segment; pick leftmost endpoint - - // look for points inside the triangle of hole Vertex, segment intersection and endpoint; - // if there are no points found, we have a valid connection; - // otherwise choose the Vertex of the minimum angle with the ray as connection Vertex - - const Node* stop = m; - double tanMin = std::numeric_limits<double>::infinity(); - double tanCur = 0; - - p = m; - double mx = m->x; - double my = m->y; - - do { - if (hx >= p->x && p->x >= mx && hx != p->x && - pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p->x, p->y)) { - - tanCur = std::abs(hy - p->y) / (hx - p->x); // tangential - - if (locallyInside(p, hole) && - (tanCur < tanMin || (tanCur == tanMin && (p->x > m->x || sectorContainsSector(m, p))))) { - m = p; - tanMin = tanCur; - } - } - - p = p->next; - } while (p != stop); - - return m; -} - -// whether sector in vertex m contains sector in vertex p in the same coordinates -template <typename N> -bool Earcut<N>::sectorContainsSector(const Node* m, const Node* p) { - return area(m->prev, m, p->prev) < 0 && area(p->next, m, m->next) < 0; -} - -// interlink polygon nodes in z-order -template <typename N> -void Earcut<N>::indexCurve(Node* start) { - assert(start); - Node* p = start; - - do { - p->z = p->z ? p->z : zOrder(p->x, p->y); - p->prevZ = p->prev; - p->nextZ = p->next; - p = p->next; - } while (p != start); - - p->prevZ->nextZ = nullptr; - p->prevZ = nullptr; - - sortLinked(p); -} - -// Simon Tatham's linked list merge sort algorithm -// http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html -template <typename N> -typename Earcut<N>::Node* -Earcut<N>::sortLinked(Node* list) { - assert(list); - Node* p; - Node* q; - Node* e; - Node* tail; - int i, numMerges, pSize, qSize; - int inSize = 1; - - for (;;) { - p = list; - list = nullptr; - tail = nullptr; - numMerges = 0; - - while (p) { - numMerges++; - q = p; - pSize = 0; - for (i = 0; i < inSize; i++) { - pSize++; - q = q->nextZ; - if (!q) break; - } - - qSize = inSize; - - while (pSize > 0 || (qSize > 0 && q)) { - - if (pSize == 0) { - e = q; - q = q->nextZ; - qSize--; - } else if (qSize == 0 || !q) { - e = p; - p = p->nextZ; - pSize--; - } else if (p->z <= q->z) { - e = p; - p = p->nextZ; - pSize--; - } else { - e = q; - q = q->nextZ; - qSize--; - } - - if (tail) tail->nextZ = e; - else list = e; - - e->prevZ = tail; - tail = e; - } - - p = q; - } - - tail->nextZ = nullptr; - - if (numMerges <= 1) return list; - - inSize *= 2; - } -} - -// z-order of a Vertex given coords and size of the data bounding box -template <typename N> -int32_t Earcut<N>::zOrder(const double x_, const double y_) { - // coords are transformed into non-negative 15-bit integer range - int32_t x = static_cast<int32_t>(32767.0 * (x_ - minX) * inv_size); - int32_t y = static_cast<int32_t>(32767.0 * (y_ - minY) * inv_size); - - x = (x | (x << 8)) & 0x00FF00FF; - x = (x | (x << 4)) & 0x0F0F0F0F; - x = (x | (x << 2)) & 0x33333333; - x = (x | (x << 1)) & 0x55555555; - - y = (y | (y << 8)) & 0x00FF00FF; - y = (y | (y << 4)) & 0x0F0F0F0F; - y = (y | (y << 2)) & 0x33333333; - y = (y | (y << 1)) & 0x55555555; - - return x | (y << 1); -} - -// find the leftmost node of a polygon ring -template <typename N> -typename Earcut<N>::Node* -Earcut<N>::getLeftmost(Node* start) { - Node* p = start; - Node* leftmost = start; - do { - if (p->x < leftmost->x || (p->x == leftmost->x && p->y < leftmost->y)) - leftmost = p; - p = p->next; - } while (p != start); - - return leftmost; -} - -// check if a point lies within a convex triangle -template <typename N> -bool Earcut<N>::pointInTriangle(double ax, double ay, double bx, double by, -double cx, double cy, double px, double py) const { - return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 && - (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 && - (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0; -} - -// check if a diagonal between two polygon nodes is valid (lies in polygon interior) -template <typename N> -bool Earcut<N>::isValidDiagonal(Node* a, Node* b) { - // dones't intersect other edges - return a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon(a, b) && - // locally visible - ((locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b) && - // does not create opposite-facing sectors - (area(a->prev, a, b->prev) != 0.0 || area(a, b->prev, b) != 0.0)) || - // special zero-length case - (equals(a, b) && area(a->prev, a, a->next) > 0 && area(b->prev, b, b->next) > 0)); -} - -// signed area of a triangle -template <typename N> -double Earcut<N>::area(const Node* p, const Node* q, const Node* r) const { - return (q->y - p->y) * (r->x - q->x) - (q->x - p->x) * (r->y - q->y); -} - -// check if two points are equal -template <typename N> -bool Earcut<N>::equals(const Node* p1, const Node* p2) { - return p1->x == p2->x && p1->y == p2->y; -} - -// check if two segments intersect -template <typename N> -bool Earcut<N>::intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2) { - int o1 = sign(area(p1, q1, p2)); - int o2 = sign(area(p1, q1, q2)); - int o3 = sign(area(p2, q2, p1)); - int o4 = sign(area(p2, q2, q1)); - - if (o1 != o2 && o3 != o4) return true; // general case - - if (o1 == 0 && onSegment(p1, p2, q1)) return true; // p1, q1 and p2 are collinear and p2 lies on p1q1 - if (o2 == 0 && onSegment(p1, q2, q1)) return true; // p1, q1 and q2 are collinear and q2 lies on p1q1 - if (o3 == 0 && onSegment(p2, p1, q2)) return true; // p2, q2 and p1 are collinear and p1 lies on p2q2 - if (o4 == 0 && onSegment(p2, q1, q2)) return true; // p2, q2 and q1 are collinear and q1 lies on p2q2 - - return false; -} - -// for collinear points p, q, r, check if point q lies on segment pr -template <typename N> -bool Earcut<N>::onSegment(const Node* p, const Node* q, const Node* r) { - return q->x <= std::max<double>(p->x, r->x) && - q->x >= std::min<double>(p->x, r->x) && - q->y <= std::max<double>(p->y, r->y) && - q->y >= std::min<double>(p->y, r->y); -} - -template <typename N> -int Earcut<N>::sign(double val) { - return (0.0 < val) - (val < 0.0); -} - -// check if a polygon diagonal intersects any polygon segments -template <typename N> -bool Earcut<N>::intersectsPolygon(const Node* a, const Node* b) { - const Node* p = a; - do { - if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i && - intersects(p, p->next, a, b)) return true; - p = p->next; - } while (p != a); - - return false; -} - -// check if a polygon diagonal is locally inside the polygon -template <typename N> -bool Earcut<N>::locallyInside(const Node* a, const Node* b) { - return area(a->prev, a, a->next) < 0 ? - area(a, b, a->next) >= 0 && area(a, a->prev, b) >= 0 : - area(a, b, a->prev) < 0 || area(a, a->next, b) < 0; -} - -// check if the middle Vertex of a polygon diagonal is inside the polygon -template <typename N> -bool Earcut<N>::middleInside(const Node* a, const Node* b) { - const Node* p = a; - bool inside = false; - double px = (a->x + b->x) / 2; - double py = (a->y + b->y) / 2; - do { - if (((p->y > py) != (p->next->y > py)) && p->next->y != p->y && - (px < (p->next->x - p->x) * (py - p->y) / (p->next->y - p->y) + p->x)) - inside = !inside; - p = p->next; - } while (p != a); - - return inside; -} - -// link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits -// polygon into two; if one belongs to the outer ring and another to a hole, it merges it into a -// single ring -template <typename N> -typename Earcut<N>::Node* -Earcut<N>::splitPolygon(Node* a, Node* b) { - Node* a2 = nodes.construct(a->i, a->x, a->y); - Node* b2 = nodes.construct(b->i, b->x, b->y); - Node* an = a->next; - Node* bp = b->prev; - - a->next = b; - b->prev = a; - - a2->next = an; - an->prev = a2; - - b2->next = a2; - a2->prev = b2; - - bp->next = b2; - b2->prev = bp; - - return b2; -} - -// create a node and util::optionally link it with previous one (in a circular doubly linked list) -template <typename N> template <typename Point> -typename Earcut<N>::Node* -Earcut<N>::insertNode(std::size_t i, const Point& pt, Node* last) { - Node* p = nodes.construct(static_cast<N>(i), util::nth<0, Point>::get(pt), util::nth<1, Point>::get(pt)); - - if (!last) { - p->prev = p; - p->next = p; - - } else { - assert(last); - p->next = last->next; - p->prev = last; - last->next->prev = p; - last->next = p; - } - return p; -} - -template <typename N> -void Earcut<N>::removeNode(Node* p) { - p->next->prev = p->prev; - p->prev->next = p->next; - - if (p->prevZ) p->prevZ->nextZ = p->nextZ; - if (p->nextZ) p->nextZ->prevZ = p->prevZ; -} -} - -template <typename N = uint32_t, typename Polygon> -std::vector<N> earcut(const Polygon& poly) { - mapbox::detail::Earcut<N> earcut; - earcut(poly); - return std::move(earcut.indices); -} -}
--- a/src/layers/edittools.cpp Tue Jun 28 19:47:34 2022 +0300 +++ b/src/layers/edittools.cpp Tue Jun 28 19:49:45 2022 +0300 @@ -18,7 +18,7 @@ #include <QMouseEvent> #include <QPainter> -#include "src/algorithm/earcut.h" +#include "thirdparty/earcut.h" #include "src/model.h" #include "src/ui/objecteditor.h" #include "src/gl/partrenderer.h"
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thirdparty/earcut.h Tue Jun 28 19:49:45 2022 +0300 @@ -0,0 +1,828 @@ +#pragma once + +#include <algorithm> +#include <cassert> +#include <cmath> +#include <cstddef> +#include <limits> +#include <memory> +#include <utility> +#include <vector> + +namespace mapbox { + +namespace util { + +template <std::size_t I, typename T> struct nth { + inline static typename std::tuple_element<I, T>::type + get(const T& t) { return std::get<I>(t); } +}; + +} + +namespace detail { + +template <typename N = uint32_t> +class Earcut { +public: + std::vector<N> indices; + std::size_t vertices = 0; + + template <typename Polygon> + void operator()(const Polygon& points); + +private: + struct Node { + Node(N index, double x_, double y_) : i(index), x(x_), y(y_) {} + Node(const Node&) = delete; + Node& operator=(const Node&) = delete; + Node(Node&&) = delete; + Node& operator=(Node&&) = delete; + + const N i; + const double x; + const double y; + + // previous and next vertice nodes in a polygon ring + Node* prev = nullptr; + Node* next = nullptr; + + // z-order curve value + int32_t z = 0; + + // previous and next nodes in z-order + Node* prevZ = nullptr; + Node* nextZ = nullptr; + + // indicates whether this is a steiner point + bool steiner = false; + }; + + template <typename Ring> Node* linkedList(const Ring& points, const bool clockwise); + Node* filterPoints(Node* start, Node* end = nullptr); + void earcutLinked(Node* ear, int pass = 0); + bool isEar(Node* ear); + bool isEarHashed(Node* ear); + Node* cureLocalIntersections(Node* start); + void splitEarcut(Node* start); + template <typename Polygon> Node* eliminateHoles(const Polygon& points, Node* outerNode); + Node* eliminateHole(Node* hole, Node* outerNode); + Node* findHoleBridge(Node* hole, Node* outerNode); + bool sectorContainsSector(const Node* m, const Node* p); + void indexCurve(Node* start); + Node* sortLinked(Node* list); + int32_t zOrder(const double x_, const double y_); + Node* getLeftmost(Node* start); + bool pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const; + bool isValidDiagonal(Node* a, Node* b); + double area(const Node* p, const Node* q, const Node* r) const; + bool equals(const Node* p1, const Node* p2); + bool intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2); + bool onSegment(const Node* p, const Node* q, const Node* r); + int sign(double val); + bool intersectsPolygon(const Node* a, const Node* b); + bool locallyInside(const Node* a, const Node* b); + bool middleInside(const Node* a, const Node* b); + Node* splitPolygon(Node* a, Node* b); + template <typename Point> Node* insertNode(std::size_t i, const Point& p, Node* last); + void removeNode(Node* p); + + bool hashing; + double minX, maxX; + double minY, maxY; + double inv_size = 0; + + template <typename T, typename Alloc = std::allocator<T>> + class ObjectPool { + public: + ObjectPool() { } + ObjectPool(std::size_t blockSize_) { + reset(blockSize_); + } + ~ObjectPool() { + clear(); + } + template <typename... Args> + T* construct(Args&&... args) { + if (currentIndex >= blockSize) { + currentBlock = alloc_traits::allocate(alloc, blockSize); + allocations.emplace_back(currentBlock); + currentIndex = 0; + } + T* object = ¤tBlock[currentIndex++]; + alloc_traits::construct(alloc, object, std::forward<Args>(args)...); + return object; + } + void reset(std::size_t newBlockSize) { + for (auto allocation : allocations) { + alloc_traits::deallocate(alloc, allocation, blockSize); + } + allocations.clear(); + blockSize = std::max<std::size_t>(1, newBlockSize); + currentBlock = nullptr; + currentIndex = blockSize; + } + void clear() { reset(blockSize); } + private: + T* currentBlock = nullptr; + std::size_t currentIndex = 1; + std::size_t blockSize = 1; + std::vector<T*> allocations; + Alloc alloc; + typedef typename std::allocator_traits<Alloc> alloc_traits; + }; + ObjectPool<Node> nodes; +}; + +template <typename N> template <typename Polygon> +void Earcut<N>::operator()(const Polygon& points) { + // reset + indices.clear(); + vertices = 0; + + if (points.empty()) return; + + double x; + double y; + int threshold = 80; + std::size_t len = 0; + + for (size_t i = 0; threshold >= 0 && i < points.size(); i++) { + threshold -= static_cast<int>(points[i].size()); + len += points[i].size(); + } + + //estimate size of nodes and indices + nodes.reset(len * 3 / 2); + indices.reserve(len + points[0].size()); + + Node* outerNode = linkedList(points[0], true); + if (!outerNode || outerNode->prev == outerNode->next) return; + + if (points.size() > 1) outerNode = eliminateHoles(points, outerNode); + + // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox + hashing = threshold < 0; + if (hashing) { + Node* p = outerNode->next; + minX = maxX = outerNode->x; + minY = maxY = outerNode->y; + do { + x = p->x; + y = p->y; + minX = std::min<double>(minX, x); + minY = std::min<double>(minY, y); + maxX = std::max<double>(maxX, x); + maxY = std::max<double>(maxY, y); + p = p->next; + } while (p != outerNode); + + // minX, minY and size are later used to transform coords into integers for z-order calculation + inv_size = std::max<double>(maxX - minX, maxY - minY); + inv_size = inv_size != .0 ? (1. / inv_size) : .0; + } + + earcutLinked(outerNode); + + nodes.clear(); +} + +// create a circular doubly linked list from polygon points in the specified winding order +template <typename N> template <typename Ring> +typename Earcut<N>::Node* +Earcut<N>::linkedList(const Ring& points, const bool clockwise) { + using Point = typename Ring::value_type; + double sum = 0; + const std::size_t len = points.size(); + std::size_t i, j; + Node* last = nullptr; + + // calculate original winding order of a polygon ring + for (i = 0, j = len > 0 ? len - 1 : 0; i < len; j = i++) { + const auto& p1 = points[i]; + const auto& p2 = points[j]; + const double p20 = util::nth<0, Point>::get(p2); + const double p10 = util::nth<0, Point>::get(p1); + const double p11 = util::nth<1, Point>::get(p1); + const double p21 = util::nth<1, Point>::get(p2); + sum += (p20 - p10) * (p11 + p21); + } + + // link points into circular doubly-linked list in the specified winding order + if (clockwise == (sum > 0)) { + for (i = 0; i < len; i++) last = insertNode(vertices + i, points[i], last); + } else { + for (i = len; i-- > 0;) last = insertNode(vertices + i, points[i], last); + } + + if (last && equals(last, last->next)) { + removeNode(last); + last = last->next; + } + + vertices += len; + + return last; +} + +// eliminate colinear or duplicate points +template <typename N> +typename Earcut<N>::Node* +Earcut<N>::filterPoints(Node* start, Node* end) { + if (!end) end = start; + + Node* p = start; + bool again; + do { + again = false; + + if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) { + removeNode(p); + p = end = p->prev; + + if (p == p->next) break; + again = true; + + } else { + p = p->next; + } + } while (again || p != end); + + return end; +} + +// main ear slicing loop which triangulates a polygon (given as a linked list) +template <typename N> +void Earcut<N>::earcutLinked(Node* ear, int pass) { + if (!ear) return; + + // interlink polygon nodes in z-order + if (!pass && hashing) indexCurve(ear); + + Node* stop = ear; + Node* prev; + Node* next; + + int iterations = 0; + + // iterate through ears, slicing them one by one + while (ear->prev != ear->next) { + iterations++; + prev = ear->prev; + next = ear->next; + + if (hashing ? isEarHashed(ear) : isEar(ear)) { + // cut off the triangle + indices.emplace_back(prev->i); + indices.emplace_back(ear->i); + indices.emplace_back(next->i); + + removeNode(ear); + + // skipping the next vertice leads to less sliver triangles + ear = next->next; + stop = next->next; + + continue; + } + + ear = next; + + // if we looped through the whole remaining polygon and can't find any more ears + if (ear == stop) { + // try filtering points and slicing again + if (!pass) earcutLinked(filterPoints(ear), 1); + + // if this didn't work, try curing all small self-intersections locally + else if (pass == 1) { + ear = cureLocalIntersections(filterPoints(ear)); + earcutLinked(ear, 2); + + // as a last resort, try splitting the remaining polygon into two + } else if (pass == 2) splitEarcut(ear); + + break; + } + } +} + +// check whether a polygon node forms a valid ear with adjacent nodes +template <typename N> +bool Earcut<N>::isEar(Node* ear) { + const Node* a = ear->prev; + const Node* b = ear; + const Node* c = ear->next; + + if (area(a, b, c) >= 0) return false; // reflex, can't be an ear + + // now make sure we don't have other points inside the potential ear + Node* p = ear->next->next; + + while (p != ear->prev) { + if (pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && + area(p->prev, p, p->next) >= 0) return false; + p = p->next; + } + + return true; +} + +template <typename N> +bool Earcut<N>::isEarHashed(Node* ear) { + const Node* a = ear->prev; + const Node* b = ear; + const Node* c = ear->next; + + if (area(a, b, c) >= 0) return false; // reflex, can't be an ear + + // triangle bbox; min & max are calculated like this for speed + const double minTX = std::min<double>(a->x, std::min<double>(b->x, c->x)); + const double minTY = std::min<double>(a->y, std::min<double>(b->y, c->y)); + const double maxTX = std::max<double>(a->x, std::max<double>(b->x, c->x)); + const double maxTY = std::max<double>(a->y, std::max<double>(b->y, c->y)); + + // z-order range for the current triangle bbox; + const int32_t minZ = zOrder(minTX, minTY); + const int32_t maxZ = zOrder(maxTX, maxTY); + + // first look for points inside the triangle in increasing z-order + Node* p = ear->nextZ; + + while (p && p->z <= maxZ) { + if (p != ear->prev && p != ear->next && + pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && + area(p->prev, p, p->next) >= 0) return false; + p = p->nextZ; + } + + // then look for points in decreasing z-order + p = ear->prevZ; + + while (p && p->z >= minZ) { + if (p != ear->prev && p != ear->next && + pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) && + area(p->prev, p, p->next) >= 0) return false; + p = p->prevZ; + } + + return true; +} + +// go through all polygon nodes and cure small local self-intersections +template <typename N> +typename Earcut<N>::Node* +Earcut<N>::cureLocalIntersections(Node* start) { + Node* p = start; + do { + Node* a = p->prev; + Node* b = p->next->next; + + // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2]) + if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) { + indices.emplace_back(a->i); + indices.emplace_back(p->i); + indices.emplace_back(b->i); + + // remove two nodes involved + removeNode(p); + removeNode(p->next); + + p = start = b; + } + p = p->next; + } while (p != start); + + return filterPoints(p); +} + +// try splitting polygon into two and triangulate them independently +template <typename N> +void Earcut<N>::splitEarcut(Node* start) { + // look for a valid diagonal that divides the polygon into two + Node* a = start; + do { + Node* b = a->next->next; + while (b != a->prev) { + if (a->i != b->i && isValidDiagonal(a, b)) { + // split the polygon in two by the diagonal + Node* c = splitPolygon(a, b); + + // filter colinear points around the cuts + a = filterPoints(a, a->next); + c = filterPoints(c, c->next); + + // run earcut on each half + earcutLinked(a); + earcutLinked(c); + return; + } + b = b->next; + } + a = a->next; + } while (a != start); +} + +// link every hole into the outer loop, producing a single-ring polygon without holes +template <typename N> template <typename Polygon> +typename Earcut<N>::Node* +Earcut<N>::eliminateHoles(const Polygon& points, Node* outerNode) { + const size_t len = points.size(); + + std::vector<Node*> queue; + for (size_t i = 1; i < len; i++) { + Node* list = linkedList(points[i], false); + if (list) { + if (list == list->next) list->steiner = true; + queue.push_back(getLeftmost(list)); + } + } + std::sort(queue.begin(), queue.end(), [](const Node* a, const Node* b) { + return a->x < b->x; + }); + + // process holes from left to right + for (size_t i = 0; i < queue.size(); i++) { + outerNode = eliminateHole(queue[i], outerNode); + outerNode = filterPoints(outerNode, outerNode->next); + } + + return outerNode; +} + +// find a bridge between vertices that connects hole with an outer ring and and link it +template <typename N> +typename Earcut<N>::Node* +Earcut<N>::eliminateHole(Node* hole, Node* outerNode) { + Node* bridge = findHoleBridge(hole, outerNode); + if (!bridge) { + return outerNode; + } + + Node* bridgeReverse = splitPolygon(bridge, hole); + + // filter collinear points around the cuts + Node* filteredBridge = filterPoints(bridge, bridge->next); + filterPoints(bridgeReverse, bridgeReverse->next); + + // Check if input node was removed by the filtering + return outerNode == bridge ? filteredBridge : outerNode; +} + +// David Eberly's algorithm for finding a bridge between hole and outer polygon +template <typename N> +typename Earcut<N>::Node* +Earcut<N>::findHoleBridge(Node* hole, Node* outerNode) { + Node* p = outerNode; + double hx = hole->x; + double hy = hole->y; + double qx = -std::numeric_limits<double>::infinity(); + Node* m = nullptr; + + // find a segment intersected by a ray from the hole's leftmost Vertex to the left; + // segment's endpoint with lesser x will be potential connection Vertex + do { + if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) { + double x = p->x + (hy - p->y) * (p->next->x - p->x) / (p->next->y - p->y); + if (x <= hx && x > qx) { + qx = x; + if (x == hx) { + if (hy == p->y) return p; + if (hy == p->next->y) return p->next; + } + m = p->x < p->next->x ? p : p->next; + } + } + p = p->next; + } while (p != outerNode); + + if (!m) return 0; + + if (hx == qx) return m; // hole touches outer segment; pick leftmost endpoint + + // look for points inside the triangle of hole Vertex, segment intersection and endpoint; + // if there are no points found, we have a valid connection; + // otherwise choose the Vertex of the minimum angle with the ray as connection Vertex + + const Node* stop = m; + double tanMin = std::numeric_limits<double>::infinity(); + double tanCur = 0; + + p = m; + double mx = m->x; + double my = m->y; + + do { + if (hx >= p->x && p->x >= mx && hx != p->x && + pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p->x, p->y)) { + + tanCur = std::abs(hy - p->y) / (hx - p->x); // tangential + + if (locallyInside(p, hole) && + (tanCur < tanMin || (tanCur == tanMin && (p->x > m->x || sectorContainsSector(m, p))))) { + m = p; + tanMin = tanCur; + } + } + + p = p->next; + } while (p != stop); + + return m; +} + +// whether sector in vertex m contains sector in vertex p in the same coordinates +template <typename N> +bool Earcut<N>::sectorContainsSector(const Node* m, const Node* p) { + return area(m->prev, m, p->prev) < 0 && area(p->next, m, m->next) < 0; +} + +// interlink polygon nodes in z-order +template <typename N> +void Earcut<N>::indexCurve(Node* start) { + assert(start); + Node* p = start; + + do { + p->z = p->z ? p->z : zOrder(p->x, p->y); + p->prevZ = p->prev; + p->nextZ = p->next; + p = p->next; + } while (p != start); + + p->prevZ->nextZ = nullptr; + p->prevZ = nullptr; + + sortLinked(p); +} + +// Simon Tatham's linked list merge sort algorithm +// http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html +template <typename N> +typename Earcut<N>::Node* +Earcut<N>::sortLinked(Node* list) { + assert(list); + Node* p; + Node* q; + Node* e; + Node* tail; + int i, numMerges, pSize, qSize; + int inSize = 1; + + for (;;) { + p = list; + list = nullptr; + tail = nullptr; + numMerges = 0; + + while (p) { + numMerges++; + q = p; + pSize = 0; + for (i = 0; i < inSize; i++) { + pSize++; + q = q->nextZ; + if (!q) break; + } + + qSize = inSize; + + while (pSize > 0 || (qSize > 0 && q)) { + + if (pSize == 0) { + e = q; + q = q->nextZ; + qSize--; + } else if (qSize == 0 || !q) { + e = p; + p = p->nextZ; + pSize--; + } else if (p->z <= q->z) { + e = p; + p = p->nextZ; + pSize--; + } else { + e = q; + q = q->nextZ; + qSize--; + } + + if (tail) tail->nextZ = e; + else list = e; + + e->prevZ = tail; + tail = e; + } + + p = q; + } + + tail->nextZ = nullptr; + + if (numMerges <= 1) return list; + + inSize *= 2; + } +} + +// z-order of a Vertex given coords and size of the data bounding box +template <typename N> +int32_t Earcut<N>::zOrder(const double x_, const double y_) { + // coords are transformed into non-negative 15-bit integer range + int32_t x = static_cast<int32_t>(32767.0 * (x_ - minX) * inv_size); + int32_t y = static_cast<int32_t>(32767.0 * (y_ - minY) * inv_size); + + x = (x | (x << 8)) & 0x00FF00FF; + x = (x | (x << 4)) & 0x0F0F0F0F; + x = (x | (x << 2)) & 0x33333333; + x = (x | (x << 1)) & 0x55555555; + + y = (y | (y << 8)) & 0x00FF00FF; + y = (y | (y << 4)) & 0x0F0F0F0F; + y = (y | (y << 2)) & 0x33333333; + y = (y | (y << 1)) & 0x55555555; + + return x | (y << 1); +} + +// find the leftmost node of a polygon ring +template <typename N> +typename Earcut<N>::Node* +Earcut<N>::getLeftmost(Node* start) { + Node* p = start; + Node* leftmost = start; + do { + if (p->x < leftmost->x || (p->x == leftmost->x && p->y < leftmost->y)) + leftmost = p; + p = p->next; + } while (p != start); + + return leftmost; +} + +// check if a point lies within a convex triangle +template <typename N> +bool Earcut<N>::pointInTriangle(double ax, double ay, double bx, double by, +double cx, double cy, double px, double py) const { + return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 && + (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 && + (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0; +} + +// check if a diagonal between two polygon nodes is valid (lies in polygon interior) +template <typename N> +bool Earcut<N>::isValidDiagonal(Node* a, Node* b) { + // dones't intersect other edges + return a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon(a, b) && + // locally visible + ((locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b) && + // does not create opposite-facing sectors + (area(a->prev, a, b->prev) != 0.0 || area(a, b->prev, b) != 0.0)) || + // special zero-length case + (equals(a, b) && area(a->prev, a, a->next) > 0 && area(b->prev, b, b->next) > 0)); +} + +// signed area of a triangle +template <typename N> +double Earcut<N>::area(const Node* p, const Node* q, const Node* r) const { + return (q->y - p->y) * (r->x - q->x) - (q->x - p->x) * (r->y - q->y); +} + +// check if two points are equal +template <typename N> +bool Earcut<N>::equals(const Node* p1, const Node* p2) { + return p1->x == p2->x && p1->y == p2->y; +} + +// check if two segments intersect +template <typename N> +bool Earcut<N>::intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2) { + int o1 = sign(area(p1, q1, p2)); + int o2 = sign(area(p1, q1, q2)); + int o3 = sign(area(p2, q2, p1)); + int o4 = sign(area(p2, q2, q1)); + + if (o1 != o2 && o3 != o4) return true; // general case + + if (o1 == 0 && onSegment(p1, p2, q1)) return true; // p1, q1 and p2 are collinear and p2 lies on p1q1 + if (o2 == 0 && onSegment(p1, q2, q1)) return true; // p1, q1 and q2 are collinear and q2 lies on p1q1 + if (o3 == 0 && onSegment(p2, p1, q2)) return true; // p2, q2 and p1 are collinear and p1 lies on p2q2 + if (o4 == 0 && onSegment(p2, q1, q2)) return true; // p2, q2 and q1 are collinear and q1 lies on p2q2 + + return false; +} + +// for collinear points p, q, r, check if point q lies on segment pr +template <typename N> +bool Earcut<N>::onSegment(const Node* p, const Node* q, const Node* r) { + return q->x <= std::max<double>(p->x, r->x) && + q->x >= std::min<double>(p->x, r->x) && + q->y <= std::max<double>(p->y, r->y) && + q->y >= std::min<double>(p->y, r->y); +} + +template <typename N> +int Earcut<N>::sign(double val) { + return (0.0 < val) - (val < 0.0); +} + +// check if a polygon diagonal intersects any polygon segments +template <typename N> +bool Earcut<N>::intersectsPolygon(const Node* a, const Node* b) { + const Node* p = a; + do { + if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i && + intersects(p, p->next, a, b)) return true; + p = p->next; + } while (p != a); + + return false; +} + +// check if a polygon diagonal is locally inside the polygon +template <typename N> +bool Earcut<N>::locallyInside(const Node* a, const Node* b) { + return area(a->prev, a, a->next) < 0 ? + area(a, b, a->next) >= 0 && area(a, a->prev, b) >= 0 : + area(a, b, a->prev) < 0 || area(a, a->next, b) < 0; +} + +// check if the middle Vertex of a polygon diagonal is inside the polygon +template <typename N> +bool Earcut<N>::middleInside(const Node* a, const Node* b) { + const Node* p = a; + bool inside = false; + double px = (a->x + b->x) / 2; + double py = (a->y + b->y) / 2; + do { + if (((p->y > py) != (p->next->y > py)) && p->next->y != p->y && + (px < (p->next->x - p->x) * (py - p->y) / (p->next->y - p->y) + p->x)) + inside = !inside; + p = p->next; + } while (p != a); + + return inside; +} + +// link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits +// polygon into two; if one belongs to the outer ring and another to a hole, it merges it into a +// single ring +template <typename N> +typename Earcut<N>::Node* +Earcut<N>::splitPolygon(Node* a, Node* b) { + Node* a2 = nodes.construct(a->i, a->x, a->y); + Node* b2 = nodes.construct(b->i, b->x, b->y); + Node* an = a->next; + Node* bp = b->prev; + + a->next = b; + b->prev = a; + + a2->next = an; + an->prev = a2; + + b2->next = a2; + a2->prev = b2; + + bp->next = b2; + b2->prev = bp; + + return b2; +} + +// create a node and util::optionally link it with previous one (in a circular doubly linked list) +template <typename N> template <typename Point> +typename Earcut<N>::Node* +Earcut<N>::insertNode(std::size_t i, const Point& pt, Node* last) { + Node* p = nodes.construct(static_cast<N>(i), util::nth<0, Point>::get(pt), util::nth<1, Point>::get(pt)); + + if (!last) { + p->prev = p; + p->next = p; + + } else { + assert(last); + p->next = last->next; + p->prev = last; + last->next->prev = p; + last->next = p; + } + return p; +} + +template <typename N> +void Earcut<N>::removeNode(Node* p) { + p->next->prev = p->prev; + p->prev->next = p->next; + + if (p->prevZ) p->prevZ->nextZ = p->nextZ; + if (p->nextZ) p->nextZ->prevZ = p->prevZ; +} +} + +template <typename N = uint32_t, typename Polygon> +std::vector<N> earcut(const Polygon& poly) { + mapbox::detail::Earcut<N> earcut; + earcut(poly); + return std::move(earcut.indices); +} +}
