I'm making something which lays items out similar to what Mac OS X does with windows in Exposé. It adapts to the aspect ratio of the items and the aspect ratio of the available area.
Basically, the available area is divided up into rows and columns. An item is put in each cell (the intersection of a row and column). The items must maintain their aspect ratio (here width / height) despite the aspect ratio of the cell. The number of cells must be greater than or equal to the number of items. In the case where the number of cells is greater than the number of items, the last row will not be fully utilized. The goal is to have as much of the available area utilized by items as possible. I'm pretty sure the closer each cell's aspect ratio is to the item's aspect ratio, the better.
The following works well when the available area's aspect ratio is equal to the items' aspect ratios:
rows := round(sqrt(count));
columns := ceiling(sqrt(count));
Where: count is the number of items; round(x) rounds x to nearest integral value, rounding halfway cases away from zero; and ceiling(x) returns the smallest integral value not less than x.
I know Compiz uses the following similar algorithm, but it doesn't take into account the aspect ratios of the items and available area:
rows := floor(sqrt(count + 1));
columns := ceiling(count / rows);
Where: floor(x) returns the largest integral value not greater than x.
I put together the following O(n) algorithm which tests every combination of rows and columns and looks for the best fit, but surely there's a O(1) algorithm since this produces exactly the same results as the first (O(1)) algorithm when the aspect ratios of the items and available area are the same:
fit (itemCount, itemRatio, ava