問題描述
給定N條線段，計算這些線段彼此之間的所有交點。
Bentley Ottmann Algorithm
算法的前提假設：
a) 不存在兩條線段的終點和交點有相同的x座標；
b) 不存在多於兩條的線段相交於一點;
c) 不存在兩條線段完全相互重疊；
關鍵的觀察結論：
a) 兩條相交的線段必然是相鄰近的；
b) 兩條線段相交後，會交換位置，在上面的線段在經過交點後，會到另一條線段的下面；
掃描線算法的Events
所有線段的終點和交點(由於交點是動態計算出來，所以採用優先級隊列記錄Events)。
掃描線算法的Active Set
所有與掃描線相交的線段，按照y座標排序.
偽代碼
PQ-Priority Queue
SL- Active Set
時間複雜度分析
假設有2N個端點和K個交點，那麼共有2N+K個Event，如果PQ和SL採用平衡二叉樹結構，那麼它們的插入、刪除、交換、尋找相鄰線段的操作可以在O(logN)時間內完成。PQ隊列的排序初始化時間複雜度為O(NlogN)。所以總的時間複雜度為O(NlogN+(2N+K)logN)=O(NlogN+KlogN)。
該算法的缺點是複雜度與交點個數有關，如果K=O(N^2)，那該算法的複雜度就會比直接遍歷計算還要慢。
分享到:
閱讀更多 半杯茶的小酒杯 的文章
