利用缩放瓦片最大化矩形区域覆盖的算法

Question

我有N可伸缩的方形瓷砖(按钮),需要放在固定大小的矩形表面(工具箱)内.我想以相同的尺寸呈现按钮.

我怎样才能解决瓷砖的最佳尺寸,这将提供瓷砖覆盖的矩形表面的最大区域.

Answer 1

设W和H是近似长方形的宽度和高度.

我们s是一个正方形的边长.

然后n(s)你可以适应矩形的方格数floor(W/s)*floor(H/s).你想找到的最大值s为这n(s) >= N

如果你绘制正方形的数量,s你将获得一个分段常数函数.不连续性处于值,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非常大,从1开始搜索i's和j's 可能会令人反感(虽然很难想象性能会有明显的差异).在这种情况下,我们可以如下估计起始值.首先,瓷砖面积的球场估计是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) ;
}

Answer 2

我相信这可以作为约束最小化问题来解决,这需要一些基本的微积分..

定义:

a, l -> rectangle sides
   k -> number of squares
   s -> side of the squares

你必须最小化功能:

   f[s]:= a * l/s^2 - k

受限制:

  IntegerPart[a/s] IntegerPart[l/s] - k >= 0
  s > 0

我编写了一个Mathematica函数来编写这个技巧

  f[a_, l_, k_] :=  NMinimize[{a l/s^2 - k , 
                               IntegerPart[a/s] IntegerPart[l/s] - k >= 0, 
                               s > 0}, 
                               {s}]     

由于方程与上述相同,因此易于阅读.

使用这个功能,我组成了一个分配6个方格的表

据我所知,结果是正确的.

正如我所说,您可以为您的环境使用标准的微积分包,或者您也可以开发自己的最小化算法和程序.如果您决定使用最后一个选项,请按铃,我会提供一些好的指示.

HTH!

编辑

为了好玩,我用结果制作了一个情节.

对于31块瓷砖:

编辑2:特征参数

该问题有三个特征参数:

1. 瓷砖的结果大小
2. 瓷砖数量
3. 包围矩形的比率l/a

Perhaps the last one may result somewhat surprising, but it is easy to understand: if you have a problem with a 7x5 rectangle and 6 tiles to place, looking in the above table, the size of the squares will be 2.33. Now, if you have a 70x50 rectangle, obviously the resulting tiles will be 23.33, scaling isometrically with the problem.

So, we can take those three parameters and construct a 3D plot of their relationship, and eventually match the curve with some function easier to calculate (using least squares for example or computing iso-value regions).

Anyway, the resulting scaled plot is: