Ear clipping beat Delaunay six times over on 3.7 million map polygons
A map renderer's Delaunay triangulator needed 2.93 seconds for one zoom level of the Masovian Voivodeship; the replacement finishes in 489 ms.
The author wrote earstrip, a C++ header with a WebAssembly build, adding a convex shortcut, strip output and branch-free counting to ear clipping. Native, it is about 14% faster than earcut.hpp.
Self-touching polygons fall back to Delaunay, as do those with 128 or more holes.
From 2.93 s to 489 ms
The write-up targets 3,740,425 polygons at zoom 13, where the existing constrained Delaunay triangulator took 2.93 seconds. A naive ear clipper took 1,119 ms; testing only reflex vertices brought it to 882 ms, and the final version reached 489 ms, with the package released as earstrip under ISC. In browsers it is 1.4 to 2.1 times faster than earcut.js. On world tiles with up to 11,675 holes, 459 ms against 2,892 ms for earcut.hpp.
Triangle quality is the tradeoff: Delaunay triangles suit interpolation, but flat fills do not need them.
The earcut author weighs in
"I deliberately had to reject some of the potential optimizations to keep the library small, so that bundle size doesn't blow up" — Earcut's author, an engineer at Mapbox and creator of Leaflet
Another commenter asked why ear clipping beats Seidel's trapezoidal method, which has near-linear complexity and handles holes naturally.
"I know big-O isn't everything, but that's essentially linear versus quadratic" — a commenter asking about Seidel's method
About 1.8 million of the test polygons have four or fewer vertices, so the convex shortcut applies to roughly half the input.
Get breakdowns like this every day
The top Hacker News stories, unpacked — by email, Telegram, or RSS.
This is the last story in the October 23, 2026 issue.
Go to the issue archive