scipy.spatial.Voronoi: Как узнать, где луч пересекает данную линию?

Всем добрый день,

У меня есть следующий сегмент кода:

import numpy as np from random import randint import matplotlib.pyplot as plt from scipy.spatial import Voronoi, voronoi_plot_2d NUM_OF_POINTS = 20 points = [] for i in range (0, NUM_OF_POINTS): points.append([randint(0, 500), randint(0, 500)]) points = np.array(points) vor = Voronoi(points) voronoi_plot_2d(vor) plt.show() 

Это производит графики Вороного, такие как: случайная диаграмма Вороного

Моя цель – найти, где «лучи» (линии, выходящие из сюжета, пунктирные или сплошные) пересекаются с данной линией (например, x = 500). Как я могу это сделать?

Я уже пробовал использовать список ridge_vertices в объекте ridge_vertices , однако эти «лучи» связаны только с одной вершиной в списке, поэтому я не могу определить линейное уравнение.

Редактировать:

Моя конечная цель заключается в том, чтобы с учетом границ плоскости находить точки, которые пересекаются с этими границами для данной ячейки кромки. Например, учитывая краевую ячейку в левом верхнем углу и границы y = -50 и x = 525, я бы нашел точки, отмеченные красным X.

примерный случай

Поэтому, если у вас есть какие-либо идеи, они будут оценены.

Спасибо.

  1. Уголки тривиальны, потому что вы знаете координаты x и y.

  2. Ребра на диаграмме Вороного равноудалены центрам двух ячеек, которые разделены этим ребром, который, естественно, включает конечную точку «луча» (в вашей терминологии). Пусть два центра – это точки (x1, y_1) и (x_2, y_2) , а пересечение луча с границей be (x*, y*) , то выполняется следующее:

(1) (x*-x_1)^2 + (y*-y_1)^2 = d^2

(2) (x*-x_2)^2 + (y*-y_2)^2 = d^2

Вы знаете x* или y* потому что они определены границей. Тогда у вас есть два уравнения и два неизвестных ( x* или y* и d ). Предполагая, что вы знаете y* , вы приходите к следующему решению для x* :

x* = ((y*-y_1)^2 - (y*-y_2)^2 + x_1^2 - x_2^2) / (2 * (x_1 - x_2))


Теперь, как вы определяете, какие пары точек (x_1, y_1) и (x_2, y_2) выбрать?

В качестве первого прохода я бы переборщил его:

(1) Итерации по всем комбинациям точек (n * (n-1) / 2 на границу, поэтому не так много), найдите x* или y* соответственно. Это дает вам список (x_1, y_1), (x_2, y_2), (x*, y*) потенциальных решений.

(2) Для каждой пары кандидатов (x*, y*) я бы нашел 2 ближайших соседа в вашем исходном наборе точек данных (эффективно через scipy.spatial.KDTree ). Если эти точки не являются (x_1, y_1) и (x_2, y_2) , отбросьте решение кандидата (x*, y*) .

Поиск ближайших соседей в KD-дереве – O (n log n) (IIRC), поэтому вы все равно O (n ^ 2) для всей процедуры.