Bentley-Ottmann算法的推廣

Question

Bentley-Ottmann算法用於確定一系列行的交點。但是這裏提到in Wiki，也有一些缺點：

該算法假定線 段不垂直，該行 線段的端點並不位於其他 線段，該口岸僅是通過形成 兩條線段，並且 沒有兩個事件點具有相同的 x座標。但是，這些通用的 位置假設不是 對於 線段交點的大多數應用都是合理的。

我的問題是有沒有這種算法的推廣可以克服/克服上述困難？

Answer 1

您鏈接到維基百科的文章有handling these special positions一個部分，這表明這些修改的基本算法：

• 按照慣例，一個點是垂直上方一個點的「左」;因此垂直線的「左」端點是其端點下端。
• 活動可能由兩個或更多線的交叉點組成。
• 當到達事件點時，其事件段必須是在掃描行中反轉（不只是交換，因爲可能有兩個以上）。
• 交叉處理後，可能有超過兩個要刪除的舊事件點或兩個以上要插入的新事件點。

Answer 2

這些是對由Skanthak here:提出的算法的修改。

算法進行如下：它首先爲輸入段的所有開始點和結束點創建事件。 它 然後按排序順序處理所有事件。
 對於每個事件，它提取 開始在該點 和FI NDS段的關聯列表大號，並刪除在搜索樹 相交當前事件點的所有段。 它 報告所有這些段作爲該點的交點。 然後 通過在當前事件之後稍微改變標誌來切換比較功能 的順序。 它 重新插入所有以前刪除的 沒有自己的終點在當前事件點 （因爲他們在這一點反正被刪除從結構 ） ，另外從l插入段段 （即從這一點開始）。 它 檢查當前事件點上方和下方的頂部和底部鄰居 新交叉點 並將它們添加爲事件點，如果它發現 任何。
     這樣，該算法對包括垂直分段和重疊分段， 以及在其端點上相交的分段在內的所有種類的簡併性 都是穩健的。

for all segments s do 
    Create events for the endpoints of s 
end for 
while event queue not empty do 
    Remove the smallest event point p from the queue 
    Let L be the set of segments that start at p 
    I ← all segments in the sweep line structure that contain p 
    remove I from sweep line structure 
    if |L| + |I| ≥ 2 then 
    Report intersections of L ∪ I 
    end if 
    C ← {s ∈ I | p is not endpoint of s} 
    Insert C in sweep line structure in reversed order 
    Check for new intersections among segments above and below p 
end while