Lat，長座標的比較

Question

我有一個超過15000個經緯度座標的列表。給定任何X，Y座標，在列表中找到最接近的座標的最快方法是什麼？

Answer 1

您將要使用一種稱爲Voronoi diagram的幾何結構。這將飛機劃分爲多個區域，每個點都有一個區域，其中包含距離每個給定點最近的所有點。

用於創建Voronoi圖和安排數據結構查找的精確算法的代碼太大，無法放入這個小編輯框中。 :)

@Linor：這基本上是你在創建Voronoi圖後所要做的。但不是製作一個矩形網格，你可以選擇與Voronoi圖線很接近的分界線（這樣你就可以獲得更少的與分界線交叉的區域）。如果按照每個子圖的最佳分界線遞歸地將Voronoi圖劃分爲兩半，則可以對每個要查找的點進行樹搜索。這需要一些前期工作，但以後可以節省時間。每次查找將按照日誌N的順序進行，其中N是點數。 16個比較比15,000好很多！

Answer 2

即使您創建了voronoi圖，這仍然意味着您需要將您的x，y座標與全部15,000個創建區域進行比較。爲了簡化起見，我首先想到的是在可能的值上創建某種網格，以便您可以輕鬆地將x/y座標放置到網格中的一個框中，如果相同對於區域列表，您應該快速縮小可能的候選對象（因爲網格會更加直角，可能會有多個網格位置）。

Answer 3

您所描述的一般概念是nearest-neighbour search，並且有一整套技術可以處理這些類型的查詢，無論是精確還是近似。其基本思想是使用空間分區技術來減少從每個查詢的O（n）到每個查詢的O（log n）的複雜度。

KD樹和KD樹的變體似乎工作得很好，但四叉樹也可以工作。這些搜索的質量取決於您的15,000個數據點集是否是靜態的（您不會將大量數據點添加到參考集）。 Mount和Arya在Approximate Nearest Neighbour圖書館的工作既易於使用和理解，即使沒有數學基礎。它還爲您在查詢的類型和容差方面提供了一些靈活性。

Answer 4

Premature optimization is the root of all evil.

15K座標並不多。爲什麼不迭代15K座標，看看這是否真的是性能問題？你可以節省很多工作，也許它永遠不會太慢，甚至不會注意到。

Answer 5

您沒有指定最快速的意思。如果你想在不寫任何代碼的情況下快速得到答案，我會給gpsbabel radius filter一試。

Answer 6

這取決於你想要做多少次，以及有哪些資源可用 - 如果你正在進行一次測試，那麼O（log N）技術是很好的。如果你在服務器上做了一千次，構建一個位圖查找表會更快，直接給出結果或作爲第一階段的結果。 2GB的位圖可以將全世界的經緯度映射到0.011度像素（赤道1.2km）處的32位值，並且應該適合內存。如果你只做單一國家，或者可以排除極點，你可以有一個更小的地圖或更高的分辨率。對於15,000分，你可能會有一張更小的地圖 - 我首先將其大小作爲第一步來完成郵政編碼搜索，這需要更高的分辨率。根據需求，您可以使用映射值直接指向結果，或使用候選列表（這將允許縮小地圖，但需要更多的後續處理 - 您不再處於O（1）查找區域）。

Answer 7

我曾爲一個網站做過一次。即找到您的郵政編碼50英里範圍內的經銷商。我用great circle calculation找到北50英里，東50英里，南50英里，西50英里的座標。這給了我一個最小和最大經度，一個最大和最小長度。從那裏，然後我做了一個數據庫查詢：

select * 
    from dealers 
    where latitude >= minlat 
     and latitude <= maxlat 
     and longitude >= minlong 
     and longitude <= maxlong 

由於其中的一些結果仍然會超過50英里遠，然後我用了great circle formula再次座標的小名單。然後我打印出與目標距離的列表。

當然，如果你想搜索國際日期線或極點附近的點，比這不起作用。但它對北美地區的搜索很有用！

Answer 8

這些座標分佈在多大的區域？他們有什麼自由？你需要多少準確度？如果它們相互靠得很近，那麼你可能會忽略地球是圓的這一事實，把它當作笛卡爾平面而不是搞亂球形幾何和大圓距。當然，當你離赤道越遠，相對於緯度，赤字的度數就越小，因此某種比例因子可能是合適的。

從一個相當簡單的距離公式和一個蠻力搜索開始，看看需要多長時間，如果結果足夠準確，然後再花點心思。

Answer 9

謝謝大家的答案。

@Tom，@Chris Upchurch：座標相當接近彼此，他們在一個相對較小的面積約800平方公里。我想我可以假設表面是平坦的。我需要一遍又一遍地處理請求，並且響應速度應該足夠快，以獲得更多的Web體驗。

Answer 10

根據您的說明，我會使用幾何數據結構，如KD樹或R樹。 MySQL有一個這樣做的SPATIAL數據類型。其他語言/框架/數據庫有庫來支持這一點。基本上，這種數據結構將點嵌入矩形樹中，並使用半徑搜索樹。這應該足夠快，我相信比構建Voronoi圖更簡單。我想有一些閾值高於此值會更喜歡Voronoi圖的附加性能，這樣您就可以爲增加的複雜性做好準備。

Answer 11

一個網格非常簡單，速度非常快。它基本上只是一個二維數組列表。每個數組條目表示落入網格單元格內的點。很容易定格了：

 
for each point p 
    get cell that contains p 
    add point to that cell's list 

而且很容易看東西：

 
given a query point p 
    get cell that contains p 
    check points in that cell (and its 8 neighbors), against query point p 

阿萊霍

Answer 12

這可以通過多種方式來解決。我首先通過生成一個連接最近點的Delaunay網絡來解決這個問題。這可以通過開源GIS應用GRASS中的v.delaunay命令完成。您可以使用GRASS中的許多network analysis modules之一來完成GRASS中的問題。或者，您可以使用空間空間RDBMS PostGIS來執行距離查詢。PostGIS空間查詢比MySQL中的更強大，因爲它們不受BBOX操作的限制。例如：

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10; 

由於您使用的經度和緯度，你可能想使用Spheroid-Distance functions。通過空間索引，PostGIS可以很好地適應大型數據集。

Answer 13

只是爲了追溯者，你的意思是距離或（駕駛）時間接近嗎？在城市地區，我很樂意在高速公路上行駛5英里（5分鐘），而不是在另一個方向行駛4英里（20分鐘停下並行駛）。

因此，如果它是您需要的「最接近」的度量標準，我會考慮使用旅行時間度量標準的GIS數據庫。