我正在使用一种算法,对于每次迭代,都需要找到一组任意坐标属于 Voronoi 图的哪个区域。即每个坐标位于哪个区域内。 (我们可以假设所有坐标都属于一个区域,如果这有什么区别的话。)
我还没有任何可以在 Python 中运行的代码,但伪代码如下所示:
## we are in two dimensions and we have 0<x<1, 0<y<1.
for i in xrange(1000):
XY = get_random_points_in_domain()
XY_candidates = get_random_points_in_domain()
vor = Voronoi(XY) # for instance scipy.spatial.Voronoi
regions = get_regions_of_candidates(vor,XY_candidates) # this is the function i need
## use regions for something
我知道 scipy.Delaunay 有一个名为 find_simplex 的函数,它几乎可以完成我想要的 Delaunay 三角剖分中的单纯形,但我需要 Voronoi 图,并且构建两者是我希望避免的事情。
问题:
1.是否有某种图书馆可以让我轻松地做到这一点?
2. 如果没有,是否有一个好的算法可以让我有效地做到这一点?
Update
杰米的解决方案正是我想要的。我有点尴尬,虽然我自己没有想到这一点......
您不需要为此实际计算 Voronoi 区域。根据定义,集合中某个点周围的 Voronoi 区域由距离该点比集合中任何其他点更近的所有点组成。所以你只需要计算距离并找到最近的邻居。使用 scipy 的cKDTree
你可以这样做:
import numpy as np
from scipy.spatial import cKDTree
n_voronoi, n_test = 100, 1000
voronoi_points = np.random.rand(n_voronoi, 2)
test_points = np.random.rand(n_test, 2)
voronoi_kdtree = cKDTree(voronoi_points)
test_point_dist, test_point_regions = voronoi_kdtree.query(test_points, k=1)
test_point_regions
现在保存一个形状数组(n_test, 1)
与点的索引voronoi_points
最接近你的每一个test_points
.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)