根據經緯度尋找最近的城市的算法解決方案

請注意，還有其他類似的問題，但1）我不想依賴在線服務，2）我正在尋找一個乾淨的算法解決方案。根據經緯度尋找最近的城市的算法解決方案

我有一個城市及其緯度/經度的數據庫。我正在尋找一種方式，給定任意緯度/經度，找到最近的城市。

解決方案，我能想到的，到目前爲止：

明顯的蠻力解決方案，當然，計算使用great-circle distance公式所有可能的距離。這也需要很長時間，並且是O（n）。
對KD-Tree算法的修改可能會有效，但我對如何修改此算法以非笛卡爾座標工作方式感到茫然，就像lat/lon的情況一樣。如果有幫助，我們可以假設Mercator projection。
使用諸如PostgreSQL之類的地理數據庫。這段時間對我來說不起作用。

任何見解？

來源

2011-01-25 Stride

約2：從範圍[-90..90, -180, 180]開始。

唯一的細微差別是，當您將整個範圍分成四個較小的矩形並計算從當前點到其中每個點的距離時，您需要考慮「溢出」的可能性。（那點(0, -179)和(0, 179)比它們的經度似乎更接近）

我還假設你沒有接近南/北極的城市。

來源

2011-01-25 17:16:38

我想你不能節省計算城市之間的距離矩陣，只需使用Haversine formula公式即可。計算矩陣只能進行一次，並且您可以在每次需要時使用它，而無需進行任何複雜的投射。

如果您無法訪問PostgreSQL，例如，您也可以使用MySQL計算距離。詳細信息請參見this article on Google Code。該部分，處理你的問題可以歸納爲以下SQL查詢：

SELECT id, (3959 * acos(cos(radians(37)) * cos(radians(lat)) * cos(radians(lng) - radians(-122)) + sin(radians(37)) * sin(radians(lat)))) AS distance FROM cities ORDER BY distance LIMIT 1;

來源

2011-01-25 17:23:36 daroczig

我有這個確切的問題並解決它直截了當地使用R-樹，即治療經/緯度，好像他們是笛卡爾座標。

這項工作相當不錯，因爲沿着國際日期線和兩極的城市明顯缺乏城市，我的申請有時可以容忍恰恰是最近的城市。

我仍然不喜歡這種不精確和asked on SO。有人提出了一個解決方案，我認爲可能的工作，雖然我還沒有找到實現它的時候：

應該有變換座標，使得經脈之間的不同距離進行補償的方式 - 這種葉子180°子午線處的不連續處和極點處理。
使用兩個不同座標系的索引：一個是規則的，另一個是旋轉的，使得它的180°子午線與主座標系中的子午線垂直相反。這樣，一個座標系中的不連續點在另一個座標系中是非常規的點。

來源

2011-01-25 17:29:31

而不是使用經緯度的功能，怎麼樣使用緯度，經度和距離0,0？你可以使用KD樹嗎？當然，計算每個城市距離原點的距離需要一定的時間，但您只需要做一次即可。

來源

2011-01-25 17:42:17 Davidann

Lat-Lon問題是在極點和日期線附近，359.9比0.1更接近0.1！你還必須處理任何城市的大圓圈路線。 – 2011-01-25 18:11:55

您可以將其視爲3D問題。將（lat，lon）座標轉換爲（x，y，z）座標。這隻需要爲您的數據庫完成一次。

對於每個測試點，轉換爲（x，y，z）並計算每個城市的距離（爲了速度和簡單性）的平方和。選擇最接近的一個。我相信三維空間中最接近的城市也將是距離大圓距離最近的城市。

如果您需要大圓距離，您可以爲最近的城市計算它。

有了（x，y，z） - 空間，可能會有一個空間分區結構，您可以使用它來限制您實際必須檢查哪些城市。我認爲沒有一個能夠直接在（lat，lon）空間中提供幫助。但是O（N）確實不是那麼糟糕。此外，問題向量化很好。

來源

2011-01-25 18:06:06

是的，如果你想象它是一個以地球表面上一個點爲中心的擴張球體，你可以看到它從這個點上找出了一個擴大的半徑。唯一的擔心是地球不是球形的，而是橢圓形的。 – 2011-01-25 18:20:47

我想使它成爲平衡節點和地圖平衡二叉樹形式的龐大數據結構。

假設根/頭始於倫敦（在世界的水平慣用地圖，格林尼治標準時選爲中心）：右邊：右半邊世界地圖中心城市。左：左半邊世界地圖中心城市。

現在以相同的方式傳播包括所有城市。 y，y將成爲數據的一部分。在遍歷每個節點時，我們可以比較我們的CityX和我們的城市Y座標。

我想，這將是一種簡單的方法，可以找到最接近的左邊，沿着樹向下走向左右節點。我沒有實施這個，但似乎很好的解決方案。

    London

/ \

  New York  Singapore 
     /  \ / \ 
     Florida  Cuba Mumbai Melborne

等等......基於距離

它而不是根據經緯度的差異。讓我們看看是否有用。

來源

2012-07-29 05:20:10 mrtipale

根據經緯度尋找最近的城市的算法解決方案

回答

相關問題