optimized grid for rectangular items

I have N rectangular items with an aspect ratio Aitem (X:Y).

I have a rectangular display area with an aspect ratio Aview

The items should be arranged in a table-like layout (i.e. r rows, c columns).

what is the ideal grid rows x columns, so that individual items are largest? (rows * colums >= N, of course - i.e. there may be "unused" grid places).

A simple algorithm could iterate over rows = 1..N, calculate the required number of columns, and keep the row/column pair with the 开发者_开发百科largest items.

I wonder if there's a non-iterative algorithm, though (e.g. for Aitem = Aview = 1, rows / cols can be approximated by sqrt(N)).

Note: I couldn't quite understand Frédéric's answer, so I worked the problem out myself and came up with what appears to be the same solution. I figured I might as well explain what I did in case it is helpful.

First I normalized the aspect ratio of the view to that of the items. (I'm assuming you don't want to rotate the items.)

a = (view_width/view_height) / (item_width/item_height)

Now packing a rectangle of width/height ratio a with squares is equivalent to packing the view with items. The ideal case would be for our grid (of squares now) to fill the rectangle completely, which would give us

a = c/r

where r and c are the numbers of rows and columns:

N = r*c

Multiplying/dividing these two equations gives us

N*a = c^2              N/a = r^2
c = sqrt(N*a)          r = sqrt(N/a)

If the grid is perfect, r and c will be integers, but if not, you have to try the three options Frédéric mentioned and keep the one where r*c is smallest but still more than N:

• floor(r), ceil(c)
• ceil(r), floor(c)
• ceil(r), ceil(c)

Your solution can be easily improved to handle the generic case :

If we (temporary) forget the need to have an integer number of rows and columns, we have

rows * columns = N

x = aitem * y

aview = rows * x = rows * aitem * y

1 = columns * y = (N/rows) * ( aview / [aitem*rows]) = N * aview /(aitem * rows²)

hence rows=sqrt(N *aview/aitem) and columns = N/rows = sqrt(N * aitem / aview)

Then ceil(rows) and ceil(columns) is a solution while floor(rows) and floor(columns) are too small to be a solution together (if rows and columns are not integers). This leaves 3 possible solutions :

• floor(rows) ceil(columns)
• ceil(rows) floor(columns)
• ceil(rows) ceil (columns)

edited to correct the equations. The first result was wrong (see comments)

Good question. If your view has dimensions A x B (fixed) and your items have dimensions a x b (variable, to be maximized), then you need:

trunc(A / a) * trunc(B / b) >= N

I have no idea how to solve this though - the trunc is the tricky part, as it's non-linear.

I wasn't able to get the answers to this question to work for me, but 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 }
}