根据n个项目，总面积和H：W比率创建最佳网格

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

我对您的某些输入参数尚不清楚，但我假设您具有Rectangle的高度和宽度，矩形的数量以及理想的高宽比（即首选gridheight / gridwidth）。

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

因此，根据定义，每个矩形的面积为1，因此我们的总面积为N，其中N是项数。然后，我们可以通过说gridHeight * gridWidth = N和gridHeight / gridWidth = K

来近似我们的高度添加宽度，以给出自己首选的网格长宽比。

有了这些，我们得到gridHeight = sqrt（KN）和gridWidth = sqrt（N / K）。

[如果您将其中一项四舍五入为合适的整数（我不确定四舍五入后的整数是否会为您带来最佳效果，或者无论哪一项四舍五入都会给该值带来最小的百分比变化，最好-如果您非常在意，可以随时尝试全部四个步骤）。一旦有了一个整数值，便可以通过找到可以乘以另一个且仍大于N的最小整数来计算另一个值，以确保适合网格中的所有矩形。]

您当然可以通过将高度乘以rectHeight，将wdith乘以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 x2180。缩小以适合768x1024意味着将两者都除以2.129（1500/768和2180/1024中的较大者）。因此，您的图片将按比例缩小2.129倍，达到141x51（ish），实际使用的总面积为705x1020，应留出最少的空白。

希望现在更有意义。我承认，我几次错误地提出了真正的价值观，所以我完全理解您为什么想要一个可行的例子。 ;-）

Answer 2

所以我认为我有一种算法可以通过蛮力获得最佳答案。最多100-1000个项目仍应相当快。这是python中的算法。它基本上是通过所有方式将项目散布到行和列中，然后选择效率最高的方法进行迭代。

def calculate_best_screen_packing(N, img_resolution = (800,600), screen_resolution = (1920, 1080)):    
    screen_x = screen_resolution[0]
    screen_y = screen_resolution[1]
    screen_area = screen_x * screen_y

    img_x = img_resolution[0]
    img_y = img_resolution[1]
    img_aspect = img_x / img_y

    best_dims = (None,None)
    best_eff = 0.0

    for n_rows in range(1,N//2 +1):
        #print(i)
        n_cols = N // n_rows
        if N % n_rows != 0: n_cols = n_cols+1

        #print(n_rows, n_cols)

        # Test by maximising image height        
        img_y_scaled = screen_y / n_rows
        img_x_scaled = img_y_scaled * img_aspect
        img_area_scaled = img_x_scaled * img_y_scaled
        eff = img_area_scaled * N / screen_area
        #print(img_x_scaled, img_y_scaled, eff)

        if eff <= 1.0 and eff > best_eff:
            best_eff = eff
            best_dims = (n_rows, n_cols)

        # Test by maximising image width                
        img_x_scaled = screen_x / n_cols
        img_y_scaled = img_x_scaled / img_aspect
        img_area_scaled = img_x_scaled * img_y_scaled
        eff = img_area_scaled * N / screen_area
        #print(img_x_scaled, img_y_scaled, eff)
        if eff <= 1.0 and eff > best_eff:
            best_eff = eff
            best_dims = (n_rows, n_cols)

    #print("Best dims:",best_dims,best_eff)
    return best_dims