算法找到附近的朋友？

Question

我有一个python程序坐在服务器端管理用户位置信息,每个朋友有一对(经度,纬度),给定一个(经度,纬度)点,我如何有效地找到附近(比如在5KM以内)的朋友？

我有10K用户在线...

谢谢.箱子

Answer 1

新答案:

我会将lat和long存储在单独的列中.在它们上放置索引.然后,当你想找到特定用户的附近朋友时,只需要做类似的事情

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树将成为这里的规范解决方案.