如何在2D中找到射线之间最接近的交点：
x = x0 + t*cos(a), y = y0 + t*sin(a)
和m多段线：
{(x1,y1), (x2,y2), ..., (xn,yn)}
很快？
我开始在所有线段和每个线段之间循环；{(x1,y1),(x2,y2)}求解：
x1 + u*(x2-x1) = x0 + t*cos(a)
y1 + u*(y2-y1) = y0 + t*sin(a)
根据克雷默的规则，然后根据距离对十字路口进行排序，但这很慢：-(
BTW：多段线恰好在x中单调增加。
坐标系变换
我建议你首先将你的设置转换为更容易的坐标：
- 接受你的观点
p = (x, y) - 将其移动
(-x0, -y0)，使光线现在从中心开始 - 将其旋转
-a，使光线现在位于x轴上
到目前为止，上述操作每点花费了四次加法和四次乘法：
ca = cos(a) # computed only once
sa = sin(a) # likewise
x' = x - x0
y' = y - y0
x'' = x'*ca + y'*sa
y'' = y'*ca - x'*sa
检查交叉口
现在您知道，只有当多段线的y''值(即y1'' * y2'' < 0)的符号发生更改时，该多段线才会与射线相交。您甚至可以将x''值的计算推迟到该检查之后。此外，只有当x>0发生线段与x轴的相交时，线段才会与射线相交，只有当任一值大于零时，即x1'' > 0 or x2'' > 0，才会发生这种情况。如果两个x''都大于零，则知道存在交集。
下面的段落是可选的，如果你不理解，不要担心，后面会有一个备选方案。
如果一个x''是阳性，但另一个是阴性，那么你必须进一步检查。假设y''的符号由负变为正，即y1'' < 0 < y2''。从p1''到p2''的线将在x>0处与x轴相交，当且仅当由p1''、p2''和原点形成的三角形定向为逆时针。您可以通过检查行列式x1''*y2'' - x2''*y1''的符号来确定该三角形的方向，对于逆时针三角形，它将是正的。如果符号变化的方向不同，那么方向也必须不同。所以综合来看，你可以检查
(x1'' * y2'' - x2'' * y1'') * y2'' > 0
如果是这样的话，那么你就有了一个十字路口。请注意，到目前为止，还没有涉及成本高昂的分歧。
计算交叉点
因为你不仅想决定是否存在一个交叉点，而且还想找到一个特定的交叉点，所以你现在必须计算这个交叉点。让我们称之为p3。它必须满足方程
(x2'' - x3'')/(y2'' - y3'') = (x1'' - x3'')/(y1'' - y3'') and
y3'' = 0
导致
x3'' = (x1'' * y1'' - x2'' * y2'')/(y1'' - y2'')
您可以始终计算此x3''值并丢弃任何结果，而不是上一段中的三角形方向检查。代码更少，但划分更多。如果对性能有疑问，请进行基准测试
要找到最接近光线原点的点，可以使用最小x3''值来获得结果，然后可以将其转换回其原始位置：
x3 = x3''*ca + x0
y3 = x3''*sa + y0
你来了。
请注意，以上所有假设都是正数或负数。如果你有零，这取决于你实际想要计算的内容的确切解释，以及你想要如何处理这些边界情况。
为了避免检查与所有线段的交集，需要一些空间分区，如四叉树、BSP树。对于空间分区，需要检查光线与空间分区的交点。
在这种情况下，由于点是按x坐标排序的，因此可以用方框(min x, min y)-(max x, max y)对多段线的部分进行空间划分。根框是所有点的最小值-最大值，它被分割为多段线第一部分和第二部分的两个框。零件中的线段数量相同，或者一个框中多了一个线段。这种框分割是递归进行的，直到一个框中只有一个段。
要检查光线相交，请从根框开始，并检查它是否与光线相交，如果是，请选中相交的两个子框，然后先测试较近的子框，再测试较远的子框。
检查光线框相交是指检查光线是否与两个位置之间的轴对齐线相交。这是针对4个框边界完成的。