Fit N rectangles within area keeping aspect ratio

Question

I have N rectangles, all of the same dimensions rectWidth*rectHeight. I have an area with dimensions areaWidth*areaHeight. I want to fit the N rectangles within the area keeping the aspect ratio of the rectangles, resizing the rectangles to make them fit. Between the rectangles I want a spacing of space.

What should be the dimensions of the rectangles to fit them all within the rectangle and keeping the aspect ratio?

Answer 1

Let there be N rectangles.
Let the rectangles be size (cw, ch), where 0 < c ≤ 1.
Let the region you want to fit in be size (W, H).
Let s ≥ 0 be the spacing between rectangles.

The horizontal size of a > 0 rectangles stacked horizontally is acw + (a - 1)s.
We know acw + (a - 1)s ≤ W.

The vertical size of b > 0 rectangles stacked vertically is bch + (b - 1)s.
We know bch + (b - 1)s ≤ H.

We then have the following optimization problem.

max c
subject to
a ≤ (W + s) / (cw + s)
b ≤ (H + s) / (ch + s)
ab ≥ N
0 < c ≤ 1
a, b > 0 and integer

Now consider the following inequalities.

a ≤ (W + s) / (cw + s)
b ≤ (H + s) / (ch + s)

Any optimal solution must make at least one of these a tight inequality.
That is, at least one of the following holds for the optimal solution (a, b, c).

a = (W + s) / (cw + s) &leftrightarrow; c = (W - s(a - 1)) / wa
b = (H + s) / (ch + s) &leftrightarrow; c = (H - s(b - 1)) / wb

Let's suppose without loss of generality that a = (W + s) / (cw + s) holds.
Since a must take one of the values in {1, 2, ..., N},
c must take one of the values in {W / w, (W - s) / 2w, (W - 2s) / 3w, ..., (W - (N - 1)s) / Nw}.

Similar reasoning gives a list of values c must be drawn from in the case where the second inequality (for b) is tight.

If you merge these two lists of values, you will have at most 2N possible values c can take in the optimal solution. Sort those values, then binary search for the maximum c in this list for which there are feasible a and b.

The way to check if a value of c is feasible is to set

a = floor((W + s) / (cw + s))
b = floor((H + s) / (ch + s))

and then check that ab ≥ N.

Answer 2

How about this javaScript solution?

var areaHeight = window.innerHeight;   //set here your area height
var areaWidth = window.innerWidth;     //set here your area width
var N = 216;                           //set amount of rectangles you want to fit
var rectRatio = 9/4;                   //set rectangle ratio
var gutter = [5, 10];                  //set x and y spacing between rectangles
var cols, rows, rectHeight, rectWidth; //variables that we need to calculate

The function assumes that grid of rectangles (canvas) will always fit the height of a container area. You feed number of rows to the function and it calculates rect size and determines whether canvas width is bigger than container width or not. If canvas is bigger we do rows++ and call the function again.

function rowIterator(iterator) {
   rows = iterator;
   cols = Math.ceil(N/rows);  

   rectHeight = (areaHeight - (rows-1)*gutter[1])/rows;          
   rectWidth = rectHeight*rectRatio;

   if (cols * rectWidth + (cols - 1)*gutter[0] > areaWidth) {
       rowIterator(rows + 1);
   }
}

rowIterator(1);                       //feed initial value
var size1 = [rectWidth, rectHeight];

If you also care about finding MAX rect size and not only fit it then iteration should be done also for columns and bigger rect size should be chosen:

function colIterator(iterator) {
   cols = iterator;
   rows = Math.ceil(N/cols);

   rectWidth = (areaWidth - (cols - 1)*gutter[0])/cols;
   rectHeight = rectWidth/rectRatio;

   if (rows * rectHeight + (rows - 1)*gutter[1] > areaHeight) {
       colIterator(cols + 1);
   }
}
colIterator(1);
var size2 = [rectWidth, rectHeight];

total amount of iterations for both iterators would be around N, the max rectangle size is:

optimalRectSize = [Math.max(size1[0], size2[0]), Math.max(size1[1], size2[1])]