将相等大小的矩形适配到更大的矩形中

Question

我有一个尺寸为 L*W 的大矩形和 n 个相同尺寸的小矩形，每个小矩形的尺寸都相同为 l*w。所有小矩形均具有相同的尺寸。

我的目标是在尽可能有效地利用大矩形空间的情况下将所有小矩形放入大矩形中。l和w可以根据需要缩放，只要保持比例不变即可。

如何确定应将小矩形缩放以使它们全部适合于大矩形？

- Joseph

---

你的意思是将所有小矩形按相同比例缩放吗？ - Leandro Caniglia

@LeandroCaniglia 是的，那正是我所指的。 - Joseph

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：

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

- Leandro Caniglia