20

给定一个线段列表,找到交点的最简单方法是遍历线段列表,检查它们是否相交并记录相交点。

但是这种方法的运行时间是O(n^2),效率很低。有没有其他算法可以加快这个过程?

4

1 回答 1

19

Bentley-Ottmann 算法可能是您正在寻找的。

于 2010-11-08T16:05:06.167 回答