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

I have N需要放置在固定大小的矩形表面（工具箱）内的可扩展方形图块（按钮）。我想以相同的尺寸呈现所有按钮。

我怎样才能解决瓷砖的最佳尺寸，以提供被瓷砖覆盖的矩形表面的最大面积。

Let W and H是矩形的宽度和高度。

Let s是正方形的边长。

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

如果你绘制方格数s你将得到一个分段常数函数。不连续性位于值处W/i and H/j, where i and j遍历正整数。

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

I.e. s_max = max(W/i_min,H/j_min)

To find i_min and j_min，只需进行强力搜索：对于每个，从 1 开始，测试并递增。

如果 N 很大，则搜索可能会令人不快。i's and j从1开始（虽然很难想象性能会有什么明显的差异）。在这种情况下，我们可以如下估计起始值。首先，对瓷砖面积的大致估计是W*H/N，对应于一侧sqrt(W*H/N). If W/i <= sqrt(W*H/N), then i >= ceil(W*sqrt(N/(W*H)))， 相似地j >= ceil(H*sqrt(N/(W*H)))

所以，不要开始循环i=1 and j=1，我们可以从以下位置开始：i = ceil(sqrt(N*W/H)) and 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) ;
}