给定一个线段列表,找到交叉点的最简单方法是循环遍历线段列表,检查它们是否相交,如果相交,则记录交叉点。
但是这个方法的运行时是 O(n^2) 这是非常低效的。有没有其他算法可以加速这个过程?
O(n^2)
这个 Bentley-Ottmann Algorithm 可能是你想要的。
