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

Question

我遇到問題。我有一些數據段（他們的協調員），需要確定他們中的哪些相交。我知道如何確定2段是否相交，這有點顯而易見，但是如何處理段數組和時間。我所知道的是，有我們可以使用AVL樹，但我不知道如何。任何建議如何做到這一點？提前致謝。

Answer 1

找到任意一組分段中的所有交叉點是經典問題所解決的典型問題，方法是通過經典的sweep line方法解決。網絡上有大量關於如何使用掃描線來解決分段交叉問題的信息。

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