Algorithm for maximizing coverage of rectangular area with scaling tiles

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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).

Answer 6

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: