算法与缩放瓷砖覆盖范围最大化矩形区域 [英] Algorithm for maximizing coverage of rectangular area with scaling tiles

问题描述

我有 N 可伸缩的广场砖（按钮）需要被放在固定大小的矩形表面（工具箱）内。我想对所有的按钮present在相同的尺寸。

I have N scalable square tiles (buttons) that need to be placed inside of fixed sized rectangular surface (toolbox). I would like to present the buttons all at the same size.

我怎么能解决了的瓦片，将提供矩形表面被覆盖的地砖面积最大的最佳尺寸。

推荐答案

让是W 和 ^ h 是宽度和高度的矩形

Let W and H be the width and height of the rectangle.

让取值是一个正方形的边长。

Let s be the length of the side of a square.

然后平方数 N（S），你可以融入矩形地板（W / S）*楼（H / S）。你想找到的最大值取值为其 N（S）＆GT; = N

Then the number of squares n(s) that you can fit into the rectangle is floor(W/s)*floor(H/s). You want to find the maximum value of s for which n(s) >= N

如果您绘制正方形对的数s ，你会得到一个分段常数函数。该间断的数值 W /我和 ^ h / J ，其中我和Ĵ通过正整数中运行。

If you plot the number of squares against s you will get a piecewise constant function. The discontinuities are at the values W/i and H/j, where i and j run through the positive integers.

您要查找的最小我为其 N（W / I）GT; = N ，和同样，最小的Ĵ为其 N（H / J）＆GT; = N 。把这些最小值 i_min 和 j_min 。然后，最大的 W / i_min 和 H / j_min 是取值你想要的。

You want to find the smallest i for which n(W/i) >= N, and similarly the smallest j for which n(H/j) >= N. Call these smallest values i_min and j_min. Then the largest of W/i_min and H/j_min is the s that you want.

即。 s_max = MAX（W / i_min，H / j_min）

要找到 i_min 和 j_min ，只是做了蛮力搜索：每个，从1日开始，测试和增量。

To find i_min and j_min, just do a brute force search: for each, start from 1, test, and increment.

在N是非常大的情况下，它可能是令人讨厌的搜索我和Ĵ记者从1开始（虽然它是很难想象会有任何性能上的显着差异）。在这种情况下，我们可以如下估算起始值。首先，瓷砖面积的大概估算 W * H / N ，相当于 A侧的sqrt（W * H / N） 。如果 W / I＆LT; =开方（W * H / N），然后 I＆GT; = CEIL（W * SQRT（N /（W * H））），同样 J＆GT; = CEIL（H * SQRT（N /（W * H）））

In the event that N is very large, it may be distasteful to search the i's and j's starting from 1 (although it is hard to imagine that there will be any noticeable difference in performance). In this case, we can estimate the starting values as follows. First, a ballpark estimate of the area of a tile is W*H/N, corresponding to a side of sqrt(W*H/N). If W/i <= sqrt(W*H/N), then i >= ceil(W*sqrt(N/(W*H))), similarly j >= ceil(H*sqrt(N/(W*H)))

所以，而不是启动环路的 I = 1 和 J = 1 ，我们可以开始他们 I = CEIL（开方（N * W / H））和 J = CEIL（开方（N * H / W）））。和OP表明，圆作品比 CEIL 更好 - 在最坏的一个额外的迭代。

So, rather than start the loops at i=1 and j=1, we can start them at i = ceil(sqrt(N*W/H)) and j = ceil(sqrt(N*H/W))). And OP suggests that round works better than ceil -- at worst an extra iteration.

下面是在C ++中阐述的算法：

Here's the algorithm spelled out in 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) ;
}

以上是为了清楚起见写的。在code可以收紧很大如下：

The above is written for clarity. The code can be tightened up considerably as follows:

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) ;
}

这篇关于算法与缩放瓷砖覆盖范围最大化矩形区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！