用于 3d 空间中距离计算的 Java 库

Question

给定 3 维空间中的大量点(x、y、z 坐标)，需要找到离原点最近的十个点。任何指向已经可用的 Java 标准库的指针。还感谢您对使用最佳数据结构和排序算法以具有成本效益的方式在时间和空间上实现解决方案的意见？提前致谢。

Answer 1

只需计算每个值的 sqrt(x^2 + y^2 + z^2) 并排序。在这里，我缓存了结果以提高效率。

// generate    
Set<Point3D> points = new HashSet<Point3D>();
for (int i = 0; i < 20; i++) {
    points.add(new Point3D(-5d + 10d * Math.random(), -5d + 10d
            * Math.random(), -5d + 10d * Math.random()));
}

// distances
final Map<Point3D, Double> distanceCache = new IdentityHashMap<Point3D, Double>();
for (Point3D point : points) {
    distanceCache.put(
            point,
            Math.sqrt(point.getX() * point.getX() + point.getY()
                    * point.getY() + point.getZ() * point.getZ()));
}

// sort
List<Point3D> tmp = new ArrayList<Point3D>(points);
Collections.sort(tmp, new Comparator<Point3D>() {
    @Override
    public int compare(Point3D o1, Point3D o2) {
        return Double.compare(distanceCache.get(o2),
                distanceCache.get(o1));
    }
});

// print results
System.out.println(tmp.subList(0, 10));
for (Point3D point : tmp.subList(0, 10)) {
    System.out.printf("%.2f,", distanceCache.get(point));
}

假设某种 3D 点类

private static class Point3D {
    private double x;
    private double y;
    private double z;
    public Point3D(double x, double y, double z) {
        super();
        this.x = x;
        this.y = y;
        this.z = z;
    }
    public double getX() {
        return x;
    }
    public double getY() {
        return y;
    }

    public double getZ() {
        return z;
    }
    @Override
    public String toString() {
        return new Formatter().format("%.2f,%.2f,%.2f", x, y, z).toString();
    }
}