HN

Comments (33)

• Menu

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

  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/delaunay32i 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!
• Menu

  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.
• Menu

  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?
• Menu

  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?
• Menu

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

  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?
• 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.
• cadamsdotcom
  > A GPU fills triangles and nothing else.Huh.
• Menu

  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?
• 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.
• abcd_f
  Fantastic write-up, kudos to the author.
• deakmisra
  [flagged]
• Menu

  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.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.