source: XIOS/dev/branch_openmp/extern/remap/src/earcut.hpp @ 1643

Last change on this file since 1643 was 1643, checked in by yushan, 3 years ago

dev on ADA. add new files

File size: 22.5 KB
Line 
1#pragma once
2
3#include <algorithm>
4#include <cassert>
5#include <cmath>
6#include <memory>
7#include <vector>
8//#include <tuple>
9//#include <cstdint>
10//#include <cstddef>
11
12namespace mapbox {
13
14namespace util {
15
16  template <std::size_t I, typename T> struct nth {
17  inline static typename std::tuple_element<I, T>::type
18  get(const T& t) { return std::get<I>(t); };
19};
20
21}
22
23namespace detail {
24
25template <typename N = std::uint32_t>
26class Earcut {
27public:
28    std::vector<N> indices;
29    std::size_t vertices = 0;
30
31    template <typename Polygon>
32    void operator()(const Polygon& points);
33
34private:
35    struct Node {
36        Node(N index, double x_, double y_) : i(index), x(x_), y(y_) {}
37        Node(const Node&) = delete;
38        Node& operator=(const Node&) = delete;
39        Node(Node&&) = delete;
40        Node& operator=(Node&&) = delete;
41
42        const N i;
43        const double x;
44        const double y;
45
46        // previous and next vertice nodes in a polygon ring
47        Node* prev = nullptr;
48        Node* next = nullptr;
49
50        // z-order curve value
51        int32_t z = 0;
52
53        // previous and next nodes in z-order
54        Node* prevZ = nullptr;
55        Node* nextZ = nullptr;
56
57        // indicates whether this is a steiner point
58        bool steiner = false;
59    };
60
61    template <typename Ring> Node* linkedList(const Ring& points, const bool clockwise);
62    Node* filterPoints(Node* start, Node* end = nullptr);
63    void earcutLinked(Node* ear, int pass = 0);
64    bool isEar(Node* ear);
65    bool isEarHashed(Node* ear);
66    Node* cureLocalIntersections(Node* start);
67    void splitEarcut(Node* start);
68    template <typename Polygon> Node* eliminateHoles(const Polygon& points, Node* outerNode);
69    void eliminateHole(Node* hole, Node* outerNode);
70    Node* findHoleBridge(Node* hole, Node* outerNode);
71    void indexCurve(Node* start);
72    Node* sortLinked(Node* list);
73    int32_t zOrder(const double x_, const double y_);
74    Node* getLeftmost(Node* start);
75    bool pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const;
76    bool isValidDiagonal(Node* a, Node* b);
77    double area(const Node* p, const Node* q, const Node* r) const;
78    bool equals(const Node* p1, const Node* p2);
79    bool intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2);
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        }
99        ~ObjectPool() {
100            clear();
101        }
102        template <typename... Args>
103        T* construct(Args&&... args) {
104            if (currentIndex >= blockSize) {
105                currentBlock = alloc.allocate(blockSize);
106                allocations.emplace_back(currentBlock);
107                currentIndex = 0;
108            }
109            T* object = &currentBlock[currentIndex++];
110            alloc.construct(object, std::forward<Args>(args)...);
111            return object;
112        }
113        void reset(std::size_t newBlockSize) {
114            for (auto allocation : allocations) alloc.deallocate(allocation, blockSize);
115            allocations.clear();
116            blockSize = std::max<std::size_t>(1, newBlockSize);
117            currentBlock = nullptr;
118            currentIndex = blockSize;
119        }
120        void clear() { reset(blockSize); }
121    private:
122        T* currentBlock = nullptr;
123        std::size_t currentIndex = 1;
124        std::size_t blockSize = 1;
125        std::vector<T*> allocations;
126        Alloc alloc;
127    };
128    ObjectPool<Node> nodes;
129};
130
131template <typename N> template <typename Polygon>
132void Earcut<N>::operator()(const Polygon& points) {
133    // reset
134    indices.clear();
135    vertices = 0;
136
137    if (points.empty()) return;
138
139    double x;
140    double y;
141    int threshold = 80;
142    std::size_t len = 0;
143
144    for (size_t i = 0; threshold >= 0 && i < points.size(); i++) {
145        threshold -= static_cast<int>(points[i].size());
146        len += points[i].size();
147    }
148
149    //estimate size of nodes and indices
150    nodes.reset(len * 3 / 2);
151    indices.reserve(len + points[0].size());
152
153    Node* outerNode = linkedList(points[0], true);
154    if (!outerNode) return;
155
156    if (points.size() > 1) outerNode = eliminateHoles(points, outerNode);
157
158    // if the shape is not too simple, we'll use z-order curve hash later; calculate polygon bbox
159    hashing = threshold < 0;
160    if (hashing) {
161        Node* p = outerNode->next;
162        minX = maxX = outerNode->x;
163        minY = maxY = outerNode->y;
164        do {
165            x = p->x;
166            y = p->y;
167            minX = std::min<double>(minX, x);
168            minY = std::min<double>(minY, y);
169            maxX = std::max<double>(maxX, x);
170            maxY = std::max<double>(maxY, y);
171            p = p->next;
172        } while (p != outerNode);
173
174        // minX, minY and size are later used to transform coords into integers for z-order calculation
175        inv_size = std::max<double>(maxX - minX, maxY - minY);
176        inv_size = inv_size != .0 ? (1. / inv_size) : .0;
177    }
178
179    earcutLinked(outerNode);
180
181    nodes.clear();
182}
183
184// create a circular doubly linked list from polygon points in the specified winding order
185template <typename N> template <typename Ring>
186typename Earcut<N>::Node*
187Earcut<N>::linkedList(const Ring& points, const bool clockwise) {
188    using Point = typename Ring::value_type;
189    double sum = 0;
190    const std::size_t len = points.size();
191    std::size_t i, j;
192    Node* last = nullptr;
193
194    // calculate original winding order of a polygon ring
195    for (i = 0, j = len > 0 ? len - 1 : 0; i < len; j = i++) {
196        const auto& p1 = points[i];
197        const auto& p2 = points[j];
198        const double p20 = util::nth<0, Point>::get(p2);
199        const double p10 = util::nth<0, Point>::get(p1);
200        const double p11 = util::nth<1, Point>::get(p1);
201        const double p21 = util::nth<1, Point>::get(p2);
202        sum += (p20 - p10) * (p11 + p21);
203    }
204
205    // link points into circular doubly-linked list in the specified winding order
206    if (clockwise == (sum > 0)) {
207        for (i = 0; i < len; i++) last = insertNode(vertices + i, points[i], last);
208    } else {
209        for (i = len; i-- > 0;) last = insertNode(vertices + i, points[i], last);
210    }
211
212    if (last && equals(last, last->next)) {
213        removeNode(last);
214        last = last->next;
215    }
216
217    vertices += len;
218
219    return last;
220}
221
222// eliminate colinear or duplicate points
223template <typename N>
224typename Earcut<N>::Node*
225Earcut<N>::filterPoints(Node* start, Node* end) {
226    if (!end) end = start;
227
228    Node* p = start;
229    bool again;
230    do {
231        again = false;
232
233        if (!p->steiner && (equals(p, p->next) || area(p->prev, p, p->next) == 0)) {
234            removeNode(p);
235            p = end = p->prev;
236
237            if (p == p->next) break;
238            again = true;
239
240        } else {
241            p = p->next;
242        }
243    } while (again || p != end);
244
245    return end;
246}
247
248// main ear slicing loop which triangulates a polygon (given as a linked list)
249template <typename N>
250void Earcut<N>::earcutLinked(Node* ear, int pass) {
251    if (!ear) return;
252
253    // interlink polygon nodes in z-order
254    if (!pass && hashing) indexCurve(ear);
255
256    Node* stop = ear;
257    Node* prev;
258    Node* next;
259
260    int iterations = 0;
261
262    // iterate through ears, slicing them one by one
263    while (ear->prev != ear->next) {
264        iterations++;
265        prev = ear->prev;
266        next = ear->next;
267
268        if (hashing ? isEarHashed(ear) : isEar(ear)) {
269            // cut off the triangle
270            indices.emplace_back(prev->i);
271            indices.emplace_back(ear->i);
272            indices.emplace_back(next->i);
273
274            removeNode(ear);
275
276            // skipping the next vertice leads to less sliver triangles
277            ear = next->next;
278            stop = next->next;
279
280            continue;
281        }
282
283        ear = next;
284
285        // if we looped through the whole remaining polygon and can't find any more ears
286        if (ear == stop) {
287            // try filtering points and slicing again
288            if (!pass) earcutLinked(filterPoints(ear), 1);
289
290            // if this didn't work, try curing all small self-intersections locally
291            else if (pass == 1) {
292                ear = cureLocalIntersections(ear);
293                earcutLinked(ear, 2);
294
295            // as a last resort, try splitting the remaining polygon into two
296            } else if (pass == 2) splitEarcut(ear);
297
298            break;
299        }
300    }
301}
302
303// check whether a polygon node forms a valid ear with adjacent nodes
304template <typename N>
305bool Earcut<N>::isEar(Node* ear) {
306    const Node* a = ear->prev;
307    const Node* b = ear;
308    const Node* c = ear->next;
309
310    if (area(a, b, c) >= 0) return false; // reflex, can't be an ear
311
312    // now make sure we don't have other points inside the potential ear
313    Node* p = ear->next->next;
314
315    while (p != ear->prev) {
316        if (pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
317            area(p->prev, p, p->next) >= 0) return false;
318        p = p->next;
319    }
320
321    return true;
322}
323
324template <typename N>
325bool Earcut<N>::isEarHashed(Node* ear) {
326    const Node* a = ear->prev;
327    const Node* b = ear;
328    const Node* c = ear->next;
329
330    if (area(a, b, c) >= 0) return false; // reflex, can't be an ear
331
332    // triangle bbox; min & max are calculated like this for speed
333    const double minTX = std::min<double>(a->x, std::min<double>(b->x, c->x));
334    const double minTY = std::min<double>(a->y, std::min<double>(b->y, c->y));
335    const double maxTX = std::max<double>(a->x, std::max<double>(b->x, c->x));
336    const double maxTY = std::max<double>(a->y, std::max<double>(b->y, c->y));
337
338    // z-order range for the current triangle bbox;
339    const int32_t minZ = zOrder(minTX, minTY);
340    const int32_t maxZ = zOrder(maxTX, maxTY);
341
342    // first look for points inside the triangle in increasing z-order
343    Node* p = ear->nextZ;
344
345    while (p && p->z <= maxZ) {
346        if (p != ear->prev && p != ear->next &&
347            pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
348            area(p->prev, p, p->next) >= 0) return false;
349        p = p->nextZ;
350    }
351
352    // then look for points in decreasing z-order
353    p = ear->prevZ;
354
355    while (p && p->z >= minZ) {
356        if (p != ear->prev && p != ear->next &&
357            pointInTriangle(a->x, a->y, b->x, b->y, c->x, c->y, p->x, p->y) &&
358            area(p->prev, p, p->next) >= 0) return false;
359        p = p->prevZ;
360    }
361
362    return true;
363}
364
365// go through all polygon nodes and cure small local self-intersections
366template <typename N>
367typename Earcut<N>::Node*
368Earcut<N>::cureLocalIntersections(Node* start) {
369    Node* p = start;
370    do {
371        Node* a = p->prev;
372        Node* b = p->next->next;
373
374        // a self-intersection where edge (v[i-1],v[i]) intersects (v[i+1],v[i+2])
375        if (!equals(a, b) && intersects(a, p, p->next, b) && locallyInside(a, b) && locallyInside(b, a)) {
376            indices.emplace_back(a->i);
377            indices.emplace_back(p->i);
378            indices.emplace_back(b->i);
379
380            // remove two nodes involved
381            removeNode(p);
382            removeNode(p->next);
383
384            p = start = b;
385        }
386        p = p->next;
387    } while (p != start);
388
389    return p;
390}
391
392// try splitting polygon into two and triangulate them independently
393template <typename N>
394void Earcut<N>::splitEarcut(Node* start) {
395    // look for a valid diagonal that divides the polygon into two
396    Node* a = start;
397    do {
398        Node* b = a->next->next;
399        while (b != a->prev) {
400            if (a->i != b->i && isValidDiagonal(a, b)) {
401                // split the polygon in two by the diagonal
402                Node* c = splitPolygon(a, b);
403
404                // filter colinear points around the cuts
405                a = filterPoints(a, a->next);
406                c = filterPoints(c, c->next);
407
408                // run earcut on each half
409                earcutLinked(a);
410                earcutLinked(c);
411                return;
412            }
413            b = b->next;
414        }
415        a = a->next;
416    } while (a != start);
417}
418
419// link every hole into the outer loop, producing a single-ring polygon without holes
420template <typename N> template <typename Polygon>
421typename Earcut<N>::Node*
422Earcut<N>::eliminateHoles(const Polygon& points, Node* outerNode) {
423    const size_t len = points.size();
424
425    std::vector<Node*> queue;
426    for (size_t i = 1; i < len; i++) {
427        Node* list = linkedList(points[i], false);
428        if (list) {
429            if (list == list->next) list->steiner = true;
430            queue.push_back(getLeftmost(list));
431        }
432    }
433    std::sort(queue.begin(), queue.end(), [](const Node* a, const Node* b) {
434        return a->x < b->x;
435    });
436
437    // process holes from left to right
438    for (size_t i = 0; i < queue.size(); i++) {
439        eliminateHole(queue[i], outerNode);
440        outerNode = filterPoints(outerNode, outerNode->next);
441    }
442
443    return outerNode;
444}
445
446// find a bridge between vertices that connects hole with an outer ring and and link it
447template <typename N>
448void Earcut<N>::eliminateHole(Node* hole, Node* outerNode) {
449    outerNode = findHoleBridge(hole, outerNode);
450    if (outerNode) {
451        Node* b = splitPolygon(outerNode, hole);
452        filterPoints(b, b->next);
453    }
454}
455
456// David Eberly's algorithm for finding a bridge between hole and outer polygon
457template <typename N>
458typename Earcut<N>::Node*
459Earcut<N>::findHoleBridge(Node* hole, Node* outerNode) {
460    Node* p = outerNode;
461    double hx = hole->x;
462    double hy = hole->y;
463    double qx = -std::numeric_limits<double>::infinity();
464    Node* m = nullptr;
465
466    // find a segment intersected by a ray from the hole's leftmost Vertex to the left;
467    // segment's endpoint with lesser x will be potential connection Vertex
468    do {
469        if (hy <= p->y && hy >= p->next->y && p->next->y != p->y) {
470          double x = p->x + (hy - p->y) * (p->next->x - p->x) / (p->next->y - p->y);
471          if (x <= hx && x > qx) {
472            qx = x;
473            if (x == hx) {
474                if (hy == p->y) return p;
475                if (hy == p->next->y) return p->next;
476            }
477            m = p->x < p->next->x ? p : p->next;
478          }
479        }
480        p = p->next;
481    } while (p != outerNode);
482
483    if (!m) return 0;
484
485    if (hx == qx) return m->prev;
486
487    // look for points inside the triangle of hole Vertex, segment intersection and endpoint;
488    // if there are no points found, we have a valid connection;
489    // otherwise choose the Vertex of the minimum angle with the ray as connection Vertex
490
491    const Node* stop = m;
492    double tanMin = std::numeric_limits<double>::infinity();
493    double tanCur = 0;
494
495    p = m->next;
496    double mx = m->x;
497    double my = m->y;
498
499    while (p != stop) {
500        if (hx >= p->x && p->x >= mx && hx != p->x &&
501            pointInTriangle(hy < my ? hx : qx, hy, mx, my, hy < my ? qx : hx, hy, p->x, p->y)) {
502
503            tanCur = std::abs(hy - p->y) / (hx - p->x); // tangential
504
505            if ((tanCur < tanMin || (tanCur == tanMin && p->x > m->x)) && locallyInside(p, hole)) {
506                m = p;
507                tanMin = tanCur;
508            }
509        }
510
511        p = p->next;
512    }
513
514    return m;
515}
516
517// interlink polygon nodes in z-order
518template <typename N>
519void Earcut<N>::indexCurve(Node* start) {
520    assert(start);
521    Node* p = start;
522
523    do {
524        p->z = p->z ? p->z : zOrder(p->x, p->y);
525        p->prevZ = p->prev;
526        p->nextZ = p->next;
527        p = p->next;
528    } while (p != start);
529
530    p->prevZ->nextZ = nullptr;
531    p->prevZ = nullptr;
532
533    sortLinked(p);
534}
535
536// Simon Tatham's linked list merge sort algorithm
537// http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
538template <typename N>
539typename Earcut<N>::Node*
540Earcut<N>::sortLinked(Node* list) {
541    assert(list);
542    Node* p;
543    Node* q;
544    Node* e;
545    Node* tail;
546    int i, numMerges, pSize, qSize;
547    int inSize = 1;
548
549    for (;;) {
550        p = list;
551        list = nullptr;
552        tail = nullptr;
553        numMerges = 0;
554
555        while (p) {
556            numMerges++;
557            q = p;
558            pSize = 0;
559            for (i = 0; i < inSize; i++) {
560                pSize++;
561                q = q->nextZ;
562                if (!q) break;
563            }
564
565            qSize = inSize;
566
567            while (pSize > 0 || (qSize > 0 && q)) {
568
569                if (pSize == 0) {
570                    e = q;
571                    q = q->nextZ;
572                    qSize--;
573                } else if (qSize == 0 || !q) {
574                    e = p;
575                    p = p->nextZ;
576                    pSize--;
577                } else if (p->z <= q->z) {
578                    e = p;
579                    p = p->nextZ;
580                    pSize--;
581                } else {
582                    e = q;
583                    q = q->nextZ;
584                    qSize--;
585                }
586
587                if (tail) tail->nextZ = e;
588                else list = e;
589
590                e->prevZ = tail;
591                tail = e;
592            }
593
594            p = q;
595        }
596
597        tail->nextZ = nullptr;
598
599        if (numMerges <= 1) return list;
600
601        inSize *= 2;
602    }
603}
604
605// z-order of a Vertex given coords and size of the data bounding box
606template <typename N>
607int32_t Earcut<N>::zOrder(const double x_, const double y_) {
608    // coords are transformed into non-negative 15-bit integer range
609    int32_t x = static_cast<int32_t>(32767.0 * (x_ - minX) * inv_size);
610    int32_t y = static_cast<int32_t>(32767.0 * (y_ - minY) * inv_size);
611
612    x = (x | (x << 8)) & 0x00FF00FF;
613    x = (x | (x << 4)) & 0x0F0F0F0F;
614    x = (x | (x << 2)) & 0x33333333;
615    x = (x | (x << 1)) & 0x55555555;
616
617    y = (y | (y << 8)) & 0x00FF00FF;
618    y = (y | (y << 4)) & 0x0F0F0F0F;
619    y = (y | (y << 2)) & 0x33333333;
620    y = (y | (y << 1)) & 0x55555555;
621
622    return x | (y << 1);
623}
624
625// find the leftmost node of a polygon ring
626template <typename N>
627typename Earcut<N>::Node*
628Earcut<N>::getLeftmost(Node* start) {
629    Node* p = start;
630    Node* leftmost = start;
631    do {
632        if (p->x < leftmost->x) leftmost = p;
633        p = p->next;
634    } while (p != start);
635
636    return leftmost;
637}
638
639// check if a point lies within a convex triangle
640template <typename N>
641bool Earcut<N>::pointInTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py) const {
642    return (cx - px) * (ay - py) - (ax - px) * (cy - py) >= 0 &&
643           (ax - px) * (by - py) - (bx - px) * (ay - py) >= 0 &&
644           (bx - px) * (cy - py) - (cx - px) * (by - py) >= 0;
645}
646
647// check if a diagonal between two polygon nodes is valid (lies in polygon interior)
648template <typename N>
649bool Earcut<N>::isValidDiagonal(Node* a, Node* b) {
650    return a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon(a, b) &&
651           locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b);
652}
653
654// signed area of a triangle
655template <typename N>
656double Earcut<N>::area(const Node* p, const Node* q, const Node* r) const {
657    return (q->y - p->y) * (r->x - q->x) - (q->x - p->x) * (r->y - q->y);
658}
659
660// check if two points are equal
661template <typename N>
662bool Earcut<N>::equals(const Node* p1, const Node* p2) {
663    return p1->x == p2->x && p1->y == p2->y;
664}
665
666// check if two segments intersect
667template <typename N>
668bool Earcut<N>::intersects(const Node* p1, const Node* q1, const Node* p2, const Node* q2) {
669    if ((equals(p1, q1) && equals(p2, q2)) ||
670        (equals(p1, q2) && equals(p2, q1))) return true;
671    return (area(p1, q1, p2) > 0) != (area(p1, q1, q2) > 0) &&
672           (area(p2, q2, p1) > 0) != (area(p2, q2, q1) > 0);
673}
674
675// check if a polygon diagonal intersects any polygon segments
676template <typename N>
677bool Earcut<N>::intersectsPolygon(const Node* a, const Node* b) {
678    const Node* p = a;
679    do {
680        if (p->i != a->i && p->next->i != a->i && p->i != b->i && p->next->i != b->i &&
681                intersects(p, p->next, a, b)) return true;
682        p = p->next;
683    } while (p != a);
684
685    return false;
686}
687
688// check if a polygon diagonal is locally inside the polygon
689template <typename N>
690bool Earcut<N>::locallyInside(const Node* a, const Node* b) {
691    return area(a->prev, a, a->next) < 0 ?
692        area(a, b, a->next) >= 0 && area(a, a->prev, b) >= 0 :
693        area(a, b, a->prev) < 0 || area(a, a->next, b) < 0;
694}
695
696// check if the middle Vertex of a polygon diagonal is inside the polygon
697template <typename N>
698bool Earcut<N>::middleInside(const Node* a, const Node* b) {
699    const Node* p = a;
700    bool inside = false;
701    double px = (a->x + b->x) / 2;
702    double py = (a->y + b->y) / 2;
703    do {
704        if (((p->y > py) != (p->next->y > py)) && p->next->y != p->y &&
705                (px < (p->next->x - p->x) * (py - p->y) / (p->next->y - p->y) + p->x))
706            inside = !inside;
707        p = p->next;
708    } while (p != a);
709
710    return inside;
711}
712
713// link two polygon vertices with a bridge; if the vertices belong to the same ring, it splits
714// polygon into two; if one belongs to the outer ring and another to a hole, it merges it into a
715// single ring
716template <typename N>
717typename Earcut<N>::Node*
718Earcut<N>::splitPolygon(Node* a, Node* b) {
719    Node* a2 = nodes.construct(a->i, a->x, a->y);
720    Node* b2 = nodes.construct(b->i, b->x, b->y);
721    Node* an = a->next;
722    Node* bp = b->prev;
723
724    a->next = b;
725    b->prev = a;
726
727    a2->next = an;
728    an->prev = a2;
729
730    b2->next = a2;
731    a2->prev = b2;
732
733    bp->next = b2;
734    b2->prev = bp;
735
736    return b2;
737}
738
739// create a node and util::optionally link it with previous one (in a circular doubly linked list)
740template <typename N> template <typename Point>
741typename Earcut<N>::Node*
742Earcut<N>::insertNode(std::size_t i, const Point& pt, Node* last) {
743    Node* p = nodes.construct(static_cast<N>(i), util::nth<0, Point>::get(pt), util::nth<1, Point>::get(pt));
744
745    if (!last) {
746        p->prev = p;
747        p->next = p;
748
749    } else {
750        assert(last);
751        p->next = last->next;
752        p->prev = last;
753        last->next->prev = p;
754        last->next = p;
755    }
756    return p;
757}
758
759template <typename N>
760void Earcut<N>::removeNode(Node* p) {
761    p->next->prev = p->prev;
762    p->prev->next = p->next;
763
764    if (p->prevZ) p->prevZ->nextZ = p->nextZ;
765    if (p->nextZ) p->nextZ->prevZ = p->prevZ;
766}
767}
768
769template <typename N = uint32_t, typename Polygon>
770std::vector<N> earcut(const Polygon& poly) {
771    mapbox::detail::Earcut<N> earcut;
772    earcut(poly);
773    return std::move(earcut.indices);
774}
775}
Note: See TracBrowser for help on using the repository browser.