我编写了一个小脚本,用于显示
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()
根据Voronoi图的概念,新点P所属的单元是由原始点中距离P最近的点生成的。找到这一点就是简单的距离最小化:
point_index = np.argmin(np.sum((points - new_point)**2, axis=1))
但是,您想要找到区域。不幸的是,
vor.regions
中的区域与vor.points
中的区域顺序不同(我不太明白为什么,因为每个点都应该有一个区域)。
所以我使用了以下方法:
vor.ridge_points
结果:
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()
这是一个演示:
注意,如果区域无界,其着色将会不正确;这是简单着色方法的缺陷,而不是区域查找算法的缺陷。请参阅为 Voronoi 图着色,了解为无界区域着色的正确方法。
旁白:我使用 NumPy 生成随机数,这比你所做的更简单。
您可以构建一个具有线性不等式的决策树,这将为您提供答案。 想想这个想法:
如果你可以通过这种方式创建多棵树,你可以选择最优的一棵,即最浅的一棵。