寻找附近的朋友的算法？

Question

寻找附近的朋友的算法？

pythonalgorithm

4

我在服务器端有一个Python程序，管理用户位置信息，每个朋友都有一对（经度，纬度）坐标，给定一个（经度，纬度）点，如何高效地找到附近的朋友（比如在5公里范围内）？

我有1万个在线用户...

谢谢。 Bin

- Bin Chen

4个回答

2

一种简单方法是按经度排序这些点，然后在查找朋友时找到可能匹配的最小和最大经度。对该列表进行排序为O（n log n），查找朋友是线性的，但仅限于经度范围内的朋友。这里有一个示例，假设您拥有所有点都在平面2D表面上的情况：

# 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）。

- Antti

2

创建一个字典{网格线：[用户]}（“网格线”是1度纬度x 1度经度的块；因此，您可以基本上舍入值）。要查找附近的用户，请首先从相同和相邻的网格线获取用户（因为目标可能靠近边缘），然后使用基本边界框测试进行过滤（即，对于所需半径内的某人，可能的最小经度/纬度是什么），然后进行详细测试（如果需要精度，则需要比勾股定理更复杂的数学计算）。

- Karl Knechtel

1

http://www.movable-type.co.uk/scripts/latlong.html 就效率而言，唯一想到的就是在数据存入数据库时预先计算距离，即创建另一个表格来存储位置对及其距离，每添加一个位置时，您需要计算它与系统中所有其他点的距离，但随后在该表格上的查找可以快速解决某个距离内的位置。

Aaronasterling 的回答似乎是我自己试图思考但不知道存在的 :) 所以这可能是一个更好的解决方案，但我相信在使用该算法时会产生一些开销（尽管可能很小，因为通常遍历树只要它合理平衡通常是一个相当快速的过程，我还需要一些时间来了解树的组成方式，因为那个是一个新概念对我来说）。

- shaunhusain

1

我正在考虑通过比较纬度和经度来粗略估计。例如）如果纬度和经度的差异都小于0.0001，那么我认为这两个位置是相近的。这有意义吗？ - Bin Chen

@Bin Chen。在看到你的评论之前，我也想到了同样的想法，所以我猜这至少是一个不错的想法。如果列被索引，那么速度应该会很快。 - aaronasterling

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aaronasterling · Accepted Answer

新回答：

我会将纬度和经度存储在不同的列中，并在它们上面放置索引。然后，当您想要查找特定用户附近的朋友时，只需执行以下操作：

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树是此处的规范解决方案。