Exposé Layout Algorithm

Question

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

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

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

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

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

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

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

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

Я собрал следующий алгоритм O (n), который проверяет каждую комбинацию строк и столбцов иищет наилучшее соответствие, но, безусловно, есть алгоритм 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.

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

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

Answer 1

Вы можете упаковать вещи с

1. нет горизонтального зазора
2. без вертикального зазора

Хорошо, давайте упаковывать без вертикального зазора. Тогда горизонтальный зазор будет:

Gh = nrows * availRatio - ncolumns * itemRatio

или написано с помощью N

Gh = x * availRatio - N * itemRatio / x

Gh близко к 0 в

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

Вы должны проверить ceil (x) и floor (x), а y = floor (N / x)

Упаковка без горизонтального зазора дает:

y = sqrt(N * availRatio / itemRatio)

Вы должны проверить ceil (y) и floor (y), а x = floor (N / y)

Таким образом, существует до 4 комбинаций для проверки пропуска. Затем выберите это с наименьшим положительным разрывом.

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

Вместо использования пробела вы также можете использовать минимальную область для принятия решения, поскольку последняя строка / столбец может быть заполнена не очень хорошо.