8

我有一些地理定位的对象（每个对象都有纬度+经度）。我的 App 需要显示移动设备 GPS 位置周围 3 公里的物体。我有数千个对象，它们分布在大范围内（例如，美国的几个州、几个小国家），这意味着在我的对象列表中，我可以有一个位于纽约市，另一个位于迈阿密，但我也可以有对象非常接近（几米）。

目前，我的应用程序执行迭代搜索。对于每个对象，我使用 GPS 位置计算距离，如果距离 <= 3KM，则保留该对象，否则忽略它。该算法效率不高，我正在寻找一种能够提供更好性能的算法。

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

我目前的想法只是用“极端点”计算矩形，北/南/东/西（距离 GPS 位置 3 公里）以限制搜索区域。接下来，我将仅计算此框内对象的距离。我认为可以做一些更好的事情，但我不知道......

任何建议将不胜感激；-) 谢谢，

塞布。

4

3 回答 3

6

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

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

于 2012-07-12T20:43:28.540 回答
1

提到空间索引的其他答案是正确的，但不一定是最简单的解决方案。

我会考虑一些更简单的事情：按国家/地区，然后按州，地区，城市，最后 - 按密集城市中的一些地标（您有很多对象）对项目进行分组。

然后，您只需执行一些查询（检查我在哪个国家、哪个州、哪个地区等），将自己限制在非常小的一组对象中，而无需在您的移动应用程序中实现高级数据结构。

于 2012-07-12T20:47:18.953 回答
0

在没有专门的数据结构的情况下执行此操作的一种方法似乎是对数据的两个副本进行排序——一次按经度，一次按纬度。任何二进制搜索以关闭纬度和经度的东西都是接近的。

同样，您可以使用常用的树（快速）或红黑树（低可变性）。

但是使用 r-tree 或 kd-tree 可能有优势。我所描述的可能只是为了避免采用新的依赖项或避免从头开始编写新的数据结构。

于 2012-07-12T21:28:30.537 回答