算法找到附近的朋友？

我有一個坐在服務器端管理用戶位置信息的蟒蛇程序，每個朋友都有一對（經度，緯度），給定一個（經度，緯度）點，我如何能夠在附近（如5KM內）找到朋友？算法找到附近的朋友？

我有10K在線的用戶...

謝謝。斌

2011-01-07 Bin Chen

新建答案：

我將存儲LAT和在單獨的列長。在其上放置索引。然後，當你想找到一個特定用戶的附近的朋友，只是像做

select field1, field1, ..., fieldn from users 
where 
    user_lat > this_lat - phi and user_lat < this_lat + phi 
    and 
    user_lon > this_lon - omega and user_lon < this_lon + omega

其中phi和omega是符合您的期望距離緯度和經度。這取決於你在全球的哪個地方，但有確定的方程式可供選擇。也有可能你的數據庫可以爲你做這些計算。

舊的答案。

我會看看quadtrees和kd-trees。我相信Kd-trees將是這裏的典型解決方案。

來源

2011-01-07 06:25:41 aaronasterling

http://www.movable-type.co.uk/scripts/latlong.html就效率而言，真正想到的唯一事情就是預先計算距離，因爲條目被放入數據庫中，而且每個位置都有另一個表格存儲一對位置以及距離這是在添加它時添加的，它會計算與系統中其他每個點的距離，但隨後在該表上查找可以快速解析某個距離內的位置。

Aaronasterling的答案似乎是我想要通過我自己的想法，但不知道存在:)所以這可能是一個更好的解決方案，但我相信你會在搜索時產生一些開銷，使用它算法（雖然可能很小，因爲通常遍歷一棵樹，只要它合理平衡通常是一個相當快的過程，需要我花一些時間來確切地理解樹是如何構成的，但這對我來說是一個新概念）。

來源

2011-01-07 06:33:43 shaunhusain

我想通過比較緯度和經度粗略估計。例如）如果緯度和經度的差異都小於0.0001，那麼我認爲這兩者是接近的。這有意義嗎？ – 2011-01-07 06:45:11

@Bin Chen。在我看到你的評論之前，我想到了同樣的想法，所以我認爲這至少是一個好主意。如果列索引，那麼它應該是相當快的。 – aaronasterling 2011-01-07 06:56:05

一個簡單的方法是沿着經度對點進行排序，然後在查找朋友時找出可能匹配的最小和最大長度。對列表進行排序是O（n log n），查找朋友是線性的，但只適用於經常使用的朋友。這裏有一個，你必須在一個平面二維表面所有的點時的一個例子：

# friends is the sorted list of (x, y) tuples, (px, py) is my location 
def get_near(friends, px, py, maxdist): 
    i1 = bisect.bisect_left(friends, (px - maxdist, py)) 
    i2 = bisect.bisect_right(friends, (px + maxdist, py)) 
    return [(x, y) for (x, y) in friends[i1:i2] if math.hypot(px - x, py - y) < maxdist]

爲經度/緯度的情況下，你必須使用另一個函數用於測試的距離，而不是歐氏距離（ math.hypot）。

來源

2011-01-07 07:13:23 Antti

製作一個字典{graticule：[users]}（一個「經緯網」是一個1度緯度x 1度的經度;所以你基本上可以圍繞這些值）。爲了找到附近的用戶，首先從相同的和相鄰的刻度線獲取用戶（因爲目標可能在邊緣附近），然後用基本的邊界框測試對它們進行過濾（即，對於某人內部可能的最小經度/緯度是什麼所需的半徑），然後做一個詳細的測試（如果你需要精度，那麼你需要一些比畢達哥拉斯更復雜的數學）。

來源

2011-01-07 08:33:34

算法找到附近的朋友？

回答

相關問題