voronoi.triangles fails with square rectangle

[isaomatsunami]

d3.geom.voronoi().triangles returns only one triangle when given 4 points that consists of rectangle.

var h = 100, w = 200, vertices = [[0,0],[w,0],[0,h],[w,h]];
console.log( d3.geom.voronoi().triangles(vertices).length ); // shows 1
vertices = [[0,0],[w,0],[0,h],[w,h + 0.001]];
console.log( d3.geom.voronoi().triangles(vertices).length ); // shows 2

And I hope any accessor to edges(.r/.l) variables inside, especially info about index-based triangles.

[jasondavies]

This is a specific instance of a more general problem: there is more than one possible Delaunay triangulation for n ≥ 4 cocircular points; otherwise there is always a unique triangulation satisfying the Delaunay property. I think a reasonable fix is to pick an arbitrary Delaunay triangulation in this situtation.

[isaomatsunami]

This problem is much grave.
The regular grids, which have much more possible triangulations, have the same problem. In this case above, d3.geom.delaunay(vertices).length is 25, instead of 50.

[jasondavies]

Regular grids contain lots of instances of n = 4 cocircular points, for which there is no unique Delaunay triangulation.

[Fil]

This issue can be closed.

If anything, it is to be reopened on d3-voronoi; but see d3/d3-voronoi#13 which claims another computation method, and d3/d3-voronoi#12 which "solves" it by adding jitter.

[199600375707]

Issue3d/3d image_1895