5

ここに問題があります;)

1 と 0 で満たされた 3 次元配列があります。1 は 3 次元の複雑な多角形 (単純な多角形ではない) を表します。ポリゴンの境界のみが値 1 を持ち、内部は 0 で埋められます。ここに問題があります：

これらのポリゴンを 1 で塗りつぶす高速アルゴリズムが必要です。配列の次元は通常、約です。512×512×100。

前もって感謝します！

2d での例を次に示します。

0000111110000
0000100010000
0000100010000
0000111110000

結果として

0000111110000
0000111110000
0000111110000
0000111110000

これは @Mikolas アルゴリズムの正しい 3 次元ソリューションですか?

    void scan_polygon(int frames, int rows, int cols, char data[][][], char result[][][]){
for(int f=0; f < frames; ++f)
for(int r=0; r<rows; ++r)
for(int s = 0, c=0; c<cols-1; ++c)
{
    s ^= s ? ( data[f][r][c] && !data[f][r][c+1]) :
             (!data[f][r][c] &&  data[f][r][c-1]);

    result[f][r][c] = s;
}

for(int f=0; f < frames; ++f)
for(int c=0; c<cols; ++c)
for(int s = 0, r=0; r<rows-1; ++r)
{
    s ^= s ? ( data[f][r][c] && !data[f][r+1][c]) :
             (!data[f][r][c] &&  data[f][r-1][c]);

    result[f][r][c] &= s;
}

}

よろしくお願いします、

ステフ

4

2 に答える 2

3

多角形が多様体であると仮定すると、単一の for ループで実行できます。左上隅から開始し、エッジを横切るときのパリティを追跡します。

単純な 2D バージョン (転置ケースを追加):

void scan_polygon(int rows, int cols, char** data, char** result)
{
    for(int r=0; r<rows; ++r)
    for(int s = 0, c=0; c<cols-1; ++c)
    {
        s ^= s ? ( data[r][c] && !data[r][c+1]) :
                 (!data[r][c] &&  data[r][c-1]);

        result[r][c] = s;
    }


    for(int c=0; c<cols; ++c)
    for(int s = 0, r=0; r<rows-1; ++r)
    {
        s ^= s ? ( data[r][c] && !data[r+1][c]) :
                 (!data[r][c] &&  data[r-1][c]);

        result[r][c] &= s;
    }
}

これが壊れる可能性があるのは、ぶら下がっているピクセルまたはエッジがスキャン ラインに沿って突き出ている場合です。次に例を示します。

00000000000000000000        
00000000*11111111111   <--- Whoops!
000000*111*000000000
00000*11111*00000000

これを修正するには、転置された配列でプロセスを繰り返してから、すべての結果を AND します。GPU でメッシュをボクセル化するために、同様のアプローチが Sud らによって使用されています。ノイズの多いコーンが交差する複数の非多様体頂点の構成を持つことができるため、完璧ではありませんが、それが起こらないことを保証できる場合 (またはまれにしか起こらない場合)、それは迅速な結果を得るために私が知っている最も簡単な方法。

編集:反復を行った後に配列を元に戻す方法を示す修正されたソリューション。

于 2011-07-07T19:53:34.957 に答える
2

この場合、標準的なフラッドフィル アプローチを使用できると思います。

active_cells = [seed]
while active_cells:
    new_active_cells = []
    for cell in active_cells:
        for nh in neighbor(cell):
            if not filled(nh):
                fill(nh)
                new_active_cells.append(nh)
    active_cells = new_active_cells

内部または外部が接続されているかどうかわからない場合 (したがって、単一の「シード」を見つけることができない場合)、できることは、すべてのセルを反復処理することです。ゼロのセルを見つけたら、次のことができます。上記のフラッドフィル コードを呼び出して、連結成分を計算します。ゼロであることが判明した他のセルに対してこれを繰り返すと、面が空間を分割しているすべての接続された領域になります。

もちろん、上記のコードが機能するためには、選択された接続に関して面がタイトである必要があります。

于 2011-07-07T20:01:33.173 に答える