c++ - 如何使用冯诺依曼邻域在 3D 空间中设置索引？

Question

给定二维空间(网格)中的索引 (x,y)我可以通过 von Neumann 邻域导出邻域索引:

http://en.wikipedia.org/wiki/Von_Neumann_neighborhood .

我如何最好地将这个概念扩展到三维空间(以最小的运行时复杂性)使用 von Neumann 邻域导出 (x,y,z) 的邻域索引？

有人可以帮我用一些伪/C 代码来说明吗？

Answer 1

如果您谈论的是 6 个近邻，最有效的方法是对其进行硬编码:

int neighbour_offsets[3][6] = {
  {1, 0, 0},
  {0, 1, 0},
  {0, 0, 1},
  {-1, 0, 0},
  {0, -1, 0},
  {0, 0, -1},
};

对于排名 <= r 的邻居, 对于嵌套的固定维度 for循环将起作用:

for (x = -r; x <= r; ++x) {
    r_x = r - abs(x);
    for (y = -r_x; y <= r_x; ++y) {
        r_y = r_x - abs(y);
        for (z = -r_y; z <= r_y; ++z) {
            printf("%d, %d, %d\n", x, y, z);
        }
    }
}

如果你想要远方的邻居d == r而不是 d <= r , 使用 z := {-r_y, r_y} .

对于任意低维度，递归都可以工作(并且相当清楚)；对于高维，您最好从递归解决方案开始并将其转换为循环。在高维度 (D >> r) 中，大部分时间偏移量在大多数维度中都将为零。