根据Voronoi图的概念,新点P所属的单元是由原始点中距离P最近的点生成的。找到这一点就是直接最小化距离:
point_index = np.argmin(np.sum((points - new_point)**2, axis=1))
然而,您想要找到region。以及这些地区vor.regions
与以下顺序不同vor.points
,不幸的是(我真的不明白为什么,因为每个点都应该有一个区域)。
所以我使用了以下方法:
- 找到我想要的点周围的所有山脊,使用
vor.ridge_points
- 将这些山脊中的所有山脊顶点作为一个集合
- 寻找具有相同顶点集的(唯一)区域。
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()
这是一个演示:
请注意,如果该区域是无界的,则该区域的着色将不正确;这是简单着色方法的缺陷,而不是区域查找算法的缺陷。看为 Voronoi 图着色 https://stackoverflow.com/questions/20515554/colorize-voronoi-diagram为无界区域着色的正确方法。
旁白:我使用 NumPy 生成随机数,这比你所做的更简单。