尋找數組中最接近的座標？

我有兩個ArrayList中，雙數據類型， 1.latitudes 2.經度，每個已超過200個元素尋找數組中最接近的座標？

說我給一個隨機測試座標，說（1.33，103.4），格式爲[緯度，經度]

是否有任何算法很容易找到最近點，或我必須蠻力計算每個可能的點，找到斜邊，然後比較超過200個斜邊以返回最近點？謝謝

2013-09-23 RadZaeem

如果你計算所有的斜邊，就可以計算出距離，並實現所有在一個循環分鐘（距離）的邏輯。此外，所有點應該在地理位置上彼此接近，以便您可以將該區域視爲一個平面，否則您需要考慮地球曲率。 –

你對距離的定義是什麼？「hypothenuse」是一個來自平面幾何的術語，但是你對「經度」和「緯度」的使用似乎表明這些點在球體的表面上... – meriton

你看過R-樹（https：// en .wikipedia.org /維基/ R樹）？或一般的空間索引算法（https://en.wikipedia.org/wiki/Spatial_index#Spatial_index）？ –

如果您的數組排序，您可以使用二進制搜索來查找數組中的請求點的位置。找到索引後，您應該查看四個附近的點以找到最近的點。

1）假設你有兩個有序陣列經度明智的和緯度明智

2）你搜索第一位，並找到附近的兩個點

3）然後你搜索第二個，發現兩分

4）現在，你從兩個到四個點，有（結果可能相交）

5）這些點會圍繞目標點方

6）找到最近的點

2013-09-23 18:16:24 Mikhail

對一個軸的點陣進行排序。然後，找到最接近該軸所需點的陣列中的點，並計算距離（使用適合問題拓撲和比例的任何度量標準）。

然後，沿着陣列在兩個方向上搜索，直到到這些點的距離大於迄今爲止的最佳結果。最短的距離點就是答案。

這可能導致必須搜索整個陣列，並且是由問題的幾何形狀約束的Branch and bound的一種形式。如果點在您正在搜索的點周圍均勻分佈，則掃描不需要進行很多試驗。

替代空間索引（如四叉樹）會給出更好的結果，但是您的小數量的點會使準備索引的設置成本比簡單排序要大得多。您將需要跟蹤排序引起的位置更改，因爲您的其他數組不會按照相同的方式排序。如果您將數據更改爲單個點數組，則排序將同時對整個點重新排序。

2013-12-22 17:12:07 Pekka

不應該選擇最接近的緯度（或長度）值來搜索長軸（或緯度軸），事實上，您可以停留在一條拉（或長）線上，但沿着長軸（或長軸） LAT）值

worng approach

所以最好的方法是計算所有的距離，並對其進行排序

2015-02-19 09:22:55 Noomak

沿着一個軸選擇最近點的方法是搜索的起點。它至少可以最小化沿一個軸的距離。隨後的探測（兩個方向）將確定最近的點。距離度量的選擇取決於正在考慮的區域的曲率。 – Pekka

回答