1

我有一个复杂的问题。我正在尝试在以下条件下随机生成不同高度的 div

  1. 没有 div 重叠，
  2. 沿同一“x 线”的 div 具有相同的宽度，并且
  3. div 在不违反条件 2 的情况下占用最大可用宽度。

我在创建每个 div 时存储它们的值。防止重叠很容易，我基本上遍历所有 div 并检查：

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

但是，当我有多个冲突的 div 时，事情会变得复杂。假设我有两个非碰撞 div（全宽）：

这是一个插图的链接（不能包含没有代表的图像：（）

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

其中 Div1.width = Div2.width = Div3.width。

我创建算法的第一次尝试失败了。基本上，当我添加一个 div 时，我会检测到有多少碰撞。在 Div3 的情况下，它会与其他 2 个 div 发生冲突，但由于 Div1 和 Div2 不会发生冲突，因此我只需将宽度乘以 1/2，而不是 1/3。我可以通过检查 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：定义一个二维数组，将所有网格的值设为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

Step4：当你在屏幕上放置一个新对象时，扫描所有可用的网格（网格的值为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 回答