2

给定二维空间（网格）中的索引（x，y），我可以通过冯诺依曼邻域推导出邻居索引：

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

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

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

4

3 回答 3

2

如果您谈论的是 6 个直接邻居，最有效的方法是对其进行硬编码：

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

对于 rank <= 的邻居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）中，大多数时候大多数维度的偏移量将为零。

于 2012-06-26T15:28:37.757 回答
0

如果您正在寻找特定点的索引，那么答案很简单：

令 D 为 3D 空间中 2 个点的曼哈顿距离：

  D = abs(x1-x2) + abs (y1-y2) + abs (z1 - z2)

那将是您的索引。

如果您正在尝试构建冯诺依曼邻域的 3D 八面体，那么最简单的方法是使用递归。

其实很容易证明，如果一个点X在 Y 的R范围内，而Y在Z的K范围内，那么X至少在Z的K+R范围内（Go from X to Y in R然后在 K 个其他步骤中从 Y 到 Z）。

该解决方案需要 O(n) 时间，其中 n 是邻域中点的确切数量。它可以很容易地优化以避免冗余。

使用类似技术的算法示例是 Dijkstra 算法。虽然它的主要目的是寻路，但它的原理是探索范围为 1、2 等的所有邻居（在未加权图上）。

于 2012-06-26T15:43:32.540 回答
0

这似乎有点简单，所以我可能误解了你的问题，但是对于r三个维度的任意，在 C 中，循环通过相邻单元格并处理它们或存储索引将类似于：

for ( i = -r ; i <= r ; i++ )
    for ( j = -r ; j <= r ; j++ )
        for ( k = -r ; k <= r ; k++ )
            if ( abs(i) + abs(j) + abs(k) <= r ) {
                do whatever in the cell (x+i,y+j,z+k).
                }

请注意，这不是最有效的方式，但可能是最直接的方式。

于 2012-06-26T15:32:29.627 回答