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

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 穿过正值整数。

您想要找到满足 n(W/i) >= N 的最小 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 和 j 可能会很令人厌恶（尽管很难想象会出现这样的情况）性能上是否有任何明显的差异）。在这种情况下，我们可以如下估计起始值。首先，图块面积的大致估计值为 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 方块

尽可能 看看，结果是正确的。

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

哈！

编辑

只是为了好玩，我用结果绘制了一个图。

对于 31 个图块：

编辑 2：特征参数

该问题具有三个特征参数：

1. 瓦片的最终大小
2. 瓦片的数量
3. 封闭矩形的 l/a 比率

也许最后一个可能是结果有些令人惊讶，但很容易理解：如果您对放置 7x5 矩形和 6 个图块有疑问，请查看上表，正方形的大小将为 2.33。现在，如果您有一个 70x50 的矩形，显然生成的图块将是 23.33，根据问题进行等距缩放。

因此，我们可以采用这三个参数并构建它们关系的 3D 图，并最终将曲线与一些更容易计算的函数相匹配（例如使用最小二乘法或计算等值区域）。

无论如何，生成的缩放图是：

Answer 3

我意识到这是一个旧线程，但我最近以一种我认为有效并且总是给出正确答案的方式解决了这个问题。它旨在保持给定的纵横比。如果您希望子项（本例中为按钮）为正方形，只需使用宽高比 1。我目前在一些地方使用此算法，效果很好。

        double VerticalScale; // for the vertical scalar: uses the lowbound number of columns
        double HorizontalScale;// horizontal scalar: uses the highbound number of columns
        double numColumns; // the exact number of columns that would maximize area
        double highNumRows; // number of rows calculated using the upper bound columns
        double lowNumRows; // number of rows calculated using the lower bound columns
        double lowBoundColumns; // floor value of the estimated number of columns found
        double highBoundColumns; // ceiling value of the the estimated number of columns found


        Size rectangleSize = new Size(); // rectangle size will be used as a default value that is the exact aspect ratio desired.
        //
        // Aspect Ratio = h / w
        // where h is the height of the child and w is the width
        //
        // the numerator will be the aspect ratio and the denominator will always be one
        // if you want it to be square just use an aspect ratio of 1
        rectangleSize.Width = desiredAspectRatio;
        rectangleSize.Height = 1;

        // estimate of the number of columns useing the formula:
        //                          n * W * h       
        //  columns = SquareRoot(  -------------  )
        //                            H * w          
        //
        // Where n is the number of items, W is the width of the parent, H is the height of the parent,
        // h is the height of the child, and w is the width of the child
        numColumns = Math.Sqrt( (numRectangles * rectangleSize.Height * parentSize.Width) / (parentSize.Height * rectangleSize.Width) );

        lowBoundColumns = Math.Floor(numColumns);
        highBoundColumns = Math.Ceiling(numColumns);

        // The number of rows is determined by finding the floor of the number of children divided by the columns
        lowNumRows = Math.Ceiling(numRectangles / lowBoundColumns);
        highNumRows = Math.Ceiling(numRectangles / highBoundColumns);

        // Vertical Scale is what you multiply the vertical size of the child to find the expected area if you were to find
        // the size of the rectangle by maximizing by rows
        //
        //                      H
        // Vertical Scale = ----------
        //                    R * h
        //
        // Where H is the height of the parent, R is the number of rows, and h is the height of the child
        //
        VerticalScale = parentSize.Height / lowNumRows * rectangleSize.Height;

        //Horizontal Scale is what you multiply the horizintale size of the child to find the expected area if you were to find
        // the size of the rectangle by maximizing by columns
        //
        //                      W
        // Vertical Scale = ----------
        //                    c * w
        //
        //Where W is the width of the parent, c is the number of columns, and w is the width of the child
        HorizontalScale = parentSize.Width / (highBoundColumns * rectangleSize.Width);

        // The Max areas are what is used to determine if we should maximize over rows or columns
        //  The areas are found by multiplying the scale by the appropriate height or width and finding the area after the scale
        //                      
        // Horizontal Area =  Sh * w * ( (Sh * w) / A )
        //                     
        // where Sh is the horizontal scale, w is the width of the child, and A is the aspect ratio of the child
        //
        double MaxHorizontalArea = (HorizontalScale * rectangleSize.Width) * ((HorizontalScale * rectangleSize.Width) / desiredAspectRatio);
        //
        //                       
        // Vertical Area =   Sv * h * (Sv * h) * A
        // Where Sv isthe vertical scale, h is the height of the child, and A is the aspect ratio of the child
        //
        double MaxVerticalArea = (VerticalScale * rectangleSize.Height) * ((VerticalScale * rectangleSize.Height) * desiredAspectRatio);


        if (MaxHorizontalArea >= MaxVerticalArea ) // the horizontal are is greater than the max area then we maximize by columns
        {
            // the width is determined by dividing the parent's width by the estimated number of columns
            // this calculation will work for NEARLY all of the horizontal cases with only a few exceptions
            newSize.Width = parentSize.Width / highBoundColumns; // we use highBoundColumns because that's what is used for the Horizontal
            newSize.Height = newSize.Width / desiredAspectRatio; // A = w/h or h= w/A

            // In the cases that is doesnt work it is because the height of the new items is greater than the 
            // height of the parents. this only happens when transitioning to putting all the objects into
            // only one row
            if (newSize.Height * Math.Ceiling(numRectangles / highBoundColumns) > parentSize.Height)
            {
                //in this case the best solution is usually to maximize by rows instead
                double newHeight = parentSize.Height / highNumRows;
                double newWidth = newHeight * desiredAspectRatio;

                // However this doesn't always work because in one specific case the number of rows is more than actually needed
                // and the width of the objects end up being smaller than the size of the parent because we don't have enough
                // columns
                if (newWidth * numRectangles < parentSize.Width)
                {
                    //When this is the case the best idea is to maximize over columns again but increment the columns by one
                    //This takes care of it for most cases for when this happens.
                    newWidth = parentSize.Width / Math.Ceiling(numColumns++);
                    newHeight = newWidth / desiredAspectRatio;

                    // in order to make sure the rectangles don't go over bounds we
                    // increment the number of columns until it is under bounds again.
                    while (newWidth * numRectangles > parentSize.Width)
                    {
                        newWidth = parentSize.Width / Math.Ceiling(numColumns++);
                        newHeight = newWidth / desiredAspectRatio;
                    }

                    // however after doing this it is possible to have the height too small.
                    // this will only happen if there is one row of objects. so the solution is to make the objects'
                    // height equal to the height of their parent
                    if (newHeight > parentSize.Height)
                    {
                        newHeight = parentSize.Height;
                        newWidth = newHeight * desiredAspectRatio;
                    }
                }

                // if we have a lot of added items occaisionally the previous checks will come very close to maximizing both columns and rows
                // what happens in this case is that neither end up maximized

                // because we don't know what set of rows and columns were used to get us to where we are
                // we must recalculate them with the current measurements
                double currentCols = Math.Floor(parentSize.Width / newWidth); 
                double currentRows = Math.Ceiling(numRectangles/currentCols);
                // now we check and see if neither the rows or columns are maximized
                if ( (newWidth * currentCols ) < parentSize.Width && ( newHeight * Math.Ceiling(numRectangles/currentCols) ) < parentSize.Height)
                {
                    // maximize by columns first
                    newWidth = parentSize.Width / currentCols;
                    newHeight = newSize.Width / desiredAspectRatio;

                    // if the columns are over their bounds, then maximized by the columns instead
                    if (newHeight * Math.Ceiling(numRectangles / currentCols) > parentSize.Height)
                    {
                        newHeight = parentSize.Height / currentRows;
                        newWidth = newHeight * desiredAspectRatio;
                    }
                }

                // finally we have the height of the objects as maximized using columns
                newSize.Height = newHeight;
                newSize.Width = newWidth;

            }

        }
        else
        {
            //Here we use the vertical scale. We determine the height of the objects based upong
            // the estimated number of rows.
            // This work for all known cases
            newSize.Height = parentSize.Height / lowNumRows; 
            newSize.Width = newSize.Height * desiredAspectRatio;
        }

在算法结束时，“newSize”保持适当的大小。这是用 C# 编写的，但移植到其他语言相当容易。

Answer 4

第一个非常粗略的启发式是采用

s = floor( sqrt( (X x Y) / N) )

其中 s 是按钮边长，X 和 Y 是按钮的宽度和高度。工具箱，N 是按钮的数量。

在这种情况下，s 将是最大可能的边长。然而，不一定可以将这组按钮映射到工具栏上。

想象一个 20 个单位 x 1 个单位、带有 5 个按钮的工具栏。启发式将为您提供边长为 2（面积为 4）的总覆盖面积为 20。但是，每个按钮的一半将位于工具栏之外。

Answer 5

我会在这里采取迭代方法。
我会检查是否可以将所有按钮放在一行中。
如果不是，请检查是否可以放入两行，依此类推。

假设 W 是工具箱较小的一侧。
H是另一边。

对于每次迭代，我都会按顺序检查最好和最坏的可能情况。最好的情况意味着，假设这是第 n 次迭代，将尝试 W/n XW/n 大小的按钮。如果 h 值足够，那么我们就完成了。如果不是，最坏的情况是尝试 (W/(n+1))+1 X (W/(n+1))+1 大小的按钮。如果可以容纳所有按钮，那么我会尝试 W/n 和 (W/(n+1))+1 之间的二分法。如果不是，则迭代在 n+1 处继续。

Answer 6

设 n(s) 为可容纳的正方形数量，s 为其边长。令 W、H 为要填充的矩形的边。那么n(s) = 楼层(W/s)* 楼层(H/s)。这是 s 中的单调递减函数，也是分段常数，因此您可以对二分搜索进行轻微修改以找到最小的 s，使得 n(s) >= N 但 n(s+eps) < N. 从 su = min(W, H) 和 l = Floor(min(W,H)/N) 的上限和下限开始，然后计算 t = (u + l) / 2。如果 n(t) >=N
那么 l = min(W/floor(W/t), H/floor(H/t)) 否则 u = max(W/floor(W/t), H/floor(H/t))。当 u 和 l 在连续迭代中保持相同时停止。
所以它就像二分搜索，但你利用了这样一个事实：函数是分段常数，并且变化点是当 W 或 H 是 s 的精确倍数时。很好的小问题，谢谢你提出来。

Answer 7

我们知道任何最佳解决方案（可能有两个）都会水平或垂直填充矩形。如果您找到了未在一维上填充矩形的最佳解决方案，则始终可以增加图块的比例以填充一维。

现在，任何最大化覆盖表面的解决方案都将具有接近矩形的长宽比。该解决方案的长宽比为垂直瓦片数/水平瓦片数（矩形的长宽比为Y/X）。

您可以通过强制 Y>=X 来简化问题；换句话说，如果X>Y，则转置矩形。这允许您只考虑宽高比 >= 1，只要您记得将解决方案转回即可。

计算出纵横比后，您需要找到 V/H ~= Y/X 问题的解决方案，其中 V 是垂直平铺数，< code>H 是水平图块计数。您将找到最多三个解决方案：最接近 Y/X 的 V/H 和 V+1、V-1< /代码>。此时，只需使用 V 和 H 根据比例计算覆盖范围并取最大值（可能有多个）。