Get point associated with Voronoi region (scipy.sp

问题:

Notice: the answer by aqueiros, although higher up voted, is not correct. Particularly this statement "vor.regions always has an empty array in the first index", is not true.

---

I'm generating a simple 2D Voronoi tessellation, using the scipy.spatial.Voronoi function. I use a random 2D distribution of points (see MCVE below).

I need a way to go through each defined region (defined by scipy.spatial.Voronoi) and get the coordinates of the point associated to it (ie: the point that said region encloses).

The issue is that there are N+1 regions (polygons) defined for the N points, and I'm not sure what this means.

Here's a MCVE that will fail when it gets to the last region:

from scipy.spatial import Voronoi
import numpy as np

# Generate random data.
N = 10
x = [np.random.random() for i in xrange(N)]
y = [np.random.random() for i in xrange(N)]
points = zip(x, y)

# Obtain Voronoi regions.
vor = Voronoi(points)

# Loop through each defined region/polygon
for i, reg in enumerate(vor.regions):

    print 'Region:', i
    print 'Indices of vertices of Voronoi region:', reg
    print 'Associated point:', points[i], '\n'

Another thing I don't understand is why are there empty vor.regions stored? According to the docs:

regions: Indices of the Voronoi vertices forming each Voronoi region. -1 indicates vertex outside the Voronoi diagram.

What does an empty region mean?

---

Add

I tried the point_region attribute but apparently I don't understand how it works. It returns indexes outside of the range of the points list. For example: in the MCVE above it will always show an index 10 for a list of 10 points, which is clearly out of range.

回答1:

For your first question:

The issue is that there are N+1 regions (polygons) defined for the N points, and I'm not sure what this means.

This is because your vor.regions will always have an empty array. Something like

    [[],[0, 0],[0, 1],[1, 1]]

This is related to your second question:

Another thing I don't understand is why are there empty vor.regions stored? According to the docs: regions: Indices of the Voronoi vertices forming each Voronoi region. -1 indicates vertex outside the Voronoi diagram. What does an empty region mean?

By default Voronoi() uses QHull with options 'Qbb Qc Qz Qx' enabled (qhull.org/html/qvoronoi.htm). This inserts a "point-at-infinity" which is used to improve precision on circular inputs. Therefore, being a "fake" point, it has no region. If you want to get rid of this, try removing the Qz option:

vor = Voronoi(points, qhull_options='Qbb Qc Qx')

回答2:

I was misreading the docs. It says:

point_region: Index of the Voronoi region for each input point.

and I was using point_region it as if it were the: "Index of the input point for each Voronoi region".

Instead of using:

points[i]

the correct point coordinates for each region can be obtained with:

np.where(vor.point_region == i)[0][0]