We have released earstrip, the polygon triangulator from our map engine, as a small open-source library under the ISC license, the same license used by earcut. It consists of a single C++ header and a WebAssembly build published on npm that accepts the same arguments as earcut. In C++ it runs 14% faster than earcut.hpp, and in the browser it runs 1.4 to 2.1 times as fast as earcut.js.
A GPU can fill only triangles, while a map is mostly made of polygons: buildings, parks, parking lots, and the strips of grass between tram tracks. Before any polygon can be filled, its outline must be cut into triangles. Our offline map of the Masovian Voivodeship, the region around Warsaw, has 3,740,425 polygons at zoom level 13. On one core of an M4 Pro, the constrained Delaunay triangulator in our engine needed 2.93 seconds to process them all.
This October we replaced it with ear clipping. Delaunay triangulation avoids skinny triangles and is useful for interpolation and simulation, but a flat fill does not need that quality, and most of the work went into simple shapes. Almost half of the Masovian polygons, 1.8 million, have four vertices or fewer, yet the Delaunay code spent 419 ms building triangulations for them from scratch. Ear clipping removes one corner at a time, and every simple polygon with more than three vertices has at least two non-overlapping ears, so it always has another cut to make.
To document the work, we rebuilt the ear clipper one idea per commit and timed each step on the same 3.7 million polygons. The final version processes the full dataset in 489 ms, which is the figure in the headline.
Source: Hacker News · Summarized by HeadlinesBriefing