CODEWITHSUNDEEP
pythonscipyvoronoi
Karim Pazoki
Karim Pazoki

Reputation: 969

How to calculate in which site of a Voronoi diagram a new point is?

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()

Upvotes: 4

Views: 3299

Answers (2)

Peter Kishalov
Peter Kishalov

Reputation: 1

You can construct a decision tree with linear inequalities which will give you the answer. Think of this idea:

  1. Select a ridge in the middle of your voronoi diagram, use its formula (dot product and comparison) to separate the space in 2 chunks
  2. repeat this separation for each chunk recursively, until you come to each polygon

If you can create multiple trees this way, you may select the most optimal one, which shall be the shallowest one.

Upvotes: 0

user6655984
user6655984

Reputation:

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.

Upvotes: 8

Related Questions