YHK - yet another hacker news clone

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

53 points molind 2 hours ago 10 comments

swiftcoder 56 minutes ago | parent

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?

entrope 32 minutes ago | parent

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.

amelius 52 minutes ago | parent

Should mention the mother of all triangulators:

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

n4r9 33 minutes ago | parent

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.

mourner 34 minutes ago | parent

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.

molind 6 minutes ago | parent

Hey! Thanks for Leaflet, earcut and all your other work. I hope some of these ideas turn out useful. Take a look at the branch-free dent count: it's what let us outperform earcut, and it's a big part of why the wasm build is that fast. The wasm module is 27 KB gzipped, about 41 KB with the base64 wrapper in the npm package.

willtemperley 20 minutes ago | parent

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

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

foxhill 18 minutes ago | parent

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.

Gravityloss 16 minutes ago | parent

Not familiar with triangularization algorithms but is it causing issues when it picks long and narrow triangles? I assume a human doing it would in general try to go for more "balanced" ones?

dan00 3 minutes ago | parent

It depends on the use case.

Having more balanced triangles in this case would only increase the number of vertices. Which means you need more memory on the GPU and the vertex pipeline has more work to do.

Because the polygons are quite small, there's also no culling advantage by having smaller triangles, being able to discard them early in the rendering process.