Получить точку, связанную с Вороной областью (scipy.spatial.Voronoi)

Обратите внимание: ответ aqueiros, хотя и проголосовал выше, не является правильным. В частности, это утверждение " vor.regions всегда имеет пустой массив в первом индексе ", не соответствует действительности.

Я создаю простую 2D тесселяцию Вороного, используя функцию scipy.spatial.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 хранится? Согласно документам:

области: индексы вершин Вороного, образующих каждую область Вороного. -1 указывает вершину за пределами диаграммы Вороного.

Что означает пустой регион?

добавлять

Я попробовал point_region атрибут, но, видимо, я не понимаю, как это работает. Возвращает индексы за пределами диапазона points список. Например: в MCVE выше он всегда будет показывать индекс 10 для списка из 10 пунктов, который явно вне диапазона.

Источник

3 ответа

Решение

Я неправильно читал документы. Это говорит:

point_region: индекс области Вороного для каждой входной точки.

и я использовал point_region это как если бы это было: "Индекс входной точки для каждой области Вороного".

Вместо того, чтобы использовать:

points[i]

правильные координаты точки для каждого региона можно получить с помощью:

np.where(vor.point_region == i)[0][0]
Источник

Для вашего первого вопроса:

Проблема в том, что для N точек определены N+1 регионов (полигонов), и я не уверен, что это значит.

Это потому, что ваши vor.regions всегда будут иметь пустой массив. Что-то вроде

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

Это связано с вашим вторым вопросом:

Другая вещь, которую я не понимаю, - почему там хранятся пустые vor.regions? По документам: регионы: индексы вершин Вороного, образующих каждую область Вороного. -1 указывает вершину за пределами диаграммы Вороного. Что означает пустой регион?

По умолчанию Voronoi() использует QHull с включенными параметрами "Qbb Qc Qz Qx" ( http://qhull.org/html/qvoronoi.htm). Это вставляет "точку в бесконечности", которая используется для повышения точности на круговых входах. Поэтому, будучи "фальшивой" точкой, у нее нет региона. Если вы хотите избавиться от этого, попробуйте удалить опцию Qz:

vor = Voronoi(points, qhull_options='Qbb Qc Qx')
Источник

Вот решение:

      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]
Источник
Другие вопросы по тегам