algorithm - 布局算法

Question

我有一个包含 N 张图片的数组，每张图片的尺寸为 WxH。我想将它们显示在尽可能接近正方形的矩形矩阵中。最后一行可能不完整。如何计算行数和列数？

Answer 1

所以，假设你有 p 横跨 q 向下；那么你的整个图像就是 pW x qH。你想包括所有的图像，所以 pq >= N;只允许最后一行不完整，因此 p(q-1) < N。并且，根据这些条件，您希望 pW 和 qH 尽可能接近相等。 (也许你也希望 pq-N 越小越好？)

条件 N < p(q-1) <= N 等价于 q = ceiling(N/p)。所以你想选择 p，使比率 p:ceiling(N/p) 尽可能接近 H:W(在某种意义上；也许你想最小化对数的绝对差，或其他东西)。

所以，非常粗略地说，p/(N/p) ~= H/W，所以 p ~= sqrt(NH/W)。

随着 p 增加，N/p 减少，因此 ceiling(N/p) 至少不会增加。所以 p/ceiling(N/p) 是 p 的增函数。因此，无论您喜欢什么接近比率的标准，只有一个 p 值可以完成这项工作，并且当您以一种方式远离它时，该比率在一个方向上变得更差，而在另一个方向上更差，因为您移开另一个。

因此， super 天真但可能足够的伪代码如下(请注意，它忽略了诸如整数和浮点值之间的转换之类的东西):

target_ratio = H/W;
p = round(sqrt(N*H/W)); // initial guess
current_ratio = p / ceiling(N/p);
merit = merit_function(current_ratio, target_ratio);
best_p = p; best_merit = merit; prev_merit = merit;
// [define merit_function however you like; e.g., -abs(log(x/y)-1)
// or -max(x/y-1,y/x-1) or whatever.]
if (current_ratio > target_ratio) {
  // p might be too big
  while (true) {
    --p; if (p<=0) break;
    current_ratio = p / ceiling(N/p);
    merit = merit_function(current_ratio, target_ratio);
    if (merit > best_merit) { best_p=p; best_merit=merit; }
    else if (merit < prev_merit) break;
    prev_merit = merit;
  }
}
else if (current_ratio < target_ratio) {
  // p might be too small
  // similar loop, but in the other direction
}

我怀疑对于 merit_function 的合理选择，您只需进行一次迭代，但我现在不想尝试证明这一点。

如果一个适当的解决方案(而不是最佳解决方案)足够好，那么您可以只使用 p=round(sqrt(N*H/W)) 并完成它。或者，为了稍微好一点的近似值，你可以说 ceiling(N/p) 可能大约是 N/p+0.5 平均而言，有点，我认为最终是这意味着你想要像 p = round(sqrt(N*H/W+0.25*H*H/(W*W)) - 0.25*H/W 这样的东西。(你应该检查我的依赖它之前的代数。我只是简化 p/(N/p-1/2) = H/W 并求解由此产生的二次方程。)