地理空間查找

Question

我正在開發一種算法和數據結構來處理大量二維點上的歐幾里德距離查找。

我試過在谷歌學者研究這個，但沒有發現任何東西（可能是因爲我不知道這個問題通常在文獻中被稱爲什麼）。

這是我認爲這兩種方法：

方法1： 創建一個水桶電網bidimentional。將點插入桶中，保留每個點桶的參考。 查找距離爲D的點P，得到它的桶B以及其網格平方的任一角具有的所有桶（到B的距離）< D. 最後，枚舉所有這些桶中的點並計算距離至P.

方法2： 創建兩個列表，每個列表的所有點都由座標（x，y）之一排序。在距離爲D的點P上查找，執行二進制搜索以在每個列表中找到兩個點，以便找到矩形區域，其點的切比雪夫距離爲P < D. 最後，計算所有這些點的歐氏距離P

我猜測最先進的算法將大大優於這個，但？在這個任何想法表示讚賞

Answer 1

一些技巧可以幫助你：

• 看看KDTree，這是一個k維樹（在你的情況2D），這是看的最佳途徑之一爲最近鄰居。
• 也許你可以從專門爲處理地理空間數據而開發的Spatial Database中受益;
• 你可以使用上述任何一種與你想要的距離功能。根據您的應用，您需要地圖距離，大圓距，恆定斜距，恆定軸承距離等。您的距離函數應由您知道。我使用大圓圈（haversine）來處理google-maps-like地圖和軌道。

如果你想要一個Python實現，有scipy.spatial（docs）。從這個模塊，功能query_ball_point((px, py), radius)似乎是你在找什麼。

希望這會有所幫助！