11

我已经到处搜索了这个，但我似乎找不到最好的方法。我有大约 22000 个纬度/经度点，我想找到最接近 iPhone 当前位置的点。我见过人们询问四叉树、Dijkstra 算法和空间数据库。哪个最适合 iPhone？空间数据库似乎最简单，但我不确定。

编辑：实际上有超过 20,000 点。你认为遍历所有这些是这样做的方法吗？但感谢您的输入。

谢谢。

4

6 回答 6

5

实际上，最好对 Lat/Long 点使用 Haversine（大圆）计算，否则越来越大的距离将是错误的，特别是如果您使用Jherico 的答案中的简单三角函数。

快速搜索提供了这个 javascript 示例：

var R = 6371; // km Radius of earth
var dLat = (lat2-lat1).toRad();
var dLon = (lon2-lon1).toRad(); 
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
        Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) * 
        Math.sin(dLon/2) * Math.sin(dLon/2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

在数据结构方面，Geohash值得一看。

于 2009-05-27T01:51:23.087 回答
5

如果你需要比 O(N) 更好的东西，你只能先支付 N lg N 来构建某种空间散列（四叉树、八叉树、散列网格或类似的）。然后每个测试将大约为 O(lg N)，如果有很多一致性（通常有），通常可以通过缓存您检查的最后一个位置来更好地进行测试。

我可能会在欧拉（地心，XYZ）空间中构建一个八叉树，因为这可以让我获得“真实”的距离，而不是“扭曲”的纬度/经度距离。但是，在实践中，纬度/经度空间中的四叉树可能会运行得很好。命中后，您将保留该树节点（假设树在运行时未重新构建），并且下一个查询从该树节点开始遍历，并且只需要担心可能更接近的节点上一点离上一个答案更远了。

于 2009-05-29T04:09:47.827 回答
2

正如您在 iPhone 上一样，您可以使用 CoreLoaction 来执行地理距离 - 使用 CLLocation 的– getDistanceFrom:

我很想在所有 2k 点上使用蛮力线性搜索，如果这还不够快，请切换到 GeoHash 之类的东西来存储针对您的搜索点的元数据。

于 2009-05-27T09:42:26.273 回答
1

为什么不将地球平铺成区域？（想想十六进制。）然后，当您将点添加到列表中时，或者在一个大的预处理循环中，对于每个点，存储它所在的区域。

那么，在 hex X 中搜索点 A 附近的点时，只需要检查 hex X 中的点和最多 3 个相邻的 hex。

如果仍然需要检查的点太多，请添加子区域。

于 2009-05-29T07:01:22.933 回答
0

您必须考虑到要使用 Dijkstra，您必须知道您在图中的节点位置，而不是您要解决的问题；你不在图中，但你想知道离你最近的点

很简单，正如 Chaos 告诉你的那样，你必须计算你的位置和所有 20.000 个点之间的所有距离，然后对它们进行排序

于 2015-02-19T09:30:17.640 回答
-3

我认为这个算法有效：

创建一个按纬度排序的数组 创建一个按经度排序的数组

要找到最接近的，首先通过在纬度数组中进行二进制搜索来按纬度找到最近的。对经度数组执行相同的操作。现在你有 2 个点，一个最接近纬度，另一个最接近经度。通过勾股定理计算到每个点的距离。最近的点获胜。

罗杰

于 2009-09-19T21:47:57.903 回答