Exposé Layout Algorithm

Question

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, 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 this isn't optimized at all

So, what's the best way to have the most available area utilized by the items as possible? (In other words, how do I find the best fit?)

Answer 1

You can pack the items with

1. no horizontal gap
2. no vertical gap

Ok, let's pack without vertical gap. Then the horizontal gap is:

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 have to check ceil(x) and floor(x), and y = floor(N/x)

Packing without horizontal gap yields:

y = sqrt(N * availRatio / itemRatio)

You have to check ceil(y) and floor(y), and x = floor(N/y)

So there are up to 4 combinations to check for the gap. Then choose that 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 the gap you could also use the minimal area to decide, since the last row/column might be not filled very well.