Evgen Bodunov rebuilt GLOBUS’s polygon triangulator one idea at a time, timing each commit against 3.74 million map polygons. Flat map fills need triangles, but their shape barely matters. Dropping the old algorithm’s triangle-quality work brought the first large gain.
The sequence makes a good performance-engineering notebook:
- Choose an algorithm for the actual output. Ear clipping, which repeatedly cuts a triangle off a polygon’s boundary, reduced runtime from 2,931 to 1,119 milliseconds.
- Test fewer points. Only inward-facing corners can block a cut. Keeping a shrinking list of those corners brought the total to 882 milliseconds.
- Write less output. Triangle strips reuse earlier indices, reducing the index count from 64.5 million to 35.8 million. Runtime fell to 762 milliseconds.
- Match the inner loop to the common case. Spatial buckets narrowed searches. A branch-free pass handled the frequent case where no point blocks a cut, with exact checks reserved for marked hits. The final total was 489 milliseconds.
- Keep an escape route. Rounded coordinates can break polygon boundaries, and thousands of holes make bridge searches expensive. The engine retains the older triangulator for those cases.
The per-size timings matter as much as the headline. Tracking inward-facing corners initially made tiny polygons slower; the convex shortcut barely changed total runtime. Those results explain where extra bookkeeping earns its cost.
The browser comparison also measures the whole interface: copying coordinates, converting strips back into separate triangles, and crossing into WebAssembly once per polygon. Caveat: these are the author’s single-threaded benchmarks on an M4 Pro; native and browser results use different calling paths. The essay supplies the data and benchmark code for checking your own workload.