是否有一种有效的算法可以找到一组无限直线的所有交点？

Question

有一些高效的算法（与 O(n²) 成对测试相比）可以找到一组线段中的所有交点，例如 Bentley-Ottmann 算法。但是，我想找到一组无限直线中的所有交点。当感兴趣的区域是像矩形这样的有限区域时，可以在剪裁线之后应用线段相交算法。但是

• 是否有比剪裁线和应用线段相交算法更简单或更有效的方法？
• 对于一组直线的整个平面上的所有交点，是否有有效的算法？

Answer 1

在一般情况下（不是所有的线都是平行的）有 O(n^2) 个交点，所以简单的循环和交点计算是最好的方法
（不计算就得不到n*(n-1)/2分）

对于存在大量平行线的情况，首先按方向对线进行分组，只检查不同组中线之间的交点

Answer 2

如果线处于一般位置，所有线对都相交并且穷举计算是最优的。