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

问题描述

我已经全面搜索了这个，但我似乎无法找到最佳方法。我有大约22000经纬度点，我想找到最接近iPhone的当前位置。我看到有人问起四叉树，Dijkstra算法和空间数据库。哪款iPhone最适合？空间数据库看起来最简单，但我不确定。

编辑：实际上有超过20,000点。你认为迭代所有这些是实现它的方法吗？但感谢您的意见。

谢谢。

解决方案

需要比O（N）更好，你只能得到如果你首先支付N lg N来构建某种类型的空间哈希（四叉树，八叉树，哈希网格或类似的）。然后每个测试将近似为O（lg N），如果存在很多一致性（通常存在），通常可以通过缓存您检查的最后一个位置来更好。

我可能会在Euler（地心，XYZ）空间中建立一个八叉树，因为这可以让我得到真实的距离，而不是扭曲纬度/经度距离。然而，在实践中，纬度/经度空间中的四叉树可能工作得很好。一旦你点击了，你可以保留那棵树节点（假设树不是在运行时重新构建的），下一个查询从树节点开始走，只需要担心可能更近的节点前一点离上一个答案更远。

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.

EDIT: 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.

Thanks.

解决方案

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).

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屋！