4

対角線に沿ってフラット バッファーに格納されている 2D マトリックスがあります。たとえば、4x4 行列のインデックスは次のように散らばっています。

 0   2   5   9
 1   4   8  12
 3   7  11  14
 6  10  13  15

この表現では、元のインデックスと X/Y オフセットが与えられた場合に、隣接する要素のインデックスを計算する最も効率的な方法は何ですか? 例えば：

// return the index of a neighbor given an offset
int getNGonalNeighbor(const size_t index,
                      const int x_offset,
                      const int y_offset){
    //...
}

// for the array above:
getNGonalNeighbor(15,-1,-1); // should return 11
getNGonalNeighbor(15, 0,-1); // should return 14
getNGonalNeighbor(15,-1, 0); // should return 13
getNGonalNeighbor(11,-2,-1); // should return 1

ここでは、オーバーフローは発生せず、ラップアラウンドもないと仮定します。

多くの三角数と三角根の計算を含むソリューションがあります。また、多くのブランチが含まれているため、可能であれば代数に置き換えることをお勧めします (これは、分岐制御フローが高価な GPU で実行されます)。私のソリューションは機能していますが、非常に時間がかかります。それを行うには、もっとシンプルで計算量の少ない方法が必要だと思います。

誰かがこの特定の問題/表現に名前を付けることができれば、おそらく助けになるでしょう.

誰かが興味を持っている場合は、完全なソリューションを投稿できますが、前述のように、このような単純なタスクでは非常に長く、比較的複雑です。一言で言えば、私のソリューションは次のことを行います。

  • 元のインデックスをより大きな三角行列に変換して、2 つの三角形を処理しないようにします (たとえば、13 は 17 になります)。

4x4 マトリックスの場合、これは次のようになります。

0   2   5   9   14  20  27
1   4   8   13  19  26  
3   7   12  18  25  
6   11  17  24  
10  16  23
15  22  
21
  • オフセットのマンハッタン距離とインデックスの三角根を使用して、この表現の近傍の対角線のインデックスを計算します。
  • オフセットを使用して、この対角線内の隣接の位置を計算します
  • パディングを削除して元の表現に変換します。

何らかの理由で、これが私が思いつく最も簡単な解決策です。

編集：

オフセットを蓄積するループを持つ：

三角形の数値のプロパティを考えると、行列を 2 つの三角形 (0 から 9 を「上の三角形」、10 から 15 を「下の三角形」と呼びましょう) に分割し、内部にテストを含むループを作成する方が簡単であることに気付きました。上の三角形で 1 を加算し、下の三角形で 1 を減算してオフセットを累積します (それが理にかなっている場合)。しかし、私のソリューションでは、ループ、特にトリップ数のバランスが取れていないループ (これもGPU にとって非常に悪いことです) は絶対に避ける必要があります。

だから私は、アルゴリズム的な解決策ではなく、代数的な解決策を探しています。

ルックアップ テーブルの作成:

繰り返しますが、GPU のため、ルックアップ テーブルの構築を避け、その中でランダム アクセスを行うことをお勧めします (非常にコストがかかります)。代数解が好ましい。

行列のプロパティ:

  • マトリックスのサイズは既知です。
  • 今のところ、私は正方行列のみを考えていますが、長方形のものの解決策もいいでしょう.
  • 私の例の関数の名前が示すように、ソリューションを N 次元のボリュームに拡張すること (したがって、N ゴナルの平坦化) も大きなプラスになります。
4

2 に答える 2

1

テーブル ルックアップ

#include <stdio.h>

#define SIZE 16
#define SIDE  4  //sqrt(SIZE)

int table[SIZE];
int rtable[100];// {x,y| x<=99, y<=99 }

void setup(){
    int i, x, y, xy, index;//xy = x + y

    x=y=xy=0;
    for(i=0;i<SIZE;++i){
        table[i]= index= x*10 + y;
        rtable[x*10+y]=i;
        x = x + 1; y = y - 1;//right up
        if(y < 0 || x >= SIDE){
            ++xy;
            x = 0;
            y = xy;;
            while(y>=SIDE){
                ++x;
                --y;
            }
        }
    }
}
int getNGonalNeighbor(int index, int offsetX, int offsetY){
    int x,y;
    x=table[index] / 10 + offsetX;
    y=table[index] % 10 + offsetY;
    if(x < 0 || x >= SIDE || y < 0 || y >= SIDE) return -1; //ERROR
    return rtable[ x*10+y ];
}

int main() {
    int i;
    setup();
    printf("%d\n", getNGonalNeighbor(15,-1,-1));
    printf("%d\n", getNGonalNeighbor(15, 0,-1));
    printf("%d\n", getNGonalNeighbor(15,-1, 0));
    printf("%d\n", getNGonalNeighbor(11,-2,-1));
    printf("%d\n", getNGonalNeighbor(0, -1,-1));

    return 0;
}

テーブルバージョンを使用しないでください。

#include <stdio.h>

#define SIZE 16
#define SIDE  4

void num2xy(int index, int *offsetX, int *offsetY){
    int i, x, y, xy;//xy = x + y

    x=y=xy=0;
    for(i=0;i<SIZE;++i){
        if(i == index){
            *offsetX = x;
            *offsetY = y;
            return;
        }
        x = x + 1; y = y - 1;//right up
        if(y < 0 || x >= SIDE){
            ++xy;
            x = 0;
            y = xy;;
            while(y>=SIDE){
                ++x;
                --y;
            }
        }
    }
}
int xy2num(int offsetX, int offsetY){
    int i, x, y, xy, index;//xy = x + y

    x=y=xy=0;
    for(i=0;i<SIZE;++i){
        if(offsetX == x && offsetY == y) return i;
        x = x + 1; y = y - 1;//right up
        if(y < 0 || x >= SIDE){
            ++xy;
            x = 0;
            y = xy;;
            while(y>=SIDE){
                ++x;
                --y;
            }
        }
    }
    return -1;
}
int getNGonalNeighbor(int index, int offsetX, int offsetY){
    int x,y;

    num2xy(index, &x, &y);

    return xy2num(x + offsetX, y + offsetY);
}

int main() {
    printf("%d\n", getNGonalNeighbor(15,-1,-1));
    printf("%d\n", getNGonalNeighbor(15, 0,-1));
    printf("%d\n", getNGonalNeighbor(15,-1, 0));
    printf("%d\n", getNGonalNeighbor(11,-2,-1));
    printf("%d\n", getNGonalNeighbor(0, -1,-1));

    return 0;
}
于 2013-04-17T22:41:03.520 に答える