Odd failure

[madcowfpb]

I haven't tried to exactly isolate the bug yet, but the attached exhibits a failure case. The voronoi library at https://github.com/Dozed12/p5.voronoi seems to handle this set of points correctly. It looks like the circumcenters are correctly computed.

vfail2.txt

[mbostock]

Here is a notebook to reproduce: https://observablehq.com/d/7624520d45e4b44f (In the future, if you’d be willing to share these reproductions as an Observable notebook, it would save us some time. Thank you!)

It renders fine when scaled and translated, as here with Plot:

Plot.marks(Plot.voronoi(points), Plot.delaunayMesh(points)).plot()

But it looks like the there are some problems computing the Voronoi cell edges for points on the Delaunay hull.

[Fil]

Not that it helps much to understand why the bug happens, but this test case is correct under d3-delaunay@4.

[Fil]

In the collinear case (a "flat triangle" on the hull)

d3-delaunay/src/voronoi.js

Line 41 in 48d091f

if (Math.abs(ab) < 1e-9) {

, we compute a to cast a long ray (1e9) towards the exterior in order to compute the circumcenter as the "point at infinity".

In this case a is sometimes 0, or going in the wrong direction, because the reference point r (point 36, marked as a green circle) happens to be exactly on the hull, and collinear with the (flat) triangle whose circumcenter we're trying to compute.

So, any flat triangle on the collinear part of the hull has a 1/2 chance to have its (degenerate) circumcenter be projected in the wrong direction. This results in the weird polygonCell 180 (also in green).

A quick and dirty patch:

-        const r = triangles[0] * 2;
-        a *= Math.sign((points[r] - x1) * ey - (points[r + 1] - y1) * ex);
+        let i=0;
+        while (i < triangles.length && Math.abs(a) < 1e-3) {
+          const r = triangles[i++] * 2;
+          a =  ((points[r] - x1) * ey - (points[r + 1] - y1) * ex);
+        }
+        a = Math.sign(a) * 1e9;

There might be a better approach though, using the fact that the hull points are enumerated clockwise? Needs a bit more thought.

[Fil]

#142 fixes it, thanks for the test case!