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.
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.
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.
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.
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!
Numbers without benchmarks are useless. :)
During vector map generation we make sure that all data is valid. But our users can import custom GeoJSON layers and they could contain all sorts of self-intersections.
== world.bin
56472 polygons
whole file, best of 7: earstrip 453.4 ms, delaunay32 1696.9 ms
up to 4 14455 polygons: earstrip 0.3 ms, delaunay32 14.4 ms
5-8 8328 polygons: earstrip 0.6 ms, delaunay32 14.5 ms
9-32 18019 polygons: earstrip 6.8 ms, delaunay32 83.7 ms
33-256 13511 polygons: earstrip 66.6 ms, delaunay32 366.9 ms
257 and more 2159 polygons: earstrip 376.8 ms, delaunay32 1209.4 ms
delaunay32: rejected 3039 (by class 0/28/365/1671/975), empty outer ring 0, area off on 0 covered, 1930016 triangles
earstrip: exact 56338, constrained 134
Having triangulation conform to Delaunay is a big advantage though! You should also try out https://github.com/mapbox/earcut.hpp for the benchmark — it got a refine function recently that refines earcut output to Delaunay as well, and earcut+refine is still pretty fast.
thanks, good suggestion! earcut plus refine sounds like sensible comparison.
i’ve since reproduced the world dataset benchmark locally and found that polygon validation was taking about two-thirds of delaunay32’s time on the accepted inputs.
For practical data, a faster approach is usually to triangulate without validation, then just measure if triangulation is valid afterwards (which is simply comparing the sum of triangle areas with polygon area)
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?
>> 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(nlogn) time complexity
In solvespace we use a simple ear clipping algorithm but I'd love to have something O(nlog(n)).
I have yet to see one that's both small and comprehensible ;-) If I were to attempt it, I'd just add a spatial index to make the check for anything inside a triangle O(log(n)) and make sure we check for new ears adjacent to clipped ears. With that it should be n*log(n), but my old spatial index is 3D and on a HD somewhere.
Very high constants and high implementation complexity — I attempted it and gave up before coming up with earcut (Seidel was both slower and less robust on typical map data). Maybe worth another attempt — working on algorithmic libraries is much easier now thanks to LLM-driven validation/optimization loops.
Historically yes, and even more so with modern systems which optimize around modern best practices. For example, Unreal Engine's Nanite breaks geometry into hierarchical clusters of triangles.
If the triangles are long and thin, they end up stretching across the screen and mess up Nanite's hierarchical streaming and culling system.
Shading artifacts also crop up on long, thin polys.
Dense geometry with hierarchical streaming will perform better on large datasets than sparse geometry with long thin triangles and traditional approaches.
Mobile GPUs use tile-based rendering. A long thin triangle touches more tiles, so it costs more. That could make you think you need to use Delaunay all the time. But the gain from nicer Delaunay triangles on the GPU is small relative to the time you pay for Delaunay on the CPU. I've measured time profiles on map data. It could be that for games it pays off.
Definitely, you have to understand where your bottlenecks are. That's why it's best just to author good models.
Nanite/triangulation can help relieve GPU bottlenecks but if you're already stomping your CPU it won't help. Whether it's a good fit depends on your workload.
The commenter probably meant https://github.com/iShape-Rust/iTriangle, a sibling library that is indeed quite fast at triangulation, especially on bigger inputs
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?
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.
You don't need to increase the number of vertices to get more balanced triangles. None of the methods in the article add vertices, but the Delaunay triangulation is better than the others at creating balanced triangles. It's just also the slowest, so there's a tradeoff between triangle quality and speed.
Triangles that repeatedly cover the same pixel are a performance issue also. Super thin strips are not great for performance and more than offset the memory cost.
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?
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.
The obsession with triangles comes from Microsoft, who around 1995 chose to support only triangles in DirectX.
As a consequence of that, the GPU vendors designed then GPUs supporting only triangles in hardware, abandoning earlier attempts to also support other figures.
That has been inherited until today, so any program that wants to use not only the general-purpose computing features of a GPU, but also the dedicated graphics hardware from it, must convert any other kinds of graphics primitives into triangles, before rendering on the GPU.
I don't think that is quite right. I had a book about computer graphics using OpenGL from before then, and I remember it saying (something like) that various polygons were supported at the API layer, but the GL implementation would decompose them into triangles at some point, and this could have surprising results for texture mapping, so it was typically a good idea to triangulate shapes explicitly.
One major technical reason that triangles are nice is that every triangle determines a plane, and rendering points onto a bitmap is easier if you know the surface is planar.
Also important for physical modelling and geometric acoustics -- you need a geometric mesh (made of triangles) to work with. Which parts of could be sent to the GPU for processing as well.
Should mention the mother of all triangulators:
https://www.cs.cmu.edu/~quake/triangle.html
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.
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.
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.
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!
Numbers without benchmarks are useless. :) During vector map generation we make sure that all data is valid. But our users can import custom GeoJSON layers and they could contain all sorts of self-intersections.
ok interesting, thanks for actually running the comparison! looks like it clearly favors earstrip on this workload
Having triangulation conform to Delaunay is a big advantage though! You should also try out https://github.com/mapbox/earcut.hpp for the benchmark — it got a refine function recently that refines earcut output to Delaunay as well, and earcut+refine is still pretty fast.
thanks, good suggestion! earcut plus refine sounds like sensible comparison.
i’ve since reproduced the world dataset benchmark locally and found that polygon validation was taking about two-thirds of delaunay32’s time on the accepted inputs.
For practical data, a faster approach is usually to triangulate without validation, then just measure if triangulation is valid afterwards (which is simply comparing the sum of triangle areas with polygon area)
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?
>> 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(nlogn) time complexity
In solvespace we use a simple ear clipping algorithm but I'd love to have something O(nlog(n)).
I have yet to see one that's both small and comprehensible ;-) If I were to attempt it, I'd just add a spatial index to make the check for anything inside a triangle O(log(n)) and make sure we check for new ears adjacent to clipped ears. With that it should be n*log(n), but my old spatial index is 3D and on a HD somewhere.
Very high constants and high implementation complexity — I attempted it and gave up before coming up with earcut (Seidel was both slower and less robust on typical map data). Maybe worth another attempt — working on algorithmic libraries is much easier now thanks to LLM-driven validation/optimization loops.
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?
Historically yes, and even more so with modern systems which optimize around modern best practices. For example, Unreal Engine's Nanite breaks geometry into hierarchical clusters of triangles.
If the triangles are long and thin, they end up stretching across the screen and mess up Nanite's hierarchical streaming and culling system.
Shading artifacts also crop up on long, thin polys.
Dense geometry with hierarchical streaming will perform better on large datasets than sparse geometry with long thin triangles and traditional approaches.
Mobile GPUs use tile-based rendering. A long thin triangle touches more tiles, so it costs more. That could make you think you need to use Delaunay all the time. But the gain from nicer Delaunay triangles on the GPU is small relative to the time you pay for Delaunay on the CPU. I've measured time profiles on map data. It could be that for games it pays off.
Definitely, you have to understand where your bottlenecks are. That's why it's best just to author good models.
Nanite/triangulation can help relieve GPU bottlenecks but if you're already stomping your CPU it won't help. Whether it's a good fit depends on your workload.
I'd be interested if it benchmarked well against iShape-rust, the overlay engine in GeoRust:
https://github.com/ishape-rust/ioverlay
Not really apples to apples. iOverlay is more like a topology toolkit - things like set operations and buffering. pretty different from triangulation.
The commenter probably meant https://github.com/iShape-Rust/iTriangle, a sibling library that is indeed quite fast at triangulation, especially on bigger inputs
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?
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.
You don't need to increase the number of vertices to get more balanced triangles. None of the methods in the article add vertices, but the Delaunay triangulation is better than the others at creating balanced triangles. It's just also the slowest, so there's a tradeoff between triangle quality and speed.
Triangles that repeatedly cover the same pixel are a performance issue also. Super thin strips are not great for performance and more than offset the memory cost.
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.
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?
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.
Nice performance. Just looking at the triangles, some of them seem a bit tiny. Does that cause rendering problems at all?
Fantastic write-up, kudos to the author.
> A GPU fills triangles and nothing else.
Huh.
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.
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.
Obsession with triangles so the GPU can show millions of polygons on a webmap.
The obsession with triangles comes from Microsoft, who around 1995 chose to support only triangles in DirectX.
As a consequence of that, the GPU vendors designed then GPUs supporting only triangles in hardware, abandoning earlier attempts to also support other figures.
That has been inherited until today, so any program that wants to use not only the general-purpose computing features of a GPU, but also the dedicated graphics hardware from it, must convert any other kinds of graphics primitives into triangles, before rendering on the GPU.
I don't think that is quite right. I had a book about computer graphics using OpenGL from before then, and I remember it saying (something like) that various polygons were supported at the API layer, but the GL implementation would decompose them into triangles at some point, and this could have surprising results for texture mapping, so it was typically a good idea to triangulate shapes explicitly.
One major technical reason that triangles are nice is that every triangle determines a plane, and rendering points onto a bitmap is easier if you know the surface is planar.
Triangles are the simplest 2-d polytope?
There’s this thing called rendering, pretty important for maps.
Also important for physical modelling and geometric acoustics -- you need a geometric mesh (made of triangles) to work with. Which parts of could be sent to the GPU for processing as well.
Hardware/software rasterizers are already doing the "inside or outside" check millions/billions of times a second using the same determinant trick.