代码之家 › 专栏 › 技术社区 › peterchen

矩形项目的优化网格

mathematical-optimization layout math algorithm

4

peterchen · 技术社区 · 15 年前

我有n个长宽比为aitem(x:y)的矩形项。
我有一个长宽比视图的矩形显示区域

项目应按类似表格的布局排列(即R行、C列)。

理想的网格行x列是什么,以便单个项最大? (行*colums>=n,当然-也就是说,可能存在“未使用”的网格位置)。

一个简单的算法可以迭代行=1..n,计算所需的列数,并将行/列对与最大的项保持在一起。

我想知道是否有一个非迭代算法(例如,对于aitem=aview=1,行/列可以用sqrt(n)来近似)。

3 回复 | 直到 15 年前

1

2

mckeed 15 年前

注:我不太明白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 将是整数,但如果不是,您必须尝试上述三个选项,并保留其中一个 r*c 最小但仍大于 N :

2

1

Frédéric Grosshans 15 年前

您的解决方案可以很容易地改进以处理一般情况:

如果我们(临时的)忘记了行和列的整数的需要,我们有

行*列=n

x= aTy*y

aview=行*x=行*aitem*y

1=列*Y=(n/行)*(aview/[aitem*行])=n*aview/(aitem*行2;)

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

然后,CEIL(行)和CEIL(列)是一个解决方案,而floor(行)和floor(列)太小,不能一起成为解决方案(如果行和列不是整数)。这留下了3个可能的解决方案:

编辑修正方程式。第一个结果是错误的(见注释)

3

0

Paul R 15 年前

问得好。如果视图的尺寸为A x B(固定),而项目的尺寸为A x B(可变,要最大化),则需要:

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

不过,我不知道如何解决这个问题——TRUC是一个棘手的部分,因为它是非线性的。