算法來計算許多地理點之間的距離

我有一個矩陣有大約1000個地理空間點（經度，緯度），我試圖找到在1KM範圍內的點。算法來計算許多地理點之間的距離

注：「分是動態的，試想一下，1000輛是移動的，所以我不得不重新計算每隔幾秒鐘，所有的距離」

我做了一些搜索和閱讀有關圖形算法，如（Floyd- Warshall）來解決這個問題，最後我得到了很多關鍵字，現在我有點迷路了。我正在考慮性能，由於搜索半徑很短，我不會考慮地球的曲率。

基本上，我似乎必須計算每個點到每個其他點之間的距離，然後對從矩陣中每個點開始的距離進行排序，並獲取其範圍內的點。所以如果我有1000個座標，我必須執行這個過程（1000^2-1000）次，我不相信這是最佳的解決方案。謝謝。

來源

2012-01-19 Alaa Qutaish

我認爲這個問題涉及到最接近的一對點問題，請檢查此進一步參考http ：//en.wikipedia.org/wiki/Closest_pair_of_points_problem –

您是否正在尋找距離特定緯度/經度1KM以內的積分，或者您是否正在尋找相互之間1KM以內的積分？ –

每個點都應該找到距離它1KM範圍內的所有點。 –

就你而言，你應該看看GeoHash，它允許你快速查詢給定距離內的座標。

僅供參考，MongoDB在內部使用geohash，表現出色。

來源

2012-01-19 07:15:36 qiao

是的，我寫了一些關於這個，但不斷分散注意力。您可以使用散列查找附近的事物，以便您不必直接比較所有1000. –

此外，您不應該排序任何內容。只需創建一個新的數據結構（最好帶有O（1）插入時間 - 如果需要排序的結果，可以使用O（log n）插入樹結構），併爲每個<1km的所有點保留一個列表點。放下任何> 1公里的東西。 –

有趣的建議，但如果使用geohash，這是什麼數據模型？ – Jasonw

您可以在這1000個座標的每一個周圍計算1km範圍的地理編碼，並檢查某些點是否在該範圍內。可能不是最佳的，但你可以節省一些排序。

來源

2012-01-19 06:51:09 koressak

如果你與1公里間距的網格上的產品型號名稱：

0 1 2 3 
___|____|____|____ 
0 | | | 
    c| b|a | d 
___|____|____|____ 
1 | | | 
    | |f | 
___|e___|____|____ 
2 | |g |

讓我們假設你的出發點是一個。如果您的網格的大小爲1km，則1km範圍內的點必須位於同一個單元格中或8個相鄰單元格中的一個（點b，d，e，f）。

每隔一個單元格可以忽略（c，g）。

雖然d與c的距離幾乎相同，但c可以提前下降，因爲有2個交叉屏障，而a和d位於它們邊界的相對區域，因此距離接近2公里從彼此。

對於提前丟棄元素，您可以排除，檢查座標的x或y部分就足夠了。由於a屬於（0,2），如果x爲0或更小，或> 3，則該點已超出範圍。

過濾只有少數候選人後，您可以使用窮舉搜索。

來源

2012-01-19 07:26:40

我正在考慮類似的事情，但是我們需要得到點的方向，例如，如果我知道（g）距離（f）南1公里並且（a）距北（北）1公里然後，當掃描（a）周圍的點時，所有離開（g）到南方的點將被排除。我們只需要在第一時間完成全部搜索以找出所有點與一個點的關係，然後可能性會減少，因爲點關係將更加相互連接。「算法從點的位置學習」我不知道還在想什麼！ –

如果你想查找每個點與每個點的矩陣，那麼你已經有了正確的公式（1000^2-1000）。這個計算沒有任何捷徑。但是，如果您知道從哪裏開始搜索，並且希望在1KM範圍內查找點，則可以使用網格或空間算法來加速查找。最有可能的是使用分而治之的算法，而最便宜的是geohash或z曲線。你也可以嘗試一個kd-tree。也許這更簡單。但是，如果你的觀點在奧克利德空間中，那麼這裏描述的是這種平面方法：http://en.wikipedia.org/wiki/Closest_pair_of_points_problem。

編輯：當我說1000^2-1000那麼我的意思是網格的大小，但它實際上是1000 ^（1000-1）/ 2對點，所以很少數學。

來源

2012-01-19 07:42:26 Bytemain

我在我工作的網頁上有類似的東西，我想。用戶單擊地圖上的某個位置並輸入一個半徑，並且函數返回給定半徑內數據庫內的所有位置。你的意思是你正在試圖找到半徑內某點的1公里內的點？或者你是否試圖找到距離彼此不到1公里的點？我認爲你應該做這樣的事情。

radius = given radius 
x1 = latitude of given point; 
y1 = longitude of given point; 
x2 = null; 
y2 = null; 
x = null; 
y = null; 
dist = null; 

for (i=0; i<locationArray.length; i++) { 
    x2 = locationArray[i].latitude; 
    y2 = locationArray[i].longitude; 
    x = x1 - x2; 
    y = y1 - y2; 
    dist = sqrt(x^2 + y^2); 
    if (dist <= radius) 
     these are your points 
}

如果你想計算都是在另一個點1公里的點，你可以添加一個外環給X1和Y1的信息，那麼這將使得內環測試之間的距離給定點和其他每個點都將給出矩陣中的每個點作爲輸入。計算不應該花太長時間，因爲它非常基礎。

來源

2012-01-22 19:21:20

是的，這是基本的蠻力搜索，如果我有1000分，那麼我有100萬次計算！在我的情況下積分是動態的，所以我必須每隔幾秒就執行一百萬次計算。這似乎並不是最佳解決方案。對？ –

嘗試使用R-Tree。 R-Tree支持查找距離給定點最近的所有點，這些點不會遠離給定的半徑。執行時間是最優的，我認爲它是O（number_of_points_in_the_result）。

來源

2013-02-07 10:36:36

我有同樣的問題，但在Web服務開發在我的情況，以避免我用一個簡單的除法&征服解決方案的計算時間問題：當時的想法是啓動距離的新點和其他人之間的計算在每一個新的數據插入，以便我的應用程序直接訪問那些已經計算，並把我的數據庫中的距離之間的距離

來源

2014-04-21 13:43:16 BiLL

算法來計算許多地理點之間的距離

回答

相關問題