4

I wrote a small script for showing voronoi diagram of M points from this tutorial. I use scipy.spatial.

I Want to give a new point of plane and say this point is in which site of voronoi diagram. Is it possible?

This is my code:

import random
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import Voronoi, voronoi_plot_2d

N = 70
M = 10

Matrix = [(random.random()*100,random.random()*100)  for x in range(M)]
points = np.array(Matrix)


vor = Voronoi(points)
print(vor.ridge_vertices)

voronoi_plot_2d(vor)
plt.show()
Karim Pazoki
  • 951
  • 1
  • 13
  • 34

1 Answers1

8

By the concept of Voronoi diagram, the cell that new point P belongs to is generated by the closest point to P among the original points. Finding this point is straightforward minimization of distance: 

point_index = np.argmin(np.sum((points - new_point)**2, axis=1))

However, you want to find the region. And the regions in vor.regions are not in the same order as vor.points, unfortunately (I don't really understand why since there should be a region for each point).

So I used the following approach:

  1. Find all ridges around the point I want, using vor.ridge_points
  2. Take all of the ridge vertices from these ridges, as a set
  3. Look for the (unique) region with the same set of vertices.

Result:

M = 15
points = np.random.uniform(0, 100, size=(M, 2))
vor = Voronoi(points)
voronoi_plot_2d(vor)

new_point = [50, 50]   
plt.plot(new_point[0], new_point[1], 'ro')

point_index = np.argmin(np.sum((points - new_point)**2, axis=1))
ridges = np.where(vor.ridge_points == point_index)[0]
vertex_set = set(np.array(vor.ridge_vertices)[ridges, :].ravel())
region = [x for x in vor.regions if set(x) == vertex_set][0]

polygon = vor.vertices[region]
plt.fill(*zip(*polygon), color='yellow')  
plt.show()

Here is a demo:

enter image description here

Note that the coloring of the region will be incorrect if it is unbounded; this is a flaw of the simple-minded coloring approach, not of the region-finding algorithm. See Colorize Voronoi Diagram for the correct way to color unbounded regions.

Aside: I used NumPy to generate random numbers, which is simpler than what you did.