I'm working on an algorithm that uses Voronoi diagrams. I need to know for every given cell, which cells it has as neighbors; that is, which neighbors it shares an edge with. This is similar to an existing question. However, I already have an algorithm that computes this, but I'm looking to speed it up and avoid redundant calculations.
Currently I'm doing this with the output from scipy.spatial.Voronoi which gives me arrays of the vertices, points, etc that I can build this mapping with. However, I'm running this algorithm with a lot of points and I'd like to speed up the process.
My understanding is that scipy and Qhull calculate the Delaunay triagulation and then uses that to compute the Voronoi diagram. I think (but could be mistaken) that adjacency information can be found from the Delaunay triangulation. I'm wondering if there is a way to extract this information (if it exists) from scipy/Qhull when I generate the Voronoi diagram.
If not, are there any preferred methods to do this? Would I be better off, in the long run, using Qhull directly ?
Thanks.
I think it's only possible with fortune algorithm:https://cs.stackexchange.com/questions/80939/voronoi-diagram-status-structure-in-fortunes-algorithm.
Look for half-egde.
Maybe you can implement the half-edge with other solution but not with qhull.