python - voronoi 和 lloyd 放松使用 python/scipy

Question

如何使用 Qhull 确定哪些 voronoi 单元(按索引)是“正确的”(由“现有顶点”组成)

我正在尝试使用 LLoyds 算法和由 scipy.spatial Voronoi(它是 Qhull 的包装器)生成的输入执行约束松弛。

就代码而言，它看起来像:

points = [n  for n in itertools.product(xrange(3),xrange(3))]
vor = Voronoi(points)

vor2 = lloyd(vor) # my relaxation function  - not relevant to the question

代码生成的输出图看起来没问题(见下文)但是 vor 结构中的数据不足以执行 Lloyds 松弛。这是因为我应该只移动有效 voronoi 单元格内的点(图像中的 #4)。另一个应该保持原样。 Qhull 打乱了点/区域的顺序，所以我无法估计哪个区域属于哪个点。

下面是问题的说明:

print vor.vertices
#[[ 0.5  0.5]
# [ 1.5  0.5]
# [ 0.5  1.5]
# [ 1.5  1.5]]

print vor.regions  
# [[], [-1, 0], [-1, 1], [1, -1, 0], [3, -1, 2], [-1, 3], [-1, 2], [3, 2, 0, 1], [2, -1, 0], [3, -1, 1]]

print vor.points
# [[ 0.  0.]
#  [ 0.  1.]
#  [ 0.  2.]
#  [ 1.  0.]
#  [ 1.  1.]
#  [ 1.  2.]
#  [ 2.  0.]
#  [ 2.  1.]
#  [ 2.  2.]]
print vor.point_region
# [1 8 6 3 7 4 2 9 5]

现在我应该以某种方式发现 vor.regions[7] 是一个属于点 vor.points[4] 的区域。如何实现？

Answer 1

你有一个你知道的 region，一个你不知道的 point，而且你知道 vor.point_region[point] == region。对于单个region，可以算出对应的point为:

point = np.argwhere(vor.point_region == region)

您还可以创建一个region_point 索引数组来从regions 数组中找出多个点，如下所示:

region_point = np.argsort(vor.point_region)
points = region_point[regions-1]