Python：检查（并计算）点位于 Voronoi 单元内的位置

Question

我认为我的问题与这个问题或其他问题有一些共同点，但无论如何，我的问题并不具体涉及它们。

在找到某些点的泰森多边形后，我希望能够检查“其他”给定点在哪个泰森多边形内。 特别是：

假设有50个额外点，我想要能够计算每个泰森多边形包含多少个这些额外点。

我的最小工作示例(MWE)

from scipy.spatial import ConvexHull, Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt

points = [[0,0], [1,4], [2,3], [4,1], [1,1], [2,2], [5,3]]
#voronoi
vor = Voronoi(points)
voronoi_plot_2d(vor)
plt.show()

现在我获得了额外的分数

extraPoints = [[0.5,0.2], [3, 0], [4,0],[5,0], [4,3]]
# In this case we have that the first point is in the bottom left, 
# the successive three are in the bottom right and the last one
# is in the top right cell.

我在考虑利用获取vor.regions或vor.vertices的事实，但是我真的想不出什么办法。

是否有参数或方法可以实现这一点？

- Euler_Salter

Answer 1

这里有一些有趣的东西，我已经使用从这里得到的答案为您解决了它。此功能的文档在这里

from scipy.spatial import cKDTree
points = [[0,0], [1,4], [2,3], [4,1], [1,1], [2,2], [5,3]]
voronoi_kdtree = cKDTree(points)
extraPoints = [[0.5,0.2], [3, 0], [4,0],[5,0], [4,3]]
test_point_dist, test_point_regions = voronoi_kdtree.query(extraPoints)
test_point_regions
>>> array([0, 3, 3, 3, 6])

这是如何解释这个数组的方式 - 将您的“extraPoints”测试点称作“额外点”。 您的第一个测试点（0.5,0.2）位于围绕您的第0个点（0,0）的区域中。第二、三和四个点位于围绕点3（0索引）的区域中，该点为（4,1）。您的最后一个测试点位于（5,3）附近。 我认为在想象这些区域是多边形并尝试应用那种算法时可能会有问题，因为其中一些边缘区域是通向无限远处的区域。

- cardamom

---

这很有趣！我进行了一些快速测试，似乎与voronoi_plot_2d图表所示的相符。它们应该总是一致吗？我很困惑为什么voronoi没有自己的查询方法。 - uhoh

Answer 2

对于非常少的点和单元格，使用“点在多边形内”算法（可能有numpy的实现）来检查每个点与每个单元格是否相交会更简单。

一般情况下，可以在单元格上构建梯形图数据结构，并快速确定每个点属于哪个单元格。 任意找到的示例。

- MBo