Algorithm for maximizing coverage of rectangular a

问题:

I have N scalable square tiles (buttons) that need to be placed inside of fixed sized rectangular surface (toolbox). I would like to present the buttons all at the same size.

How could I solve for the optimal size of the tiles that would provide the largest area of the rectangular surface being covered by tiles.

回答1:

Let W and H be the width and height of the rectangle.

Let s be the length of the side of a square.

Then the number of squares n(s) that you can fit into the rectangle is floor(W/s)*floor(H/s). You want to find the maximum value of s for which n(s) >= N

If you plot the number of squares against s you will get a piecewise constant function. The discontinuities are at the values W/i and H/j, where i and j run through the positive integers.

You want to find the smallest i for which n(W/i) >= N, and similarly the smallest j for which n(H/j) >= N. Call these smallest values i_min and j_min. Then the largest of W/i_min and H/j_min is the s that you want.

I.e. s_max = max(W/i_min,H/j_min)

To find i_min and j_min, just do a brute force search: for each, start from 1, test, and increment.

In the event that N is very large, it may be distasteful to search the i's and j's starting from 1 (although it is hard to imagine that there will be any noticeable difference in performance). In this case, we can estimate the starting values as follows. First, a ballpark estimate of the area of a tile is W*H/N, corresponding to a side of sqrt(W*H/N). If W/i <= sqrt(W*H/N), then i >= ceil(W*sqrt(N/(W*H))), similarly j >= ceil(H*sqrt(N/(W*H)))

So, rather than start the loops at i=1 and j=1, we can start them at i = ceil(sqrt(N*W/H)) and j = ceil(sqrt(N*H/W))). And OP suggests that round works better than ceil -- at worst an extra iteration.

Here's the algorithm spelled out in 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) ;
}

The above is written for clarity. The code can be tightened up considerably as follows:

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

回答2:

I believe this can be solved as a constrained minimisation problem, which requires some basic calculus. .

Definitions:

a, l -> rectangle sides
   k -> number of squares
   s -> side of the squares

You have to minimise the function:

   f[s]:= a * l/s^2 - k

subject to the constraints:

  IntegerPart[a/s] IntegerPart[l/s] - k >= 0
  s > 0

I programed a little Mathematica function to do the trick

  f[a_, l_, k_] :=  NMinimize[{a l/s^2 - k , 
                               IntegerPart[a/s] IntegerPart[l/s] - k >= 0, 
                               s > 0}, 
                               {s}]     

Easy to read since the equations are the same as above.

Using this function I made up a table for allocating 6 squares

as far as I can see, the results are correct.

As I said, you may use a standard calculus package for your environment, or you may also develop your own minimisation algorithm and programs. Ring the bell if you decide for the last option and I'll provide a few good pointers.

HTH!

Edit

Just for fun I made a plot with the results.

And for 31 tiles:

Edit 2: Characteristic Parameters

The problem has three characteristic parameters:

1. The Resulting Size of the tiles
2. The Number of Tiles
3. The ratio l/a of the enclosing rectangle

Perhaps the last one may result somewhat surprising, but it is easy to understand: if you have a problem with a 7x5 rectangle and 6 tiles to place, looking in the above table, the size of the squares will be 2.33. Now, if you have a 70x50 rectangle, obviously the resulting tiles will be 23.33, scaling isometrically with the problem.

So, we can take those three parameters and construct a 3D plot of their relationship, and eventually match the curve with some function easier to calculate (using least squares for example or computing iso-value regions).

Anyway, the resulting scaled plot is:

回答3:

I realize this is an old thread but I recently solved this problem in a way that I think is efficient and always gives the correct answer. It is designed to maintain a given aspect ratio. If you wish for the children(buttons in this case) to be square just use an aspect ratio of 1. I am currently using this algorithm in a few places and it works great.

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

At the end of the algorithm 'newSize' holds the appropriate size. This is written in C# but it would be fairly easy to port to other languages.

回答4:

The first, very rough heuristic is to take

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

where s is the button-side-length, X and Y are the width and height of the toolbox, and N is the number of buttons.

In this case, s will be the MAXIMUM possible side-length. It is not necessarily possible to map this set of buttons onto the toolbar, however.

Imagine a toolbar that is 20 units by 1 unit with 5 buttons. The heuristic will give you a side length of 2 (area of 4), with a total covering area of 20. However, half of each button will be outside of the toolbar.

回答5:

I would take an iterative approach here. I would check if it is possible to fit all button in a single row. If not, check if it is possible to fit in two rows, and so on.

Say W is the smaller side of the toolbox. H is the other side.

For each iteration, I would check for the best and worst possible cases, in that order. Best case means, say it is the nth iteration, would try a size of W/n X W/n sized buttons. If h value is enough then we are done. If not, the worst case is to try (W/(n+1))+1 X (W/(n+1))+1 sized buttons. If it is possible to fit all buttons, then i would try a bisection method between W/n and (W/(n+1))+1. If not iteration continues at n+1.

回答6:

Let n(s) be the number of squares that can fit and s their side. Let W, H be the sides of the rectangle to fill. Then n(s) = floor(W/s)* floor(H/s). This is a monotonically decreasing function in s and also piecewise constant, so you can perform a slight modification of binary search to find the smallest s such that n(s) >= N but n(s+eps) < N. You start with an upper and lower bound on s u = min(W, H) and l = floor(min(W,H)/N) then compute t = (u + l) / 2. If n(t) >= N then l = min(W/floor(W/t), H/floor(H/t)) otherwise u = max(W/floor(W/t), H/floor(H/t)). Stop when u and l stay the same in consecutive iterations. So it's like binary search, but you exploit the fact that the function is piecewise constant and the change points are when W or H are an exact multiple of s. Nice little problem, thanks for proposing it.

回答7:

We know that any optimal solution (there may be two) will fill the rectangle either horizontally or vertically. If you found an optimal solution that did not fill the rectangle in one dimension, you could always increase the scale of the tiles to fill one dimension.

Now, any solution that maximizes the surface covered will have an aspect ratio close to the aspect ratio of the rectangle. The aspect ratio of the solution is vertical tile count/horizontal tile count (and the aspect ratio of the rectangle is Y/X).

You can simplify the problem by forcing Y>=X; in other words, if X>Y, transpose the rectangle. This allows you to only think about aspect ratios >= 1, as long as you remember to transpose the solution back.

Once you've calculated the aspect ratio, you want to find solutions to the problem of V/H ~= Y/X, where V is the vertical tile count and H is the horizontal tile count. You will find up to three solutions: the closest V/H to Y/X and V+1, V-1. At that point, just calculate the coverage based on the scale using V and H and take the maximum (there could be more than one).