Exposé Layout Algorithm

Question

I am doing something that lays out elements similar to what Mac OS X does with windows in Exposé. It adapts to the aspect ratio of the elements and the aspect ratio of the accessible area.

In principle, the available area is divided into rows and columns. An element is placed in each cell (the intersection of a row and a column). Elements must maintain 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 elements. In the case where the number of cells is greater than the number of elements, the last row will not be fully used. The goal is to have as much as possible accessible area used by the elements. I am sure that the closer the aspect ratio of each cell to the aspect ratio of the element, the better.

The following works well when the aspect ratio of the available area is equal to the proportions of the elements:

 rows := round(sqrt(count)); columns := ceiling(sqrt(count)); 

Where: count - the number of elements; round(x) rounds x to the nearest integer value, rounding half the cases from zero; and ceiling(x) returns the smallest integer value of at least x .

I know that Compiz uses the following similar algorithm, but it does not take into account the proportion of elements and the available area:

 rows := floor(sqrt(count + 1)); columns := ceiling(count / rows); 

Where: floor(x) returns the largest integer value of at most x .

I put together the following O (n) algorithm, which checks every combination of rows and columns and looks for the best match, but certainly there is O (1) algorithm, since it gives exactly the same results as the first (O (1)), when the proportions of the elements and the available area are the same:

 fit (itemCount, itemRatio, availableRatio) { bestRows := infinity; bestColumns := infinity; bestDiff := infinity; for (rows := 1; rows <= count; rows += 1) { columns := ceiling(count / rows); cellWidth := availableRatio / columns; cellHeight := 1.0 / rows; cellRatio := cellWidth / cellHeight; diff := abs(cellRatio - itemRatio); if (diff < bestDiff) { bestRows := rows; bestColumns := columns; bestDiff := diff; if (diff = 0) break; } } return (bestRows, bestColumns); } 

Where: abs(x) returns the absolute value of x .

NOTE. You may notice that this is not optimized at all.

So what is the best way to use the most accessible area used by the elements as much as possible? (In other words, what is the best way for me to approach?)

Answer 1

You can pack the items with

• lack of horizontal clearance
• no vertical gap

Ok, let the package be without vertical clearance. Then the horizontal clearance:

 Gh = nrows * availRatio - ncolumns * itemRatio 

or written with N

 Gh = x * availRatio - N * itemRatio / x 

Gh is close to 0 at

 x² = N * itemRatio / availRatio x = sqrt(N * itemRatio / availRatio) 

You should check ceil (x) and gender (x), and y = gender (N / x)

Packaging without horizontal clearance gives:

 y = sqrt(N * availRatio / itemRatio) 

You should check ceil (y) and gender (y), and x = gender (N / y)

Thus, there can be up to 4 combinations for checking a space. Then select it with the smallest positive gap.

 fit (itemCount, itemRatio, availableRatio) { x := sqrt(itemcount * itemRatio / availableRatio); x1 := floor(x); y1 := ceil(itemCount / x1); x2 := ceil(x); y2 := ceil(itemCount / x2); y := sqrt(itemcount * availableRatio / itemRatio); y3 := floor(x); x3 := ceil(itemCount / y3); y4 := ceil(x); x4 := ceil(itemCount / y4); gap := y1 * availableRatio - x1 * itemRatio; x := x1; y := y1; gap2 := y2 * availableRatio - x2 * itemRatio; if (gap2 >= 0 && gap2 < gap || gap < 0) { gap := gap2; x := x2; y := y2; } gap3 := x3 * itemRatio / availRatio - y3; if (gap3 >= 0 && gap3 < gap || gap < 0) { gap := gap3; x := x3; y := y3; } gap4 := x4 * itemRatio / availRatio - y4; if (gap4 >= 0 && gap4 < gap || gap < 0) { gap := gap4; x := x4; y := y4; } return (x, y); } 

Instead of using a space, you can also use a minimal area to solve, since the last row / column may not be filled very well.