what does the -1 mean in Scipy's voronoi algorithm?
<p>I am trying to custom plot the <a href="http://scipy.github.io/devdocs/generated/scipy.spatial.Voronoi.html" rel="nofollow">Voronoi</a> regions of random points in 2D</p>

<pre><code>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] &gt; 0:
        plt.plot( z[:,0], z[:,1])

plt.xlim([0,2])
plt.ylim([0,2])
</code></pre>

<p>why do the regions overlap?  any advice for plotting the infinite regions?</p>

<p><a href="http://i.stack.imgur.com/oXSjA.png" rel="nofollow"><img src="http://i.stack.imgur.com/oXSjA.png" alt="enter image description here"></a></p>

<hr>

<p>The data points are just random numbers:</p>

<pre><code>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]])
</code></pre>

<p>the regions are listed by number</p>

<pre><code>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]]
</code></pre>

<p>and from this we can re-construct the plot.  My question is what does the <code>-1</code> mean?</p>

<p><a href="http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Voronoi.html" rel="nofollow"><code>scipy.spatial.Voronoi</code></a> uses the Qhull library underneath. In my experience Qhull contains several usability bugs. You hit <a href="http://www.qhull.org/html/qvoronoi.htm#outputs" rel="nofollow">one of them</a>:</p>

<blockquote>
  <h2>qvoronoi outputs</h2>
  
  <h3>Voronoi vertices</h3>
  
  <p>[...]</p>
  
  <p><code>FN</code>: 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. <strong>Negative indices (e.g., -1) indicate
  vertices outside of the Voronoi diagram.</strong></p>
</blockquote>

<hr>

<hr>

<blockquote>
  <p>why do the regions overlap?</p>
</blockquote>

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

<blockquote>
  <p>any advice for plotting the infinite regions?</p>
</blockquote>

<p>Why don't you simply use <a href="http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.voronoi_plot_2d.html" rel="nofollow"><code>scipy.spatial.voronoi_plot_2d()</code></a>?</p>

python graphics scipy computational-geometry voronoi