7

サイズの異なる四角形が重ならないように並べて表示できるアルゴリズムへのポインタを探しています。

異なるサイズの長方形のセットが与えられた場合、それらを H x W のサイズの領域に重ねずに並べます。目的は、使用されるスペースを最大化すること、または逆にギャップの領域を最小化することです。十分なスペースがない場合は、同じサイズの 2 番目の領域に進みます。

各長方形の幅と高さは、タイリング領域のそれぞれの寸法よりも小さいと想定されています。四角形は回転したり変形したりしません。つまり、四角形の辺は水平または垂直です。

私は完成したコードを探しているのではなく、この問題を解決するためにどのアプローチ/アルゴリズムを使用するのが最適かを知りたいだけです。

4

2 に答える 2

2

最も単純なのは、kd-tree を使用して、ツリーを垂直および水平のユークリッド 2d 空間に分割することです。次に、長方形を作成されたスペースの 1 つにパックし、ツリーを再帰的に再分割できます。オンラインで入手できる Jquery ツリーマップ プラグインの例があります。jquery プラグイン masonry でも同じことができますが、1D ビン パッキング ソルバーに似ています。2D ビン パッキングははるかに複雑で、四角形を回転させることも意味します。ライトマップをパッキングする例を次に示します: http://www.blackpawn.com/texts/lightmaps/default.html。

于 2012-07-30T15:30:08.647 に答える
0

正しい方向に進む可能性のあるアイデアが 1 つあります。アイデアは、境界ボックス内のタイル領域と白い領域の比率を追跡することです。

入力: 入力矩形の順序付けられていないセット 出力: 塗りつぶされた領域

  1. 空の境界ボックスを定義
  2. 境界ボックス B に最小の空白領域比率が含まれる入力セットから、そのような 2 つの四角形 A_i および B_j を選択します。
  3. 2 つの最適なボックスで境界ボックスを更新する
  4. バウンディングボックスをコーナーに置きます、例えば (1,1)
  5. ボックスがなくなるまで繰り返す
    1. 更新されたバウンディング ボックスに最小限の空白があるなど、セットから新しいボックスを取得します
    2. 境界ボックスの幅または高さが出力領域の幅または高さを超える場合、水平方向または垂直方向の成長を制限します
    3. 新しいボックスを追加できない場合は、新しい領域 H x W に進み、アルゴリズムを再起動します。そうでない場合は、境界ボックスを更新します

まだ定義すべき点がいくつかあります。バウンディング ボックスの場所を最適に決定するにはどうすればよいでしょうか。境界ボックスの成長制限を課す方法は? 最適な境界ボックスを効率的に見つける方法は?

于 2012-07-30T15:39:21.097 に答える