algorithm - 从体素列表创建邻域图比在 O(n^2) 中更快？

Question

我目前正在通过大致执行以下操作来创建“邻域图”：

for every voxel
  look at every other unseen voxel 
    check if neighbours

它大致以 n 平方（减去 n）运行。对于一定数量的体素是可以接受的，但显然对于更大的列表需要更多时间。

另一个简单的解决方案是将所有内容放入一个大的 3d 数组或 hashmap 中，这将在 O(n) 中运行，但会以更多内存为代价。

有更快的方法吗？我似乎无法在 google 中输入正确的搜索词...

Answer 1

您可能想查看空间分区树，例如八叉树或kd 树结构。这些结构通常可以非常有效地构建（O(n) 或 O(n log n)，IIRC），然后提供极快的查找以查找给定边界框中的最近邻居或点。使用其中一种结构应该会给您带来巨大的性能提升，而不会产生巨大的 3D 阵列所需的巨大内存成本。

希望这可以帮助！