Extract neighbors from first shell of Voronoi tesselation

[cheins]

I’m assuming the best answer to this question requires using VoronoiDelaunay.jl, but I’m also open to other packages/approaches.

If I have a set of points in 2D (or 3D? Though not I’m not sure this is possible with the package VoronoiDelaunay.jl), what is the fastest way to get each of their nearest neighbors in a Voronoi-tesselation sense (e.g the neighbors within the ‘first Voronoi shell’)? I am also not really confident on the mathematics behind this or how it relates to Delaunay triangulation.

The data structure doesn’t matter too much to me, but let’s just assume the data is stored in a 2D array of type Array{Float64,2} called my_points, whose size is (nDims, nPoints), and nDims is 2 or 3, and nPoints is the number of points. Let’s say I want to have the output be an edge list of some kind, e.g. array of arrays called edge_list (Array{Array{Int64,1}}) where each element i of edge_list gives me the indices of those points that are Voronoi neighbors of the focal point i (whose coordinates are stored in my_points[:,i]).

[lobingera]

Can you do an example picture? It’s not clear which point you want to address as neighbor.

[cheins]

sure, i’ll add it now!

[lobingera]

I did something like this in different context (and not in julia), but it was straight forward: Neighor cells share an edge. So in my case i collected the polygon corners to an index list (match equal x,y) and found candidates that share a corner (index) and then looked left and right if they share an edge. If you need to be really, really fast, you can use the distances between points (that define voronoi cells) to limit the area to test.