10

入力として 0 または 1 の値の 2 次元グリッドを取り、その中の重複しないすべての可能な長方形を識別するアルゴリズムを探すには、どこに行けばよいでしょうか?

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

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

補遺: どうやら私が探しているのはテッセレーションと呼ばれる技術のようです。今、私はこの特定のケースの適切な説明を見つける必要があるだけです.

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

正解:速度と効率の最適なバランスを得るには、グリッド データを使用して、各ノードのステータス値が空/部分的に満たされている/満たされているクワッド ツリーを埋めるのが最適です。

4

5 に答える 5

2

私は、OpenGL を使用した 3D ボックスのボクセルの簡単な視覚化のために、同様のことを行いました。

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

塗りつぶされている場合は、長方形を描画します。

ボックスが残っている場合は、最後の四角形によって生成された残りの 3 つの四角形 (右、下、右下) に対して手順を再帰的に繰り返します。

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333
于 2008-11-02T17:44:38.063 に答える
1

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

最善の解決策はデータによって異なりますが、簡単な方法の 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: をクリアします。

于 2008-11-02T17:20:07.317 に答える
0

では、「ON」の正方形の長方形の境界を探していますか?
内側または外側の境界が必要ですか?
すなわち。境界には「ON」の正方形のみが含まれている必要がありますか?それとも、グループ内のすべての「ON」の正方形を長方形に含める必要がありますか?

于 2008-11-02T17:15:15.627 に答える