瞭解賓利奧特曼算法

Question

這是代碼：

Initialize event queue EQ = all segment endpoints; 
    Sort EQ by increasing x and y; 
    Initialize sweep line SL to be empty; 
    Initialize output intersection list IL to be empty; 

    While (EQ is nonempty) { 
     Let E = the next event from EQ; 
     If (E is a left endpoint) { 
      Let segE = E's segment; 
      Add segE to SL; 
      Let segA = the segment Above segE in SL; 
      Let segB = the segment Below segE in SL; 
      If (I = Intersect(segE with segA) exists) 
       Insert I into EQ; 
      If (I = Intersect(segE with segB) exists) 
       Insert I into EQ; 
     } 
     Else If (E is a right endpoint) { 
      Let segE = E's segment; 
      Let segA = the segment Above segE in SL; 
      Let segB = the segment Below segE in SL; 
      Delete segE from SL; 
      If (I = Intersect(segA with segB) exists) 
       If (I is not in EQ already) 
        Insert I into EQ; 
     } 
     Else { // E is an intersection event 
      Add E’s intersect point to the output list IL; 
      Let segE1 above segE2 be E's intersecting segments in SL; 
      Swap their positions so that segE2 is now above segE1; 
      Let segA = the segment above segE2 in SL; 
      Let segB = the segment below segE1 in SL; 
      If (I = Intersect(segE2 with segA) exists) 
       If (I is not in EQ already) 
        Insert I into EQ; 
      If (I = Intersect(segE1 with segB) exists) 
       If (I is not in EQ already) 
        Insert I into EQ; 
     } 
     remove E from EQ; 
    } 
    return IL; 
} 

我在左端點的情況下 如果a或b犯規存在哪些例如幾個問題嗎？如果存在並且不是，我們是否應該檢查第二個，如果沒有或沒有？

在第一次迭代中，SL大部分是空的，因此在開始時大部分點被刪除而未被使用。那是什麼意思？

Answer 1

如果a和b不存在，那麼當然與它們沒有交集是可能的。如果只有一個存在，那麼只有那個可以檢查相交。

我不確定你的意思是關於「未經使用而被移除」的點。事件隊列中的所有事件都很重要，要麼是因爲它們即將到來的交叉路口，要麼是通過保持掃描線保持最新狀態來設置潛在即將到來的交叉路口。

最後是Bentley-Ottmann，而不是Bentley-Ottoman。