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

Question

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

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

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

我很想看到算法、参考和一些实现；）非常感谢！

Answer 1

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

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

Answer 2

这种快速而肮脏的方法可能会为您节省一些麻烦：将地球表面划分为 1 度的盒子。然后，您将拥有一个 180x360 元素数组，您只需要搜索少量框，包括包含新点的框和紧邻它的所有框，其中一个角在用户指定的距离内。你会发现有一些技巧可以用来快速找出要使用的盒子，而无需考虑所有这些。只是不要忘记纬度和经度环绕。

如果你的“唯一”有数百万个点，并且它们没有聚集成热点，那可能会让你通过。

一种理论上优越的方法：您可以将每个点映射到三维空间，然后将它们存储在octree中，这样您就可以快速找到任意距离内的附近点。当然，三维空间中的距离会与地球上的大圆距离略有不同，所以需要计算一个换算系数。不过，这应该很简单。您没有提到实现语言，但几乎可以肯定，对于您正在使用的任何语言，都会有一个经过良好测试的八叉树实现。如果您不介意插入第三方代码，这个解决方案就是去。

Answer 3

一位同事告诉我，他在使用Morton-Code作为 GIS 数据的空间索引方面有很好的经验，也许这值得研究。