使用缩放图 block 最大化矩形区域覆盖的算法

Question

我有 N 个可缩放的方形图 block (按钮)，它们需要放置在固定大小的矩形表面(工具箱)内。我想以相同的尺寸展示按钮。

我如何才能找到最佳尺寸的瓷砖，以提供被瓷砖覆盖的矩形表面的最大面积。

Answer 1

让W和 H是矩形的宽度和高度。

让s是正方形的边长。

然后是方格数n(s)您可以放入矩形的是 floor(W/s)*floor(H/s) .你想找到 s 的最大值为此 n(s) >= N

如果根据 s 绘制方 block 数你会得到一个分段常数函数。不连续点的值是 W/i和 H/j , 其中i和 j遍历正整数。

您想找到最小的 i为此 n(W/i) >= N ，同样最小的j为此 n(H/j) >= N .将这些最小值称为 i_min和 j_min .那么最大的W/i_min和 H/j_min是s你要的那个。

即s_max = max(W/i_min,H/j_min)

寻找i_min和 j_min ，只需进行强力搜索:对于每个，从 1 开始，测试并递增。

如果N很大，搜索i可能会令人反感的和j是从 1 开始的(尽管很难想象在性能上会有什么明显的差异)。在这种情况下，我们可以按如下方式估算起始值。首先，瓷砖面积的粗略估计是 W*H/N , 对应于 sqrt(W*H/N) 的一侧.如果W/i <= sqrt(W*H/N) , 然后 i >= ceil(W*sqrt(N/(W*H))) , 同样 j >= ceil(H*sqrt(N/(W*H)))

因此，与其在 i=1 开始循环和 j=1 , 我们可以在 i = ceil(sqrt(N*W/H)) 启动它们和 j = ceil(sqrt(N*H/W))) . OP 建议 round比 ceil 效果更好- 最坏的情况是额外的迭代。

这是用 C++ 拼写的算法:

#include <math.h>
#include <algorithm>
// find optimal (largest) tile size for which
// at least N tiles fit in WxH rectangle
double optimal_size (double W, double H, int N)
{
    int i_min, j_min ; // minimum values for which you get at least N tiles 
    for (int i=round(sqrt(N*W/H)) ; ; i++) {
        if (i*floor(H*i/W) >= N) {
            i_min = i ;
            break ;
        }
    }
    for (int j=round(sqrt(N*H/W)) ; ; j++) {
        if (floor(W*j/H)*j >= N) {
            j_min = j ;
            break ;
        }
    }
    return std::max (W/i_min, H/j_min) ;
}

以上是为了清楚起见而写的。代码可以大大收紧，如下所示:

double optimal_size (double W, double H, int N)
{
    int i,j ;
    for (i = round(sqrt(N*W/H)) ; i*floor(H*i/W) < N ; i++){}
    for (j = round(sqrt(N*H/W)) ; floor(W*j/H)*j < N ; j++){}
    return std::max (W/i, H/j) ;
}