Tile Scaling for Maximum Area Coverage Based Upon Aspect Ratio of Tiles
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 children 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 up 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 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 children 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 rectangles area, we can say that we want the total area of the children 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 needed 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 increases from zero it would look something like:
Where the ‘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 children 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 the 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 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 children 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 see in C# code how to find the number of columns based up the previous explanation.The number of rows, the vertical/horizontal scale, and the max vertical/horizontal area are all determined here as well.
Size newSize = new Size(); // used to hold the new size of the children after resizing
Size rectangleSize = new Size();// holds the original size of the children
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.
Download ScalingTiles.zip - 62.79 KB 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
"