c++ - 优化在 Z^3 中查找邻居

Question

我在 Z^3 中有一个点数组（整数 3 元组）。

如何快速确定每个点的邻居？邻居是正好一个单位距离之外的点（欧几里得度量）。

例如，假设数组是：

{ {0,0,0}, {0,0,1}, {1,1,1} }

然后{0,0,0}和{0,0,1}是邻居，{1,1,1}没有邻居。

目前，我正在按字典顺序对 a 中的所有点进行排序std::vector，然后使用std::lower_bound它来搜索邻居（6 个二进制搜索）。这比std::unordered_map用于我的测试数据要快得多。

是否有另一种可能更快的方法？（请注意，我不能使用常规网格，因为这些点可能相距甚远。另请注意：由于下面有一些混淆，这是一个关于优化的问题，而不是正确性。我上面建议的实现是微不足道的。）

对于测试数据集，假设一个半径为 256 的体素球体。

标签： c++algorithm

Answer 1

请注意，我不能使用常规网格，因为这些点可能相距甚远

体育场的茶壶问题可以通过多级网格或一些八叉树来解决。每个节点包含其父节点的 1/8 体积。由于一切都是整数，您可能可以通过字符而不是整数来执行此操作。他们只需要在树上爬一次，检查邻居的孩子，如果空了，就上两次，检查邻居的父母。这应该比检查整个数组（多少个？）要快得多（最近的邻居可能只有 64 个节点）。我猜只有 64 个节点就足够了，因为通过只检查每个点的 x0+1,y0+1,z0+1，您不需要检查 x0-1,y0-1,z0-1，因为它重复相同的内容。所以，包括它自己和邻居（所有父母）它是最近邻居的 8x8=64 个节点（即使是对角线，你当然可以省略它们）也许你可以省略对角线节点并只检查 3x8=24 个节点。

当节点中没有点时，不要构建该节点。如果有，那么只需有一个 char 值 0,1,2,3,4,5,6,7 从其父级的角度显示其（z-index）。

还可以有一个用于固定点的缓存，可能是为了在需要重新计算场景时减少计算次数。