algorithm - 根据 n 项、总面积和 H :W ratio 创建最优网格

Question

我正在创建一个应用程序，它采用许多大小相同的矩形并将它们放置在屏幕上的网格中。我已经完成了调整单元格内矩形大小和居中矩形的大部分逻辑，但我在定义矩形必须符合的网格的实际部分时遇到了问题。

理想情况下，最终我会得到这样的函数(伪代码):

function getGridDimensions (rect surface, int numItems, float hwRatio) {
    // do something to determine grid-height and grid-width
    return gridDimensions;
}

我最初的尝试涉及这样的事情:

gridHeight = surface.width / sqrt(numItems);
gridWidth = surface.height / sqrt(numItems);

如果我的项目都是完美的正方形，这会很好地工作，但由于它们是矩形，每个单元格中都有很多未使用的空白区域。

Google 有任何想法或条款可以为我指明正确的方向吗？

Answer 1

我不太清楚你的一些输入参数，但我假设你有矩形的高度和宽度、矩形的数量和理想的高宽比(即首选网格高度/网格宽度)。

如果是这种情况，那么我可能会从“规范化”您的尺寸开始，因此为了以下计算的目的，我们说宽度单位与矩形的宽度相同，同样对于宽度单位高度。如果以实际单位表示的高/宽比为 k，则以矩形单位表示的高/宽比将为 k*RectWidth/RectHeight。我将其称为 K。

现在每个矩形的面积都为 1，所以我们的总面积为 N，其中 N 是项目的数量。然后我们可以通过说 gridHeight*gridWidth = N 和 gridHeight/gridWidth = K

通过这些我们得到 gridHeight = sqrt(KN) 和 gridWidth = sqrt(N/K)。

如果您将其中一个四舍五入为一个合适的整数(我不确定四舍五入的整数中最接近的那个是否会给您最好的结果，或者无论哪个四舍五入都会给出该值的最小百分比变化是最好的- 如果你很在意，你可以随时尝试所有四种)。一旦你有了一个整数值，你就可以通过找到可以与另一个相乘并且仍然大于 N 的最小整数来计算另一个，以确保你适合网格中的所有矩形)。

然后，您当然可以通过将高度乘以 rectHeight 并将宽度乘以 RectWidth 将整数值更改回实数。

希望一切都有意义。 :)

编辑工作示例:

所需的最终网格纵横比 = 1024/768 (k)(假设 768 是宽度，1024 是高度 - 我一直想把它作为标准屏幕分辨率反过来:))

“标准化”纵横比 = (1024/768) * (300/109) = 3.6697 (K)

因此网格高度为 sqrt(KN) = sqrt(366.97) = 19.16

网格宽度为 sqrt(N/K) = 5.22

从这里我们可以直观地看出，宽度 5 和高度 20 将是​​我们的最佳匹配。其他选项可能是 6 和 19。但这会浪费更多空间(我认为实际上最小化宽度和高度的乘积可能是最好的计算方法，但我不确定)。

现在这是我们的单元格网格大小。然后将其放大到 1500 x 2180 的像素尺寸。缩小以适应 768x1024 意味着将两者除以 2.129(1500/768 和 2180/1024 中的较大者)。因此，您的图像将缩小 2.129 倍至 141x51(ish)，而您使用的总面积实际上为 705x1020，这应该提供最少的空白。

希望现在更有意义。我承认，我在输入实际值时出错了几次，所以我完全理解你为什么想要一个有效的例子。 ;-)