矩形内未知数字的最大平方大小

Question

如果我有一组可以是任意数字的瓷砖(正方形)并且它们要填充未知尺寸的容器(矩形),我如何计算出瓷砖的最大尺寸而不会有任何重叠.

所以如果我有2个瓷砖并且矩形是100*100那么最大瓷砖尺寸是50*50.如果这个尺寸的rectanlgle有3或4个瓷砖,这也是瓷砖的最大尺寸,这恰好恰好在这个例子中是一个正方形.

如果rectanlge是100*30并且我有2个瓷砖,则正方形的最大尺寸将是30*30,如果我有4个瓷砖,则最大尺寸将是25*25.

我怎样才能以编程方式执行此操作而不会通过遍历每个可能的组合来占用处理器.

---

我试着总结一下,我有一个:

矩形/边界框,我需要尽可能多地填充而不重叠瓷砖.

我知道矩形的高度和宽度(但这可以在运行时更改).

我有X个瓦片(这可以在运行时改变),这些是正方形.

没有一块瓷砖应该重叠,每块瓷砖的最大尺寸是多少.它们都是相同的大小.

Answer 1

这是一个包装问题.很难找到最佳解决方案.参见例如在正方形中包装N个方块.

您可以通过将总面积除以平方数来计算(乐观)上限:sqrt(width*height/n).

Answer 2

概念:

• 从1平方开始
• 对于每个额外的正方形,如果到目前为止您的网格框中没有空间,请将现有框缩小到足以为其他行或列腾出空间.

伪代码:给定M×N矩形以填充K个方块

// initial candidate grid within the rectangle
h=1
w=1
maxsquares=1
size=min(M,N) //size of the squares
while K > maxsquares
  if M/(h+1) >= N/(w+1)
    h=h+1
  else
    w=w+1
  endif
  maxsquares=h*w
  size=min(M/h,N/w)
done
print size

可能有更快的方法来跳转到非常大的K的答案,但我想不起它们.如果你知道M和N是整数,那么可能会有更快的方法.

Answer 3

这是一个没有循环的 O(1) 解决方案。

使用矩形的纵横比（高度/宽度），您可以对 x 和 y 方向的图块数量进行初步猜测。这给出了瓦片总数的上限和下限：在 xy 和 (x+1)(y+1) 之间。

基于这些界限，存在三种可能性：

1. 下界是正确的。计算将产生 xy 切片的最大 tileSize。
2. 上限是正确的。计算将导致 (x+1)(y+1) 瓦片的最大 tileSize
3. 正确答案介于上限和下限之间。求解方程以确定 x 和 y 的正确值，然后计算将导致正确瓷砖数量的最大 tileSize

int GetTileSize(int width, int height, int tileCount)
{
    // quick bailout for invalid input
    if (width*height < tileCount) { return 0; }

    // come up with an initial guess
    double aspect = (double)height/width;
    double xf = sqrtf(tileCount/aspect);
    double yf = xf*aspect;
    int x = max(1.0, floor(xf));
    int y = max(1.0, floor(yf));
    int x_size = floor((double)width/x);
    int y_size = floor((double)height/y);
    int tileSize = min(x_size, y_size);

    // test our guess:
    x = floor((double)width/tileSize);
    y = floor((double)height/tileSize);
    if (x*y < tileCount) // we guessed too high
    {
        if (((x+1)*y < tileCount) && (x*(y+1) < tileCount))
        {
            // case 2: the upper bound is correct
            //         compute the tileSize that will
            //         result in (x+1)*(y+1) tiles
            x_size = floor((double)width/(x+1));
            y_size = floor((double)height/(y+1));
            tileSize = min(x_size, y_size);
        }
        else
        {
            // case 3: solve an equation to determine
            //         the final x and y dimensions
            //         and then compute the tileSize
            //         that results in those dimensions
            int test_x = ceil((double)tileCount/y);
            int test_y = ceil((double)tileCount/x);
            x_size = min(floor((double)width/test_x), floor((double)height/y));
            y_size = min(floor((double)width/x), floor((double)height/test_y));
            tileSize = max(x_size, y_size);
        }
    }

    return tileSize;
}

我已经使用以下代码针对 1 到 1000 之间的所有整数宽度、高度和 tileCounts 测试了此函数：

for (width = 1 to 1000)
{
    for (height = 1 to 1000)
    {
        for (tileCount = 1 to 1000)
        {
            tileSize = GetTileSize(width, height, tileCount);

            // verify that increasing the tileSize by one
            // will result in too few tiles
            x = floor((double)width/(tileSize+1));
            y = floor((double)height/(tileSize+1));
            assert(x*y < tileCount);

            // verify that the computed tileSize actually
            // results in the correct tileCount
            if (tileSize > 0)
            {
                x = floor((double)width/tileSize);
                y = floor((double)height/tileSize);
                assert(x*y >= tileCount);
            }
        }
    }
}

Answer 4

我设法想出了一个“相对”最优的解决方案。部分基于扎克的伪代码答案。

        //total number of tiles
        var tile_count : Number = numberOfSlides;
        //height of rectangle
        var b : Number = unscaledHeight;
        //width of rectanlge
        var a : Number = unscaledWidth;

        //divide the area but the number of tiles to get the max area a tile could cover
        //this optimal size for a tile will more often than not make the tiles overlap, but
        //a tile can never be bigger than this size
        var maxSize : Number = Math.sqrt((b * a) / tile_count);
        //find the number of whole tiles that can fit into the height
        var numberOfPossibleWholeTilesH : Number = Math.floor(b / maxSize);
        //find the number of whole tiles that can fit into the width
        var numberOfPossibleWholeTilesW : Number = Math.floor(a / maxSize);
        //works out how many whole tiles this configuration can hold
        var total : Number = numberOfPossibleWholeTilesH * numberOfPossibleWholeTilesW;

        //if the number of number of whole tiles that the max size tile ends up with is less than the require number of 
        //tiles, make the maxSize smaller and recaluate
        while(total < tile_count){
            maxSize--;
            numberOfPossibleWholeTilesH = Math.floor(b / maxSize);
            numberOfPossibleWholeTilesW = Math.floor(a / maxSize);
            total = numberOfPossibleWholeTilesH * numberOfPossibleWholeTilesW;
        }

        return maxSize;

其作用是计算出矩形的总面积，然后除以所需的瓷砖数量。由于每个图块都是一个正方形，我可以对其进行平方，以便获得最佳图块的最大尺寸。

有了这个最佳尺寸，我然后检查宽度和高度可以容纳多少个整块瓷砖。将它们相乘，如果小于所需的图块数量，则减小最佳尺寸并再次执行检查，直到所有图块都适合矩形。

我可以通过执行诸如每次将最佳大小减少 -2 代替 -1 之类的操作来进一步优化此操作，然后如果所有图块都适合则增加 1，以确保我没有错过有效大小。或者我可以跳回超过-2，比如说-10，然后如果它们所有的瓷砖适合增加5，那么如果不适合减少-2等等，直到我得到最佳适合。

查看http://kennethsutherland.com/flex/stackover/SlideSorterOK.html我的示例。感谢您提供的所有各种信息。