Wrong hull in specific situations

[viltit]

It seems that in certain situation the hull is incorrect. See the attached demo for the behaviour we encountered.

In our case, we have solved the issue by doubling the hashSize.

Example html. demo.zip

[mbostock]

As a notebook:

https://beta.observablehq.com/d/2ffd8a583a29944d

[bryangingechen]

I just ran into this issue too. Here's a smaller broken example (117 points): https://beta.observablehq.com/d/8b0bdd309749444d

[mourner]

I've looked into it yesterday, and it seems like a difficult issue to fix — it's caused by non-robust floating point orientation tests. Here's an excellent article explaining the issue. A workaround would be to switch to integer coordinates (which won't have this problem as long as they're not too big), or round up / perturb the coordinates in any other way until the problem goes away.

[mourner]

Here's the smallest test case, reduced from the one by @bryangingechen. Changing any digit in this input (or flipping sings everywhere) resolves the issue, indicating a floating point error.

[
  [-537.7739674441619, -122.26130468750004],
  [-495.533967444162, -183.39195703125006],
  [-453.29396744416204, -244.5226093750001],
  [-411.0539674441621, -305.6532617187501],
  [-164, -122],
]

[Fil]

Interestingly the three examples above are solved if you change coords to be a Float32Array. Applying the same coercion in d3-delaunay also solves https://github.com/d3/d3-delaunay/issues/72 and https://github.com/d3/d3-delaunay/issues/79 — of course it's but a (gross?) way of enforcing an automatic rounding of the values.

[mbostock]

That sounds like an eminently practical solution to me, if gross. 👍

[Fil]

I don't know — If this trick is simply changing the scale at which the issue appears, it's not a win. We've solved 5 cases but maybe introduced bugs in other (unknown and untested) cases.

OTOH I've tried a little to generate buggy situations and didn't succeed, so maybe it is enough.

[Fil]

Not for me to say if Delaunator should use this trick or find a different solution — and anyway it can be decided by the user when they create the points typedArray.

PR #85 for d3-delaunay ; see it in action at https://observablehq.com/d/ae9686bd1a058bc2

[Fil]

Trying to make sense of why the Float32Array worked, I ended up with this patch which passes all delaunator tests, and solves the four test cases listed in https://github.com/d3/d3-delaunay/pull/85

function dist(ax, ay, bx, by) {
    [ax, ay, bx, by] = [ax, ay, bx, by].map(Math.fround);
    const dx = ax - bx;
    const dy = ay - by;
    return dx * dx + dy * dy;
}

function orient(px, py, qx, qy, rx, ry) {
    [px, py, qx, qy, rx, ry] = [px, py, qx, qy, rx, ry].map(Math.fround);
    return (qy - py) * (rx - qx) - (qx - px) * (ry - qy) < 0;
}

(I know the syntax is dreadful, bear with me.)

From here maybe we can investigate which dists and orients botch the examples, and do something about it?

For example, this triangle shows a different orientation if we fround its coordinates:

{
  px: 11.25,
  py: 41.61530616515118,
  qx: 11.025,
  qy: 41.29760211738566,
  rx: 10.8,
  ry: 40.979898069620134
}