小さな正方形で構成される領域を大きな長方形に分割する方法は？

Question

入力として0または1のいずれかの値の2Dグリッドを取得し、その中の重複しない可能性のあるすべての長方形を識別するアルゴリズムを探すにはどこに行きますか？

より実用的な説明：多数の正方形で表されるグリッドを描画していますが、できるだけ多くの隣接する正方形を組み合わせて長方形にする方法を見つけて、費やされる時間を削減したいと思います各正方形をサイクリングして描画します。

最大効率は必要ありません。速度がより重要です。

補遺：どうやら私が探しているのはテセレーションと呼ばれるテクニックのようです。今、私はこの特定のケースのための良い説明を見つけることだけが必要です。

補遺2：＆quot; 1＆quot;の境界正方形は不規則であり、場合によっては「1」の分布が正方形は完全にランダムになります。これらの不規則な形状を識別し、通常の長方形に分割する必要があります。

正解：速度と効率の最適なバランスを得るには、グリッドデータを使用して、各ノードのステータス値が空/部分的/

Answer 1

OpenGLを使用した3Dボックスのボクセルをすばやく視覚化するために、同様のことを行いました。

左上のボックスから開始し、空/塗りつぶしフラグを保存しました。次に、別のフラグが付いたボックスに到達するまで、長方形を右に拡大しようとしました。下方向にも同じことをしました。

四角形が塗りつぶされている場合は描画します。

ボックスが残っている場合、右、下、右下の最後の長方形によって引き起こされた残りの3つの長方形すべてについて、手順を再帰的に繰り返します。

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 2

ドブ博士のポータルからのこの記事をご覧になり、状況で最大の長方形を見つけてください。これは非常に効率的なアルゴリズムの非常に詳細な説明であり、反復的に繰り返すことで問題を解決できる可能性があると思います。

Answer 3

最小数の正方形を探していないので、アルゴリズムをシンプルに保つ妥協案を使用することをお勧めします。

最善の解決策はデータによって異なりますが、1つの簡単な代替策は、1つの行に沿ってボックスを収集することです。つまり：

0 0 1 1 1 0 0 0 1 1 1 1 0

結果は次のとおりです：

skip 2
draw 3
skip 3
draw 4
skip 1

これにより、キャッシュを必要とせずにボックスを描画する呼び出しの回数が減ります（つまり、ボックスをその場で構築できます）。

より大きなボックスを作成する場合は、最初の1を見つけて、すべての方向にボックスを展開しようとするバックトラッキングアルゴリズムをお勧めします。ボックスのリストを作成し、使用したとおりに1：sをクリアします。

Answer 4

では、「ON」の四角形の長方形の境界を探していますか？
内側または外側の境界が必要ですか？
すなわち。境界に「ON」の正方形のみが必要ですか、またはグループにすべての「ON」の正方形を長方形に含めますか？

Answer 5

同様の問題を解決しなければなりませんでした。私のアルゴリズムはギザギザの配列をサポートします。よくテストしてコメントしましたが、joel-in-g＆＃246;の提案よりも遅いです： https://stackoverflow.com/a/13802336