将相等的矩形拟合到更大的矩形中

Question

我有一个 dimensions L*W 和 n smaller rectangles 的大矩形，每个矩形都具有相同的尺寸 l * w。每个小矩形都有相同的dimensions.

我的目标是将所有 n of smaller 个矩形都放入大矩形中，同时在大矩形中最有效地使用 space 成为可能。 l 和 w 可以根据需要放大或缩小，只要比例保持不变即可。

如何确定小矩形应该如何缩放以适合大矩形？

Answer 1

这是一种算法，它找到缩放因子 F 的最大值，这样所有小的 a x b 矩形在按 F 缩放时将适合包含的矩形 A x B:

1. 对于每对 (p, q) 正整数，使得

   • p <= n
   • q <= n
   • n = p * q - r 对于某个整数 r >= 0 满足 r < p 或 p < q

   计算f = min(A/(a*p), B/(b*q)).

2. 设 F 为在 1 中计算的所有因子 f 中的最大值。

所有对(p, q)的计算可以按如下方式进行：

1. [初始化]p := 0
2. [递增]p := p + 1
3. [结束?]如果p > n,停止
4. [下一步]让q := n + p - 1 / p（整数除法）。下一对 (p, q).
5. [重复]转到 2。

算法思路

每对 (p, q) 代表缩放矩形的特定布局，水平行中有 p 个矩形和 q 行，最后一个可能不完整。下面是 n = 13 写成 3 * 5 - 2 的例子：

由于 p 宽度 f*a 的缩放矩形必须适合宽度 A 的矩形，我们有：p*f*a <= A 或 f <= A/(p*a)。类似地 f <= B/(q*b). 因此此配置的最大比例为 min(A/(p*a), B/(q*b)).