1

複雑な問題があります。次の条件で、高さの異なる div をランダムに生成しようとしています。

  1. 重複する div はありません。
  2. 同じ「x ライン」に沿った div は同じ幅を持ち、
  3. div は、条件 2 に違反することなく、使用可能な最大幅を占有します。

作成時に各 div の値を保存しています。オーバーラップを防ぐのは簡単です。基本的に、すべての div をループしてチェックします。

if (obj1.y < obj2.x && obj2.x < obj1.y)

ただし、衝突する div が複数あると、事態は複雑になります。2 つの衝突しない div (全幅) があるとします。

ここにイラストへのリンクがあります（担当者なしで画像を含めることはできません:( ）

https://dl.dropboxusercontent.com/u/23220381/divs.png

ここで、Div1.width = Div2.width = Div3.width です。

アルゴリズムを作成する最初の試みは失敗します。基本的に、div を追加すると、衝突の数が検出されます。Div3 の場合は他の 2 つの div と衝突しますが、Div1 と Div2 は衝突しないので、幅を 1/3 ではなく 1/2 で乗算するだけで済みます。Div1 と Div2 が衝突するかどうかを確認することでアルゴリズムを修正できますが、これを n Div に一般化する方法がわかりません。

どんな助けでも大歓迎です:)

編集：基本的なシナリオを説明するために画像を追加しました:)

4

1 に答える 1

0

ここのような「空のボックスを見つける」アルゴリズムを使用しています: http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529

Step1: 画面をグリッドに分割します。

var screenWidth = 1360,
    screenHeight = 900;
var unitHeight = 10,
    unitWidth = 10;
var X_grids_count = screenWidth/unitWidth;
var Y_grids_count = screenHeight/unitHeight;

Step2: 2 次元配列を定義し、すべてのグリッドの値を 0 にします。

GridArray = [];
for(i=0;i<X_grids_count;i++)
{
    GridArray[i] = [];
    for(j=0;j<Y_grids_count;j++)
    {
        GridArray[i][j] = 0;     
    }
}

Step3: 画面にオブジェクトを配置するときは、占有されているグリッドの値を 1 にします。

//Get the width and length of the object
...
//Get the position of the object
...
//Calculate how many grids in X-coordinate
...
//Calculate how many grids in Y-coordinate
...
//Calculate the start grids
...
//Use a for loop to make the value of the occupied grids into 1

ステップ 4: 画面に新しいオブジェクトを配置するときは、使用可能なすべてのグリッドをスキャンします (グリッドの値は 0)。

//Scan from the first grid, check if all grids within the square that the new object occupies are available
...
//Get all available squares in the screen. You can make all startpoints(grids) as candidates
...
//Calculate the best one through all candidates based on your constraints, e.g. the shortest distance
...
//Convert the index of grids to actual pixel and put the object on that position
...
//Set the value of the occupied grids into 1

終わり

于 2013-07-09T14:43:15.243 に答える