我有一個〜5000點的列表（指定爲經度/緯度對），我想從用戶指定的另一點中找到最近的5個點。最近點的算法
任何人都可以提出一個有效的算法來解決這個問題嗎？我在Ruby中實現了這個功能，所以如果有一個合適的庫，那麼這將是很好的知道，但我仍然對算法感興趣！
更新：有幾個人問過關於這個問題的更多具體細節。所以這裏是：
你可以使用曼哈頓距離（比例爲緯度）距離非常快速上限估計，這應該是足夠好拒絕考生的99.9％，如果他們不密切（編輯：從那以後你告訴我們它們很接近，在這種情況下，你的指標應該是距離平方，按照Lars H的評論）。 考慮相當於拒絕球形矩形邊界框外的任何東西（作爲圓形邊界框的近似）。 我不這樣做的Ruby所以這裏是算法僞代碼：
讓緯度，你參照點P（PA，PO）的經度和另一點X（XA，XO）。 預先計算ka，縱向距離的緯度比例因子：ka（= cos（pa in°））。 （嚴格地說，KA =常數是在P附近的線性近似）
然後距離估計是：D(X,P) = ka*|xa-pa| + |xo-po| = ka*da + do
其中| Z |意味着abs（z）。在最壞情況下，這會高估真實距離√2（當da == do時），因此我們允許如下：
做一個運行搜索並保持Dmin，第五小縮放曼哈頓距離 - 估計。 因此，您可以預先剔除D（X，P）>√2* Dmin（因爲它們必須至少遠離√（（ka * da）2 +do²）的所有點 - 應該消除99.9％點）。 用D（X，P）保留所有剩餘候選點的列表< =√2* Dmin。如果發現新的第五個最小的D，則更新Dmin。優先級隊列，否則（coord，D）列表是良好的數據結構。 請注意，我們從未計算歐幾里得距離，我們只使用浮點乘法和加法。
（這一類似，只是過濾掉一切，除了我們所感興趣的區域，因此無需計算準確的距離前期或建立數據結構四叉樹。）
如果您告訴我們預期的蔓延這將有助於在緯度，經度（度數，分鐘或什麼？）中，如果所有點都接近，則此估計器中的√2因子將過於保守，並將每個點標記爲候選者;基於查找表的距離估計器將是更可取的。）
Pseudocode：
initialize Dmin with the fifth-smallest D from the first five points in list
for point X in list:
if D(X,P) <= √2 * Dmin:
insert the tuple (X,D) in the priority-queue of candidates
if (Dmin>D): Dmin = D
# after first pass, reject candidates with D > √2 * Dmin (use the final value of Dmin)
# ...
# then a second pass on candidates to find lowest 5 exact distances
你可以通過加速與quad-tree或kd-tree劃分二維空間的搜索，然後，一旦你達到你一個比較剩下的距離，一個葉節點，直到找到最接近的匹配。
另請參見this blog post這是指this other blog post這兩個討論最近的鄰居搜索與Ruby中的kd-trees。
一般來說 - 一個好主意，但有5000點，創建數據結構需要更長的時間，而不是手動計算所有可能的距離。 – Gleno
取決於〜5000點的列表更改的頻率 –
既然你的名單很短，我會強烈推薦蠻力。只需比較所有5000到用戶指定的點。這將是O（N），你會得到報酬。
除此之外，四叉樹或Kd樹是空間細分的常用方法。但在你的情況下，你最終會在樹中進行線性插入，然後進行常數對數查找......這有點浪費，如果你可能更適合做線性數目的距離比較和完成它。
現在，如果您想查找N個最近的點，您正在計算計算出的距離並對第一個N進行排序，但這仍然是O（n log n）ish。
編輯：值得注意的是，如果您要重複使用多個查詢點的列表，那麼構建空間樹就變得有價值。
既然你有這麼幾點，我會建議做一個蠻力搜索，嘗試所有點對彼此的影響是O(n^2)操作，n = 5000，或大約2550萬次迭代的合適算法，並只存儲相關結果。這在C中會有100毫秒的執行時間，所以我們最多在Ruby中查看一兩秒鐘。
當用戶選擇一個點時，您可以使用您存儲的數據以恆定時間給出結果。
編輯我重新讀你的問題，似乎用戶提供了自己的最後一點。在這種情況下，每當用戶提供一個點時，通過您的設置執行O(n)線性搜索會更快。
而不是純粹的蠻力，對於5000個節點，我會計算每個節點的單獨x + y距離，而不是直線距離。
一旦您對該列表進行了排序，例如，第五個節點的x + y爲38，可以排除x或y距離大於38的任何節點。這樣，您可以排除很多節點而無需計算直線距離。然後蠻力計算剩餘節點的直線距離。
這些算法不容易解釋，因此我只會給你一些正確方向的提示。你應該尋找Voronoi Diagrams。使用Voronoi圖，您可以輕鬆地預先計算O（n^2 log n）時間內的圖形，並在O（log n）時間內搜索最近的點。
預計算是在晚上完成一個cron工作並且搜索是實時的。這符合你的規格。
現在，您可以保存5000個點中每個點的k個閉合對，然後從Voronoi圖的最近點開始搜索剩下的4個點。
但是要警告，這些算法不是很容易實現。
一個很好的參考是：
如果你需要這個多次重複，以不同的用戶輸入的位置，但不想實現四叉樹（或不能找到庫實現），那麼你可以使用相當直觀的局部敏感哈希（種類）方法：
然後當給定一個點（X，Y），
所有你正在做的是說，附近的一個點必須有一個類似x和類似的Y值...
如果是幾個點這是確定一個走一個。 – Andrey
無論您選擇哪種算法，您都可以通過比較平方距離而不是實際距離來節省一些時間。如果您不需要知道實際距離，則無需執行平方根操作。 –