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)) item的纵横比和可用区域相同时的算法:

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

除了使用间隙，您还可以使用最小面积来决定，因为最后一行/列可能没有很好地填充。