Invalid halfedges on some collinear input

[mbostock]

For example, note the missing edge here:

It seems you can avoid some of these cases by introducing surrounding points, e.g.,

Live test case in Observable:

https://beta.observablehq.com/d/02bcb6fb83d7e33f

[mbostock]

Here’s a bit more context. I’m trying to construct a Voronoi diagram from a tree layout, which tends to contain many collinear points. Notice that the Voronoi diagram is corrupt here (because the Delaunay it is derived from is missing edges):

[mourner]

Thanks for the report! Reduced test case:

[[382,302],[382,328],[382,205],[623,175],[382,188],[382,284],[382,267],[623,87],[623,341],[141,227]]

[mourner]

@mbostock it appears that Delaunator itself triangulates these cases properly. So it must be something on the d3-delaunay side:

[mbostock]

Apologies, but I’m seeing this exact behavior in Delaunator, too. (d3-delaunay doesn’t do anything to the fields generated by Delaunator, so this isn’t surprising.) I’ve updated my Observable notebook to render by hand using Delaunator rather than using d3-delaunay.

https://beta.observablehq.com/d/02bcb6fb83d7e33f

Perhaps I’m not using Delaunator correctly?

[mbostock]

Ah… I’ve discovered the issue. Broken iteration over halfedges:

function renderEdges(delaunator, context) {
  for (let i = 0, n = delaunator.halfedges.length; i < n; ++i) {
    if (delaunator.halfedges[i] > i) {
      const p = delaunator.triangles[i];
      const q = delaunator.triangles[delaunator.halfedges[i]];
      context.moveTo(delaunator.coords[p * 2], delaunator.coords[p * 2 + 1]);
      context.lineTo(delaunator.coords[q * 2], delaunator.coords[q * 2 + 1]);
    }
  }
}

Fixed iteration:

function renderEdges(delaunator, context) {
  for (let i = 0, n = delaunator.halfedges.length; i < n; ++i) {
    if (i > delaunator.halfedges[i]) {
      const p = delaunator.triangles[i];
      const q = delaunator.triangles[i % 3 === 2 ? i - 2 : i + 1];
      context.moveTo(delaunator.coords[p * 2], delaunator.coords[p * 2 + 1]);
      context.lineTo(delaunator.coords[q * 2], delaunator.coords[q * 2 + 1]);
    }
  }
}

[mbostock]

To add a little more detail here, I had assumed that for each internal edge of the Delaunay triangulation, there would be two corresponding halfedges. So, for a halfedge i corresponding to an internal edge:

const j = delaunator.halfedges[i]; // the opposite halfedge of i
const k = delaunator.halfedges[j]; // the opposite halfedge of j
k === i; // should be true

However, in the case of collinear input like here, we end up with a bad triangulation, where k !== i, and hence the different behavior between the two loops above.

And critically, even though it appears I can render the Delaunay edges by taking a different approach to iteration, it seems that the computed halfedges aren’t correct (they’re asymmetric), and so I can’t traverse the Delaunay graph or construct the Voronoi diagram… and hence I think this still counts as a Delaunator bug. 😁

[mourner]

Thanks for the details! I'll investigate the invalid halfedges issue.

[redblobgames]

My code also breaks if halfedges[halfedges[i]] !== i for internal edges. I think I've avoided the problem mostly because my input points are random so the chance of being collinear is low.

@mbostock I agree — I think your old iteration loop should work.

[mourner]

I've narrowed this down to Delaunator breaking the validity of the hull structure after a certain triangle flip. By definition, all hull edges should always conform to halfedges[e] === -1, but after a certain flip in this case, this breaks. I haven't tracked down the root cause yet though — the code I wrote is quite mind-bending. Perhaps I also need to add some more comments with diagrams for future digging.

[mbostock]

Thanks for investigating! Visualizing this algorithm has long been on my wishlist for Observable notebooks.

[mourner]

I think I've got to the bottom of this. Early in the triangulation, when a triangle is added outside the hull and triangle flipping is recursively propagated, it might flip deeply up to the opposite side of the hull, which isn't updated when the halfedge is swapped. It's a variation of #11, and apparently the fix in #12 didn't cover all the cases where it happens. I don't yet have a solution for this — will try to come up with a better fix.

[mourner]

@mbostock should be fixed in #25 — can you try Delaunator v2.0.2 in your tree layouts now?

[mbostock]

Looks great! 👍