Voronoi cell neighbors via delaunay.neighbors

[ttran17]

Issue #51 Find Voronoi cells and neighbors recommends using delaunay.neighbors to find neighboring Voronoi cells:

And given a point i, delaunay.neighbors returns the connected points on the Delaunay triangulation, which are also the adjacent Voronoi cells.

For cells on the convex hull using delaunay.neighbors does not always produce correct results.

Two examples: in the Delaunay / Voronoi diagrams below, delaunay.neighbors was used to find adjacent cells to the yellow cell; the result is the green cells.

I don't think the issue is with delaunay.neighbors. I think the artificial / arbitrary boundary imposed on this type of problem means that the Delaunay - Voronoi duality isn't always realized accurately for cells on the convex hull.

Here's a gist that provides a solution.

[Fil]

In my understanding, the issue is not related to the convex hull, only to clipping.

The cells are topologically adjacent, but their common edge might be outside the clipping range.

This raises two questions:

1. Can we come up with a better wording?

2. How do you test for that situation if you want to filter out neighbors that are not "visibly" connected?

For 2) I think the solution is to look if one of the (possibly two) triangles that have the two points in common has a circumcenter with coordinates inside the clipping region. If that's not the case and if there are two such points, then you'll need to check if the line connecting the two circumcenters crosses one of the edges of the clipping rectangle.

[ttran17]

The cells are topologically adjacent, but their common edge might be outside the clipping range.

I agree that is the issue. I just didn't describe it very well.

[Fil]

Here's my solution
https://observablehq.com/@fil/unconnected-delaunay-neighbors

[Fil]

Reopening as we might want to (at least) mention the solution in the documentation, or add a convenience function. Note that the solution in my observable is based on the circumcenters’s coordinates—a definite solution should be based on their index.

[Fil]

Maybe we should implement this in voronoi.neighbors; it would be like delaunay.neighbors, but clipped.

[ttran17]

The gist referenced at the bottom of my opening post implements a solution in voronoi.neighbors. The first part of the solution is delaunay.neighbors except it also keeps track of whether or not additional processing is needed to find "true" adjacent voronoi cells. If additional processing is needed it simply checks cell polygon coordinates (though not as succinctly as your observablehq solution).

I agree that a solution that checks circumcenter indices as opposed to coordinates is safer and more efficient except I don't see how you would do that when there is clipping involved. voronoi.js as currently implemented computes the clipped coordinates on the fly as needed when you ask for the cell polygon. Not sure if it's worth it to change the code to keep track of clipped coordinates in some persistent array.

[Fil]

Oh I see!—I'm sorry I was not able to read your gist in depth.

I would personally prefer something that has less code, if possible calling delaunay.neighbors rather than forking it. We would also need unit tests.

I see a comment in your code mentions 2 common points. In my version I checked only 1 point (and now I agree that 2 points make more sense, to avoid cells connected exactly by a vertex on the clipping edge).

[ttran17]

I would personally prefer something that has less code, if possible calling delaunay.neighbors rather than forking it.

I forked delaunay.neighbors (rather than calling) to save myself a for-loop. Perhaps someday when people look up "pre-mature optimization" on the internet they will be shown that piece of code.

We would also need unit tests.

I know you didn't like that your observablehq solution checked coordinates rather than indices for equality but that seems like the most economical solution. So I guess I'm in favor of changing the documentation and noting that you can compute voronoi neighbors using cell polygons as you did in your observablehq. In contrast to the fork / unit test / pull request route.

[Fil]

This is now available in d3-delaunay @5.2. Thank you for the suggestion.