search

mapbox / delaunator

An incredibly fast JavaScript library for Delaunay triangulation of 2D points
https://mapbox.github.io/delaunator/
ISC License
2.3k stars 141 forks source link

Fix race condition that produced broken triangulation #26

Closed mourner closed 6 years ago

mourner commented 6 years ago

Closes #13. Turns out on certain kinds of degenerate input (such as points on a circle), the algorithm tried to flip triangles on the boundary (which don't have a pair). cc @fogleman

mourner commented 6 years ago

Ha, so you've found the same fix in https://github.com/fogleman/delaunay/commit/b6dfa1814edb23c117d05d4e4362b1935e34058c :)

fogleman commented 6 years ago

Yeah. I wasn't sure if my "fix" was a hack or not though, so I'm glad to see this.

fogleman commented 6 years ago

Oh nice, I was wondering how best to validate the triangulation. Comparing the hull area to the sum of the triangle areas looks like a good approach!

mourner commented 6 years ago

@fogleman yeah, I've been using this approach for a few years in earcut and it works very well.

Regarding the fix — the issue is that recursive flipping can go deep enough to get to the other side of the hull, which is common in the circle case because all triangles are sliver and likely to need flipping in the same pass when adding a point on the side, but it can happen in other cases. The check simply stops the flipping if we reached the boundary.