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.
Size newSize = new Size();
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)
{
newSize.Width = parentSize.Width / highBoundColumns;
newSize.Height = newSize.Width / desiredAspectRatio;
rowsMaximized = false;
if (newSize.Height * Math.Ceiling(numRectangles /
highBoundColumns) > parentSize.Height)
{
double newHeight = parentSize.Height / highNumRows;
double newWidth = newHeight * desiredAspectRatio;
rowsMaximized = true;
if (newWidth * numRectangles < parentSize.Width)
{
newWidth = parentSize.Width / Math.Ceiling(numColumns++);
newHeight = newWidth / desiredAspectRatio;
rowsMaximized = false;
while (newWidth * numRectangles > parentSize.Width)
{
newWidth = parentSize.Width / Math.Ceiling(numColumns++);
newHeight = newWidth / desiredAspectRatio;
}
if (newHeight > parentSize.Height)
{
newHeight = parentSize.Height;
newWidth = newHeight * desiredAspectRatio;
rowsMaximized = true;
}
}
double currentCols = Math.Floor(parentSize.Width / newWidth);
double currentRows = Math.Ceiling(numRectangles / currentCols);
if ((newWidth * currentCols) < parentSize.Width &&
(newHeight * Math.Ceiling(numRectangles /
currentCols)) < parentSize.Height)
{
newWidth = parentSize.Width / currentCols;
newHeight = newSize.Width / desiredAspectRatio;
rowsMaximized = false;
if (newHeight * Math.Ceiling(numRectangles /
currentCols) > parentSize.Height)
{
newHeight = parentSize.Height / currentRows;
newWidth = newHeight * desiredAspectRatio;
rowsMaximized = true;
}
}
newSize.Height = newHeight;
newSize.Width = newWidth;
}
}
else
{
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.