Optimized grid for rectangular elements

Question

I have N rectangular elements with aspect ratio Aitem (X: Y).
I have a rectangular display area with aspect ratio Aview

Elements should be arranged in a table (for example, r rows, c columns).

what are the ideal row rows in the x columns so that the individual elements are the largest? (* colums> = N lines, of course - that is, there may be "unused" grid spaces).

A simple algorithm can iterate through the rows = 1..N, calculate the required number of columns and support a couple of rows / columns with the largest elements.

I wonder if there is a non-iterative algorithm (for example, for Aitem = Aview = 1, rows / columns can be approximated by sqrt (N)).

Answer 1

Note. I could not fully understand Frederick's answer, so I myself dealt with this problem and came up with something that looks like the same thing. I thought I could explain what I did if it would be helpful.

First, I normalized the aspect ratio of the view to the object. (I assume you do not want to rotate the elements.)

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

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

 a = c/r 

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

 N = r*c 

Multiplication / division of 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 need to try the three options mentioned by Frederick, and save the one where r*c smallest, but even more N

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

Answer 2

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

If we (temporarily) forget about 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²)

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

Then ceil (rows) and ceil (columns) are the solution, while the floor (rows) and the floor (columns) are too small to be a solution together (if the 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 equations. The first result was incorrect (see comments)

Answer 3

Good question. If your view has dimensions A x B (fixed) and your elements have dimensions axb (variable that should be maximum), you need to:

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

I have no idea how to solve this - trunc is the hard part because it is non-linear.