尋找到指定點的最近點

我已經遍尋此地，但我似乎無法找到最佳方法。我有大約22000經緯度點，我想找到最接近iPhone的當前位置。我看到有人問起四叉樹，Dijkstra算法和空間數據庫。哪款iPhone最適合？空間數據庫看起來最簡單，但我不確定。尋找到指定點的最近點

編輯：實際上有超過20000點。你認爲迭代所有這些是實現它的方法嗎？但是，謝謝你的意見。

謝謝。

來源

2009-05-27 edrai

不成熟的優化是萬惡之源。特別是，我不認爲你可以找到小於O（n）的最小值（你必須檢查每個元素至少一次以檢查它是否最接近），所以我認爲你可以優化的唯一東西是距離計算（仍然應該相當快）。 – las3rjock 2009-05-29 04:00:56

看看這個答案http://stackoverflow.com/a/12997900/779408 – breceivemail 2012-10-22 12:16:33

實際上，最好使用Haversine（大圓圈）計算緯度/長點，否則越來越大的距離將是錯誤的，尤其是如果您使用簡單的三角如Jherico's answer。

快速搜索提供了這段JavaScript例如：

var R = 6371; // km Radius of earth 
var dLat = (lat2-lat1).toRad(); 
var dLon = (lon2-lon1).toRad(); 
var a = Math.sin(dLat/2) * Math.sin(dLat/2) + 
     Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * 
     Math.sin(dLon/2) * Math.sin(dLon/2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

在數據結構方面，Geohash值得一看。

來源

2009-05-27 01:51:23 Chaos

很高興知道。然而，最初的問題不是關於距離的計算，而是關於要使用的數據結構。除非應用程序需要實時重新計算，否則我同意Jherico：簡單的線性搜索就足夠了。 – 2009-05-27 02:02:39

如你在iPhone上，你可以使用CoreLoaction執行地理距離 - 使用CLLocation的– getDistanceFrom:

我會非常想使用，雖然所有2K點NAD強力線性搜索，如果不是快足夠的話，切換到GeoHash之類的東西來存儲元數據，以針對您的要點進行搜索。

來源

2009-05-27 09:42:26

如果你需要比O（N）更好，你只能得到，如果你第一次支付N lg N建立某種空間哈希（四叉樹，八叉樹，哈希網格或類似的）。然後每個測試將大約爲O（lg N），如果存在很多一致性（通常存在），通常可以通過緩存您檢查的最後一個位置來更好地進行測試。

我可能會在歐拉（地心，XYZ）空間中建立一個八叉樹，因爲這可以讓我獲得「真實」距離，而不是「扭曲」緯度/經度距離。然而，在實踐中，緯度/經度空間中的四叉樹可能工作得很好。一旦你點擊了，你可以保留那棵樹節點（假設樹不是在運行時重新構建的），下一個查詢從樹節點開始走，只需要擔心可能更近的節點前一點離上一個答案更遠。

來源

2009-05-29 04:09:47

爲什麼不把地球鋪成地區？（認爲是hexes。）然後，無論是在列表中添加點還是在一個大的預處理循環中爲每個點添加點時，都要存儲它所在的區域。

然後，當在十六進制X中搜索點A附近的點時，只需要檢查十六進制X中的點和最多3個相鄰的六邊形。

如果這仍然太多檢查點，添加子區域。

來源

2009-05-29 07:01:22

-3

我覺得這個算法的工作：

創建緯度排序數組創建數組排序由經度

要找到最接近的，首先由找到緯度最接近做的二進制搜索緯度陣列。對於經度數組，是否相同。現在你有2點，其中一個最靠近緯度，另一個最靠近經度。通過畢達哥拉斯定理計算到每個點的距離。最近的勝點。

羅傑

來源

2009-09-19 21:47:57

，你必須考慮到使用的Dijkstra你必須知道你的圖形節點的位置，這是不是你正在試圖解決的問題;你不是在圖中，但是你想知道的最近點到你

如此簡單，因爲已經混亂告訴你，你必須計算beetween您的位置所有的距離和所有的20.000點，然後對它們進行排序

來源

2015-02-19 09:30:17 Noomak

尋找到指定點的最近點

回答

相關問題