CODEWITHSUNDEEP
pythongraphicsscipycomputational-geometryvoronoi
john mangual
john mangual

Reputation: 8172

what does the -1 mean in Scipy's voronoi algorithm?

I am trying to custom plot the Voronoi regions of random points in 2D

import matplotlib.pyplot as plt
%matplotlib inline

from scipy.spatial import Voronoi
pt = np.random.random((10,2))
x = sp.spatial.Voronoi(pt)

# trial an error to figure out the type structure of [x]

plt.plot(x.vertices[:,0], x.vertices[:,1], '.', markersize=5)

# how to iterate through the x.regions object?
for poly in x.regions:
    z = np.array([ x.vertices[k] for k in poly])
    print z
    if z.shape[0] > 0:
        plt.plot( z[:,0], z[:,1])

plt.xlim([0,2])
plt.ylim([0,2])

why do the regions overlap? any advice for plotting the infinite regions?

enter image description here

The data points are just random numbers:

x.vertices

array([[ 0.59851675,  0.15271572],
       [ 0.24473753,  0.70398382],
       [ 0.10135325,  0.34601724],
       [ 0.42672008,  0.26129443],
       [ 0.54966835,  1.64315275],
       [ 0.24770706,  0.70543002],
       [ 0.39509645,  0.64211128],
       [ 0.63353948,  0.86992423],
       [ 0.57476256,  1.4533911 ],
       [ 0.76421296,  0.6054079 ],
       [ 0.9564816 ,  0.79492684],
       [ 0.94432943,  0.62496293]])

the regions are listed by number

x.regions

[[],
 [2, -1, 1],
 [3, 0, -1, 2],
 [5, 1, -1, 4],
 [6, 3, 2, 1, 5],
 [11, 9, 7, 8, 10],
 [8, 4, 5, 6, 7],
 [9, 0, 3, 6, 7],
 [10, -1, 4, 8],
 [11, -1, 0, 9],
 [11, -1, 10]]

and from this we can re-construct the plot. My question is what does the -1 mean?

Upvotes: 2

Views: 474

Answers (1)

Leon
Leon

Reputation: 32494

scipy.spatial.Voronoi uses the Qhull library underneath. In my experience Qhull contains several usability bugs. You hit one of them:

qvoronoi outputs

Voronoi vertices

[...]

FN: list the Voronoi vertices for each Voronoi region. The first line is the number of Voronoi regions. Each remaining line starts with the number of Voronoi vertices. Negative indices (e.g., -1) indicate vertices outside of the Voronoi diagram.

why do the regions overlap?

So, -1 in the first Voronoi region [2, -1, 1] from x.regions stands for a vertex-at-infinity (that is not represented in x.vertices). Yet, when you access x.vertices with that spurious index, you get the last vertex. This happens for every -1 in your x.regions (note that those -1's denote different vertices-at-infinity). As a result you get spurious Voronoi edges connecting to the last vertex from x.vertices.

any advice for plotting the infinite regions?

Why don't you simply use scipy.spatial.voronoi_plot_2d()?

Upvotes: 5

Related Questions