如何对地理数据进行排序以便快速搜索

Question

我有一些地理定位的对象(我为每个对象提供纬度+经度).我的应用程序需要显示移动设备GPS位置周围3公里的对象.我有几千个对象,它们本地化在大面积区域(例如,几个美国州,几个小国),这意味着在我的对象列表中我可以有一个位于纽约市,另一个位于迈阿密但我也可以拥有对象非常接近(几米).

目前,我的应用程序执行迭代搜索.对于每个物体,我用GPS位置计算距离,如果距离<= 3KM,那么我保留物体,否则我忽略它.这个算法不是很有效,我正在寻找一种能提供更好性能的算法.

我想有一种方法可以使用地理坐标对物体进行排序,然后可以更快地找到位于GPS位置周围的物体.

我目前的想法是计算具有"极值点"的矩形,北/南/东/西(从GPS位置的3km)以限制搜索区域.接下来,我将仅计算此框内对象的距离.我认为可以做得更好但我没有这个想法......

任何建议将不胜感激;-)谢谢,

SEB.

Answer 1

听起来像是最近邻居搜索，但不具有最大邻居数（如kNN），但具有最大距离阈值。

一种常见的方法是将对象放入特殊的数据结构中，以允许快速排除大部分搜索空间。但是，这些通常是在考虑欧几里德空间的情况下制作的，而不是针对球形（纬/经）面的（环绕问题）。因此，您可能需要先将笛卡尔系统中的坐标转换为相对于球体中心的3d坐标，然后才能应用以下数据结构之一有效地搜索对象：

• 八位
• 树