如何优化矩形布局

Question

我有动态数量的等比例和大小的矩形对象，我想在屏幕上以最佳方式显示它们。我可以调整对象的大小，但需要保持比例。

我知道屏幕尺寸是多少。

如何计算将屏幕划分为的最佳行数和列数以及将对象缩放到什么尺寸？

谢谢，

杰米。

Answer 1

假设所有矩形具有相同的尺寸和方向，并且不应更改。

让我们玩！

// Proportion of the screen
// w,h width and height of your rectangles
// W,H width and height of the screen
// N number of your rectangles that you would like to fit in

// ratio
r = (w*H) / (h*W)

// This ratio is important since we can define the following relationship
// nbRows and nbColumns are what you are looking for
// nbColumns = nbRows * r (there will be problems of integers)
// we are looking for the minimum values of nbRows and nbColumns such that
// N <= nbRows * nbColumns = (nbRows ^ 2) * r
nbRows = ceil ( sqrt ( N / r ) ) // r is positive...
nbColumns = ceil ( N / nbRows )

我希望我的数学是正确的，但这离你想要的不远；）

编辑：
比率与宽度和高度之间没有太大区别...

// If ratio = w/h
r = ratio * (H/W)

// If ratio = h/w
r = H / (W * ratio)

// If r1 = (w/h) and r2 = W/H
r = r1 / r2

然后您返回使用“r”来找出行和列使用了多少。

Answer 2

我喜欢的一种方法是使用面积的平方根：

让

r = 矩形数量

w = 显示宽度

h = 显示高度

那么，

A = (w * h) / r 是每个矩形的面积

，

L = sqrt(A) 是每个矩形的底长。

如果它们不是正方形，则只需相应相乘即可保持相同的比率。

做类似事情的另一种方法是只取矩形数量的平方根。这将为您提供网格的一维（即列数）：

C = sqrt(n) 是网格中的列数

，

R = n / C code> 是行数。

请注意，其中一个必须ceiling，另一个floor，否则您将截断数字并可能会错过一行。

Answer 3

杰米，我将“最佳行数和列数”解释为“有多少行和列将提供最大的矩形，与所需的比例和屏幕尺寸一致”。这是一种解释该解释的简单方法。

每个可能的选择（矩形的行数和列数）都会产生指定比例的矩形的最大可能尺寸。循环可能的选择并计算结果大小，在可能的解决方案空间上实现简单的线性搜索。下面是执行此操作的一些代码，使用 480 x 640 的示例屏幕和 3 x 5 比例的矩形。

def min (a, b)
  a < b ? a : b
end

screenh, screenw = 480, 640
recth, rectw = 3.0, 5.0
ratio = recth / rectw

puts ratio

nrect = 14

(1..nrect).each do |nhigh|
  nwide = ((nrect + nhigh - 1) / nhigh).truncate
  maxh, maxw = (screenh / nhigh).truncate, (screenw / nwide).truncate
  relh, relw = (maxw * ratio).truncate, (maxh / ratio).truncate
  acth, actw = min(maxh, relh), min(maxw, relw)
  area = acth * actw
  puts ([nhigh, nwide, maxh, maxw, relh, relw, acth, actw, area].join("\t"))
end

运行该代码会提供以下跟踪：

1 14 480 45 27 800 27 45 1215
2 7 240 91 54 400 54 91 4914
3 5 160 128 76 266 76 128 9728
4 4 120 160 96 200 96 160 15360
5 3 96 213 127 160 96 160 15360
6 3 80 213 127 133 80 133 10640
7 2 68 320 192 113 68 113 7684
8 2 60 320 192 100 60 100 6000
9 2 53 320 192 88 53 88 4664
10 2 48 320 192 80 48 80 3840
11 2 43 320 192 71 43 71 3053
12 2 40 320 192 66 40 66 2640
13 2 36 320 192 60 36 60 2160
14 1 34 640 384 56 34 56 1904

由此可以清楚地看出，4x4 或 5x3 布局将生成最大的矩形。同样清楚的是，矩形大小（作为行数的函数）在极端处最差（最小），在中间点处最佳（最大）。假设矩形的数量不多，您可以简单地用您选择的语言编写上面的计算代码，但一旦结果面积在上升到最大值后开始减少，就立即退出。

这是一个快速而肮脏的（但我希望，相当明显的）解决方案。如果矩形的数量变得足够大，您可以通过多种方式调整性能：

• 使用更复杂的搜索算法（划分空间并递归搜索最佳部分）
• 如果矩形的数量在程序期间不断增长，则 ，保留之前的结果并仅搜索附近的解，
• 应用一些微积分以获得更快、更精确但不太明显的公式。

Answer 4

这几乎与肯尼思的问题完全一样。他还将其写在他的博客上。

如果在一维上缩放比例以便包装正方形，则会出现同样的问题。

Answer 5

您提到的行和列表明您设想将矩形排列在网格中，可能有一些空格（例如底行的一些）未填充。假设情况是这样：

假设您缩放对象，使得（数量未知）n 的对象适合整个屏幕。现在

objectScale=screenWidth/(n*objectWidth)

假设有 N 个对象，因此将有

nRows = ceil(N/n)

几行对象（其中 ceil 是 Ceiling 函数)，它将占据

nRows*objectScale*objectHeight

垂直高度。我们需要找到n，并选择最小的n，使得该距离小于screenHeight。

由于存在上限函数，n 的简单数学表达式变得更加棘手。如果列数相当小，找到 n 的最简单方法可能就是循环增加 n 直到满足不等式。

编辑：我们可以从 for n 的上限开始循环

floor(sqrt(N*objectHeight*screenWidth/(screenHeight*objectWidth)))

，然后向下计算：然后在 O(sqrt(N)) 中找到解决方案。 O(1) 解决方案是假设

nRows = N/n + 1

或 采用

n=ceil(sqrt(N*objectHeight*screenWidth/(screenHeight*objectWidth)))

（Matthieu M. 的解决方案），但这些解决方案的缺点是 n 的值可能不是最优的。

当 N=0 和 N=1 且对象的长宽比满足 objectHeight/objectWidth > 时，会出现边框情况。 screenHeight/screenWidth - 这两个都很容易处理。