还有什么比边界框更好的吗？

Question

我有一个场景，其中我有 x 万个经度纬度点。

当添加新的长/纬度点时我想知道 有效率的 哪些其他点位于用户配置的距离参数内，因此我可以将它们添加到列表中。

还有什么比边界框更好的吗？

我很想看到算法、参考资料和一些实现；）谢谢您！

Answer 1

有很多更好的选择，主要基于 空间划分.

一个常见且通常非常好的选择（实现起来并不太难）是使用 KD树. 四叉树 更容易实现，但搜索速度较慢。根据数据的分布和您的要求，其他空间分区算法可能性能更好、内存要求较低或存在其他相关问题。

Answer 2

有一个同事告诉我，他有很好的经验，使用莫顿代码作为GIS数据空间索引，也许这是值得研究。

Answer 3

此快速和肮脏的方法可能会节省你一些悲痛：地球表面划分成1个箱。然后，您将有一个180x360元素的数组，你只需要搜索少数盒，包括包含新点盒子，所有的箱子立即围绕它其中一个角是用户指定的范围内。你会发现，有一些技巧，你可以用它来快速找出箱子不考虑他们都使用。只是不要忘记经纬度环绕。

如果您的“唯一”拥有数百万个点，而他们没有聚成热点，可能通过让你。

一个理论上优于方式：可以每个点映射到三维空间中，然后将它们存储在一个八叉树，这将让你迅速找到附近的点到任意的距离之内。当然，在三维空间的距离会比在地球上的大圆距离略有不同，所以你必须计算转换因子。这应该是简单的，但。你不提实现语言，但几乎可以肯定将成为你在工作的任何语言一个屡试不爽的八叉树的实现。如果你不介意插入第三方代码，该解决方案的方式去。