1

次の問題を解決する必要があります: シンプルだが大きなグリッドマップ (サイズ: mX-times-mY) があります。私は、タイルが障害物によって占有されているか、空いているかだけを区別します。

ここで、n 倍のサイズの比較的小さなスライディング ウィンドウを使用するとします。つまり、n << mX、n << mY です。その n 倍のウィンドウ内の占有タイルと空きタイルのすべての可能な組み合わせに対して、識別子 (数字としましょう) を割り当てます。次に、そのウィンドウのサイズで大きな地図の一部の「スナップショット」を撮ります。

私の質問: マップから抽出された現在のパターンの識別番号を決定するための最も簡単で最速の方法は何ですか?

実演するために: 私は 2x2 ウィンドウ (2x2 マトリックス) を持っています。パターンの組み合わせは 2^(2x2)=16 通りあります。

Pattern    #1    #2    #3    #4    #5    #6    #7    #8

           00    #0    0#    00    00    ##    #0    00
           00    00    00    #0    0#    00    #0    ##

Pattern    #9    #10   #11   #12   #13   #14   #15   #16

           0#    #0    0#    0#    #0    ##    ##    ##
           0#    0#    #0    ##    ##    0#    #0    ##

with # = obscured
     0 = free

パターンを抽出すると仮定します

#0
0#

私のマップから、これが上記の例のパターン番号 10 であることを簡単かつ迅速に特定するにはどうすればよいですか?

これまでの私のアイデア:

1: シンプルなループ

おそらく両方のパターンの差がゼロ行列であるかどうかをチェックして、正しいパターンが見つかるまですべてのパターンをループします。

2: Row-Sum と Column-Sum を識別子として使用する

n 行と n 列すべてを合計し、それらの合計を多次元配列のサブインデックスとして使用します。上記の例: sumRow1 = 1 sumRow2 = 1 sumCol1 = 1 sumCol2 = 1 したがって、私のパターンは patternNumbers[1][1][1][1] = 10 に保存されます。別の例はパターン 16 で、次の場所に保存されます。パターン番号[2][2][2][2] = 16。

ウィンドウが大きい場合の利点: 2*n の合計を計算するだけでよく、それらの合計をすぐに使用して探していたパターンに対処できます。大きな、大きな欠点: 多くの空のエントリが残る (2*n) 次元の配列が必要です。したがって、比較的大きなオーバーヘッドです。

あなたの誰かが前にこれをしたことがありますか？これを解決する方法はありますか？また、いかなる種類の対称性 (回転または線) も考慮しませんでした。

どんな助けでも大歓迎です！

4

1 に答える 1

0

まあ、他の誰かが私に指摘した比較的簡単な解決策を見つけたようです：

すべての行またはすべての列 (選択は問題ではありません!) を特定の順序 (すべてのパターンで同じでなければなりません) で取得し、それらを 1 つの長いベクトルとして整列させると、正規のバイナリ表現が得られます。その 2 進数を 10 進数に変換するだけで、「一意の識別子」が得られます。

Example 1:

00
#0

can also be written as
00
10

now reorder the rows to

0010 = 2

=============================

Example 2:

##
00

can also be written as
11
00

now reorder the rows to

1100 = 12
于 2012-09-19T08:30:53.947 に答える