algorithm – Maximum number of rectangles to fit in another rectangle

Question:

You are given a figure (A) of size M by N. Given a second figure (B), smaller, size K by L.

It is necessary to determine how many maximum B figures will fit in figure A. They should be located one next to another, part of the figures can be located vertically, the other part horizontally, in order to take up the maximum possible space in the main figure.

Someone can suggest something on this issue?


At the moment, I have thoughts only if:

count the number of rectangles located horizontally that will fit horizontally in the figure, that is, put a rectangle next to the second, fill in the line, then put another line from below, and so on to the very bottom.

Further on the right, there may be space. We check if the rectangle fits there vertically, if so, then fill the column with vertical rectangles.

As a result, we get a number – how many rectangles fit.

Then we repeat the same thing, only we initially place the rectangles vertically, and if there is space at the bottom, we check if the rectangles are placed there horizontally, if so, then fill the line. And again we count how much fits.

Of the two, by counting, we choose the one that gave the greatest result.

Here's the counting example I described, implemented in JavaScript:

function calcFigures(FigureA, FigureB) {
    var total1 = 0,
        total2 = 0;

    (function() {
        var figures_per_row = Math.floor(FigureA.width / FigureB.width),
            figures_per_col = Math.floor(FigureA.height / FigureB.height),
            invers_figures_per_row = 0,
            invers_figures_per_col = 0;

        if (FigureA.width - (figures_per_row * FigureB.width) >= FigureB.height) {
            invers_figures_per_row = Math.floor((FigureA.width - (figures_per_row * FigureB.width)) / FigureB.height);
            invers_figures_per_col = Math.floor(FigureA.height / FigureB.width);
        }

        total1 = (figures_per_row * figures_per_col) + (invers_figures_per_row * invers_figures_per_col);
    }());

    (function() {
        var figures_per_row = Math.floor(FigureA.width / FigureB.height),
            figures_per_col = Math.floor(FigureA.height / FigureB.width),
            invers_figures_per_row = 0,
            invers_figures_per_col = 0;

        if (FigureA.width - (figures_per_row * FigureB.height) >= FigureB.width) {
            invers_figures_per_row = Math.floor((FigureA.width - (figures_per_row * FigureB.height)) / FigureB.width);
            invers_figures_per_col = Math.floor(FigureA.height / FigureB.height);
        }

        total2 = (figures_per_row * figures_per_col) + (invers_figures_per_row * invers_figures_per_col);
    }());

    return Math.max(total1, total2);
}

Answer:

There are obvious estimates for the number R of rectangles KxL (K> = L) that can be placed inside the rectangle MxN (side M is below).

  1. If K = L, then F = (M mod K) * (N mod K).
  2. If K> L, then F> = max (F1, F2), where
    F1 = (M mod K) * (N mod L) + ((M% K) mod L) * (N mod K),
    F2 = (N mod K) * (M mod L) + ((N% K) mod L) * (M mod K).

The F1 estimate corresponds to the variant in which the left side of the large rectangle is laid to the maximum with the long side K along the side M, and the remaining right side is turned around.
The estimate F2 is obtained if the roles of the sides M and N are reversed.

In this case, the maximum estimate F is determined by the areas of the rectangles, i.e.
F <= MN mod KL.

PS Within the framework of these estimates, combinatorial search can be applied.
For example, in the case (5×5,3×2) 3 <= F <= 4, and you can search for the best styling using the following algorithm:
1) calculate the number of free cells with F = 4 (one cell);
2) set a cycle for all options for placing free cells (without taking into account symmetry – 25 options);
3) enumerate all the ways of placing figures (top to bottom, left to right, without a turn and with a turn), leaving no additional free cells (2 methods in the variant with a free central cell).

Scroll to Top