\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2021年8月13日 星期五

[Multiple line segment intersection] Bentley–Ottmann 演算法

 基本上這個問題就是給你一些線段(格式通常為兩個端點),你要找出這些線段的交點。直觀的做法兩兩進行計算會花上$\ord{n^2}$的時間,但大多數的情況下交點不會很多。為了解決這個問題,修改自Shamos–Hoey演算法的Bentley–Ottmann演算法可以在$\ord{(n+k)\log n}$的時間內找出所有交點,其中$k$是交點數量。

這裡附上實作時需要用到的基本資料結構:

演算法使用掃描線進行。掃描線是一條垂直線從左邊掃到右邊(有些實作是水平線從上面掃到下面),並且在遇到事件點的時候進行相關處理。

線段的兩端點以及交點都作為事件點被紀錄在最終結果中。對於每個事件點$P$,我們會計算三個集合:

  • U集合:所有以$P$為起始點的線段集合
  • C集合:所有包含$P$的線段集合
  • L集合:所有以$P$為結束點的線段集合
當然要先保證每條線段的起始點移動會在結束點的左方,只要得到線段後稍微判斷一下就可以做到了。每個事件點找出這三個集合後就可以很容易的判斷相交資訊,但要注意的是會有以下的退化情形:
  • 線段退化成點:這種情況該點的U和L都會包含該線段。
  • 兩線段重合:只有重合處的兩端點會被紀錄為事件點,可以根據UCL判斷出是否線段重合
  • 垂直線段:排序點和線段時如果x一樣就按照y來比較
最後是掃描線的資料結構,需要一棵平衡的BST根據當前掃描線和各個線段切點的y值進行排序,但這件事是可以用STL做到的!我們把當前事件點傳進比較函數裡面進行計算,因為在任何一個時刻BST中的資料都是根據當前的比較函數由小排到大的,應該不算undefined behavior。另外該演算法的浮點數誤差很大,建議使用時套上處理誤差的模板或是直接用分數計算:

最後是測試的部分,以下圖做為測試範例:

將該圖轉換成我們接受的input如下:
10
-2 7 2 0
-2 7 -2 0
-2 6 2 5
-2 6 2 2
-2 4 2 7
-2 4 2 2
-2 4 4 1
-2 0 2 2
0 1 0 1
0 3 4 1

最後附上測試程式碼,需要的話可以自己執行看看:


沒有留言:

張貼留言