已知条件：
宽度已知且有限，高度无限的区域内，有n个方格，已知这些方格的x ，y 坐标以及宽度w和高度h，方格不重叠
需求：
在空间内找个一个位置，可以放的下一个固定宽高（如4 x 4）的方格，原则：离原点最近且Y轴最上
关键点：
- 位置信息转化为二维数组
- 目标点：每个已知方格的左下角点 A，右下角点 B，和右上角点 C
- 目标点位置调整：A点依照高度向左平移，B C点按照宽度向上平移
- 补充点：原点检测
位置信息转化为二维数组 => 目标点获取 => 目标点位置调整 => 空间检测 => 最优点获取，原则：原点最近 && Y轴最上
代码实现：
/**
* spotGenerator
* 将该文件中的 spotGenerator 方法暴露出去以供调用
*
* 1. 实现思想:位置信息转化为二维数组 => 目标点获取 => 目标点位置调整 => 空间检测 => 最优点获取，原则：原点最近 && Y轴最上
* 2. 使用：调用spotGenerator(data, column, initialWidth, initialHeight) 方法
* 参数：
* 1. data : 类型 Array, 现有gird的位置信息，示例[{ x: 9, y: 9, w: 6, h: 7 }]
* 2. column: 类型 Number,分割的列数,例如 24
* 3. initialWidth: 类型 Number,新添加grid的默认宽度，如 4
* 4. initialHeight: 类型 Number,新添加grid时默认高度，如 4
* 返回值：
* 最优点的位置坐标，类型：Object 示例 { x:1 , y:1 }
*/
//获取数组的深度
function getDepth(data) {
var depths = [];
for (var i = 0; i < data.length; i++) {
depths.push(data[i].y + data[i].h)
}
return Math.max.apply(null, depths);
}
//点集填充
function initSpotByData(arr, data) {
var x, y, w, h;
for (var i = 0; i < data.length; i++) {
x = data[i].x;
y = data[i].y;
w = data[i].w;
h = data[i].h;
for (var j = 0; j < h; j++) {
for (var k = 0; k < w; k++) {
arr[y + j][x + k] = 1;
}
}
}
for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < arr[i].length; j++) {
!arr[i][j] && (arr[i][j] = 0)
}
}
return arr;
}
//获取目标点
function getTargetSpot(data) {
var leftBottom = [],
rightBottom = [],
topRight = [],
x, y, w, h;
for (var i = 0; i < data.length; i++) {
x = data[i].x;
y = data[i].y;
w = data[i].w;
h = data[i].h;
leftBottom.push({ x: x, y: y + h });
rightBottom.push({ x: x + w, y: y + h });
topRight.push({ x: x + w, y: y })
}
return {
leftBottom: leftBottom,
rightBottom: rightBottom,
topRight: topRight
}
}
//调节目标点的位置
function tuneTargetSpot(spot, rootArr, initialWidth, initialHeight) {
for (var key in spot) {
switch (key) {
case "leftBottom":
for (var i = 0; i < spot[key].length; i++) {
var newX = leftBottomTune(spot[key][i], rootArr, initialHeight);
spot[key][i].x = newX;
}
break;
case "rightBottom":
for (var i = 0; i < spot[key].length; i++) {
var newY = rightBottomTune(spot[key][i], rootArr, initialWidth);
spot[key][i].y = newY;
}
break;
case "topRight":
for (var i = 0; i < spot[key].length; i++) {
var newY = topRightTune(spot[key][i], rootArr, initialWidth);
spot[key][i].y = newY;
}
break;
}
}
}
//leftBottom的点向左微调,参数 ： {x:x,y:y}
function leftBottomTune(spotPosition, rootArr, initialHeight) {
var x = spotPosition.x,
y = spotPosition.y,
find = false;
for (var j = x; j > 0; j--) {
for (var i = 0; i < initialHeight; i++) {
if (rootArr[y + i] && rootArr[y + i][j] == 1) {
find = true;
break;
};
}
if (find) break;
}
return j == 0 ? j : ++j;//调整后的x值
}
//rightBottom的点向上微调,参数 ： {x:x,y:y}
function rightBottomTune(spotPosition, rootArr, initialWidth) {
var x = spotPosition.x,
y = spotPosition.y,
find = false;
for (var j = y; j > 0; j--) {
for (var i = 0; i < initialWidth; i++) {
if (rootArr[j] && rootArr[j][x + i] == 1) {
find = true;
break;
};
}
if (find) break;
};
return j == 0 ? j : ++j;
}
//topRight向上调整,参数 ： {x:x,y:y}
function topRightTune(spotPosition, rootArr, initialWidth) {
var x = spotPosition.x,
y = spotPosition.y,
find = false;
for (var j = y; j > 0; j--) {
for (var i = 0; i < initialWidth; i++) {
if (rootArr[j] && rootArr[j][x + i] == 1) {//先取y轴
find = true;
break;
};
}
if (find) break;
};
return j == 0 ? j : ++j;//是否是到边缘
}
//检测是否可以放的下方格 参数 ： {x:x,y:y} 返回值true为可以放得下 false为不能放下
function checkRoom(spotPosition, rootArr, initialWidth, initialHeight) {
var x = spotPosition.x,
y = spotPosition.y,
find = false;
for (var i = 0; i < initialHeight; i++) {
for (var j = 0; j < initialWidth; j++) {
if (rootArr[y + i][x + j] == 1 || rootArr[y + i][x + j] == undefined) {//右边空间有限
find = true;
break;
}
}
if (find) break;
}
return !find;
}
//获取最终的点的位置
function getFinalSpot(spotPosition) {
//取优先考上的点
var yArr = [], yMin, indexArr = [];
for (var i = 0; i < spotPosition.length; i++) {
yArr.push(spotPosition[i].y);
}
yMin = Math.min.apply(null, yArr);
//找到最小值的下标
for (var j = 0; j < yArr.length; j++) {
if (yArr[j] == yMin) {
indexArr.push(j);
}
}
if (indexArr.length == 1) {
return spotPosition[indexArr[0]]
} else {
//如果y轴的坐标有相同的点，优先取靠原点最近的
var spotArr = [], lengthArr = [], lengthMin, x, y, finalIndex;
for (var i = 0; i < indexArr.length; i++) {
spotArr.push(spotPosition[indexArr[i]]);
}
//勾股定理取最近的点
for (var k = 0; k < spotArr.length; k++) {
x = spotArr[k].x;
y = spotArr[k].y;
lengthArr.push(x * x + y * y);
}
lengthMin = Math.min.apply(null, lengthArr);//最短的距离
for (var p = 0; p < lengthArr.length; p++) {
if (lengthArr[p] == lengthMin) { finalIndex = p }
}
return spotArr[finalIndex];
}
}
function spotGenerator(data, column, initialWidth, initialHeight) {//column 分割的列数
//初始化二维数组
var rootArr = [],
depth = getDepth(data) + initialHeight,
filterTargetSpot = [];//过滤可以放得下方格的点位置
for (var i = 0; i < depth; i++) {
rootArr[i] = new Array(column);//长度指定
}
//点集填充
initSpotByData(rootArr, data);
var targetSpot = getTargetSpot(data);
tuneTargetSpot(targetSpot, rootArr, initialWidth, initialHeight);//位置调整
//原点检测
if (rootArr[0][0] == 0) {
targetSpot.rightBottom.push({ x: 0, y: 0 });
}
for (var key in targetSpot) {
for (var i = 0; i < targetSpot[key].length; i++) {
var x = targetSpot[key][i].x;
var y = targetSpot[key][i].y;
if (checkRoom(targetSpot[key][i], rootArr, initialWidth, initialHeight)) {//检测是否能放得下
filterTargetSpot.push(targetSpot[key][i]);
}
}
}
var finalSpot = getFinalSpot(filterTargetSpot);
return finalSpot;
}
//获取当前鼠标位置可以容纳下的最大方格的尺寸 x:为
function spaceCheckByCursor(data,column,x,y){
}