尋找其他用戶附近的用戶

我應該探索哪些算法來實現一項功能，該功能可以讓用戶找到位於他附近的其他用戶，所有用戶的緯度和經度都是事先知道的，並且是固定的[不動態]。此外，我相信應該有一個更好的方式來存儲這些數據，然後簡單地存儲用戶對數據庫中的lat，long的用戶ID。有效的方法來處理這個問題是什麼？尋找其他用戶附近的用戶

來源

2012-03-22 Bunny Rabbit

MySQL（及其他）現在支持spatial indexing.

如果你的數據庫可以做spatial queries你不需要實現算法自己的任何部分。

來源

2012-03-22 17:10:46 DigitalRoss

使用k-D樹作爲nearest neighbor search。

來源

2012-03-22 17:11:29 Jacob

您不需要最近的鄰居。這在計算上是昂貴的，並且只會在已經執行最佳點減少的情況下使用。 – FlavorScape 2012-03-22 17:25:12

有數據結構的空間搜索的兩大類是：

空間劃分樹（如k-D tree）
重疊邊框的樹木（如R-tree）

如果你想一個絕對完整的回答你的問題，看看哈南沙美的書，多維和公制數據結構的基礎

來源

2012-03-22 17:24:49 comingstorm

如果您只是發現接近點，您所需要的只是一個簡單的圓形邊界半徑，您可以調整或偏向中心對數座標。當然，您應該避免在每個查詢的整個數據集上執行此操作。一般來說，除了緯度/經度，你可以將地圖分解成象限，你知道你可以忽略蝙蝠。 - 只要確定您的興趣領域是否處於邊緣位置，還可以查詢相鄰象限。這是一個鏈接表，只提取該象限中的行。

一旦你減小了象限。使用最基本的幾何：

1）用一個簡單的邊界框消除大部分數據。

僞代碼：

DistanceLat = abs(P2lat - P1lat); 
DistanceLon = abs(P2lon - P1lat)

2）不要勾股定理，看是否點落在withing半徑。在簡化數據集內（a2 + b2 = c2）

Distance = Sqrt(DistanceLat * DistanceLat + DisanceLon * DistanceLon) 
if (Distance < radius) keep the data

來源

2012-03-22 17:36:12 FlavorScape

是的，這更類似於物理模擬中經常使用的OBB樹。最近的一點是更進一步。 – FlavorScape 2012-03-22 17:37:34

尋找其他用戶附近的用戶

回答

相關問題