A new triangulator beats earcut on 3.7 million map polygons
Faster than earcut: triangulating 3.7M map polygons in 489 ms
Globus Software open-sourced earstrip, the ear-clipping triangulator from its map engine, under the ISC license as a single C++ header plus a WebAssembly build on npm with an earcut-compatible API. It runs 14% faster than earcut.hpp in C++ and 1.4 to 2.1 times faster than earcut.js in the browser. The post walks through each optimization, from skipping Delaunay in favor of ear clipping to testing only reflex vertices, cutting 3.7 million Masovian polygons in 489 ms.
Of all the ways to triangulate the same points, it has the largest smallest angle.
- morishuz
awesome. the performance improvements looks impressive!
i’m the author of Delaunay32, a constrained delaunay triangulator with polygon and hole support. it uses divide-and-conquer rather than incremental insertion, so im curious how it would compare with the delaunay baseline here.
https://github.com/morishuz/delaunay32
i havent benchmarked on your corpus yet, and our current polygon api requires simple rings with non-touching holes. thanks for publishing the datasets, they look useful for testing and comparison!
- amelius
Should mention the mother of all triangulators:
- mistercow
I've wondered for a long time why ear clipping + optimizations has won on triangulation over stuff like Seidel's trapezoidal method, which has O(nlog*n) time complexity and handles holes naturally. I know big-O isn't everything, but that's essentially linear versus quadratic, and it seems like we care about triangulating more and more complex polygons as time goes on.
Is it just a triangle quality thing? Does Seidel lead to too many hard to deal with slivers?
- mourner
Hey Evgen, Earcut author here — thanks for the writeup and a really cool library! I need to see if there are any tricks to borrow for Earcut's JS version. :)
One thing to note is that I deliberately had to reject some of the potential optimizations to keep the library small, so that bundle size doesn't blow up — for most practical applications (e.g. Mapbox GL JS), it's already fast enough (and 4.1k min/gz). Curious how big the WASM build of Earstrip is.
On the C++ side, Mapbox now uses a hybrid approach where small polygons are processed with earcut.hpp, while big and complex polygon switch to a different algorithm based on monotone decomposition, because while it has higher constants in algorithmic complexity, it scales much better with input size.
- stymaar
I see that the result contains lots of very long, very thin triangles. Aren't those generally the worse case scenario for the GPU rasterizer?