7

我有 N 个长宽比为 Aitem (X:Y) 的矩形项目。
我有一个长宽比 Aview 的矩形显示区域

项目应排列在类似表格的布局中（即 r 行，c 列）。

什么是理想的网格行 x 列，以便单个项目最大？（当然，行 * 列 >= N - 即可能存在“未使用”的网格位置）。

一个简单的算法可以遍历行 = 1..N，计算所需的列数，并保持行/列对与最大的项目。

不过，我想知道是否有非迭代算法（例如，对于 Aitem = Aview = 1，rows / cols 可以用 sqrt(N) 来近似）。

4

4 回答 4

5

注意：我不太明白 Frédéric 的回答，所以我自己解决了这个问题，并想出了似乎是相同的解决方案。我想我不妨解释一下我做了什么，以防万一。

首先，我将视图的纵横比标准化为项目的纵横比。（我假设您不想旋转这些项目。）

a = (view_width/view_height) / (item_width/item_height)

现在用正方形包装一个宽/高比的矩形a相当于用项目包装视图。理想的情况是我们的网格（现在的正方形）完全填充矩形，这会给我们

a = c/r

其中r和c是行数和列数：

N = r*c

乘/除这两个方程给我们

N*a = c^2              N/a = r^2
c = sqrt(N*a)          r = sqrt(N/a)

如果网格是完美的，r并且c是整数，但如果不是，则必须尝试 Frédéric 提到的三个选项，并保留r*c最小但仍大于的选项N：

  • floor(r), ceil(c)
  • ceil(r), floor(c)
  • ceil(r), ceil(c)
于 2010-03-19T22:24:09.317 回答
1

您的解决方案可以轻松改进以处理通用案例：

如果我们（暂时）忘记了需要整数行和列，我们有

行 * 列 = N

x = 项目 * y

aview = 行 * x = 行 * aitem * y

1 = 列 * y = (N/行) * (aview / [aitem*rows]) = N * aview /(aitem * rows²)

因此 rows=sqrt(N *aview/aitem) 和 columns = N/rows = sqrt(N * aitem / aview)

然后 ceil(rows) 和 ceil(columns) 是一个解决方案，而 floor(rows) 和 floor(columns) 太小而不能一起成为一个解决方案（如果行和列不是整数）。这留下了 3 种可能的解决方案：

  • 楼层（行） 天花板（列）
  • 天花板（行） 地板（列）
  • ceil（行） ceil（列）

编辑以更正方程式。第一个结果是错误的（见评论）

于 2010-03-19T11:29:28.130 回答
0

好问题。如果您的视图具有尺寸 A x B（固定）并且您的项目具有尺寸 axb（可变，要最大化），那么您需要：

trunc(A / a) * trunc(B / b) >= N

我不知道如何解决这个问题 - 截断是棘手的部分，因为它是非线性的。

于 2010-03-19T11:22:56.213 回答
0

我无法得到这个问题的答案来为我工作，但我找到了一个针对Neptilo的类似问题的简洁实现。但它不适用于矩形，仅适用于正方形。所以我应用mckeed的想法来规范化矩形，然后按照正方形的算法。

结果就是fitToContainer() 函数。给它适合的矩形数量n，containerWidthandcontainerHeight和原始的itemWidthand itemHeight。如果项目没有原始宽度和高度，请使用itemWidth和itemHeight指定项目的所需比例。

例如，fitToContainer(10, 1920, 1080, 16, 9)结果为{nrows: 4, ncols: 3, itemWidth: 480, itemHeight: 270}4 列和 3 行，大小为 480 x 270（像素，或任何单位）。

为了在 1920x1080 的相同示例区域中放置 10 个正方形，您可以调用fitToContainer(10, 1920, 1080, 1, 1)导致{nrows: 2, ncols: 5, itemWidth: 384, itemHeight: 384}.

function fitToContainer(n, containerWidth, containerHeight, itemWidth, itemHeight) {
    // We're not necessarily dealing with squares but rectangles (itemWidth x itemHeight),
    // temporarily compensate the containerWidth to handle as rectangles
    containerWidth = containerWidth * itemHeight / itemWidth;
    // Compute number of rows and columns, and cell size
    var ratio = containerWidth / containerHeight;
    var ncols_float = Math.sqrt(n * ratio);
    var nrows_float = n / ncols_float;

    // Find best option filling the whole height
    var nrows1 = Math.ceil(nrows_float);
    var ncols1 = Math.ceil(n / nrows1);
    while (nrows1 * ratio < ncols1) {
        nrows1++;
        ncols1 = Math.ceil(n / nrows1);
    }
    var cell_size1 = containerHeight / nrows1;

    // Find best option filling the whole width
    var ncols2 = Math.ceil(ncols_float);
    var nrows2 = Math.ceil(n / ncols2);
    while (ncols2 < nrows2 * ratio) {
        ncols2++;
        nrows2 = Math.ceil(n / ncols2);
    }
    var cell_size2 = containerWidth / ncols2;

    // Find the best values
    var nrows, ncols, cell_size;
    if (cell_size1 < cell_size2) {
        nrows = nrows2;
        ncols = ncols2;
        cell_size = cell_size2;
    } else {
        nrows = nrows1;
        ncols = ncols1;
        cell_size = cell_size1;
    }

    // Undo compensation on width, to make squares into desired ratio
    itemWidth = cell_size * itemWidth / itemHeight;
    itemHeight = cell_size;
    return { nrows: nrows, ncols: ncols, itemWidth: itemWidth, itemHeight: itemHeight }
}
于 2019-11-06T16:42:25.167 回答