Calculate resizing factor for N small rectangles inside a large rectangle to cover maximum area

Question

I have a variable number of small rectangles which are natively 39 x 83 (width by length).

I will also have an arbitrary sized, container rectangle that I need to fit all of the smaller rectangles into. I can resize the small rectangles but I must preserve their aspect ratio and they must all be the same size as each other.

The goal is to resize them such that I cover the maximum possible area of the container rectangle. The small rectangles can not overlap each other or extend outside of the container rectangle.

I feel like this should be a straightforward problem well within my capability of solving - but after struggling with it for 2 days, consulting with my grade 9 son and performing a couple of dozen Google searches, I’m ready to ask for help.

What is the correct way to approach this problem?

Answer 1

I will assume all the small rectangles have to have the same orientation. It is already hard and I give a thought if this is not true at the end. Let the bounding rectangle be $W \times H$. We are trying to choose a scale factor $s$ for the $39 \times 83$ rectangles that is as large as possible so that we can fit $N$ scaled rectangles in the bounding one.

Assuming the small rectangles have to have the same orientation means the optimum tiling is rectangular. We just have to choose the orientation of the small rectangles and the number that fit across the width.

As a first cut, assume the small rectangles are oriented with the long axis horizontal. They are then $83s$ wide and $39s$ tall, so we get $\lfloor \frac W{83s} \rfloor$ rectangles horizontally and $\lfloor \frac H{39s}\rfloor$ vertically. We need $\lfloor \frac W{83s} \rfloor\lfloor \frac H{39s}\rfloor\ge N$ for the proper number to fit. We start by ignoring the floor signs, so we can find $s=\sqrt{\frac {WH}{83\cdot 39 N}}$. This just expresses the fact that the small rectangles have to have less area than the large one, ignoring any problems about whether they fit.

At this point you will only succeed if $\frac W{83s}$ and $\frac H{39s}$ are integers, so the outer rectangle is completely filled. You are lucky-declare victory! If not, you have an approximation $n=\frac W{83s}$ to the number of small rectangles you want horizontally. If you place $m$ rectangles horizontally, you need $k=\lceil \frac Nm \rceil$ rows. You can compute the scale factors in each direction as $\frac W{83m}$ and $\frac H{39k}$. Take the lower of these. Now search for the best $m$, which will be near the $n$ we computed above, based on finding the largest scale factor.

Repeat the process for the other orientation of the small rectangles, exchanging $39$ and $83$ and you have the answer under these restrictions.

If you don't insist that the small rectangles have the same orientation, you have one more degree of freedom. You can split $N$ into $N=K+M$ and have $K$ small rectangles in vertical orientation and $M$ in horizontal orientation. You want either the heights or the widths of the two rectangles to be close, but there is more searching to do.

Answer 2

I found a neat implementation to a similar question from Neptilo. It didn't work for rectangles though, only squares. So I applied the idea from mckeed to normalise the rectangle and then follow the algorithm for squares.

The result is the fitToContainer() function. Give it the number of rectangles to fit n, the containerWidth and containerHeight and the original itemWidth and itemHeight. In case items have no original width and height, use itemWidth and itemHeight to specify the desired ratio of the items.

For example fitToContainer(10, 1920, 1080, 16, 9) results in {nrows: 4, ncols: 3, itemWidth: 480, itemHeight: 270}, so four columns and 3 rows of 480 x 270 (pixels, or whatever the unit is).

And to fit 10 squares in the same example area of 1920x1080 you could call fitToContainer(10, 1920, 1080, 1, 1) resulting in {nrows: 2, ncols: 5, itemWidth: 384, itemHeight: 384}.

function fitToContainer(n, containerWidth, containerHeight, itemWidth, itemHeight) {
    // We're not necessarily dealing with squares but rectangles (itemWidth x itemHeight),
    // temporarily compensate the containerWidth to handle as rectangles
    containerWidth = containerWidth * itemHeight / itemWidth;
    // Compute number of rows and columns, and cell size
    var ratio = containerWidth / containerHeight;
    var ncols_float = Math.sqrt(n * ratio);
    var nrows_float = n / ncols_float;

    // Find best option filling the whole height
    var nrows1 = Math.ceil(nrows_float);
    var ncols1 = Math.ceil(n / nrows1);
    while (nrows1 * ratio < ncols1) {
        nrows1++;
        ncols1 = Math.ceil(n / nrows1);
    }
    var cell_size1 = containerHeight / nrows1;

    // Find best option filling the whole width
    var ncols2 = Math.ceil(ncols_float);
    var nrows2 = Math.ceil(n / ncols2);
    while (ncols2 < nrows2 * ratio) {
        ncols2++;
        nrows2 = Math.ceil(n / ncols2);
    }
    var cell_size2 = containerWidth / ncols2;

    // Find the best values
    var nrows, ncols, cell_size;
    if (cell_size1 < cell_size2) {
        nrows = nrows2;
        ncols = ncols2;
        cell_size = cell_size2;
    } else {
        nrows = nrows1;
        ncols = ncols1;
        cell_size = cell_size1;
    }

    // Undo compensation on width, to make squares into desired ratio
    itemWidth = cell_size * itemWidth / itemHeight;
    itemHeight = cell_size;
    return { nrows: nrows, ncols: ncols, itemWidth: itemWidth, itemHeight: itemHeight }
}