I have a set of points with x and y coordinates. I would like to build a Voronoi diagram from these points, and then build a graph based on this diagram, with the following rules:
How do I build this graph? I just a need a starting point, so I know where to begin.
The graph you are looking for is the Delaunay triangulation, which is the dual of the Voronoi diagram. In this graph, nodes correspond the points in the input and nodes are connected in the graph/triangulation if the associated Voronoi cells touch each other.
You can build the Delaunay triangulation in scipy using scipy.spatial.Delaunay. The data you are looking for (which vertices are connected to each other) is available through the vertex_neighbor_vertices attribute of the result.
>>> import numpy as np
>>> points = np.array([[0, 0], [0, 1.1], [1, 0], [1, 1]])
>>> from scipy.spatial import Delaunay
>>> tri = Delaunay(points)
>>> tri.vertex_neighbor_vertices
(array([ 0, 3, 5, 7, 10], dtype=int32), array([2, 3, 1, 3, 0, 3, 0, 2, 0, 1], dtype=int32))
In the above example, the graph connectivity is stored using two array: the second containing all the neighboring vertices and the first containing the ranges of positions in the each corresponding to each particular vertex. The verticies are numbered: 0=[0,0], 1=[0,1.1], 2=[1,0], 3=[1,1]). Then in the resulting graph, vertex 0 is connected to vertices 2, 3, and 1 (in positions 0, 1, and 3 in the second array), vertex 1 is connected to vertices 3 and 0 (n positions 3 and 4 in the second array), vertex 2 is connected to vertices 3 and 0 and vertex 3 is connected to vertices 2, 0, and 1.
From the scipy doc, triangulation is shown below: vertices 0 and 3 have three neighbors and the other two vertices only have two neighbors.
