我有一些地理定位的对象（我为每个对象提供纬度经度） . 我的应用程序需要显示移动设备GPS位置周围3公里的对象 . 我有几千个对象，它们本地化在大面积区域（例如，几个美国州，几个小国），这意味着在我的对象列表中我可以有一个位于纽约市，另一个位于迈阿密但我也可以拥有对象非常接近（几米） .
目前，我的应用程序执行迭代搜索 . 对于每个物体，我用GPS位置计算距离，如果距离<= 3KM，那么我保留物体，否则我忽略它 . 这个算法不是很有效，我正在寻找一种能提供更好性能的算法 .
我想有一种方法可以使用地理坐标对物体进行排序，然后可以更快地找到位于GPS位置周围的物体 .
我目前的想法是计算具有“极值点”的矩形，北/南/东/西（从GPS位置的3km）以限制搜索区域 . 接下来，我将仅计算此框内对象的距离 . 我认为可以做得更好但我没有这个想法......
任何建议将不胜感激;-)谢谢，
SEB .
3 回答
听起来像nearest neighbor search，但没有最大邻居数（如kNN），但具有最大距离阈值 .
一种常见的方法是将对象放入特殊的数据结构中，以便快速排除搜索空间的大部分内容 . 然而，这些通常是考虑到欧几里德空间而不是球形（纬度/纬度）平面（环绕问题） . 因此，您可能需要将坐标转换为笛卡尔系统中相对于球体中心的3d坐标，然后才能应用以下数据结构之一来有效搜索对象：
Octree
kd-tree
提到空间索引的其他答案是正确的，但不一定是最简单的解决方案 .
我会考虑更简单的事情：按国家，然后按州，地区，城市，最后 - 通过密集城市中的一些地标（您有很多对象）对项目进行分组 .
然后，您只需要执行一些查询（检查我所在的国家/地区，状态，区域等），将自己限制在一小组对象中，而无需在移动应用中实现高级数据结构 .
在没有专门数据结构的情况下执行此操作的一种方法似乎是对数据的两个副本进行排序 - 一次是经度，一次是纬度 . 二进制搜索在lat和long上关闭的任何东西都很接近 .
同样，您可以使用通常的treap（快速）或红黑树（低可变性） .
但是使用r-tree或kd-tree可能有好处 . 我所描述的可能只是为了避免采用新的依赖关系或避免从头开始编写新的数据结构 .