查找包含任意坐标列表的voronoi地区 [英] Finding voronoi regions that contain a list of arbitrary coordinates

问题描述

我正在使用一种算法，对于每次迭代，都需要找到一组Voronoi图属于哪个Voronoi图的区域.也就是说，每个坐标位于哪个区域. (我们可以假设所有坐标都属于一个区域，如果有任何区别的话.)

I am working with an algorithm that, for each iteration, needs to find which region of a Voronoi diagram a set of arbirary coordinats belong to. that is, which region each coordinate is located within. (We can assume that all coordinates will belong to a region, if that makes any difference.)

我还没有在Python中可用的代码，但是伪代码看起来像这样:

I don't have any code that works in Python yet, but the the pseudo code looks something like this:

## 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图，并且构造两者都是我要避免的事情.

I know that the scipy.Delaunay has a function called find_simplex which will do pretty much what I want for simplices in a Delaunay triangulation, but I need the Voronoi diagram, and constructing both is something I wish to avoid.

问题:

1.有某种可以让我轻松完成此任务的库吗?

2.如果没有，那么我是否可以考虑一个好的算法，让我高效地做到这一点?

更新

Jamie的解决方案正是我想要的.令我有些尴尬的是我自己却没有想到...

Jamie's solution is exactly what I wanted. I'm a little embarrassed that I didn't think of it myself though ...

推荐答案

您不需要为此实际计算Voronoi地区.根据定义，集合中某个点周围的Voronoi区域是由比该集合中任何其他点都近的所有点组成的.因此，您只需要计算距离并找到最近的邻居即可.使用scipy的cKDTree，您可以执行以下操作:

You don't need to actually calculate the Voronoi regions for this. By definition the Voronoi region around a point in your set is made up of all points that are closer to that point than to any other point in the set. So you only need to calculate distances and find nearest neighbors. Using scipy's cKDTree you could do:

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.

test_point_regions Now holds an array of shape (n_test, 1) with the indices of the points in voronoi_points closest to each of your test_points.

这篇关于查找包含任意坐标列表的voronoi地区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！