图片动态平铺简化算法
💡待补充图片，整理表达
考虑这样一个问题：给定一个最大为 (W,H) 的窗口，在其中显示 200 张尺寸不一但相对接近的图片（比如表情包），图片可以缩小，但不能放大也不能改变宽高比。有两种具体需求：
- 按给定的图片顺序一行一行（或一列一列）平铺，比如按文件时间顺序。
- 任意顺序平铺，目标是最小化图片之间的空隙，这样可以更加紧凑地在屏幕上预览所有图片
该问题可以看作二维装箱（2D bin packing）的变体，但条件和目标都更加松散，二维装箱的一个典型场景是把尺寸不同的箱子装入到长宽为 W 和 H 的车上，假设所有箱子的高度和车一样，因此箱子不能垂直堆叠（这是更复杂的三维装箱），尽可能最大化箱子空间的占用率。 这种场景下，箱子的尺寸是固定的，但箱子可以旋转，由于空间占用率和现实中成本相关，因此该问题相对“严肃”，给人一种努力追求最优的压力。
本文描述场景里，图片是可以缩小的但不能旋转的，并且 (W,H) 只是最大窗口，而不是严格限制, 如果只有一张尺寸是 (W/2,H/2) 的图片，由于它不超过宽高限制, 直接将其放入窗口就是最优解了，显示的时候窗口会根据所有图片的有效矩形进行裁剪， 优化目标是基于视觉的，所以实现起来并不需要那么努力去追求“最优”，只要基本满足视觉需求即可。
按顺序平铺
下文以按行平铺进行分析，按列平铺思路是类似的。
实现思路
先描述出一种朴素的思路 A:
给定图片顺序后，关键是确定平铺的行数 r，这样可以计算出图片最大高度为 H/r, 所有图片按照比例缩小（或者保持原始大小）到 H/r 后从第一行开始逐一加入行中， 如果该行的宽度超过了 W 则将图片从下一行开始放入。
该思路存在的一个问题是，假设有 100 张 10x10 的表情包放入 W 和 H 都是 1000 的窗口, 按照以上算法，一行就足以平铺完所有表情包，最终平铺的有效宽高是 1000x10 ，非常扁平，视觉上不集中。
所以我们还需要更具体的表达视觉上集中和紧凑性的指标，在当前问题下，W 和 H 是最大长宽而非固定，最终平铺的空间是根据平铺后所有图片的最大外接矩形确定, 但既然给出了尺寸，我们也不希望最终有效平铺区域的高宽比和 H:W 相差太大，假定 (W,H) 是符合视觉偏好的，比如是常见屏幕比例，那么可以在原始问题上额外加入了一个优化目标，即按给定的图片顺序一行一行平铺完成后，所有图片占据的有效空间的宽高比尽可能接近 W/H 且宽高不会超过 (W,H)
有了这些考虑，可以给出思路 B:
遍历所有可能的行的范围，比如 1 到 20 ，在每个候选行上执行思路 A 得到一个平铺结果，计算该结果的有效宽高，选择最终最接近 W:H 的平铺结果。
以上描述中存在一个疏漏，即在每行中用思路 A 平铺时，如果还是以 W 作为最大宽度会有问题，比如 100 个表情包的例子，无论给定行数是多少，平铺所有图片都只需要一行。
因此再进行优化，给出思路 C:
遍历所有可能的行的范围，比如 1 到 20 ，给定行数 r 下计算出每行最大高度 H/r，以此对所有图片按比例缩小（或保持原始大小），统计出缩放后图片的最大高度（如果所有图片的原始的最大高度 h 本身就小于 H/r, 那么就是 h），乘以 r 就得到平铺空间的有效高度 ，它一定是小于等于 H 的，乘以 W/H 得到预期的最大宽度，在有了该宽度的情况下执行思路 A 进行平铺。
该算法使得平铺后的宽高比 ratio 一定是接近但小于 W/H 的，这个值在给定行平铺后是固定的，因此在搜索中，我们不再需要去选择有效宽高比最接近 W/H 的行数，而是要选择另一种新的指标 – 纯图片面积和平铺后图片所占矩形的面积之比，这里称为紧凑度，它是所有缩放后图片的面积的和除以平铺有效空间的面积的比值（因为每次要先计算出缩放后所有图片宽高，因此很容易计算出图片面积。）。
此外，有了图片宽高，还可以计算出所有图片的总宽度，如果它大于预期宽度乘以行数 r，意味着无法在该预期有效空间里平铺完，因此不需要尝试平铺，直接 r+=1 即可，这样可以更快找到目标行数；而如果能在预期空间平铺则执行平铺，当平铺结束发现还有空行剩余，那么直接结束循环。
初步实现
假设所有图片被读取到一个 list 中，每个元素是一个字典，记录图片的尺寸和路径等信息
infos1d = [{"width": 100, "height": 120, "path" "/path/to/img.png"}]
def evenly_fit(
infos1d: List[dict],
max_width,
max_height,
) -> List[list]:
def get_scaled_infos(infos1d, row):
height_limit = max_height // row
scaled_infos = scaling_by(infos1d, height_limit, width=False)
height_per_row = max([info["height"] for info in scaled_infos])
height = height_per_row * row
width = int(height * max_width / max_height)
all_width = sum([info["width"] for info in scaled_infos])
if all_width > width * row:
return scaled_infos, 2 # invalid
area = sum([info["width"] * info["height"] for info in scaled_infos])
compact_ratio = area / (width * height)
return scaled_infos, compact_ratio
best_layout = [[]]
best_ratio = 0
row = 1
while True:
scaled_infos, ratio = get_scaled_infos(infos1d, row)
if ratio > 1: # invalid
row += 1
continue
actual_row, layout = tile(row, scaled_infos, max_width)
if ratio > best_ratio:
best_ratio = ratio
best_layout = layout
if actual_row < row:
break
row += 1
return best_layout
以下 tile 是一维 bin packing 的 next fit 实现：
def tile(rows, infos1d, width_limit):
layout = [[] for _ in range(rows)]
current_width = 0
row_count = 1
for info in infos1d:
width = info["width"]
if current_width + width > width_limit:
row_count += 1
current_width = width
else:
current_width += width
if row_count <= rows:
layout[row_count - 1].append(info)
return row_count, layout
修正
实践中发现以上算法的问题是：
get_scaled_infos(infos1d, row) 返回的 ratio 并不一定是最终平铺后的 ratio,
比如在 get_scaled_infos 中 row = 1 的时候计算出所有图片缩放后宽度正好等于多行的总宽度加 1，那么 row=2 才能被平铺，但 row=2 的情况下，图片大小平均变成了 row=1 时的 1/2, 这时候大概率是可以一行就平铺完的，此时计算 ratio 的分母应该是一行的高度乘以图片总宽度，而不是两行的高度乘以标准预测的 width
再比如在 get_scaled_infos 中计算出所有图片缩放后宽度正好等于多行的总宽度，那么在平铺的时候大概率是不会正好完全塞入整个空间的，而是会多出一行。
因此 get_scaled_infos 不应该去计算 ratio, 而是放在 tile 中根据真实平铺结果计算。
def evenly_fit(
infos1d: List[dict],
max_width,
max_height,
) -> List[list]:
def get_scaled_infos(infos1d, row):
height_limit = int(max_height / row)
scaled_infos = scaling_by(infos1d, height_limit, width=False)
height_per_row = max([info["height"] for info in scaled_infos])
height = height_per_row * row
width = int(height * max_width / max_height)
all_width = sum([info["width"] for info in scaled_infos])
if all_width > width * row:
height_per_row = -1
return scaled_infos, height_per_row, width
best_layout, best_ratio, best_width, best_scaled_info = [[]], 0, 0, []
row = 1
while True:
scaled_infos, height_per_row, width = get_scaled_infos(infos1d, row)
if height_per_row == -1:
row += 1
continue
layout = tile(scaled_infos, width)
actual_row = len(layout)
if actual_row == 1 and row > 1:
# do some adjustment to make it more rows
layout = tile(scaled_infos, width * 0.7)
actual_row = len(layout)
area = sum([info["width"] * info["height"] for info in scaled_infos])
actual_width = max(
[sum([info["width"] for info in r]) for r in layout]
)
hw_ratio = height_per_row * actual_row / actual_width
ratio = area / (actual_width * height_per_row * actual_row) * hw_ratio
if ratio > best_ratio:
best_ratio, best_layout, best_width = ratio, layout, actual_width
best_scaled_info = scaled_infos
if actual_row < row:
break
row += 1
best_layout = adjust_width(best_scaled_info, best_width, len(best_layout))
adjust_height(best_layout, max_height)
return best_layout
def tile(infos1d, width_limit):
layout = []
current_width = 0
row_count = 0
for info in infos1d:
width = info["width"]
if current_width + width > width_limit:
row_count += 1
current_width = width
else:
current_width += width
while len(layout) <= row_count:
layout.append([])
layout[row_count].append(info)
return [row for row in layout if len(row) > 0]
宽度微调
在 evenly_fit 的最后两行有：
best_layout = adjust_width(best_scaled_info, best_width, len(best_layout))
adjust_height(best_layout, max_height)
因为按前文思路平铺，最后一行里大概率只有少量的图片，其他行则是紧凑排列，这是因为给定特定行，计算出了一个固定的 width，各行紧凑排列后，最后总会出现少量的“余数”，它大概率比其他行的实际宽度都小。
因此在行数 row 确定之后，还要对宽度进行微调，逐渐减小宽度，然后重新平铺，直到有图片无法平铺进去为止，这种情况下图片不需要重新缩放，只需要重复执行平铺算法，找到最小的在当前行数里就可以平铺的宽度。
可以用以下二分算法：
def adjust_width(scaled_info, width, row):
"""
binary search to find the smallest width that can fit in current row
"""
left, right = width // 2, width
while left <= right:
mid = (left + right) // 2
_layout = tile(scaled_info, mid)
if len(_layout) > row:
left = mid + 1
else:
right = mid - 1
best_layout = tile(scaled_info, left)
return best_layout
高度微调
对于平铺后多出一行的场景，总高度很可能超过 max_height ，因此要做一次全局缩放：
def adjust_height(layout, max_height):
actual_height = 0
for row in layout:
actual_height += max([info["height"] for info in row])
if max_height >= actual_height:
return
scale = max_height / actual_height
for row in layout:
for info in row:
info["width"] = int(info["width"] * scale)
info["height"] = int(info["height"] * scale)
任意顺序平铺
什么情况下能获得更好的平铺效果呢？考虑这样的场景，假设有 4 张图片，它们宽度都一样，但其中两张高度是 100, 另外两张高度 50, 那么直觉上更好的算法是把高度相同的放在一行，这样每行都可以获得更紧凑空间，因此这里做法是：
def best_evenly_fit(
infos1d: List[dict],
max_width,
max_height,
) -> List[list]:
# sort by height
infos1d = sorted(infos1d, key=lambda x: x["height"])
layout2d = evenly_fit(infos1d, max_width, max_height)
# shuffle each row
for row in layout2d:
random.shuffle(row)
# shuffle the rows
random.shuffle(layout2d)
return layout2d
当然还可以在每一行中用一维 bin packing 的思路（first fit,best fit）等按每行剩余宽度以及图片宽度启发式地去添加图片，但个人发现以上方式在视觉上就足够好了