python - 如何计算新点在Voronoi图的哪个位置？

Question

我写了一个小脚本来显示来自 this tutorial 的 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()

Answer 1

根据Voronoi图的概念，新点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 生成随机数，这比您做的更简单。