| #pragma once |
| #ifndef EARCUT_HPP |
| #define EARCUT_HPP |
| |
| #include <array> |
| #include <algorithm> |
| #include <cassert> |
| #include <cmath> |
| #include <memory> |
| #include <vector> |
| |
| namespace qt_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; |
| N 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); |
| void eliminateHole(Node* hole, Node* outerNode); |
| Node* findHoleBridge(Node* hole, Node* outerNode); |
| 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 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(N i, const Point& p, Node* last); |
| void removeNode(Node* p); |
| |
| bool hashing; |
| double minX, maxX; |
| double minY, maxY; |
| double size; |
| |
| 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.allocate(blockSize); |
| allocations.emplace_back(currentBlock); |
| currentIndex = 0; |
| } |
| T* object = ¤tBlock[currentIndex++]; |
| alloc.construct(object, std::forward<Args>(args)...); |
| return object; |
| } |
| void reset(std::size_t newBlockSize) { |
| for (auto allocation : allocations) alloc.deallocate(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; |
| }; |
| 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; |
| size = 0; |
| 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) 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 = p->x; |
| minY = maxY = p->y; |
| do { |
| x = p->x; |
| y = p->y; |
| minX = (std::min)(minX, x); |
| minY = (std::min)(minY, y); |
| maxX = (std::max)(maxX, x); |
| maxY = (std::max)(maxY, y); |
| p = p->next; |
| } while (p != outerNode); |
| |
| // minX, minY and size are later used to transform coords into integers for z-order calculation |
| size = (std::max)(maxX - minX, maxY - minY); |
| } |
| |
| 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 int len = static_cast<int>(points.size()); |
| int i, j; |
| Point p1, p2; |
| Node* last = nullptr; |
| |
| // calculate original winding order of a polygon ring |
| for (i = 0, j = len - 1; i < len; j = i++) { |
| p1 = points[i]; |
| 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 - 1; i >= 0; i--) 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) return nullptr; |
| 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(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)(a->x, (std::min)(b->x, c->x)); |
| const double minTY = (std::min)(a->y, (std::min)(b->y, c->y)); |
| const double maxTX = (std::max)(a->x, (std::max)(b->x, c->x)); |
| const double maxTY = (std::max)(a->y, (std::max)(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 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++) { |
| 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> |
| void Earcut<N>::eliminateHole(Node* hole, Node* outerNode) { |
| outerNode = findHoleBridge(hole, outerNode); |
| if (outerNode) { |
| Node* b = splitPolygon(outerNode, hole); |
| filterPoints(b, b->next); |
| } |
| } |
| |
| // 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->prev; |
| |
| // 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->next; |
| double mx = m->x; |
| double my = m->y; |
| |
| while (p != stop) { |
| 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 ((tanCur < tanMin || (tanCur == tanMin && p->x > m->x)) && locallyInside(p, hole)) { |
| m = p; |
| tanMin = tanCur; |
| } |
| } |
| |
| p = p->next; |
| } |
| |
| return m; |
| } |
| |
| // 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; |
| |
| while (true) { |
| 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) / size); |
| int32_t y = static_cast<int32_t>(32767.0 * (y_ - minY) / 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) 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) { |
| return a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon(a, b) && |
| locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b); |
| } |
| |
| // 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) { |
| if ((equals(p1, q1) && equals(p2, q2)) || |
| (equals(p1, q2) && equals(p2, q1))) return true; |
| return (area(p1, q1, p2) > 0) != (area(p1, q1, q2) > 0) && |
| (area(p2, q2, p1) > 0) != (area(p2, q2, q1) > 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(N i, const Point& pt, Node* last) { |
| Node* p = nodes.construct(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) { |
| qt_mapbox::detail::Earcut<N> earcut; |
| earcut(poly); |
| return earcut.indices; |
| } |
| } |
| #endif //EARCUT_HPP |