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)

您还可以创建一个索引数组以从asregion_point数组中找出多个：pointsregions

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