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

Question

我正在用scipy.spatial.Voronoi函数生成一个简单的2D Voronoi图解。我使用点的随机2D分布(见下面的MCVE )。

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

问题是，N+1区域(多边形)是为N点定义的，我不知道这意味着什么。

这里有一个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存储？根据医生的说法：

区域:形成每个Voronoi区域的Voronoi顶点的指数。-1表示Voronoi图外的顶点。

空旷的区域意味着什么？

添加

我尝试了point_region属性，但显然我不明白它是如何工作的。它返回points列表范围之外的索引。例如:在上面的MCVE中，它总是显示一个包含10个点的索引10，这显然超出了范围。

Answer 1

关于你的第一个问题：

问题是，N点定义了N+1区域(多边形)，我不知道这意味着什么。

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

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

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

另一件我不明白的事情是，为什么会有空的vor.regions存储？根据docs: regions:构成Voronoi区域的Voronoi顶点的指数。-1表示Voronoi图外的顶点。空区域意味着什么？

默认情况下，Voronoi()使用QHull，选项‘Qz’已启用(qhull.org/html/qvoronoi.htm)。这就插入了一个“点无穷大”，用于提高圆形输入的精度。因此，它是一个“假”点，没有地域。如果您想摆脱这种情况，请尝试删除Qz选项：

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

Answer 2

我误读了医生。上面写着：

point_region：Voronoi区域的索引，用于每个输入点。

我使用point_region，就好像它是：“每个Voronoi区域的输入点索引”。

而不是使用：

points[i]

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

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

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)

和示例的结果

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]