CODEWITHSUNDEEP
algorithmgeometryrectangles
Joseph
Joseph

Reputation: 85

Fitting equal rectangles into larger rectangle

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.

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.

How can it be determined how the smaller rectangles should be scaled to fit them all in the large rectangle?

Upvotes: 6

Views: 2767

Answers (1)

Leandro Caniglia
Leandro Caniglia

Reputation: 14858

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. For every pair (p, q) of positive integers such that
  • p <= n
  • q <= n
  • n = p * q - r for some integer r >= 0 satisfying r < p or p < q

compute f = min(A/(a*p), B/(b*q)). 2. Let F be the maximum of all factors f computed in 1.

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

  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.

Idea of the algorithm

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: enter image description here

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)).

Upvotes: 2

Related Questions