找出包含一组任意坐标的Voronoi区域

Question

我将为您翻译以下关于IT技术的内容：

我正在使用一个算法，每次迭代需要找到一组任意坐标属于 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的解决方案正是我想要的。不过，我有点尴尬，因为我自己没有想到...

- inconvergent

Answer 1

您不需要实际计算 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)的数组，其中包含与每个test_points最接近的voronoi_points中点的索引。

- Jaime