alt Hacker NewsI'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?
Replies
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'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.