Mercurial > ldforge2 / changeset

--- a/CMakeLists.txt	Tue Jun 14 23:04:49 2022 +0300
+++ b/CMakeLists.txt	Wed Jun 15 12:17:29 2022 +0300
@@ -75,6 +75,7 @@
 	src/uiutilities.h
 	src/version.h
 	src/vertexmap.h
+	src/algorithm/earcut.h
 	src/gl/axesprogram.h
 	src/gl/basicshaderprogram.h
 	src/gl/common.h

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/algorithm/earcut.h	Wed Jun 15 12:17:29 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 = &currentBlock[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/document.cpp	Tue Jun 14 23:04:49 2022 +0300
+++ b/src/document.cpp	Wed Jun 15 12:17:29 2022 +0300
@@ -18,11 +18,26 @@
 
 #include <QMouseEvent>
 #include <QPainter>
+#include "algorithm/earcut.h"
 #include "document.h"
 #include "model.h"
 #include "ui/objecteditor.h"
 #include "gl/partrenderer.h"
 
+// Make mapbox::earcut work with glm::vec3
+namespace mapbox {
+namespace util {
+template<> struct nth<0, glm::vec3>
+{
+	static constexpr float get(const glm::vec3& t) { return t.x; };
+};
+template<> struct nth<1, glm::vec3>
+{
+	static constexpr float get(const glm::vec3& t) { return t.y; };
+};
+}
+}
+
 EditTools::EditTools(QObject* parent) :
 	QObject{parent},
 	RenderLayer{}
@@ -72,6 +87,10 @@
 		this->worldPosition = this->gridMatrix * glm::vec4{*this->worldPosition, 1};
 		this->polygon.back() = *this->worldPosition;
 	}
+	this->numpoints = this->polygon.size();
+	if (this->isCloseToExistingPoints()) {
+		this->numpoints -= 1;
+	}
 }
 
 static QVector<QPointF> convertWorldPointsToScreenPoints(
@@ -152,7 +171,6 @@
 		.pointBrush = {Qt::white},
 		.pointPen = {QBrush{Qt::black}, 2.0},
 		.polygonPen = {QBrush{Qt::black}, 2.0, Qt::DashLine},
-		.badPolygonPen = {QBrush{Qt::red}, 2.0, Qt::DashLine},
 		.greenPolygonBrush = {QColor{64, 255, 128, 192}},
 		.redPolygonBrush = {QColor{255, 96, 96, 192}},
 	};
@@ -160,7 +178,6 @@
 		.pointBrush = {Qt::black},
 		.pointPen = {QBrush{Qt::white}, 2.0},
 		.polygonPen = {QBrush{Qt::white}, 2.0, Qt::DashLine},
-		.badPolygonPen = {QBrush{Qt::red}, 2.0, Qt::DashLine},
 		.greenPolygonBrush = {QColor{64, 255, 128, 192}},
 		.redPolygonBrush = {QColor{255, 96, 96, 192}},
 	};
@@ -169,7 +186,7 @@
 	case SelectMode:
 		break;
 	case DrawMode:
-		painter->setPen(this->isconcave ? pens.badPolygonPen : pens.polygonPen);
+		painter->setPen(pens.polygonPen);
 		for (const ModelAction& action : this->actions()) {
 			const opt<std::vector<glm::vec3>> points = modelActionPoints(action);
 			if (points.has_value()) {
@@ -201,13 +218,6 @@
 	}
 }
 
-void EditTools::updatePreviewPolygon()
-{
-	if (this->polygon.size() > 2) {
-		this->isconcave = not isConvex(this->polygon);
-	}
-}
-
 void EditTools::removeLastPoint()
 {
 	if (this->polygon.size() > 1) {
@@ -215,12 +225,17 @@
 	}
 }
 
-template<typename T>
-bool isCloseToExistingPoints(T begin, T end, const glm::vec3 &pos)
+bool EditTools::isCloseToExistingPoints() const
 {
-	return std::any_of(begin, end, [&pos](const glm::vec3& p){
-		return isclose(pos, p);
-	});
+	if (this->worldPosition.has_value()) {
+		const glm::vec3& pos = *this->worldPosition;
+		return std::any_of(this->polygon.begin(), this->polygon.end() - 1, [&pos](const glm::vec3& p){
+			return isclose(pos, p);
+		});
+	}
+	else {
+		return false;
+	}
 }
 
 EditingMode EditTools::currentEditingMode() const
@@ -239,12 +254,11 @@
 		break;
 	case DrawMode:
 		if (event->button() == Qt::LeftButton and this->worldPosition.has_value()) {
-			if (isCloseToExistingPoints(this->polygon.begin(), this->polygon.end() - 1, *this->worldPosition)) {
+			if (isCloseToExistingPoints()) {
 				this->closeShape();
 			}
 			else {
 				this->polygon.push_back(*this->worldPosition);
-				this->updatePreviewPolygon();
 			}
 		}
 		else if (true
@@ -252,53 +266,142 @@
 			and this->polygon.size() > 1
 		) {
 			this->removeLastPoint();
-			updatePreviewPolygon();
 		}
 		break;
 	}
 }
 
+constexpr float distancesquared(const glm::vec3& p1, const glm::vec3& p2)
+{
+	const float dx = p2.x - p1.x;
+	const float dy = p2.y - p1.y;
+	const float dz = p2.z - p1.z;
+	return (dx * dx) + (dy * dy) + (dz * dz);
+}
+
+inline float area(const Quadrilateral& q)
+{
+	return 0.5 * (
+		glm::length(glm::cross(q.p2 - q.p1, q.p3 - q.p1)) +
+		glm::length(glm::cross(q.p3 - q.p2, q.p4 - q.p2))
+	);
+}
+
+inline float energy(const Quadrilateral& q)
+{
+	const float L2 = distancesquared(q.p1, q.p2)
+		+ distancesquared(q.p2, q.p3)
+		+ distancesquared(q.p3, q.p4)
+		+ distancesquared(q.p4, q.p1);
+	return 1 - 6.928203230275509 * area(q) / L2;
+}
+
+struct MergedTriangles
+{
+	std::vector<Quadrilateral> quadrilaterals;
+	std::set<std::size_t> cutTriangles;
+};
+
+static MergedTriangles mergeTriangles(
+	const std::vector<std::uint16_t>& indices,
+	const std::vector<glm::vec3>& polygon)
+{
+	MergedTriangles result;
+	using indextype = std::uint16_t;
+	using indexpair = std::pair<indextype, indextype>;
+	struct boundaryinfo { indextype third; std::size_t triangleid; };
+	std::map<indexpair, boundaryinfo> boundaries;
+	for (std::size_t i = 0; i < indices.size(); i += 3) {
+		const auto add = [&](int o1, int o2, int o3){
+			const auto key = std::make_pair(indices[i + o1], indices[i + o2]);
+			boundaries[key] = {indices[i + o3], i};
+		};
+		add(0, 1, 2);
+		add(1, 2, 0);
+		add(2, 0, 1);
+	}
+	std::vector<std::array<indextype, 4>> quadindices;
+	std::vector<Quadrilateral> quads;
+	bool repeat = true;
+	const auto iscut = [&result](const std::size_t i){
+		return result.cutTriangles.find(i) != result.cutTriangles.end();
+	};
+	while (repeat) {
+		repeat = false;
+		// TODO: make this a function that returns quadrilateral indices
+		// Go through triangle boundaries
+		for (const auto& it1 : boundaries) {
+			const indexpair& pair1 = it1.first;
+			const boundaryinfo& boundary1 = it1.second;
+			// .. the ones we haven't already merged anyway
+			if (not iscut(boundary1.triangleid)) {
+				// Look for its inverse boundary to find the touching triangle
+				const auto pair2 = std::make_pair(pair1.second, pair1.first);
+				const auto it2 = boundaries.find(pair2);
+				// Also if that hasn't been cut
+				if (it2 != boundaries.end() and not iscut(it2->second.triangleid)) {
+					const Quadrilateral quad{
+						polygon[pair1.first],
+						polygon[it2->second.third],
+						polygon[pair1.second],
+						polygon[boundary1.third],
+					};
+					if (isConvex(quad)) {
+						result.quadrilaterals.push_back(quad);
+						result.cutTriangles.insert(boundary1.triangleid);
+						result.cutTriangles.insert(it2->second.triangleid);
+						repeat = true;
+					}
+				}
+			}
+		}
+	}
+	return result;
+}
+
 const std::vector<ModelAction> EditTools::actions() const
 {
 	std::vector<ModelAction> result;
-	if (this->polygon.size() >= 2 and this->polygon.size() <= 4) {
-		switch (this->polygon.size()) {
-		case 2:
-			result.push_back(AppendToModel{
-				.newElement = Colored<LineSegment>{
-					LineSegment{
-						.p1 = this->polygon[0],
-						.p2 = this->polygon[1],
-					},
-					EDGE_COLOR,
-				}
-			});
-			break;
-		case 3:
+	if (this->numpoints == 2) {
+		result.push_back(AppendToModel{
+			.newElement = Colored<LineSegment>{
+				LineSegment{
+					.p1 = this->polygon[0],
+					.p2 = this->polygon[1],
+				},
+				EDGE_COLOR,
+			}
+		});
+	}
+	else if (this->numpoints > 2) {
+		const glm::mat4 inverseGrid = glm::inverse(this->gridMatrix);
+		std::vector<std::vector<glm::vec3>> polygons{1};
+		std::vector<glm::vec3>& polygon2d = polygons.back();
+		polygon2d.reserve(this->numpoints);
+		for (std::size_t i = 0; i < this->numpoints; ++i) {
+			polygon2d.push_back(inverseGrid * glm::vec4{this->polygon[i], 1});
+		}		
+		using indextype = std::uint16_t;
+		const std::vector<indextype> indices = mapbox::earcut<std::uint16_t>(polygons);
+		MergedTriangles mergedTriangles = mergeTriangles(indices, this->polygon);
+		for (const Quadrilateral& quad : mergedTriangles.quadrilaterals) {
 			result.push_back(AppendToModel{
-				.newElement = Colored<Triangle>{
-					Triangle{
-						.p1 = this->polygon[0],
-						.p2 = this->polygon[1],
-						.p3 = this->polygon[2],
-					},
-					MAIN_COLOR,
-				}
+				.newElement = Colored<Quadrilateral>{quad, MAIN_COLOR},
 			});
-			break;
-		case 4:
-			result.push_back(AppendToModel{
-				.newElement = Colored<Quadrilateral>{
-					Quadrilateral{
-						.p1 = this->polygon[0],
-						.p2 = this->polygon[1],
-						.p3 = this->polygon[2],
-						.p4 = this->polygon[3],
-					},
-					MAIN_COLOR,
-				}
-			});
-			break;
+		}
+		for (std::size_t i = 0; i < indices.size(); i += 3) {
+			if (mergedTriangles.cutTriangles.find(i) == mergedTriangles.cutTriangles.end()) {
+				result.push_back(AppendToModel{
+					.newElement = Colored<Triangle>{
+						Triangle{
+							.p1 = this->polygon[indices[i]],
+							.p2 = this->polygon[indices[i + 1]],
+							.p3 = this->polygon[indices[i + 2]],
+						},
+						MAIN_COLOR,
+					}
+				});
+			}
 		}
 	}
 	return result;
@@ -310,5 +413,4 @@
 		Q_EMIT this->modelAction(action);
 	}
 	this->polygon.clear();
-	this->updatePreviewPolygon();
 }

--- a/src/document.h	Tue Jun 14 23:04:49 2022 +0300
+++ b/src/document.h	Wed Jun 15 12:17:29 2022 +0300
@@ -50,7 +50,7 @@
 {
 	Q_OBJECT
 	std::vector<glm::vec3> polygon = {{0, 0, 0}};
-	bool isconcave = false;
+	std::size_t numpoints = 1;
 	EditingMode mode = SelectMode;
 	glm::mat4 mvpMatrix;
 	glm::mat4 gridMatrix{1};
@@ -76,6 +76,6 @@
 private:
 	const std::vector<ModelAction> actions() const;
 	void closeShape();
-	void updatePreviewPolygon();
 	void removeLastPoint();
+	bool isCloseToExistingPoints() const;
 };

--- a/src/geometry.cpp	Tue Jun 14 23:04:49 2022 +0300
+++ b/src/geometry.cpp	Wed Jun 15 12:17:29 2022 +0300
@@ -199,6 +199,22 @@
 	};
 }
 
+bool isConvex(const Quadrilateral& quad)
+{
+	glm::vec3 crosses[4] = {
+		glm::cross(quad.p4 - quad.p1, quad.p2 - quad.p1),
+		glm::cross(quad.p1 - quad.p2, quad.p3 - quad.p2),
+		glm::cross(quad.p2 - quad.p3, quad.p4 - quad.p3),
+		glm::cross(quad.p3 - quad.p4, quad.p1 - quad.p4),
+	};
+	return not std::any_of(
+		&crosses[1],
+		&crosses[4],
+		[&crosses](const glm::vec3& vector) {
+			return glm::dot(crosses[0], vector) < 1e-6;
+		});
+}
+
 bool isConvex(const std::vector<glm::vec3>& polygon)
 {
 	const int n = polygon.size();

--- a/src/geometry.h	Tue Jun 14 23:04:49 2022 +0300
+++ b/src/geometry.h	Wed Jun 15 12:17:29 2022 +0300
@@ -138,6 +138,7 @@
 LineSegment2D bottom(const QRectF& rectangle);
 LineSegment2D left(const QRectF& rectangle);
 LineSegment2D right(const QRectF& rectangle);
+bool isConvex(const Quadrilateral& quad);
 bool isConvex(const std::vector<glm::vec3>& polygon);
 Winding winding(const QPolygonF& polygon);
 struct ScalingExtract