algorithm - 线交点横向

Question

我有几个随机线段。我必须检查任何两条线段之间是否有任何交集。线路可能已连接或未连接。什么是解决这个问题的好算法？

Answer 1

假设您在这里谈论线段（否则，只需比较线的斜率：如果它们的斜率不相等，则它们相交）。

要确定一组 2 个或更多线段中是否存在 [单个] 交点，可以使用 Shamos-Hoey 算法。

要查找一组 2 个或更多线段中的所有交点，可以使用 Bentley-Ottmann 算法。

这两种算法以及其他基于“扫描线”的算法的实现在 Internet 上随处可见。