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

Question

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

Answer 1

由于这是一个没有代码的理论问题，我将在这里投入我的 2 美分。如果你不使用postgis之类的几何数据库（http://postgis.net/），我会在点具有三个坐标（X，Y，Z）的前提下建议以下。

制作三个包含点的id和一个坐标的数组。按坐标对它们进行排序。然后对于每个点，检查最后一个和下一个是否在范围内。如果两者不是，则消除该点。为每个数组做那个。然后你将有更少的 space 来计算。然后对一个点范围内的每个点，计算距离并标记，剔除最远的点。

希望这会有所帮助。

Answer 2

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

Answer 3

使用预分配为完整大小的 ArrayList。（使用立方体形状区域）

public class Point3D {
    public int x, y, z;

    public static List<Point3D> allWithinRange(List<Point3D> possiblePoints, int x, int y, int z, int inter) {
        List<Point3D> list = new ArrayList<Point3D>(possiblePoints.size());
        possiblePoints.stream()
                .filter(it -> it.x <= x + inter && it.x >= x - inter)
                .filter(it -> it.y <= y + inter && it.y >= y - inter)
                .filter(it -> it.z <= z + inter && it.z >= z - inter)
                .forEach(list::add);
        return list;
    }
}

Answer 4

您可以使用 space 填充曲线和近似值。将这些点视为二进制并将其交错。然后对数字进行排序并利用曲线首先访问附近的点。您可以尝试很多曲线，这很可能取决于点数。

Answer 5

听起来你需要 R-tree。或者可能是像 kd-tree 这样的范围树，它将 return 所有点都放在一个框中，然后您只需在距查询点所需距离处过滤所有点。

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

What is the fastest way to calculate nearby points from large data set of points

java

geometry

java-3d