高效的算法在地圖

Question

我在從OpenStreetMap的處理地圖數據的Python程序工作發現對附近的，平行的街道，我需要能夠識別的街道（路）對那些彼此靠近和平行。現在，我使用的基本算法是相當低效：

1. 把所有的街道（街道對象）進入大名單
2. 使用嵌套循環for查找列表中的每一個可能對兩條街道;對於每一對，在兩條街道周圍繪製一個矩形，並計算每條街道所朝向的角度。
3. 如果該矩形重疊時，重疊區域是足夠大的，並且角是相似的，在對中的兩個街道被認爲是平行且相互靠近。

這對於小地圖很好，但對於大地圖，最大的問題顯然是會有大量的對要迭代，因爲可能會有成千上萬的城市街道。我希望能夠在大面積（如城市）上運行該程序，而不必將區域分割成更小的部分。

一個想法，我想的是通過經緯度排序街道的名單，而只有比較對街道是內說，50個位置遠離彼此的名單。它可能會更有效率，但它看起來還不夠優雅;有沒有更好的辦法？

每個街道由Node對象的，我可以很容易地檢索兩個節點對象和每個節點的緯度/經度位置。我還可以輕鬆地檢索街道所朝向的角度。

Answer 1

我認爲首先要做的是按角度對所有街道進行排序，從而使所有平行的街道彼此靠近。

然後，假設一開始，你可以識別的角度正是和你需要對具有完全相同相同的角度街道。 （由於浮點精度以及由於所需街道在數據中可能不完全平行的事實，這並非真實情況，但我們暫時忘了這一點。）

然後所有排序的街道都可以被分成相同方向的組。在每個這樣的組中，存在如下定義的自然順序。考慮另一條垂直於所有街道的方向相同的線。對於任何這樣的街道，考慮與該垂直線的交叉點，並通過該交叉點對所有這些街道進行分類（我假設所有街道都是無限長的）。

此排序可以在沒有任何交集很容易做到，你只需要通過這個距離計算各街道從產地（或任何其他固定點）到街道線的距離和排序街道。 （如果你有一條由標準直線方程Ax+By+C=0定義的街道，那麼這個距離原點的距離是C/sqrt(A*A+B*B)。）

現在你已經擁有了所有需要的平行靠得很近的街道，這個排序順序非常接近。如果所有的街道都是無限長的，那麼最接近的兩條街道總是會一個接一個。有限長度的街道之間可能會有額外的街道，但我認爲在任何實際的數據中都會有很少的街道。所以，你可以採取一些距離差異的門檻，並檢查其中的所有對。

現在讓我們記住角度沒有精確定義。我可以建議那麼下面的方法。爲街道維護一個二叉搜索樹（類似於C++的std::map），搜索鍵將是從原點到街道的距離。按順序沿街道排列，因爲它們按角度排序。在樹中，我們將保持角度相差小於某個閾值的所有街道。因此，在樹中的每條街道的每一次，其樹中的鄰居將具有不同於小於閾值的兩個角度，並且與起點的距離相差小於某個閾值。因此，對於每個街道，做到以下幾點：

• 這條街上添加到樹
• 對於這一切都在樹上，而是有自己的角度，從當前街道的角度也不同街道，清除這些從樹上的街道
• 現在處理添加的街道：查看樹中具有所需閾值內的搜索關鍵字（距離原點的距離）中的所有街道，並檢查一對（增加的街道，另一條街道）。

第一點是O(log N)，第二個是O(log N)每刪除街頭，如果你只是一味另一個指針指向一起到街上排序的角度陣列要刪除運行，第三個是O(log N)％的人認爲鄰居街道。

一個非常粗糙的僞代碼：

sort lines by angle 
r = 0 // the street to be deleted from the tree 
for l=0..n-1 
    tree.add(street[l]) 
    while street[r].angle<streel[l].angle-angle_threshold 
     tree.remove(street[r]) 
    other_street=tree.prev(street[l]) 
    while other_street.dist>street[l].dist-dist_threshold 
     process(street[l], other_street) 
     other_street = tree.prev(other_street) 
    other_street=tree.next(street[l]) 
    while other_street.dist<street[l].dist+dist_threshold 
     process(street[l], other_street) 
     other_street = tree.next(other_street) 

這裏tree.prev找到以前的街道樹，即具有最大距離的街道是小於給定街的距離，tree.next同樣發現了另一條街上。這兩項操作都可以在O(log N)中完成。

這不會「循環」數組，即不會考慮一對位於排序數組非常末端而另一個位於最開始處的街道對，但這很容易解決。

Answer 2

你的處理垃圾箱中段的想法並不差。您確實需要考慮通過箱體邊界的路段會發生什麼情況。

另一個想法是霍夫變換所有的路段。每個段所在的無限長線對應於2d Hough空間中的一個點：該線的極角是一個軸，並且該線的最近點的原點的距離是另一個軸的距離。從一條線上的兩點到霍夫點的轉換是簡單的代數。

現在，您可以使用最近點對算法來檢測幾乎共線的路段。令人高興的是，這可以在O（n log n）預期的時間內完成。例如。使用k-d樹。將所有點插入樹中。使用標準k-d樹算法來查找每個點的最近鄰居。排序對距離並以結果的前綴作爲成對的考慮對象，停止對的距離太遠而不符合「附近和平行」的標準。這些最近鄰居對有O（n）個。

剩下的就是過濾出線段對 - 雖然幾乎是線性的 - 不會重疊。這些部分位於同一無限線的不同部分或其附近，但它們並不感興趣。這只是一個更多的代數。

這裏提到的所有算法都有相當不錯的維基百科文章。如果他們不熟悉，請查看他們。