什么比边框更好？

我有一种情况，在那里我有X百万经纬度点。什么比边框更好？

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

有什么比包围盒好？

我很想看到的算法，参考和几个实现;）千恩万谢！

2009-12-04 Setori

这只是在几分钟前在这里回答：http://stackoverflow.com/questions/1847310/count-number-of-points-inside-a-circle-fast – hirschhornsalz 2009-12-04 17:06:57

请记住，长/纬是奇怪的，因为距离根据纬度变化。如果所有数据都在一个国家内，这不是什么大不了的事情。但我看到有人忘记在全球数据集上处理这个问题。 – Nosredna 2009-12-04 17:56:31

哦，当然，不要忘记经度是环绕的。 :-) – Nosredna 2009-12-04 17:57:59

有相当多的选项，是更好的，大多是围绕space partitioning为主。

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

来源

2009-12-04 17:07:27

我绝对同意他想做一些空间分区。然而，他将不得不修改四叉树的概念以使其起作用，因为它旨在用于矩形区域的二维空间。正如Nosredna正确指出的那样，他还需要担心包装。 – PeterAllenWebb 2009-12-04 21:58:07

是的，但是在这些情况下可以使用quadtrees和kd树。 Quadtrees更容易，因为在这种情况下处理包装变得容易得多。但是，通常情况下，您并不是在处理这样的情况下处理全局案例，而是处理较小的区域，在这种情况下，大多数问题的问题较少。 – 2009-12-04 22:03:41

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

来源

2009-12-04 17:06:42

我在数据库中使用了数千万条记录的Morton代码 - 它们运行良好。 – 2009-12-19 03:46:32

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

如果您的“唯一”有几百万分，并且它们没有聚集到热点，那可能会让您通过。

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

来源

2009-12-04 21:52:16 PeterAllenWebb