Faster than earcut: triangulating 3.7M map polygons in 489 ms

Globus Software has released earstrip, a lightweight polygon triangulation library. Distributed under the ISC license (matching the license of earcut), it is available as a single C++ header and a WebAssembly build via npm, maintaining API compatibility with earcut.

Performance Benchmarks

The performance gains are significant depending on the environment:

• C++: $\approx 14\%$ faster than earcut.hpp.
• Browser: $1.4\times$ to $2.1\times$ faster than earcut.js.

---

The Challenge: Mapping the World

Digital maps are essentially collections of polygons—think of buildings, parks, or the narrow strips of grass separating tram lines.

For example, a few city blocks in Śródmieście, Warsaw, consist of:

• 331 polygons
• 5,151 vertices
• 4,514 resulting triangles

Before a GPU can render a fill, these outlines must be decomposed into triangles. To test the limits, the author used a zoom level 13 offline map of the Masovian Voivodeship, which contains a staggering 3,740,425 polygons.

On a single core of an M4 Pro, a constrained Delaunay triangulator takes $2.93$ seconds to process this dataset. To optimize this, the author rebuilt the ear clipper incrementally.

Optimization Roadmap

• Implement basic ear clipping
• Optimize vertex traversal
• Refine hole bridging
• Final performance tuning

---

Understanding Delaunay Triangulation

A triangulation is considered Delaunay if no point in the set falls inside the circumcircle (the circle passing through the three vertices) of any triangle in the network.

If two adjacent triangles violate this rule, the shared edge is "flipped" to repair the local area. This process continues until no more flips are possible.

Key Characteristics

1. Angle Optimization: It maximizes the minimum angle of all triangles, avoiding "skinny" triangles.
2. Constrained Delaunay: In map rendering, the polygon's original boundaries must remain edges, even if the circle rule suggests a flip. Delaunay is always the best choice $\rightarrow$ Delaunay is only best when triangle quality is critical.

Comparison: Delaunay vs. Simple Fills

For a GPU, a thin triangle is just as easy to fill as a fat one. Since nearly half of the Masovian polygons (1.8 million) have $\le 4$ vertices, the overhead of Delaunay is unnecessary.

---

The Ear Clipping Method

An "ear" is a convex corner of a polygon that can be removed by a single straight cut without intersecting any other part of the polygon.

According to Gary Meisters (1975), any simple polygon with $n > 3$ vertices possesses at least two non-overlapping ears. By repeatedly removing these ears, a polygon with $n$ vertices is reduced to $n - 2$ triangles.

The Logic

To determine if a vertex $b$ is an ear, we check:

1. Convexity: The corner must turn "inward."
2. Emptiness: No other boundary vertices can reside within the triangle $abc$.

The convexity is determined using a $2 \times 2$ determinant, often called the cross product:

$\text{cross}(a, b, c) = (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x)$

static double cross ( double ax, double ay, double bx, double by, double cx, double cy ) {
    return ( bx - ax ) * ( cy - ay ) - ( by - ay ) * ( cx - ax );
}

bool isEar ( uint32_t v ) const {
    const Node b = _nodes [ v ];
    const Node a = _nodes [ b.next ];
    const Node c = _nodes [ b.prev ];

    if ( cross ( a, b, c ) <= 0 ) return false; // Not convex

    for ( uint32_t w = c.next; w != a; w = _nodes [ w ].next ) {
        if ( pointInTriangle( _nodes[w], a, b, c ) ) return false;
    }
    return true;
}

---

Handling Holes

Ear clipping typically requires a single continuous boundary. However, many map polygons (like a forest with a clearing) have holes. To solve this, we use bridges.

A bridge is an edge that connects a hole to the outer boundary, traversed twice (once in each direction). This transforms a polygon with holes into one single, complex ring.

The Bridging Algorithm (Eberly's Method)

By following this logic, the bridge is guaranteed not to cross any other boundaries, allowing the ear-clipping process to proceed on the newly unified ring.