算法找到附近的朋友？

我有一个坐在服务器端管理用户位置信息的蟒蛇程序，每个朋友都有一对（经度，纬度），给定一个（经度，纬度）点，我如何能够在附近（如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

算法找到附近的朋友？

回答

相关问题