矩形内未知数的最大正方形尺寸

Question

如果我有一组可以是任意数量的图块（正方形），并且它们要填充未知大小的容器（矩形），我如何计算出图块的最大尺寸而不使它们重叠。

因此，如果我有 2 个图块且矩形为 100 * 100，则最大图块尺寸为 50 * 50。如果此大小的矩形有 3 或 4 个图块，这也将是图块的最大尺寸，而这种情况恰好发生在这个例子中是一个正方形。

如果矩形是 100 * 30 并且我有 2 个图块，则正方形的最大尺寸将为 30 * 30，如果我有 4 个图块，则最大尺寸将为 25 * 25。

如何以编程方式执行此操作而不占用处理器尝试每一种可能的组合。

---

我试着总结得更好一些 我有一个：

矩形/边界框，我需要在不重叠瓷砖的情况下尽可能多地填充它。

我知道矩形的高度和宽度（但这可能在运行时改变）。

我有 X 个图块（这可以在运行时更改），这些是正方形。

任何图块都不应重叠，每个图块的最大尺寸是多少。 它们的尺寸都相同。

Answer 1

从概念上讲：

• 从 1 个正方形开始
• 对于每个额外的正方形，如果您没有
  到目前为止，你的网格框中的空间，缩小
  现有的盒子足以制作
  额外的行或列的空间。

伪代码：给定 M x 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 2

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

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

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

1. 下限是正确的。 计算将产生 xy 图块的最大图块大小。
2. 上限是正确的。 计算将产生 (x+1)(y+1) 个图块的最大图块大小
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 3

这是一个包装问题。 最佳解决方案很难找到。 例如，请参阅将 N 个正方形打包在一个正方形中。

您可以通过将总表面积除以正方形数量来计算（乐观）上限：sqrt(width*height/n)。

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我的例子。
感谢您提供的所有各种信息。

Answer 5

以下函数计算给定信息的最大尺寸图块。

如果它是用 Python 编写的，这让您难以理解，请在评论中告诉我，我会尝试用其他语言来完成它。

import math
from __future__ import division

def max_tile_size(tile_count, rect_size):
    """
    Determine the maximum sized tile possible.

    Keyword arguments:
    tile_count -- Number of tiles to fit
    rect_size -- 2-tuple of rectangle size as (width, height)
    """

    # If the rectangle is taller than it is wide, reverse its dimensions
    if rect_size[0] < rect_size[1]:
        rect_size = rect_size[1], rect_size[0]

    # Rectangle aspect ratio
    rect_ar = rect_size[0] / rect_size[1]

    # tiles_max_height is the square root of tile_count, rounded up
    tiles_max_height = math.ceil(math.sqrt(tile_count))

    best_tile_size = 0

    # i in the range [1, tile_max_height], inclusive
    for i in range(1, tiles_max_height + 1):

        # tiles_used is the arrangement of tiles (width, height)
        tiles_used = math.ceil(tile_count / i), i

        # tiles_ar is the aspect ratio of this arrangement
        tiles_ar = tiles_used[0] / tiles_used[1]

        # Calculate the size of each tile
        # Tile pattern is flatter than rectangle
        if tile_ar > rect_ar:
            tile_size = rect_size[0] / tiles_used[0]
        # Tile pattern is skinnier than rectangle
        else:
            tile_size = rect_size[1] / tiles_used[1]

        # Check if this is the best answer so far
        if tile_size > best_tile_size:
            best_tile_size = tile_size

    return best_tile_size

print max_tile_size(4, (100, 100))

该算法可以大致描述如下：

• 如果矩形的高度大于宽度，则翻转它，使其宽度大于高度。
• 计算s，即图块数量的平方根，向上舍入。 （在代码中命名为 tiles_max_height。）
• 循环，其中 i 从 1 到 s（含）：
  • 构造一个方格网格，其宽度为块数 / i 方格、高 i 方格。 （将所有内容四舍五入。这会“填充”缺少的图块，例如当您的图块总数为 3 时，使用 2 个图块乘 2 个图块。）
  • 使这个网格尽可能大。 （使用纵横比来计算。）确定一个图块的大小。
  • 使用该尺寸确定图块覆盖的总面积。
  • 检查这是否是迄今为止最好的总面积； 如果是，则存储正方形大小
• 返回该正方形大小

这可能是此处列出的更快的算法之一，因为它计算 n 的最佳正方形大小 O(sqrt(n)) 瓷砖。

---

更新

经过进一步考虑，这个问题在上面的解决方案的基础上有了更简单的解决方案。 假设你有 30 块瓷砖。 您可能的图块排列很容易计算：

• 30 x 1（纵横比 30.0000）
• 15 x 2（纵横比 7.5000）
• 10 x 3（纵横比 3.3333）
• 8 x 4（纵横比 2.0000）
• 6 x 5（纵横比 1.2000）
• 6 x 6（纵横比 1.0000）

假设您的矩形为 100 x 60。您的矩形的纵横比为 1.6667。 该值介于 1.2 和 2 之间。现在，您只需计算 8 x 4 和 6 x 5 排列的图块大小。

不过，从技术上讲，第一步仍然需要 O(sqrt(n))，因此这个更新的方法并不比第一次尝试渐近更快。

---

评论区的一些更新

/*
Changes made:

tiles_used -> tiles_used_columns, tiles_used_rows
    (it was originally a 2-tuple in the form (colums, rows))
*/

/* Determine the maximum sized tile possible. */
private function wesleyGetTileSize() : Number {
    var tile_count : Number = slideCount.value;
    var b : Number = heightOfBox.value;
    var a : Number = widthOfBox.value;
    var ratio : Number;    

    // // If the rectangle is taller than it is wide, reverse its dimensions    

    if (a < b) {
        b = widthOfBox.value;
        a = heightOfBox.value;
    } 

    // Rectangle aspect ratio   
    ratio = a / b;    

    // tiles_max_height is the square root of tile_count, rounded up    
    var tiles_max_height : Number = Math.ceil(Math.sqrt(tile_count))    
    var tiles_used_columns : Number;
    var tiles_used_rows : Number;
    var tiles_ar : Number;
    var tile_size : Number;

    var best_tile_size : Number = 0;    

    // i in the range [1, tile_max_height], inclusive   
    for(var i: Number = 1; i <= tiles_max_height + 1; i++) {       
        // tiles_used is the arrangement of tiles (width, height)        
        tiles_used_columns = Math.ceil(tile_count / i);   
        tiles_used_rows = i;

        // tiles_ar is the aspect ratio of this arrangement        
        tiles_ar = tiles_used_columns / tiles_used_rows;        

        // Calculate the size of each tile        
        // Tile pattern is flatter than rectangle       
        if (tiles_ar > ratio){           
            tile_size = a / tiles_used[0]   ;
        }    
        // Tile pattern is skinnier than rectangle        
        else {            
            tile_size = b / tiles_used[1];
        }        
        // Check if this is the best answer so far        
        if (tile_size > best_tile_size){           
            best_tile_size = tile_size;
        }   
    }

    returnedSize.text = String(best_tile_size);
    return best_tile_size;
}

Answer 6

您能详细说明一下您如何定义填充吗？ 如果我按照你的描述（大如果），似乎你描述的许多情况实际上并没有填充矩形。 例如，您说 100*100 矩形中的 2 个正方形将是 50*50。 如果我正确理解你的配置，它们将被放置在这个矩形的“对角线”上。 但在该矩形中也会有两个大小为 50*50 的“间隙”。 这不是我所认为的“填充”矩形。 相反，我会将问题表述为 2 个（大小相等的正方形）的最大可能尺寸是多少，其边界框为 100*100（假设每个正方形必须与至少一个其他正方形接触？）。

这里的关键点是你的矩形似乎是一个边界框并且没有填充。

另外，你能为这个计算编写一个函数接口吗？ 给定边界框的尺寸，您是否需要对 n 个可能的正方形执行此操作？

Answer 7

给定值：

N - number of tiles
a, b - sides of the rectangle

可以使用以下函数计算图块的边：

def maxSize(n: Int, a: Int, b: Int) = {
  var l = 0
  for (i <- 1 until a.min(b)) { // 
    val newL = (a.min(b) / i).min( (a.max(b) * i)/n )
    if (l < newL && ((a.min(b)/newL) * (a.max(b)/newL) >= n )  )
      l = newL
  }
  return l
}

我假设您不会制作小于 1x1 的图块，无论 1 的度量是什么，

首先您从大小 0 开始：

l = 0

然后从 1 迭代到 K瓦片的列，

K = min(a, b)

其中每次迭代使用此公式计算瓦片的新最大边，

val newL = ( a.min(b) / i ).min( (a.max(b) * i)/n )

此公式采用这两个值中较小的一个：

1. min(a, b)/i -- maximum length of a tile if there are i columns in the smaller side of the rectangle
2. (i * max(a, b))/n -- maximum length of a tile if there are i columns and n tiles in the bigger side of the rectangle

如果候选 newL 大于初始值 l 和可以放入的瓦片的最大可能数量没有重叠的正方形大于或等于瓷砖数量 n 然后

l = newL

最后返回 l

Answer 8

我认为正方形不能旋转。 我很确定，如果允许轮换它们，这个问题会非常困难。

因此，我们从左上角开始用正方形填充矩形。 然后我们将正方形放在该正方形的右侧，直到到达矩形的右侧，然后对下一行执行相同的操作，直到到达底部。 这就像在纸上书写文字一样。

请注意，永远不会出现右侧和底部有剩余空间的情况。 如果两个方向都有空间，那么我们仍然可以增加正方形的大小。

假设我们已经知道第一行应该放置 10 个正方形，并且这完全适合宽度。 那么边长就是width/10。 因此我们可以在第一列中放置m = height/sidelength 正方形。 这个公式可以说我们可以在第一列放置 2.33 个正方形。 不可能放置 0.33 个方格，我们只能放置 2 个方格。 真正的公式是m = Floor(高度/边长)。

一个不太快（但比尝试每种组合快得多）的算法是尝试首先在第一行/列上放置 1 个正方形，然后看看我们是否可以在矩形中放置足够的正方形。 如果它不起作用，我们会在第一行/列上尝试 2 个正方形，依此类推，直到我们可以容纳您想要的图块数量。

我认为如果允许在 O(1) 中进行算术运算，则存在 O(1) 算法，但到目前为止我还没有弄清楚。

这是该算法的 Ruby 版本。 如果矩形不是很薄，则此算法的复杂度为 O(sqrt(# oftiles))。

def squareside(height, width, tiles)
  n = 0
  while true
    n += 1
    # case 1: the squares fill the height of the rectangle perfectly with n squares
    side = height/n
    m = (width/side).floor # the number of squares that fill the width
    # we're done if we can place enough squares this way
    return side if n*m >= tiles
    # case 2: the squares fill the width of the rectangle perfectly with n squares
    side = width/n
    m = (height/side).floor
    return side if n*m >= tiles
  end
end

您还可以使用二分搜索来实现此算法。 在这种情况下，它的复杂度为 O(log(图块数))。

Answer 9

x = max(rectHeight/numberOfSquares, rectangleLength/numberOfSquares)

if x <= retangleHeight && x <= rectangleLength then
  squareSideLength = x
else
  squareSideLength = min(rectangleHeight, rectangleLength)

Answer 10

将长边除以瓷砖数量。 使用较短的一侧作为瓷砖尺寸。 急！ # 瓷砖。

Rectagle = 200 x 10
Each tile is 10 x 10 (length of shorter side)
200/10 = 20 (number of tiles needed)