如何高效并行地基于参考点邻近性排序2D/3D点向量？

我有两个2D/3D空间中的点向量：

std::vector<Eigen::Vector3d> points_to_sort;
std::vector<Eigen::Vector3d> reference_points;
assert(points_to_sort.size() == reference_points.size());

reference_points具备两个关键特性：

• 呈准均匀分布
• 序列中每个后续点与前一点在距离和角度上都“相距较远”

我最初想到的朴素方案是：遍历reference_points，为每个参考点p在points_to_sort中找到最近点p_c，标记p_c为已访问后存入结果容器。但这个方法存在明显问题：

• 效率偏低
• 难以并行化（多个待排序点可能以同一个参考点为最近点，处理流程繁琐）

目前我能想到的优化方向是用包围体层次结构（BVH）或八叉树加速最近点搜索，但还想探索其他思路。

换个角度思考：我需要实现与Morton/Hilbert曲线排序相反的效果——这类曲线排序会让空间邻近的点在序列中相邻，而我要的是让空间上相距较远的点在序列中相邻。

有没有人遇到过这类问题，或者有相关的实现思路？

可行思路整理 #

1. 基于参考点的二分图匹配优化

既然reference_points本身已是“远距序列”，且两个点集大小相等，本质是要建立两个点集的一一映射，同时保留参考点的序列特性：

• 可以用匈牙利算法解决二分图最优匹配问题，将“最近点距离”作为匹配权重，但直接计算复杂度为O(n³)，大数据量下不友好。
• 优化版：先通过BVH/八叉树为每个参考点筛选出k个候选最近点（比如k=5），再在缩小后的候选集上运行匈牙利算法，能大幅降低复杂度。
• 并行化潜力：候选点筛选阶段可完全并行，后续匹配阶段若采用分布式匈牙利算法或近似匹配算法（如贪心+局部调整），也能提升并行效率。

2. 脱离参考点的“反空间填充曲线”实现

如果不依赖参考点，要生成让远距点相邻的序列，可从空间填充曲线的逆逻辑入手：

• 随机打乱+空间排斥调整：先随机打乱待排序点序列，遍历过程中若当前点与前一点距离过近，就在剩余未处理点中选取距离最远的点替换。该方法简单易并行，仅需维护全局已处理点集合即可。
• 基于空间划分的交替选取：将空间均匀划分为若干单元格（如3D下用八叉树划分至一定深度），按“跨单元格优先”规则选点：先选单元格A的点，再选与A最远的单元格B的点，接着选与B最远的单元格C的点，以此类推。这种方法天然适合并行，单元格距离可提前预处理，点的选取可按单元格分组并行处理。
• 频谱排序（Spectral Sorting）：利用点集的拉普拉斯矩阵特征值，选取对应最小特征值的特征向量（除常数向量），按特征向量值排序。这种排序会让空间远距点在序列中交替出现，本质是利用图论的“点集分割”逻辑，适配均匀分布的点集。

3. 参考点序列的直接映射简化

如果reference_points的准均匀分布特性足够强，可跳过最近点搜索，直接将待排序点映射到参考点序列上：

• 分别对参考点和待排序点做空间坐标的主成分分析（PCA），将两者投影至同一主成分空间。
• 按参考点的序列顺序，匹配待排序点中投影位置最接近的点（如按PCA分量距离排序），该方法比全空间最近点搜索快很多，且并行性强。

内容的提问来源于stack exchange，提问作者Gleb Shigin