Simple Polygon Triangulation

Every simple polygon with $n$ vertices admits a triangulation into exactly $n - 2$ triangles using only its vertices — the Two Ears Theorem of Meisters guarantees that any simple polygon with at least four vertices has at least two ears, where an ear is a vertex whose two neighbors can be joined by a diagonal that lies entirely inside the polygon.

Ear clipping exploits that fact directly: repeatedly find an ear, emit the triangle formed by the ear vertex and its two neighbors, and delete the ear from the vertex list. After $n - 2$ clips the polygon collapses to a single triangle. It is the simplest correct triangulation algorithm; $O(n \log n)$ and $O(n)$ alternatives (Chazelle's monotone-polygon sweep, Seidel's randomized algorithm) exist for performance-critical code.

Codes

Python

def solve(xs):
    polygon = xs[0]
    n = len(polygon)
    if n < 3:
        return []

    def cross(o, a, b):
        return ((a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]))

    area2 = 0
    for i in range(n):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i+1) % n]
        area2 += x1*y2 - x2*y1
    idx = list(range(n))
    if area2 < 0:
        idx.reverse()

    def in_triangle(p, a, b, c):
        d1 = cross(a, b, p)
        d2 = cross(b, c, p)
        d3 = cross(c, a, p)
        has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
        has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0)
        return not (has_neg and has_pos)

    def is_ear(i):
        m = len(idx)
        prev_i = idx[(i - 1) % m]
        curr_i = idx[i]
        next_i = idx[(i + 1) % m]
        a = polygon[prev_i]
        b = polygon[curr_i]
        c = polygon[next_i]
        if cross(a, b, c) <= 0:
            return False
        for j in range(m):
            k = idx[j]
            if k in (prev_i, curr_i, next_i):
                continue
            if in_triangle(polygon[k], a, b, c):
                return False
        return True

    triangles = []
    guard = 0
    while len(idx) > 3 and guard < n * n:
        guard += 1
        found = False
        for i in range(len(idx)):
            if is_ear(i):
                m = len(idx)
                prev_i = idx[(i - 1) % m]
                curr_i = idx[i]
                next_i = idx[(i + 1) % m]
                triangles.append(sorted([prev_i, curr_i, next_i]))
                idx.pop(i)
                found = True
                break
        if not found:
            break
    if len(idx) == 3:
        triangles.append(sorted(idx))
    triangles.sort()
    return triangles

C++

#include <algorithm>
#include <array>
#include <vector>

using Pt = std::array<double, 2>;

static double cross(Pt o, Pt a, Pt b) {
    return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]);
}

static bool in_triangle(Pt p, Pt a, Pt b, Pt c) {
    double d1 = cross(a, b, p), d2 = cross(b, c, p), d3 = cross(c, a, p);
    bool neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    bool pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
    return !(neg && pos);
}

std::vector<std::array<int,3>> ear_clip(std::vector<Pt> poly) {
    int n = poly.size();
    std::vector<std::array<int,3>> out;
    if (n < 3) return out;
    double area2 = 0;
    for (int i = 0; i < n; ++i) {
        auto& p = poly[i]; auto& q = poly[(i+1) % n];
        area2 += p[0]*q[1] - q[0]*p[1];
    }
    std::vector<int> idx(n);
    for (int i = 0; i < n; ++i) idx[i] = i;
    if (area2 < 0) std::reverse(idx.begin(), idx.end());

    auto is_ear = [&](int i) {
        int m = idx.size();
        int a = idx[(i - 1 + m) % m], b = idx[i], c = idx[(i + 1) % m];
        if (cross(poly[a], poly[b], poly[c]) <= 0) return false;
        for (int j = 0; j < m; ++j) {
            int k = idx[j];
            if (k == a || k == b || k == c) continue;
            if (in_triangle(poly[k], poly[a], poly[b], poly[c])) return false;
        }
        return true;
    };

    while ((int)idx.size() > 3) {
        bool clipped = false;
        for (int i = 0; i < (int)idx.size(); ++i) {
            if (is_ear(i)) {
                int m = idx.size();
                int a = idx[(i - 1 + m) % m], b = idx[i], c = idx[(i + 1) % m];
                std::array<int,3> t = {a, b, c};
                std::sort(t.begin(), t.end());
                out.push_back(t);
                idx.erase(idx.begin() + i);
                clipped = true;
                break;
            }
        }
        if (!clipped) break;
    }
    if (idx.size() == 3) {
        std::array<int,3> t = {idx[0], idx[1], idx[2]};
        std::sort(t.begin(), t.end());
        out.push_back(t);
    }
    std::sort(out.begin(), out.end());
    return out;
}

Example

Loading Python runner...

Description

Run time analysis

$O(n^3)$ for the naive ear-clipping loop. Each of the $n - 2$ clips scans every remaining vertex for ear status, and the ear test itself walks the remaining vertices. The running time drops to $O(n^2)$ if one caches the ear status of each vertex and only updates its two neighbors after a clip.

Space analysis

$O(n)$. We maintain a single vertex index list plus the output triangle list, both of length linear in the input.

Proof of correctness

Meisters' Two Ears Theorem states that every simple polygon with $n \ge 4$ vertices has at least two ears. Therefore, as long as the current polygon has at least four vertices, the inner loop finds at least one ear, clips it, and the remaining vertex sequence is again a simple polygon (the clip replaces two consecutive edges with one diagonal, and the diagonal lies inside the polygon by the definition of an ear, so no self-intersection is introduced). Induction on the number of vertices completes the proof: the three-vertex polygon is trivially a single triangle, and an ear clip reduces the problem from $n$ to $n - 1$ vertices while emitting exactly one triangle. The total number of emitted triangles is $n - 2$.

Extensions

Applications

References

• de Berg, Cheong, van Kreveld, Overmars. Computational Geometry: Algorithms and Applications, 3rd ed., Chapter 3 (Polygon Triangulation).
• Meisters, G. H. "Polygons have ears." The American Mathematical Monthly, 1975.
• Chazelle, B. "Triangulating a simple polygon in linear time." Discrete and Computational Geometry, 1991.
• cp-algorithms — Computational geometry