5

我正在使用一种算法，对于每次迭代，都需要找到一组任意坐标所属的 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. 如果没有，是否有一个好的算法可以让我有效地做到这一点？

更新

Jamie 的解决方案正是我想要的。我有点尴尬，虽然我自己没有想到它......

4

1 回答 1

7

您不需要为此实际计算 Voronoi 区域。根据定义，集合中某个点周围的 Voronoi 区域由与该点比集合中任何其他点更接近的所有点组成。所以你只需要计算距离并找到最近的邻居。使用 scipy'scKDTree你可以这样做：

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.

于 2013-07-25T13:03:01.877 回答