algorithm - Haskell中的Bentley-Ottmann算法?



computational-geometry (1)

如果片段僅在交點處改變,並且僅在給定點處相交的片段的順序。 這可以通過刪除交叉段並再次插入來實現。

排序函數是由y坐標,當y是相等時,由斜率。 相交的部分將按照正確的順序插入。 隨著掃描的進行,掃描線段的交點的實際y坐標將改變。 不要緊,因為順序將保持不變(直到我們交換,即刪除並再次插入,相交段)。 實際的y坐標無需存儲。 對於掃描線的任何給定位置,應該動態計算,因為我們插入或移除段。

所討論的數據結構不應該被稱為Set ,它是一個Map ,更確切地說,是一個Ordered Map。 找到一個元素的鄰居的操作在這裡是必不可少的。

所以我一直在Haskell中編寫一個計算幾何庫,因為我在Hackage上找不到一個,我認為這樣做會很有趣。 然而,我已經停留了將近一周的時間,但是我似乎無法進入一個很好的“類似於haskell”的表單。 該算法是用於在一組線段中找到交點的Bentley-Ottmann算法。 如果你熟悉算法,你可以跳到最後一段為我的求助:)

我選擇實現這個功能的方式是把一個線段列表作為一個函數,並返回一個點列表,以及在那個點上相交的線段。 這讓我們可以處理多個線段在相同點相交的情況。

bentleyOttmann :: [Segment] -> [(Point, [Segment])]

該算法是一個掃描線算法。 我們想像一條線掃過飛機,在不同的地方做算法工作。 Bentley-Ottmann算法中的事件點是:

  • 線段的起始端點。
  • 線段的結束端點。
  • 一堆細分的交點。

請注意,事件點可以以多種方式與多個線段關聯。 為了跟踪哪些段對應於哪個端點,我使用容器包中的映射。 這張地圖的關鍵是點,這些值是分段的列表,標記是從那一點開始,在那一點結束還是在那一點相交。

掃描線決定點的順序。 想像一下,一條垂直線掃過飛機,在事件點停下來做工。 事件點先按x值排序,小點先處理。 一般來說,這是我們所需要的。 在退化情況下,事件點可能具有相同的x坐標。 我們還通過它們的y坐標來排序,如果存在x坐標系,那麼首先處理具有較小y坐標的事件點。

所以我使用的結構自然是一個優先隊列。 我使用的是來自Hackage的堆包。

我們在每個活動點上所做的工作是什麼? 那麼,首先我們檢查哪些片段與事件點相關聯。 如果有多個,那就是一個交點。 我們可以將它添加到我們迄今為止發現的十字路口列表中。

棘手的部分來了。 當我們掃過飛機時,我們會跟踪一組相對於掃掠線相交點的線段 。 當我們處理事件點時,我們首先刪除在該事件點結束的所有段。 然後,在該點相交的所有分段按順序顛倒 。 最後,我們將從該事件點開始的段添加到有序集。 請注意,由於這些分段都在事件點相交,所以必須相對於稍前擾動的掃掠線進行排序。

在每個事件點,我們必須添加任何新事件點,新發生的交點。 因為我們跟踪與掃掠線相交的線段的相對順序,我們做兩件事之一:

  • 如果我們交換了兩個分段或添加了一個新的分段,我們找到最下面的(相對於掃掠線)修改的分段,最上面的修改分段,並測試它們與它們的直接未修改的鄰居的交集。

  • 如果我們沒有交換或添加新的細分市場,那麼我們至少會刪除一個細分市場,從而使其前鄰居現在相鄰。 我們測試這些新鄰居的交集。

這是Bentley-Ottmann算法的關鍵,當我們橫掃飛機時,我們只用鄰居來測試新的候選片段。 這意味著當交叉口相對較少時,我們擊敗了天真的O(n ^ 2)算法。

我的問題(最後,我很抱歉,這是如此冗長)是這樣的:我不知道如何實現這種排序邏輯。 我無法使用Data.Set,因為在我們掃描時排序發生了變化。 我試圖實現我自己的數據結構來跟踪信息,但它是蹩腳的,越野車,可能是低效的,也是醜陋的! 我討厭醜陋的代碼。

我知道Haskell是關於漂亮的代碼。 我也相信,如果我不能以一種漂亮的方式實現一個算法,這意味著我並不真正了解它。 任何人都可以給我一個洞察力干淨地實現這個算法?

編輯:我現在有一個“工作”的實施。 我打算使用通用輸入法,以及在同一點上交叉的多個線段和垂直線段。 這似乎與我所做的微不足道的測試有關。 段在重疊時不起作用。 我不知道如何處理這些。 我將不勝感激關於如何適應他們的意見。 目前,我的掃描線結構跟踪它們在同一個節點,但它只會使用其中的一個在相交測試,並可以給出不一致的結果。

我使用Data.Set作為我的事件隊列,Data.Map進行查找,並且在他的書中使用了基於Okasaki的基於拉鍊的紅黑樹。 如果我的片段沒有足夠的上下文,我可以添加更多。

我將不勝感激關於重構實施的提示,所以它不那麼難看。 我不知道它有多正確,這讓我感到緊張。

代碼可以在這裡找到





computational-geometry