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

swiftcoder

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?

amelius

Should mention the mother of all triangulators: https://www.cs.cmu.edu/~quake/triangle.html

mourner

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.

willtemperley

I'd be interested if it benchmarked well against iShape-rust, the overlay engine in GeoRust: https://github.com/ishape-rust/ioverlay

foxhill

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

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?

airbreather

Why the obsession with triangles? If you just want areas, or to know if a point is inside or outside the shape there is a better way. Given a simple closed curve, points (ax, ay) (bx, by) (cx, cy) (dx, dy) as a trivial example. Line them up a,b,c,d,a vertically and take the "determinant" as we were taught. Ax by - ay bx + bx cy - by cx etc etc. Divide the result by -2 and you have the are, positive is clockwise, negative is anticlockwise. Put an anticlockwise shape inside a clockwise shape and you have a donut. There is more, have to go to dinner.

morishuz

awesome. the performance improvements looks impressive! i’m the author of Delaunay32, a constrained delaunay triangulator with polygon and hole support. it uses divide-and-conquer rather than incremental insertion, so im curious how it would compare with the delaunay baseline here. https://github.com/morishuz/delaunay32 i havent benchmarked on your corpus yet, and our current polygon api requires simple rings with non-touching holes. thanks for publishing the datasets, they look useful for testing and comparison!

abcd_f

Fantastic write-up, kudos to the author.

mistercow

I've wondered for a long time why ear clipping + optimizations has won on triangulation over stuff like Seidel's trapezoidal method, which has O(nlog*n) time complexity and handles holes naturally. I know big-O isn't everything, but that's essentially linear versus quadratic, and it seems like we care about triangulating more and more complex polygons as time goes on. Is it just a triangle quality thing? Does Seidel lead to too many hard to deal with slivers?

jplusequalt

I hand wrote an earcut implementation a few years back. It was a pain in the ass to cover all the edge cases, but cool to see it working at the end.

stymaar

I see that the result contains lots of very long, very thin triangles. Aren't those generally the worse case scenario for the GPU rasterizer?

cadamsdotcom

> A GPU fills triangles and nothing else. Huh.

anon291

Nice performance. Just looking at the triangles, some of them seem a bit tiny. Does that cause rendering problems at all?