0

我想找到直线（无限）之间的所有交点。我正在尝试更改适用于线段集的 Bentley-Ottmann 算法，但我不知道如何正确表示无限直线。第一个想法是确定可以模拟每条线的开始和结束的边界点，但我认为这是不正确的解决方案（如何找到“无限”点？）。下一个想法是使用方程来表示直线，但我不知道我是否可以使用 Bentley-Ottmann 算法（如何对线进行排序以及将事件添加到调度中？）。更重要的是，我可能需要使用除法来检测两条线的交点（同时求解一组方程）。我想避免它。

你能给我一些建议吗？

非常感谢

4

2 回答 2

0

假设您在二维欧几里得空间中执行此操作，则您的问题过度膨胀了。高中生会告诉你，线条可以用一个等式表示：

y = m*x + b

但它不能代表一条垂直线。您可以使用更通用的方程式（请参阅MathWorld）：

a*x + b*y = c

在二维欧几里得空间中，有两条线：

  • 有一个共同点；或者
  • 没有共同点：它们彼此平行；或者
  • 有无数个共同点：它们是同一条线。

前两种情况是方程求解。第三种情况为真，如果：

a1/a2 == b1/b2

（当然你需要处理a2 = 0or的情况b2 = 0）

于 2015-01-02T12:55:16.907 回答
0

忘记宾利奥特曼吧。它的聪明之处在于处理你没有的线段。

如果线是无限的，那么每一对不平行的线将只有一个交点。因此，如果 {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] 的原因之一。它使这个测试与规模无关。

于 2015-01-04T17:26:14.833 回答