确定是否存在相互交叉的部分

Question

我遇到问题。我有一些数据段（他们的协调员），需要确定他们中的哪些相交。我知道如何确定2段是否相交，这有点显而易见，但是如何处理段数组和时间。我所知道的是，有我们可以使用AVL树，但我不知道如何。任何建议如何做到这一点？提前致谢。

Answer 1

找到任意一组分段中的所有交叉点是经典问题所解决的典型问题，方法是通过经典的sweep line方法解决。网络上有大量关于如何使用扫描线来解决分段交叉问题的信息。

http://www.cs.tufts.edu/comp/163/notes05/seg_intersection_handout.pdf