optimized grid for rectangular items

Question

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

Accepted Answer

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

optimized grid for rectangular items

Solution

Problem