algorithm - 空间排序 3d 空间中的百万个点

Question

我在 3d 空间中有百万个点的集合。

每个点都是一个对象

Struct Point
{
    double x;
    double y;
    double z;
};

一百万个点以某种随机顺序存储在 C++ 向量 MyPoints 中。

我想根据空间中点的空间分布对这百万个点进行排序，这样物理上更接近的点在排序后也应该在我的数组中更接近。

我对如何做到这一点的第一个猜测如下:首先对 Z 轴排序点，然后沿 Y 轴排序点，然后沿 X 轴排序点

MyPointsSortedAlongZ = Sort(MyPoints, AlongZAxis )
MyPointsSortedAlongY = Sort(MyPointsSortedAlongZ , AlongYAxis  )
MyPointsSortedAlongX = Sort(MyPointsSortedAlongY , AlongYAxis  )

首先，我不知道这个方法是否正确。我的最终点数组 MyPointsSortedAlongX 会在空间上完美排序(或接近空间排序)吗？

其次，如果这个方法是正确的，那么它是不是最快的方法呢？有什么更好的方法来做到这一点？

Answer 1

CGAL图书馆提供 implementation空间填充曲线算法可用于该任务。