找到离给定点最近的点 [英] Finding the closest point to a given point

问题描述

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

I have searched all over for this, but I can't seem to find the best approach to this. I have about 22000 lat/lon points and I want to find the closest one's to the current location of the iPhone. I've seen people ask about Quad Trees, Dijkstra's Algorithm, and spatial databases. Which is the best for the iPhone? Spatial databases seem easiest, but I am not sure.

实际上有超过 20,000 点.你认为遍历所有这些是这样做的方法吗?不过感谢您的意见.

there are actually over 20,000 points. You think iterating through all of them is the way to do it? But thanks for you input.

谢谢.

推荐答案

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

If you need better than O(N), you can only get that if you first pay N lg N for building a spatial hash of some sort (a quadtree, octree, hash grid, or similar). Then each test will be approximately O(lg N), and can be much better typically by caching the last location you checked, if there's a lot of coherency (generally, there is).

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

I would probably build an octree in Euler (geocentric, XYZ) space, because that allows me to get "true" distance, not "warped" lat/lon distance. However, in practice, a quad tree in lat/lon space will probably work well enough. Once you have a hit, you hold on to that tree node (assuming the tree isn't re-built at runtime), and the next query starts walking from that tree node, and only needs to worry about nodes that may be closer if the previous point moved further away from the previous answer.

这篇关于找到离给定点最近的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！