mourner
commented
3 years ago This is a numerical robustness issue — Delaunator (the underlying library) fails on certain cases with convoluted floating point data. If I round the coordinates (in this case to 2 decimal points), it works properly:
Closing in favor of https://github.com/mapbox/delaunator/issues/61 — there is a workaround for the library but it would increase the dependency size quite a bit, so I'm thinking of producing multiple builds (robust and lite non-robust).
update: 100% sure this is due to repeated or near-repeated points in the input. Not sure if this is a bug or something you want to fix or try to help clients of the library not shoot themselves in the foot doing. Happy to close this as a user_error_wont_fix.
tl;dr: I noticed today that having repeated points (or near-repeated points because floating point numbers) causes d3-delaunay to return very strange tilings.
I built a tool that makes extensive use of d3-delaunay, and today when messing around with it I ended up in this surprising state:
(if you follow the blue, it's the raw output of d3-delaunay, you can see that those middle circles are pulling up in a weird way). My code uses cellPolygons and iterates over the points of each polygon.
I put the parameters I was using into an observable notebook and got a slightly different, but still broken tiling: https://observablehq.com/@blackmad/voronoi-neighbors
(blue are seed points) - notice how those round-ish tiles in the center don't meet?
I don't know how to debug this further. Is this a bug in d3-delaunay?