基于人工智能的雪碧图拼接算法
keywords: bin-pack image-pack max-rect genetic typescript javascript node.js image-resource ai
应用场景
前端资源中经常需要将所有的小图合成大图，如何将合成大图的图片压缩到最小，就是本算法要解决的问题。
使用本算法可以有效减小图片资源的解析时长和内存占用。
基于目前亿级PV项目验证，可以减小10%～30%的内存占用。
算法
算法分为两层
- 底层是基于
max-rect-bin-pack的Rectangle Bin Pack算法 - 上层是基于 遗传算法 的最优化的搜索算法。 // 更新了二分法
FYI: 底层算法分为在线和离线两种模式: 离线算法有一定的优化方案，所以离线算法效果更好。上层的遗传算法强制调用了离线算法。
算法的复杂度
- 底层
max-rect-bin-pack算法
在线算法虽然效率更高，但是在线算法结果没有离线算法结果好。
- 上层 遗传算法
遗传算法的时间空间复杂参考paper。
大致上可以认为和种群中孩子个数和生态个数成正相关。
API & demo
- FindPosition
寻找矩形位置的五种策略。
enum FindPosition {
ShortSideFit = 0,
BottomLeft,
ContactPoint,
LongSideFit,
AreaFit,
}- Rect
const rect = new Rect();
rect.width = 90; // 宽度
rect.height = 90; // 高度
rect.x;// x 坐标
rect.y;// y 坐标
rect.isRotated; // 是否被旋转了
rect.info; // 开发者自行写入一些属性，可以在返回值中拿到（基于浅拷贝）max-rect-bin-pack调用
import { MaxRectBinPack, Rect } from 'name';
const width = 200;
const height = 200;
const allowRotate = true;
const packer = MaxRectBinPack(width, height, allowRotate);
const findPosition = 0; // 参照第一条
// 在线算法 尽量不要使用
for(const rect of rects){
const result = packer.insert(rect.width, rect.height, findPosition);
if(result.width!==rect.width||result.height!==rect.height){ // 插入失败返回一个宽高为0的Rect
throw new Error('insert failed');
}else{
console.log(result.x, result.y, result.widht, result.height); // 插入成功
}
}
//离线算法 推荐使用
const rects: Rect[] = [];
const rectsCopy = rects.map($=>$.clone());// js引用传递，这里直接操纵了传入的数组，所以�传入一份clone的。
const result = packer.insertRects(rectsCopy, findPosition);
if(result.length!==rects.length){ // 插入失败，因为容器大小不足
throw new Error('insert failed');
}else{ //插入成功
result.forEach(rect => {
console.log(rect.x, rect.y, rect.width, rect.height);
});
}genetic遗传算法 调用
import { MaxRectBinPack, Rect, genetic } from '';
const rects: Rect[] = [];
const findPosition = 0; // 参照第一条
const bestSize = genetic(rects, { // 遗传算法确定最优策略
findPosition: findPosition,
lifeTimes: 50, // 代数
liveRate: 0.5, // 存活率
size: 50, // 每一代孩子个数
allowRotate: false,// 不支持旋转
});
const width = bestSize.x;
const height = bestSize.y;
const packer = new MaxRectBinPack(width, height, false);//不支持旋转
const result = packer.insertRects(rects, findPosition);
console.log(result.length === /* rects.length */);搜索算法
/**
* 初始化
* @param rects 要插入的矩形数组
* @param allowRotate 是否旋转
* @param step 搜索步长 建议10
* @param findPosition FindPostion 策略
* @param rate 大于一的比率 等于1不可以的
*/
const serach = new Search(rects, false, 10, 0, 1.1);
const bestNode = serach.search();
console.log(bestNode);
const packer = new MaxRectBinPack(bestNode.x, bestNode.y, false);
const result = packer.insertRects(rects, FindPosition.AreaFit);TODO
- 基因编码策略升级
- 返回结果优化
- 提升算法稳定性，回归点有多个的时候会出现回归到次点的情况