Алгоритм компоновки Exposé

Я делаю что-то такое, что делает элементы похожими на то, что Mac OS X делает с окнами в Exposé. Он адаптируется к соотношению сторон элементов и соотношению сторон доступной области.

Обычно доступная область делится на строки и столбцы. В каждую ячейку помещается элемент (пересечение строки и столбца). Элементы должны сохранять свое соотношение сторон (здесь ширина / высота ), несмотря на соотношение сторон ячейки. Количество ячеек должно быть больше или равно количеству элементов. В случае, когда количество ячеек превышает количество элементов, последняя строка не будет использоваться полностью. Цель состоит в том, чтобы как можно больше доступной площади использовалось для предметов. Я почти уверен, что чем ближе соотношение сторон каждой ячейки к соотношению сторон элемента, тем лучше.

Следующее работает хорошо, когда доступная область ' s соотношение сторон равно соотношению сторон элементов:

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

Где: count - количество элементов; round (x) округляет x до ближайшего целого значения, округляя половину случаев от нуля; и потолок (x) возвращает наименьшее целое значение не меньше, чем x .

Я знаю, что Compiz использует следующий аналогичный алгоритм, но он не принимает во внимание соотношение сторон элементов и доступной области:

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

Где: floor (x) возвращает наибольшее целое значение, не превышающее x .

Я собрал следующие O (n) алгоритм, который проверяет каждую комбинацию строк и столбцов и ищет наиболее подходящую, но, безусловно, есть sa O (1), поскольку он дает точно такие же результаты, что и первый алгоритм (O (1)), когда пропорции элементов и доступная область одинаковы:

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);
}

Где: abs (x) возвращает абсолютное значение x .

ПРИМЕЧАНИЕ: вы можете заметить, что это не оптимизировано вообще

Итак, как лучше всего использовать наиболее доступную область для предметы как можно? (Другими словами, как мне найти наиболее подходящий вариант?)