把许多小矩形放进同一张图,可以按横向货架一行行摆放。即使图片总面积不变,排列顺序与选行方法也会影响最终需要的高度。
先固定规则与数据
图集宽度固定十二,图片不旋转。比较两种明确规则:原顺序只尝试当前行,放不下则新开行;另一种先按高度降序,同高按编号,再放入最早同时满足高度和剩余宽度的旧行,否则新开行。
图片零至六的宽高[[6, 3], [6, 5], [7, 5], [2, 5], [3, 3], [4, 5], [8, 4]],图集宽十二
逐项记录过程
策略1第1行起点高度0,行高5,已用宽12,物品[0, 1];该行空余宽0。
策略1第2行起点高度5,行高5,已用宽12,物品[2, 3, 4];该行空余宽0。
策略1第3行起点高度10,行高5,已用宽12,物品[5, 6];该行空余宽0。
策略1各编号图片的[左,上,宽,高][[0, 0, 6, 3], [6, 0, 6, 5], [0, 5, 7, 5], [7, 5, 2, 5], [9, 5, 3, 3], [0, 10, 4, 5], [4, 10, 8, 4]],总高15,外接图集面积180。
策略2第1行起点高度0,行高5,已用宽12,物品[1, 3, 5];该行空余宽0。
策略2第2行起点高度5,行高5,已用宽10,物品[2, 4];该行空余宽2。
策略2第3行起点高度10,行高4,已用宽8,物品[6];该行空余宽4。
策略2第4行起点高度14,行高3,已用宽6,物品[0];该行空余宽6。
策略2各编号图片的[左,上,宽,高][[0, 14, 6, 3], [0, 0, 6, 5], [0, 5, 7, 5], [6, 0, 2, 5], [7, 5, 3, 3], [8, 0, 4, 5], [0, 10, 8, 4]],总高17,外接图集面积204。
图片自身总面积154,因此高度下界为13。两种实际高度[15, 17],不能仅凭一次比较就认定其中一种对所有素材都更好。
独立复核的方法
检查每张图片只出现一次、矩形互不重叠且未越过宽度。总面积除以宽度再向上取整只是高度下界,不表示一定能达到。两种策略都只是可行摆法,不宣称全局最优。
建议先按原始数据自己算一遍,保留中间状态后再与本例对照。发生分歧时,先寻找最早不同的步骤,检查边界是否包含、编号与坐标方向是否一致,以及状态是在事件之前还是之后更新。最终结果相同并不能替代对过程规则的理解,修改输入后也需要重新核算。
使用范围
例子没有图片间留边、压缩块对齐或旋转许可。实际图集若需要这些约束,应先把有效占用尺寸算进去,再比较摆放效果,不能只按可见像素面积估算。
