将相等的矩形拟合为较大的矩形 [英] Fitting equal rectangles into larger rectangle

问题描述

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

I have a single large rectangle of dimensions L*W, and n smaller rectangles that each have the same dimension l * w. Every small rectangle has the same dimensions.

我的目标是使所有n of smaller矩形都适合大矩形，同时最大可能地利用大矩形中的空间.只要保持相同的比例，就可以根据需要放大或缩小l和w.

My goal is to fit all n of smaller rectangles into the large rectangle while making the most efficient use of space in the large rectangle possible. l and w can be scaled up or down as needed, as long as the proportion is kept the same.

如何确定较小的矩形应如何缩放以使其全部适合大矩形?

推荐答案

这里是一种算法，该算法可以找到缩放因子F的最大值，这样，当按F进行缩放时，所有小的a x b矩形都将适合在包含矩形的A x B中:

Here is an algorithm that finds the max value of a scaling factor F such that all small a x b rectangles, when scaling by F will fit in the containing rectangle A x B:

1. 对于每对(p, q)个正整数，例如

• p <= n
• q <= n
• n = p * q - r用于满足r < p或p < q
的某些整数r >= 0

• p <= n
• q <= n
• n = p * q - r for some integer r >= 0 satisfying r < p or p < q

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

所有对(p, q)的计算可以如下进行:

The computation of all pairs (p, q) may proceed as follows:

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

1. [Initialize] p := 0
2. [Increment] p := p + 1
3. [End?] If p > n, stop
4. [Next] Let q := n + p - 1 / p (integer division). Next pair (p, q).
5. [Repeat] Go to 2.

算法的思想

每对(p, q)代表缩放后的矩形的特定布局，水平行和q行中分别包含p个矩形，最后一个可能不完整.这是写为3 * 5 - 2的n = 13的示例:

Every pair (p, q) represents a particular layout of the scaled rectangles with p rectangles in an horizontal row and q rows, the last one possibly incomplete. Here is an example for n = 13 written as 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)).

Since p scaled rectangles of width f*a must fit in a rectangle of width A, we have: p*f*a <= A or f <= A/(p*a). Similarly f <= B/(q*b). Therefore the maximum scale for this configuration is min(A/(p*a), B/(q*b)).

这篇关于将相等的矩形拟合为较大的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！