search

mapbox / delaunator

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

Improve numerical robustness #27

Closed mourner closed 6 years ago

mourner commented 6 years ago

cc @fogleman. I think the elimination of Something is wrong with the input points. error in the second commit is important — if we looped through the hull and didn't find any visible edges, this means that the point is likely a near-duplicate we somehow missed in earlier filtering.

mourner commented 6 years ago

I also pushed improve-robustness-scale branch which scales coords to [1.0, 2.0), but not yet sure whether to do that.

mourner commented 6 years ago

Merged a simpler approach for now because it's an obvious improvement, will leave these branches for now and reconsider when we encounter more "bad" cases.