如何计算新点在 Voronoi 图的哪个站点？

Question

我为展示来自这篇教程的M个点的voronoi图编写了一个小脚本。我使用了scipy.spatial。

我想要提供一个新的平面点，并指出这个点在voronoi图的哪个站点。这是否可能？

以下是我的代码：

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

Answer 1

通过沃罗诺伊图的概念，新点P所属的单元格是由原始点中离P最近的点生成的。找到这个点是直接最小化距离：

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

然而，您想要找到“区域”。不幸的是，vor.regions 中的区域顺序与 vor.points 不同（我真的不明白为什么，因为每个点应该都有一个区域）。

所以，我采用了以下方法：

1. 使用 vor.ridge_points 找到我想要的所有边缘。
2. 将这些边缘的所有顶点作为集合。
3. 查找具有相同顶点集的（唯一的）区域。

结果：

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

以下是示例：

请注意，如果区域未被限制，则区域的着色将不正确；这是简单色彩方法的缺陷，而不是区域查找算法的缺陷。请参见Colorize Voronoi Diagram以了解正确的方法来着色无界区域。

此外：我使用NumPy生成随机数，这比您的方法更简单。

- user6655984