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

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?

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!

Should mention the mother of all triangulators:

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

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.

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.

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

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

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?

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.

Fantastic write-up, kudos to the author.

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?

[flagged]

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.

Axby - aybx + bxcy - bycx 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.