从大量数据点中计算附近点的最快方法是什么？

Question

我有一大组3d点，(20,000+)，散落在一个3d空间中。我需要确定哪些点在集合中每个点的特定任意范围内。例如，对于每一点，什么是在10个单位范围内的一组点。这方面的排列相当大。那么，在计算上最有效的方法是什么呢？(我只需要使用java来解决这个问题。)

Answer 1

您可以使用k-d树，它基本上是一个k维二叉树.k-d树中的范围搜索是非常有效的.

Answer 2

因为这是一个没有代码的理论性问题，我将把我的2分钱扔在这里。如果您不使用任何几何DB，如postgis (http://postgis.net/)，我将建议以下的前提是，点有三个坐标(X，Y，Z)。

创建三个数组，其中包含点的id和一个坐标。按坐标分类。然后，对每个点，检查最后和下一个是否在范围内。如果两者都不是，那就消除这一点。为每个数组做这个。然后，您将有一个更少的空间来计算。然后，对于一个点范围内的每一个点，计算距离和标志，消除最远处的点。

希望这能帮上忙。

Answer 3

你可以使用一个空间填充曲线和近似。将这些点视为二进制，并将其交叉起来。然后对数字进行排序，并利用曲线首先访问附近的点。你可以尝试许多曲线，这很可能取决于点。