Exposé布局算法

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

您可以用以下方式包装物品

\n\n

\n
1. 无水平间隙
\n
2. 无垂直间隙
\n

\n\n

好吧，让我们打包，不要有垂直间隙。则水平间隙为：

\n\n

Gh = nrows * availRatio - ncolumns * itemRatio\n

\n\n

或写成N

\n\n

Gh = x * availRatio - N * itemRatio / x\n

\n\n

Gh 接近于 0

\n\n

x\xc2\xb2 = N * itemRatio / availRatio\nx = sqrt(N * itemRatio / availRatio)\n

\n\n

您必须检查 ceil(x) 和 Floor(x)，并且 y = Floor(N/x)

\n\n

无水平间隙的包装产量：

\n\n

y = sqrt(N * availRatio / itemRatio)\n

\n\n

您必须检查 ceil(y) 和 Floor(y)，并且 x = Floor(N/y)

\n\n

因此最多有 4 种组合来检查间隙。然后选择正间隙最小的那个。

\n\n

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

\n\n

您也可以使用最小区域来决定，而不是使用间隙，因为最后一行/列可能没有很好地填充。

\n