delaunay.find returns zero when it should not

[boygirl]

I maintain a cloned and slimmed down version of d3-delaunay, and recently had the following edge case brought to my attention:

var scaled_data = [
  [60    ,17113.1],
  [106.5 ,17113.1],
  [153   ,17113.1],
  [199.5 ,17113.1],
  [246   ,17113.1],
  [292.5 ,17113.1],
  [339   ,17113.1],
  [385.5 ,17113.1]]

let delaunay = Delaunay.from(scaled_data)

delaunay.find(300, 17113.1)  // returns 0 but should return 5

I find that it fails when added to your test suite as well.

See FormidableLabs/delaunay-find#9 for original report

[Fil]

From what I see, it comes from the poor precision of area, which in this case return ~2e-10 (instead of 0 as the points are collinear). As a consequence, the test at https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js#L53 is skipped, and the collinear "hack" doesn't kick in. Which means we have no neighbors for (0), and find stops there.

tldr: We need a better formula for area.

[boygirl]

Would it also work to alter the threshold for collinearity to be a bit higher than the current value of 1e-10? Perhaps to match the jitter constant of 1e-8? I don't understand where these values are coming from, so forgive me if this is an unhelpful suggestion.

[Fil]

We can fiddle and move thresholds around, but the risk is that, while it would solve the issue for this specific set of values, it might break for another. What we want is probably a larger set of test cases, a more precise area computation, or a different strategy.

[mourner]

Maybe try https://en.wikipedia.org/wiki/Kahan_summation_algorithm ?

[Fil]

just tried this in my notebook and the area is evaluated as 1.1641532182693481e-10 ; better than 2.3283064365386963e-10 but still not good enough.

A way to get to a very nice and round 0 is to substract hull[0]'s coordinates from each subsequent point… but isn't this cheating?

function area(hull, points) {
  let n = hull.length, x0, y0,
      x1 = points[2 * hull[n - 1]],
      y1 = points[2 * hull[n - 1] + 1];

  const v = [];
  for (let i = 0; i < n; i ++) {
    x0 = x1, y0 = y1;
    x1 = points[2 * hull[i]] - points[2 * hull[0]];   // substract point[hull[0]]
    y1 = points[2 * hull[i] + 1] - points[2 * hull[0] + 1];
    v.push(y0 * x1, - x0 * y1);
  }

  return kahansum(v) / 2;
}

function kahansum(values) {
  let summ = 0,
    c = 0;
  for (const num of values) {
    let y = num - c,
      t = summ + y;
    c = t - summ - y;
    summ = t;
  }
  return summ;
}

[Fil]

Ref. d3/d3-array#35

[Fil]

In this case, we can tell the collinearity because the triangles returned is empty. See #93 for a solution that includes this, a kahan summation and a translation by -point[hull[0]].

[Fil]

I've updated #93 with much saner solution (faster, more accurate, and with less code).

[Fil]

fixed in c403f4b

thank you Lauren for the report