algorithm - 矩形项目的优化网格

Question

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

项目应该以类似表格的布局排列(即 r 行，c 列)。

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

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

不过，我想知道是否存在非迭代算法(例如，对于 Aitem = Aview = 1，行/列可以近似为 sqrt(N))。

Answer 1

注意:我不太理解 Frédéric 的回答，所以我自己解决了这个问题并提出了看似相同的解决方案。我想我不妨解释一下我所做的，以防有帮助。

首先，我将 View 的纵横比标准化为项目的纵横比。 (我假设您不想旋转项目。)

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

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

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)