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?
willtemperley 14 minutes ago [-]
I'd be interested if it benchmarked well against iShape-rust, the overlay engine in GeoRust:
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.
foxhill 12 minutes 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.
mourner 28 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.
swiftcoder 51 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?
entrope 27 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.
deakmisra 59 minutes ago [-]
[flagged]
Rendered at 11:27:57 GMT+0000 (Coordinated Universal Time) with Vercel.
https://github.com/ishape-rust/ioverlay
https://www.cs.cmu.edu/~quake/triangle.html
either way, neat stuff, and the write up itself is excellent.
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.
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.