将相等的矩形拟合成更大的矩形

Question

我有一个大矩形

dimensions L*W

和

n smaller rectangles

，每个矩形都具有相同的尺寸

l * w

。每个小矩形都有相同的

dimensions

。

我的目标是将所有

n of smaller

矩形放入大矩形中，同时尽可能最有效地利用大矩形中的空间。 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)).