d3 / d3-delaunay

Compute the Voronoi diagram of a set of two-dimensional points.
https://d3js.org/d3-delaunay
ISC License
611 stars 57 forks source link

fix incorrect voronoi diagram for 5 collinear points #147

Closed Fil closed 4 months ago

Fil commented 4 months ago

This fixes #146 by adopting a simpler jittering strategy in the collinear case

Sharing for discussion, because this "fix" is really feeble: if we increase the radius a little bit more (to 5e-8), another test breaks. I'd like to find a more robust approach.

Maybe at some point we'll need to create a fake voronoi diagram from scratch, rather than replay with jittered points, but it seems that this is working well enough for now.

closes #146