如何查找与多边形最短时间相交的射线？

Question

令P是一个简单的，但不一定是凸的，多边形和q任意 点P.

设计一个有效的算法找到的线段从q个始发相交P的边缘的最小数量不一定

Answer 1

如果q是您在2D空间中的点，我们可以写q(x,y)。我们知道多面体具有边（E），顶点（V）和面（F），这些项都与欧拉定理中的公式V - E + F = 2有关，但问题变得更容易，因为它是用于多边形。

所以平原是找到一个边，并将点q(x,y)的方向向量计算到边的中心，这样做（如果多边形是凸的），我们确信这个线段只会经过一个P.

计算将需要一点线性代数，但它并不难，例如边缘：

1 -查找从线到点的距离（这样我们就可以找到在这个问题中使用的最接近的边缘）：

2 -此外，一个好的想法是找到这条线最接近(x0,y0)点坐标为：

当直线的方程是ax + by + c = 0和(x0,y0)是一个任意的点不一定在P.

所以，现在我们可以找到点的线k(x,y) t最接近初始点q(x0,y0)，做的是|q-k| = d。其中d是我们刚刚计算的距离。之后，你已经拥有你需要找到一个线段从q个始发相交P.

有些地方的边缘，你可以研究和发现更多的有关此主题的最小数目的一切：

Wiki

mathwords

Answer 2

想到要这样做在地图上，这样你就可以认为像北，南，东，西，和轴承方向的。

如果你有一条射线从某个特定的方向从q出发到无穷大，它是否与点A和B之间的一条直线相交只取决于射线的方位，以及从q到A和B的方位：if射线的方位在由q方向到A的方位和q方向到B的方位所跨越的范围内，将这个方向作为线的方向，那么射线将与该线相交。

所以你可以减少这个问题到一个更简单的问题。想象一下，所有的点都围绕着q围成一个圆，这些线是这个圆的弧。现在您需要在该圆上找到一个与最小弧数重叠的点。如果将每个0度的弧线分成0度的两个弧线，你就可以使生活变得更容易。从320度到40度的弧线成320度到360 = 0度之间的弧线，以及从0度到40度的弧线。

这是一个很好的候选点，它只是圆圈中每个点的顺时针方向的点。现在命令每个弧线从低角度到高角度，以低角度对弧线进行排序，然后按顺序对其进行排序，当看到弧线的起点时递增计数器，并在看到弧线时递减计数器（你不需要担心绕0 = 360度的圆弧，因为你刚刚确定没有）。你想找到的点是与计数器的最小值相关联的点。

Answer 3

以q作为坐标原点，计算顶点的极坐标参数。这是以线性时间完成的。

然后每条边跨越一个角度间隔。要处理环绕，可以拆分跨越360°边界的间隔。

您在1D间隔重叠的情况下解决了问题。这很容易在O(N Log(N))时间内解决。