Python：检查（并计算有多少）点位于 voronoi 单元内的位置

Question

我认为我的问题与 this question 或其他人有一些共同点，但无论如何，我的问题并不是专门针对这些问题。

我希望在找到某些点的 voronoi 镶嵌之后，能够检查其他给定点在镶嵌中的位置。特别是：

假设有 50 个额外点，我希望能够计算出每个 voronoi 单元包含多少个额外点。

我的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 的事实，但我真的想不出任何东西..

是否有参数或方法可以做到这一点

Answer 1

对于非常少的点和单元格，使用“point in polygon”算法（可能有它的 numpy 实现）检查每个点和每个单元格可能更简单

一般情况下，您可以在单元格上构建 梯形图 数据结构并快速确定 - 每个点属于哪个单元格。

Arbitrary found example

Answer 2

这个东西很有意思，我用here The docs for this function are here

的答案给你解决了

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) 左右。

我认为将这些区域想象成多边形并尝试应用这种算法可能存在问题，因为边缘上的一些区域是无限远的区域。

Python：检查（并计算有多少）点位于 voronoi 单元内的位置

Python: check (and count how many) where points sit within voronoi cells

python

geometry

voronoi

numpy

scipy