scipy.spatial.Voronoi: 如何知道光线在何处穿过给定线？

Question

大家好，

我有以下代码段：

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()

生成如下 Voronoi 图：

我的目标是找到 'rays'（绘图之外的线，虚线或实线）与给定线（例如 x = 500）相交的位置。我该怎么做呢？

我已经尝试在 Voronoi 对象中使用 ridge_vertices 列表，但是，这些 'rays' 仅与列表中的一个顶点相关联，所以我无法弄清楚线方程.

编辑：

我的最终目标是，给定平面的边界，为给定的边缘单元找到与这些边界相交的点。例如，给定左上角的边缘单元格以及边界 y = -50 和 x = 525，我会找到标有红色 X 的点。

因此，如果您对此有任何见解，我们将不胜感激。

谢谢。

Answer 1

角落很简单，因为您知道 x 和 y 坐标。
Voronoi 图中的边与被该边分隔的两个单元格的中心等距，这自然包括 "ray"（在您的术语中）的端点。设两个中心为点(x1, y_1)和(x_2, y_2)，射线与边界的交点为(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)。

scipy.spatial.Voronoi: 如何知道光线在何处穿过给定线？

scipy.spatial.Voronoi: How to know where a ray crosses a given line?

python

voronoi

scipy