在标识点周围的区域中查找点

Question

我想根据拥有许多用户的位置制作一个移动应用程序。用户想要快速找到他周围一定距离（例如：10km）中的所有其他用户，距离不需要太精确（可能从9km到11km而不是10km），服务器将处理此过程。如果我有数百万用户，那么蛮力将意味着进行太多计算。你能建议我一些其他的解决方案或算法吗？

谢谢！

Answer 1

以下是您可以执行的操作：

将

整个区域划分为伪网格。每当用户从一个磁贴移动到另一个磁贴时，你的应用都会使用其位置更新服务器，该位置表示磁贴编号。这通常可以使用GPS AFAIK来完成。

因此，服务器会持续跟踪移动设备所在的当前磁贴。现在，当用户请求附近的邻居时，只需几秒钟，因为服务器只需要发送当前用户磁贴旁边的磁贴中的用户列表。

另外，请注意，您需要根据要扫描附近用户的距离来选择磁贴大小。

Answer 2

我会保留一个Map<Area，Set>>其中Area是从用户坐标派生的表达式。作为一个简单的情况，使用具有 N/S 和 E/W 度的函数。如果用户想要找到亲密的好友，您必须从该区域和（可能）从一个、两个或三个相邻区域检索用户。

有 360*180 = 64800 对<度，度>但远远超过（猜，猜）90% 根本不会使用。您可以将其扩展到对<deg.min，deg.min>，即 360*180*3600 = 233280000 个不同的对，未使用百分比相同。