2

2 次元空間 (グリッド) のインデックス (x,y) が与えられると、フォン ノイマン近傍から隣接インデックスを導き出すことができます。

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

フォンノイマン近傍を使用して (x、y、z) の隣接インデックスを導出するには、この概念を 3 次元空間 (ランタイムの複雑さを最小限に抑えて) に拡張するにはどうすればよいでしょうか?

誰かがそれを説明するためにいくつかの擬似/ 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},
};

ランク <= の近傍では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範囲内にあることを証明するのは簡単です(R で X から Y に移動します)。その後、Y から Z までの K のステップ)。

この解には O(n) 時間が必要です。ここで、n は近傍内のポイントの正確な数です。冗長性を避けるために簡単に最適化できます。

同様の手法を使用するアルゴリズムの例は、ダイクストラ アルゴリズムです。その主な目的はパス検索ですが、その原則は、範囲 1、2 などのすべての近隣を探索することです (重み付けされていないグラフで)。

于 2012-06-26T15:43:32.540 に答える
0

これは少し単純に思えるので、あなたの質問を誤解している可能性がありますがr、C で任意の 3 次元の場合、隣接するセルをループして処理するか、インデックスを保存すると、次のようになります。

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 に答える