获取与 Voronoi 区域关联的点 (scipy.spatial.Voronoi)

Question

我正在使用 scipy.spatial.Voronoi 函数生成一个简单的 2D Voronoi 曲面细分。我使用点的随机二维分布（参见下面的 MCVE）。

我需要一种方法来遍历每个定义的区域（由 scipy.spatial.Voronoi 定义）并获取与其关联的点的坐标（即：所述区域包围的点）。

问题是为 N 个点定义了 N+1 个区域（多边形），我不确定这意味着什么。

这是一个 MCVE，它在到达最后一个区域时会失败：

from scipy.spatial import Voronoi
import numpy as np

# Generate random data.
N = 10
x = [np.random.random() for i in xrange(N)]
y = [np.random.random() for i in xrange(N)]
points = zip(x, y)

# Obtain Voronoi regions.
vor = Voronoi(points)

# Loop through each defined region/polygon
for i, reg in enumerate(vor.regions):

    print 'Region:', i
    print 'Indices of vertices of Voronoi region:', reg
    print 'Associated point:', points[i], '\n'

我不明白的另一件事是为什么存储的 vor.regions 是空的？根据文档：

regions: Indices of the Voronoi vertices forming each Voronoi region. -1 indicates vertex outside the Voronoi diagram.

空白区域是什么意思？

添加

我尝试了 point_region 属性，但显然我不明白它是如何工作的。它 returns 索引在 points 列表的范围之外。例如：在上面的 MCVE 中，对于 10 个点的列表，它将始终显示一个索引 10，这显然超出了范围。

Answer 1

我误读了文档。它说：

point_region: Index of the Voronoi region for each input point.

我正在使用 point_region 它就好像它是：“每个 Voronoi 的 输入点 的索引地区".

而不是使用：

points[i]

可以通过以下方式获得每个区域的正确点坐标：

np.where(vor.point_region == i)[0][0]

Answer 2

第一个问题：

The issue is that there are N+1 regions (polygons) defined for the N points, and I'm not sure what this means.

这是因为您的 vor.regions 总是有一个空数组。像

    [[],[0, 0],[0, 1],[1, 1]]

这与你的第二个问题有关：

Another thing I don't understand is why are there empty vor.regions stored? According to the docs: regions: Indices of the Voronoi vertices forming each Voronoi region. -1 indicates vertex outside the Voronoi diagram. What does an empty region mean?

默认情况下，Voronoi() 使用启用选项 'Qbb Qc Qz Qx' 的 QHull (qhull.org/html/qvoronoi.htm)。这会插入一个 "point-at-infinity" 用于提高循环输入的精度。因此，作为 "fake" 点，它没有区域。如果您想摆脱它，请尝试删除 Qz 选项：

vor = Voronoi(points, qhull_options='Qbb Qc Qx')

Answer 3

这是一个解决方案：

import numpy as np
from scipy.spatial import Voronoi
import matplotlib.pyplot as plt
from plotutils_moje import voronoi_plot_2d


class VoronoiRegion:
    def __init__(self, region_id):
        self.id = region_id
        self.vertices = []
        self.is_inf = False
        self.point_inside = None

    def __str__(self):
        text = f'region id={self.id}'
        if self.point_inside:
            point_idx, point = self.point_inside
            text = f'{text}[point:{point}(point_id:{point_idx})]'
        text += ', vertices: '
        if self.is_inf:
            text += '(inf)'
        for v in self.vertices:
            text += f'{v}'
        return text

    def __repr__(self):
        return str(self)

    def add_vertex(self, vertex, vertices):
        if vertex == -1:
            self.is_inf = True
        else:
            point = vertices[vertex]
            self.vertices.append(point)

def voronoi_to_voronoi_regions(voronoi):
    voronoi_regions = []

    for i, point_region in enumerate(voronoi.point_region):
        region = voronoi.regions[point_region]
        vr = VoronoiRegion(point_region)
        for r in region:
            vr.add_vertex(r, voronoi.vertices)
        vr.point_inside = (i, voronoi.points[i])
        voronoi_regions.append(vr)
    return voronoi_regions


points = np.array([[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]])
vor = Voronoi(points)
regions = voronoi_to_voronoi_regions(vor)
for r in regions:
    print(r)

和 sample 的结果：

region id=1[point:[0. 0.](point_id:0)], vertices: (inf)[0.5 0.5]
region id=3[point:[0. 1.](point_id:1)], vertices: (inf)[0.5 1.5][0.5 0.5]
region id=2[point:[0. 2.](point_id:2)], vertices: (inf)[0.5 1.5]
region id=8[point:[1. 0.](point_id:3)], vertices: (inf)[1.5 0.5][0.5 0.5]
region id=7[point:[1. 1.](point_id:4)], vertices: [0.5 0.5][0.5 1.5][1.5 1.5][1.5 0.5]
region id=9[point:[1. 2.](point_id:5)], vertices: (inf)[1.5 1.5][0.5 1.5]
region id=6[point:[2. 0.](point_id:6)], vertices: (inf)[1.5 0.5]
region id=4[point:[2. 1.](point_id:7)], vertices: (inf)[1.5 1.5][1.5 0.5]
region id=5[point:[2. 2.](point_id:8)], vertices: (inf)[1.5 1.5]

获取与 Voronoi 区域关联的点 (scipy.spatial.Voronoi)

Get point associated with Voronoi region (scipy.spatial.Voronoi)

python

voronoi

scipy