基于瓦片纵横比的瓦片缩放以获得最大面积覆盖

• 下载缩放瓦片项目 - 30.6 KB

介绍  

考虑到有n个尺寸为h x w的矩形，为了在尺寸为H x W的大矩形父容器中占据最多面积，同时保持子矩形的纵横比，这些矩形的最优尺寸应该是多少？

解决这个问题的第一个尝试是穷举法，但人们希望有运行更快的解决方案。下面的解释概述了我的尝试和解决方案。

背景

审视这个问题，首先要识别的是，有两种方法可以优化内部的矩形。要么通过列数最大化，要么通过行数最大化。

在第一张图中，父矩形的宽度被完全填充，从而最大化列数以获得最多的覆盖面积。而在第二张图中，父矩形的高度被完全填充，从而最大化行数以覆盖最多的面积。

最初的穷举法只是根据纵横比迭代行数或列数直到所有矩形都能容纳，并假定这就是行和列优化的最优解决方案。然后，它比较了每种最大化方式所覆盖的面积，并选择了较大的那个。

我希望找到一种解决方案，能够无需耗时的穷举法就能找到子矩形的最优尺寸。为了做到这一点，我们需要找到一个公式来计算使尺寸最大化所需的列数或行数。以下是我解决问题的方法。

If

h = height of the child rectangles 
w = width of the child rectangles
    H = height of parent rectangle
W = width of parent rectangle
n = number of child rectangles
c = number of columns

那么

a = aspect of child rectangles
  = w/h 
r = number of rows
  = ceiling (n/c)

在我的代码中，纵横比是通过用户输入获得的，但也可以通过任何方式指定。

现在，为了定义这两种情况，我们有两组类似的方程。

假设在水平最大化时，我们将不得不缩放子矩形的宽度以最优地适应父容器。

W = c*w*HS

或

HS = (c*w)/W

其中HS是水平缩放因子。

对于垂直最大化，也可以做同样的假设。

H = r*h*VS

或

VS = H/(r*h)

其中VS是垂直缩放因子。

因为这两种方程都可以用列数来表示（r = ceiling (n/c)），而我们知道其他变量，所以我们需要找到一个表示列数的方程。

因为目标是覆盖父矩形面积的100%，我们可以说我们希望子矩形的总面积等于父矩形的总面积。反过来，这意味着父矩形纵横比与子矩形总纵横比之间的差异为零。

D= (H/W) - (r*h) / (c*w)

或

D = H/W - (ceiling (n/c)*h)/(c*w)

其中D是差异，需要为零。

如果我们解出这个关于c的方程，我们就能快速解决问题。然而，向上取整函数使得这非常困难，因为你会得到不等式，而永远得不到精确的答案。所以我尝试在忽略向上取整函数的情况下进行，结果是

D = (H/W) – (n*h) / (c^2 * w)

如果我们解出这个关于c的方程，并令D等于零，结果是

c = sqrt ( (n*W*h)/(H*w) )

如果我们观察c从零开始增加时D的图，它看起来会是这样的

其中x轴代表D = 0。这是最优的列数。然而，列数很少会是整数。所以我们会有一个上限(cu)和下限(cl)的列数。我们需要回顾缩放因子的方程来确定使用哪个界限。

对于垂直缩放因子，我们有方程

VS = (r*h)/H or VS = (ceiling (n/c)*h)/H

我们希望垂直缩放因子尽可能大（使子矩形覆盖最大面积）。为了做到这一点，我们需要(n/c)的值大。因此，在计算垂直缩放因子时，我们需要c是两个界限中较小的一个。

对于水平缩放因子，我们有方程

HS = (c*w)/W

我们也希望水平缩放因子尽可能大，所以为了做到这一点，我们需要c大。因此，在计算水平缩放因子时，我们需要c是两个界限中较大的一个。

现在我们知道了如何找到列数，以及如何计算水平和垂直缩放因子，让我们来看看如何找到每个子矩形的大小。为了做到这一点，我们必须比较使用两种缩放因子所覆盖的面积。

可以使用简单的矩形面积公式来计算面积

Area = x*y

其中x是高度，y是宽度。

但是，因为根据我们使用的缩放因子，我们只知道高度或宽度，所以我们必须利用纵横比方程来消去未知变量。

a = w / h

对于h

h = w/a

对于w

w = h*a

所以垂直面积(VA)将通过将高度替换为h*VS，将宽度替换为(h*VS*a)来计算。

VA = VS*h*(VS*h*a)

而水平面积(HA)将通过将宽度替换为w*HS，将高度替换为((w*HS)/a)来计算。

HA = w*HS*((w*HS)/a)

现在我们有了水平面积和垂直面积的值，我们可以比较两者并决定是按行还是按列最大化。如果我们发现按行最大化，那么我们将把子项的新高度(h2)设为父容器的高度除以用于计算垂直缩放因子的行数（以列数为基础）。

h2 = H/ ( ceiling (n/cl) )

同样，对于按列最大化，我们将子项的宽度设为父容器的宽度除以用于计算水平缩放因子的列数。

w2 = W/cu

最后，我们可以通过使用纵横比关系来计算矩形的剩余边，因为我们希望最终保持该纵横比。

如果按行最大化，则计算新宽度

w2 = h2*a

如果按列最大化，则计算新高度

h2 = w2/a

我们得到了一种新的子矩形尺寸，它尽可能多地覆盖了父矩形。然而，在我实现这个算法时，有少数几个案例它不起作用。这些在代码中得到了处理。

Using the Code

在这里，我们将看到如何使用 C# 代码根据前面的解释找到列数。行数、垂直/水平缩放因子以及最大垂直/水平面积也都在这里确定。

// used to hold the new size of the children after resizing
Size newSize = new Size();
// holds the original size of the children
Size rectangleSize = new Size();
rectangleSize.Width = desiredAspectRatio;
rectangleSize.Height = 1;

double numColumns = Math.Sqrt((numRectangles * rectangleSize.Height * 
                    parentSize.Width) / (parentSize.Height * rectangleSize.Width));

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

double lowNumRows = Math.Ceiling(numRectangles / lowBoundColumns);
double highNumRows = Math.Ceiling(numRectangles / highBoundColumns);

double VerticalScale = parentSize.Height / lowNumRows * rectangleSize.Height;
double HorizontalScale = parentSize.Width / (highBoundColumns * rectangleSize.Width);

double MaxHorizontalArea = (HorizontalScale * rectangleSize.Width) * 
                           ((HorizontalScale * rectangleSize.Width) / desiredAspectRatio);
double MaxVerticalArea = (VerticalScale * rectangleSize.Height) * 
                         ((VerticalScale * rectangleSize.Height) * desiredAspectRatio);

而这里是我们项目中的核心部分。这就是实际确定尺寸的地方。

if (MaxHorizontalArea >= MaxVerticalArea)
// the horizontal area 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
    rowsMaximized = false;//used for testing

    // 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;
        rowsMaximized = true;

        // 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;
            rowsMaximized = false;

            // 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;
                rowsMaximized = true;
            }
        }

        // 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;
            rowsMaximized = false;

            // 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;
                rowsMaximized = true;
            }
        }

        // 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;
    rowsMaximized = true;
}

关注点

需要注意的是，尽管算法正确地找到了我测试过的所有情况，但并非所有情况都是线性解决的。大部分是，但仍然有一些情况我不得不“穷举”解决。你可以在代码中看到这一点。

历史

• 2011年6月28日 - 发布了原始文章。
• 2011年6月29日 - 向文章添加了代码。