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

A new small library, earstrip, repackages a highly optimized ear-clipping triangulator for map polygons as a single C++ header and a WebAssembly npm build that accepts earcut-compatible arguments. Replacing a constrained Delaunay triangulator used in a map engine, the ear-clipping approach was rebuilt incrementally with timed benchmarks on 3.74 million zoom‑13 polygons from an offline Masovian map. Through targeted optimizations - bounding-box buckets, bitmasking dents, testing only marked candidate vertices, and short-list handling - the final C++ run cuts those polygons in 489 ms on one M4 Pro core (about 6× faster than the original Delaunay 2.93 s). Native earstrip is 14% faster than earcut.hpp; in browsers the WebAssembly builds and an npm package yield 1.4-2.1× speedups over earcut.js depending on call patterns, with the best gains when polygons are bulk-passed into module memory.

The implementation keeps correctness and robustness in mind: it falls back to constrained Delaunay for degenerate or self-touching polygons, when ear clipping produces wrong area, or for polygons with ≥128 rings, and emits status flags indicating which method ran. That hybrid strategy fixes rounding-induced degenerate cases and preserves accurate fills - on zoom 13 earstrip’s triangles deviate from an even‑odd fill by only 0.15% of pixels versus 31% for earcut in some tests. Benchmarks and test polygons are provided with the library so results are reproducible.