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

Posted by molind 1 hour ago

Counter48Comment7OpenOriginal

Comments

Comment by foxhill 44 seconds ago

the resulting topology is somewhat.. violent, no? that said, i wonder how much of an impact it actually has on rendering.

either way, neat stuff, and the write up itself is excellent.

Comment by willtemperley 3 minutes ago

I'd be interested if it benchmarked well against iShape-rust, the overlay engine in GeoRust:

https://github.com/ishape-rust/ioverlay

Comment by amelius 35 minutes ago

Should mention the mother of all triangulators:

https://www.cs.cmu.edu/~quake/triangle.html

Comment by n4r9 16 minutes ago

Have used (a dotnet wrapper of) this to generate colour-coded round area polygons for municipal waste collections for many years now. works flawlessly and fast.

Comment by mourner 16 minutes ago

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.

Comment by swiftcoder 39 minutes ago

Interesting optimisation, curious if you are willing to divulge which of the optimisation steps the LLM came up with, versus which it needed human assistance with?

Comment by entrope 15 minutes ago

I'm not sure, but "This post is about how we got there.\nA GPU fills triangles and nothing else." is very Claude-ish. So does "[I created] one commit per idea, and timed every commit on those same 3.7 million polygons, so each section below ends with a number." And "A triangle needs no cutting at all".

My experience is that Claude Opus 5 and 5.5 are very good at implementing optimizations, reasonably good at suggesting approaches to try, and not very inclined to identify slow runtime as a problem. It tends to go for simple implementations until I ask about speed, which is certainly conventional wisdom for development.

Comment by deakmisra 47 minutes ago

[flagged]