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 :
edited to correct the equations. The first result was wrong (see comments)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With