我正在使用“查找空框”算法,如下所示: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
完毕