寻找其他用户附近的用户

Question

我应该探索哪些算法来实现一项功能，该功能可以让用户找到位于他附近的其他用户，所有用户的纬度和经度都是事先知道的，并且是固定的[不动态]。 此外，我相信应该有一个更好的方式来存储这些数据，然后简单地存储用户对数据库中的lat，long的用户ID。有效的方法来处理这个问题是什么？

Answer 1

MySQL（及其他）现在支持spatial indexing.

如果你的数据库可以做spatial queries你不需要实现算法自己的任何部分。

Answer 2

使用k-D树作为nearest neighbor search。

Answer 3

有数据结构的空间搜索的两大类是：

• 空间划分树（如k-D tree）
• 重叠边框的树木（如R-tree）

如果你想一个绝对完整的回答你的问题，看看哈南沙美的书，多维和公制数据结构的基础

Answer 4

如果您只是发现接近点，您所需要的只是一个简单的圆形边界半径，您可以调整或偏向中心对数坐标。当然，您应该避免在每个查询的整个数据集上执行此操作。一般来说，除了纬度/经度，你可以将地图分解成象限，你知道你可以忽略蝙蝠。 - 只要确定您的兴趣领域是否处于边缘位置，还可以查询相邻象限。这是一个链接表，只提取该象限中的行。

一旦你减小了象限。使用最基本的几何：

1）用一个简单的边界框消除大部分数据。

伪代码：

DistanceLat = abs(P2lat - P1lat); 
DistanceLon = abs(P2lon - P1lat) 

2）不要勾股定理，看是否点落在withing半径。在简化数据集内（a2 + b2 = c2）

Distance = Sqrt(DistanceLat * DistanceLat + DisanceLon * DistanceLon) 
if (Distance < radius) keep the data