Tile Scaling for Maximum Area Coverage Based Upon Aspect Ratio of Tiles

• Download Scaling Tiles Project - 30.6 KB

Introduction  

Considering n number rectangles each of size h x w, what would the optimal size of these rectangles be in order to occupy the most area of a larger rectangular parent container of size H x W, while maintaining the aspect ratio of the child rectangles?

The first attempt at this problem was a brute force method, but something that ran faster was desired. The following explanation outlines my attempt and my solution.

Background

Looking at the problem, the first thing to identify is the fact that there are two ways to optimize the rectangles inside. Maximization either by the number of columns or the number of rows:

In the first image, the width of the parent rectangle is filled entirely, thus maximizing columns to gain the most area covered. Whereas, the second image shows the height of the parent rectangle being filled entirely, thus maximizing rows to cover the most area.

The original brute force method just iterated through the number of rows or columns until all the rectangles fit, based on the aspect ratio, and assumed that was the optimal solution for row and column optimization, respectively. It then compared the area covered for by each maximization and chose the larger of the two.

My desire was to find a solution that allowed me to find the optimal size of the child rectangles without the timely approach of brute force. In order to do that, we need to find an equation for the number of columns or rows required to make the maximum size. The following is how I approached the problem.

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

Then:

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

In my code, the aspect ratio is obtained simply by user input, but it can be specified any way.

Now, in order to define the two cases, we have two similar sets of equations.

Assuming that for horizontal maximization, we will have to scale the width of the child rectangles to optimally fit inside the parent:

W = c*w*HS

or

HS = (c*w)/W

where HS is the horizontal scale.

You can also assume the same for vertical maximization:

H = r*h*VS

or

VS = H/(r*h)

where VS is the vertical scale.

Because both equations can be defined in terms of columns (r = ceiling (n/c)), and we know the rest of the variables, we need to find an equation for the columns.

Because the goal is to try to cover 100% of the parent rectangle's area, we can say that we want the total area of the child rectangles to be the same as the parent rectangle. This in turn means the difference in the aspect ratio of the parent and the total aspect ratio of the children would be zero.

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

or

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

where D is the difference and needs to be zero.

If we solve this equation for c, then we will have a quick solution to the problem. However, the ceiling function makes this really hard because you end up with inequalities and never an exact answer. So I tried it while ignoring the ceiling function and we end up with:

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

If we solve this equation for c with D equaling zero, we end up with:

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

If we look at a plot of D as c is increased from zero, it would look something like:

Where x is at D = 0. This is the optimal number of columns. However, the number of columns will seldom be an integer. So we will have an upper bound (cu) and lower bound (cl) number of columns. We have to look back at the equations for the scales in order to determine which bound to use.

For the vertical scale, we have the equation:

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

We want the vertical scale to be as large as possible (causing the child rectangles to cover the most area). In order to do this, we need the value of (n/c) to be large. Thus, we need c to be the smaller of the two bounds when calculating the vertical scale.

For the horizontal scale, we have the equation:

HS = (c*w)/W

We also want the horizontal scale to be as large as possible, so to do this, we need c to be large. Thus, we need c to be the larger of the two bounds when calculating the horizontal scale.

Now that we know how to find the number of columns, and how to calculate the horizontal and vertical scale, let us find out how to find the size of each individual child rectangle. In order to do this, we have to make a comparison between the amounts of area covered with the two scales.

The areas can be calculated by using the simple area of a rectangle equation:

Area = x*y

where x is the height and y is the width.

But, because we only know either the height or width based upon which scale we’re using, we must get rid of the unknown variable by utilizing the aspect ratio equation:

a = w / h

For h:

h = w/a

For w:

w = h*a

So the vertical area (VA) will be calculated by supplementing h*VS for the height and (h*VS*a) for the width:

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

And the horizontal area (HA) will be calculated by supplementing w*HS for the width and ((w*HS)/a) for the height:

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

Now that we have values for the horizontal and vertical areas, we can compare the two and decide if we maximize by rows or columns. If we find out that we maximize by rows, we will find the new height of the children (h2) to be the height of the parent divided by the number of rows, in terms of columns, used to calculate the vertical scale.

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

Similarly, for maximization by columns, we find the width of the children to be the width of the parent divided by the number of columns used to calculate the horizontal scale.

w2 = W/cu

Finally, we can calculate the remaining side of the rectangles by using the aspect relationships because we want to maintain that aspect ratio in the end.

If maximized by rows, then we calculate the new width:

w2 = h2*a

If maximized by columns, then we calculate the new height:

h2 = w2/a

We are left with a new size for the child rectangles that covers as much of the parent rectangle as possible. However, when I implement this, I am left with a select few cases for which this doesn’t work. These are addressed in the code.

Using the Code

Here we will see in C# code how to find the number of columns based on the previous explanation. The number of rows, the vertical/horizontal scale, and the max vertical/horizontal area are all determined here as well.

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

And here we see the bread and butter of the project. This is where the size is actually determined.

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

Points of Interest

One thing to take note of is the fact that although the algorithm correctly finds all cases that I have tested, it is not all solved linearly. Most of it is, but there are still those few cases for which I had to 'brute force' my way through. You can see this in the code.

History

• 6/28/11 - Posted the original article.
• 6/29/11 - Added code to the article.