寻找附近朋友的算法？

Question

我有一个在服务器上运行的Python程序，用来管理用户的位置信息。每个朋友都有一对（经度，纬度）坐标。现在给我一个（经度，纬度）的点，我该怎么高效地找到附近的朋友（比如在5公里以内）呢？

我现在有1万个用户在线……

谢谢！

Bin

Answer 1

创建一个字典，格式是 {graticule: [users]}。这里的“graticule”指的是一个1度纬度乘1度经度的区域，所以你可以简单地把这些值四舍五入。要找到附近的用户，首先要获取同一个和相邻的graticule里的用户（因为目标用户可能在边缘附近），然后用一个简单的边界框测试来筛选他们（也就是找出在你想要的半径内，可能的最小经度和纬度），最后如果需要更准确的结果，就得进行一些比简单的勾股定理更复杂的数学计算。

Answer 2

一种简单的方法是先把点按经度排序，然后在查找朋友的时候，找到可能匹配的朋友的最小和最大经度。排序这个列表的时间复杂度是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）。

Answer 3

新回答：

我会把经纬度分别存放在不同的列里，并在这些列上建立索引。这样，当你想找某个用户附近的朋友时，只需要做类似下面的操作：

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 是你想要的距离对应的纬度和经度的度数。这个值会根据你所在的地球位置而变化，但有一些固定的公式可以帮助你计算出来。还有可能你的数据库可以帮你完成这些计算。

---

旧回答：

我会看看 四叉树 和 Kd树。

我认为 Kd树是这里的标准解决方案。