我有一些地理定位的对象(我有每个对象的纬度 + 经度)。 我的应用程序需要显示移动设备 GPS 位置周围 3 公里的对象。 我有几千个物体，它们分布在很大的区域(例如，美国的几个州，几个小国家)，这意味着在我的物体列表中，我可以有一个位于纽约市，另一个位于迈阿密，但我也可以有物体非常近(几米)。
目前，我的应用程序执行迭代搜索。对于每个对象，我计算与 GPS 位置的距离，如果距离 <= 3KM，那么我保留该对象，否则我将忽略它。该算法效率不高，我正在寻找能够提供更好性能的算法。
我想有一种方法可以使用地理坐标对我的对象进行排序，然后可以更快地找到位于 GPS 位置周围的对象。
我目前的想法只是计算具有“极值点”的矩形，北/南/东/西(从 GPS 位置的 3 公里)来限制搜索区域。接下来我将只计算这个盒子内的物体的距离。 我认为可以做一些更好的事情，但我没有这个想法...
任何建议将不胜感激;-) 谢谢，
Séb.
最佳答案
听起来像 nearest neighbor search ，但不具有最大邻居数(如在 kNN 中)，但具有最大距离 阈值。
一种常见的方法是将对象放入特殊的数据结构中，以便快速排除大部分搜索空间。 然而，这些通常是在考虑欧几里德空间的情况下制作的，而不是针对球形(纬度/经度)平面(环绕问题)。 因此，您可能需要将坐标转换为相对于球体中心的笛卡尔坐标系中的 3d 坐标，然后才能应用以下数据结构之一来有效地搜索对象:
关于algorithm - 如何对地理数据进行排序以便快速搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11460074/