曝光布局算法

Question

我正在制作一些类似于Mac在Exposé中使用windows所做的东西。它适应项目的高宽比和可用面积的高宽比。

基本上，可用区域被划分为行和列。在每个单元格中放置一个项(行和列的交集)。项目必须保持其纵横比(此处为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)

你必须检查赛尔(X)和地板(X)，而y=地板(N/x)

无水平间隙的包装产量：

y = sqrt(N * availRatio / itemRatio)

你必须检查赛尔(Y)和地板(Y)，以及x=地板(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);
}

与其使用间隙，您还可以使用最小的区域来决定，因为最后一行/列可能不是很好地填充。