如何快速找到距離給定的點最近的10個點?

時間 2021-06-01 09:20:01

1樓:史強

這裡類似共享單車,對地圖位置的查詢功能演算法。

實際上已經很成熟了。

最簡單的是基於geohash的一些資料篩選。

有興趣可以參考一下我的開源時間,迅速找到給定乙個點周邊半徑為r最近的點。

freeeyes/geohash

當然,如果想簡單一些。

你可以用redis,3.8.0以上版本已經支援直接的語法完成你需要的查詢。

具體可以參考這裡

Redis新特性GEOHASH - CSDN部落格

2樓:思念

如果索引都在記憶體中速度會很快,上週日我剛實現類似的演算法,測試也是在10萬個資料中,如果允許一定的誤差,則效率很高。測試結果具體如下:

初始化 100000 個GPS 共消耗 374 毫秒

100000個GPS 更新 2次共消耗 531 毫秒

V1 在 100000 個GPS中執行矩形區域查詢 100000 次,共消耗 249 毫秒

V1 查詢結果如下:7

38739 13643 57936 28262 76751 23789 6027

在 100000 個GPS中執行遍歷矩形區域查詢 1000 次,共消耗 1030 毫秒

驗證查詢結果如下:7

6027 13643 23789 28262 38739 57936 76751

SearchTopNearest 100000次耗時:1591 毫秒

索引查出的最近20/20個點

(6027,3.25) (74655,3.02) (99477,2.45) (49389,2.65) (73085,1.33)

(9280,2.64) (44542,1.84) (19489,2.46) (2877,1.32) (13643,4.93)

(57936,4.62) (28262,2.22) (76751,4.15) (23789,3.90) (63114,2.27)

(38335,2.91) (10662,5.13) (65542,2.69) (39407,1.80) (84651,1.99)

正確的最近20個點

(6027,3.25) (56131,3.24) (23616,3.18) (68131,3.10) (74655,3.02)

(49389,2.65) (9280,2.64) (65542,2.69) (38335,2.91) (28262,2.22)

(39407,1.80) (63114,2.27) (2877,1.32) (62408,2.26) (84651,1.99)

(99477,2.45) (73085,1.33) (44542,1.84) (19489,2.46) (72790,1.91)

以上測試結果,(6027,3.25)為(具體的點,與目標點的距離)。索引查出的點與正確的點集合有些誤差。

3樓:

上面有同學提到的geohash是正解。我說個更簡單的近似演算法。有個東西叫空間填充曲線,能把二維投影到一維,而且相近的點投影後還是相近。

所以,你可以投影後直接二分法,so easy。

4樓:蔣甬杭

將地圖切割,比如說和圍棋棋盤那樣的。

然後對於乙個特定經緯度的點A,先找和A在同乙個格仔裡的,如果最近點不夠多,再找臨近格仔……如果此人在撒哈拉或者南極或者火星之類的地方,直接說」附近無人「就好。總不能說成百上千公里開外也算」附近「……

高階點的,既然地點會時刻變動,那在每次收到使用者登入資訊時調整格仔大小。比如說,發現乙個格仔裡人太多,就把這個格仔切一刀變成兩個格仔。如果格仔裡人太少,就把格仔和相鄰格仔合併。

如果維護四叉樹麻煩,那就直接切整行整列,反正格仔數量相對使用者點數量來說開銷不大。每個格仔裡的點記得先分別按照經度和緯度排序,維護兩個有序列表,這樣拆分和合併都很快。

5樓:左慶

mysql什麼的我不懂,但是你的這個要求用ANN可以做http://www.

cs.stonybrook.edu/~algo

rith/implement/ANN/implement.shtml

6樓:方圓

輪子哥的回答基本符合,select top 10 id, distance = 懶得寫公式

from points

order by distance 這種方式主要是需要空間索引,oracle/sql server/pgsql都實現了空間索引,可以直接用這種方式。mysql的myisam表也支援空間索引,但是innodb不支援,因此比較麻煩。可以改成

select top 10 id, distance = 懶得寫公式

from points where distance < ...

order by distance 這種方式。

還有geohash其實不太適合做空間距離運算,因為geohash跟四叉樹沒區別,就是把空間分成小格,但是格仔的尺寸比較難於掌握,實現的好的四叉樹索引並不是均勻的四叉樹,而是根據點的稀疏密集程度劃分的,但是簡單的Geohash比較難達到這個效果,還有一般空間資料庫使用R tree。

如果只是10W條的話,求簡單你在記憶體裡維護乙份資料,然後硬排序也沒啥。

如何在知乎快速找到曾經關注或點贊的答案?

不二 首先如果是真的有價值,值得回頭品味的答案最好收藏起來,強烈建議用 evernote pocket 或者記事本等最習慣的方式進行本地 雲儲存。不要依賴知乎本身的收藏,和知乎搜尋一樣起不到其應有的作用。如果事先沒有做好儲存,還是要用搜尋。隨手點了側邊的乙個問題,選了章魚哥的乙個回答。如何在知乎上面...

如何快速找到正確的自我?

受盡苦難而不厭 哪有什麼自我,回頭看昨天的自己弄不好都會覺得怎麼會是那個樣子。我覺著吧,或許人生就是一場自我救贖,亦或是終此一生的執迷不悟。你這個找到正確的自我,可能就是所謂的修行的過程。歷代先賢求而不得,又何況這個物欲橫流心分無數的時代。能獲得救贖的人越來越少,執迷不悟的人越來越多。哪還能談快速。...

如何快速的找到自己的錯誤?

空白迷茫 自己的錯誤最快的都會是別人發現便向裡提出的,當然自己也可能是最快的發現者。不管是別人發現的還是自己發現的,發現那一刻才能找到。 Nio龍 想要快速找到自己的錯誤,先搞清楚何為正確。乙個人要找到自己的錯誤,首先要明確何為正確,如果沒有正確的標準,便無所謂正確錯誤。從心裡學上講,乙個人如何看待...