Globus releases earstrip, an open-source earcut rival that triangulates 3.7M map polygons in 489 ms

The team behind the Globus map engine has released its polygon triangulation code as earstrip, an open-source library published under the ISC licence, the same one earcut uses. It ships as a single C++ header plus a WebAssembly build on npm that takes the same arguments as earcut, which makes it close to a drop-in replacement. According to the engineering post on globus.software, which reached the front page of Hacker News, earstrip is roughly 14% faster than earcut.hpp in C++, and between 1.4 and 2.1 times faster than earcut.js in the browser.

The benchmark

The headline numbers come from a real workload rather than a synthetic suite: zoom level 13 of Globus's offline map of the Masovian Voivodeship, the region around Warsaw, which contains 3,740,425 polygons. On a single core of an M4 Pro, the constrained Delaunay triangulator in the engine needed 2.93 seconds to cut all of them. The author rebuilt the replacement ear clipper one idea at a time, timing every commit against the same dataset, and the final version finishes the job in 489 ms, roughly six times faster overall.

A large part of the win comes from the shape of map data itself. Nearly half of the polygons, 1.8 million of them, have four vertices or fewer: a triangle needs no cutting at all, and a convex quad is just two triangles. The Delaunay code nevertheless spent 419 ms on these trivial cases because it constructed each triangulation from scratch.

How ear clipping works

An ear is a corner of a polygon that can be sliced off with one straight cut: three consecutive vertices where the middle corner is convex and no other part of the boundary reaches into the triangle they form. A theorem proved by Gary Meisters in 1975 guarantees that every simple polygon with more than three vertices has at least two non-overlapping ears, so there is always another one to cut until n vertices have become n - 2 triangles.

The first complete implementation, which tests each corner and then every other boundary vertex, already ran at 1.12 seconds, 2.6 times faster than Delaunay. Each subsequent commit shaved off more time:

• only dents: 882 ms
• convex shortcut: 880 ms
• zig-zag strips: 762 ms
• buckets: 697 ms
• no branches: 519 ms
• marked hits: 489 ms

Holes and map-specific quirks

Ear clipping operates on one closed boundary, but 11,345 of the Masovian polygons have holes, such as courtyards inside buildings and clearings inside forests. The remedy, which the post credits to David Eberly's write-up of the algorithm, is to bridge each hole to the outer ring: take the rightmost vertex of the hole, cast a ray to the right, connect to a vertex of the first edge the ray hits, and verify that no boundary point lies inside the candidate bridge triangle.

Map data adds two cases the author had to handle specially. Coordinates are integers on a tile grid, so a ray cast along a grid line degenerates, and the first version of the crossing test got exactly this case wrong. Mappers also often draw a courtyard that touches the outer ring at a single point; such a hole needs no bridge at all because the two rings are already joined.

Where Delaunay still wins

Ear clipping is not uniformly faster. The 1,123 largest polygons, those with 257 vertices or more, take 199 ms to clip but only 90 ms with Delaunay, because each ear test walks hundreds of vertices and a polygon needs hundreds of tests, so the cost grows with the square of its size. Delaunay also produces better-shaped triangles, maximising the smallest angle, which matters if you interpolate across the mesh or run a simulation on it. For flat GPU fills, the post notes, a needle-thin triangle is filled just as correctly as a fat one.

Why it matters

Anyone rendering filled polygons, from map engines to vector graphics and geometry tooling, needs triangulation, and earcut is the default choice in that niche. earstrip offers the same API and licence with better benchmark numbers on both native and web platforms, so the cost of trying it is close to zero. The post also works as a case study in optimisation: picking the right algorithm delivered most of the sixfold gain, and disciplined, commit-by-commit tuning nearly halved what remained. Workloads dominated by very large polygons should still benchmark both approaches, since Delaunay keeps the upper hand there.