直线交叉口的求解算法

Question

我想找出直线(无限)之间的所有交叉点。我试图改变Bentley-渥太华算法，它适用于线段的集合，但我不知道如何正确地表示无限直线。第一个想法是确定边界点，这将模拟每条线的开始和结束，但我认为这是不正确的解决方案(如何找到“无限”点？)下一个想法是使用方程来表示直线，但我不知道是否可以使用Bentley-奥特曼算法(如何排序行并将事件添加到计划中？)更重要的是，我可能需要使用除法来检测两条线的相交(同时求解一组方程)。我想避开它。

你能给我一些建议吗？

非常感谢

Answer 1

假设你是在二维欧几里得空间做这件事，你就是在过度膨胀你的问题。高中生会告诉你，线可以用一个等式来表示：

y = m*x + b

但它不能代表一条垂直线。您可以使用更通用的等式(参见MathWorld)：

a*x + b*y = c

在二维欧氏空间中，有两条线：

• 有一个共同点；或
• 没有共同点:它们是平行的；或
• 有无数的共同点:它们是同一条线。

前2例为方程求解。第三种情况是：

a1/a2 == b1/b2

(当然，您需要处理a2 = 0或b2 = 0的情况)

Answer 2

忘了本特利·奥特曼吧。这是聪明的处理线段，而你没有。

如果直线是无限的，那么每一对非平行线都会有一个交点。如果{L1，L2，.Ln}是所有行的集合，算法是：

for Li, i = 1, 2, ... n-1
  for Lj, j = i+1, ... n
    if Li parallel to Lj, output <i, j, PARALLEL> 
    else output <i, j, intersection(Li, Lj)>

如果这是有用的话，你可以单独检查一下细平行线。

存储任意行的最健壮的方法是(如前所述)，系数为三倍：

<A, B, C>

使得Ax + By +C= 0。规范A^2 + B^2 = 1是一种方便和良好的做法。现在A，B是与线正常的单位。用一些向量数学可以很容易地看出，两行g和h的交点P是由一个简单的交叉积给出的：

P = [x/w, y/w], where [x,y,w] = [Ag, Bg, Cg] X [Ah, Bh, Ch]

请注意，对于并行(包括重合)行，您将得到w=0，因此除法将如您所期望的那样失败。您可以使用非常小的绝对w值来检测上面的并行情况。这是将A，B标准化的原因之一，它使这个测试尺度独立。