Max square size for unknown number inside rectangle

Question

If I have a set of tiles (squares) which can be any number and they are to fill a container (rectangle) of an unknown size how do I work out the maximum size of the tiles without having any of them overlap.

So if I have 2 tiles and the rectangle is 100 * 100 then the max tile size is 50 * 50. This would also be the max size of tile if there was 3 or 4 tiles for this size of rectanlgle, which just so happens to be a square in this example.

If the rectanlge was 100 * 30 and I had 2 tiles, the max size of the square would be 30 * 30, if I have 4 tiles the max size would be 25 * 25.

How can I do this programatically without hogging the processor by going through every possible combination.

---

I try to summarise a bit better, I have a:

rectangle/bounding box that I need to fill as much as possible without the tiles overlapping.

I know the height and width of the rectangle (but this can change during runtime).

I have X number of tiles (this can change at run time), these are squares.

None of the tiles should overlap, what is the maximum size that each tile can be. They are all to be the same size.

Answer 1

Conceptually:

• start with 1 square
• For each additional square, if you don't have room in your grid box so far, shrink the existing box just enough to make room for an additional row or column.

pseudocode: given M x N rectangle to fill with K squares

// initial candidate grid within the rectangle
h=1
w=1
maxsquares=1
size=min(M,N) //size of the squares
while K > maxsquares
  if M/(h+1) >= N/(w+1)
    h=h+1
  else
    w=w+1
  endif
  maxsquares=h*w
  size=min(M/h,N/w)
done
print size

There are probably faster ways to jump to the answer for very large K, but I can't think of them. If you know that M and N are integers, there may be even faster methods.

Answer 2

Here is an O(1) solution with no loops.

Using the aspect ratio (height/width) of the rectangle, you can come up with an initial guess at the number of tiles in the x and y directions. This gives an upper and lower bound for the total number of tiles: between xy and (x+1)(y+1).

Based on these bounds, there are three possibilities:

1. The lower bound is correct. Compute the largest tileSize that will result in xy tiles.
2. The upper bound is correct. Compute the largest tileSize that will result in (x+1)(y+1) tiles
3. The correct answer lies somewhere between the upper and lower bounds. Solve an equation to determine the correct values of x and y, and then compute the largest tileSize that will result in the correct number of tiles

int GetTileSize(int width, int height, int tileCount)
{
    // quick bailout for invalid input
    if (width*height < tileCount) { return 0; }

    // come up with an initial guess
    double aspect = (double)height/width;
    double xf = sqrtf(tileCount/aspect);
    double yf = xf*aspect;
    int x = max(1.0, floor(xf));
    int y = max(1.0, floor(yf));
    int x_size = floor((double)width/x);
    int y_size = floor((double)height/y);
    int tileSize = min(x_size, y_size);

    // test our guess:
    x = floor((double)width/tileSize);
    y = floor((double)height/tileSize);
    if (x*y < tileCount) // we guessed too high
    {
        if (((x+1)*y < tileCount) && (x*(y+1) < tileCount))
        {
            // case 2: the upper bound is correct
            //         compute the tileSize that will
            //         result in (x+1)*(y+1) tiles
            x_size = floor((double)width/(x+1));
            y_size = floor((double)height/(y+1));
            tileSize = min(x_size, y_size);
        }
        else
        {
            // case 3: solve an equation to determine
            //         the final x and y dimensions
            //         and then compute the tileSize
            //         that results in those dimensions
            int test_x = ceil((double)tileCount/y);
            int test_y = ceil((double)tileCount/x);
            x_size = min(floor((double)width/test_x), floor((double)height/y));
            y_size = min(floor((double)width/x), floor((double)height/test_y));
            tileSize = max(x_size, y_size);
        }
    }

    return tileSize;
}

I have tested this function for all integer widths, heights and tileCounts between 1 and 1000 using the following code:

for (width = 1 to 1000)
{
    for (height = 1 to 1000)
    {
        for (tileCount = 1 to 1000)
        {
            tileSize = GetTileSize(width, height, tileCount);

            // verify that increasing the tileSize by one
            // will result in too few tiles
            x = floor((double)width/(tileSize+1));
            y = floor((double)height/(tileSize+1));
            assert(x*y < tileCount);

            // verify that the computed tileSize actually
            // results in the correct tileCount
            if (tileSize > 0)
            {
                x = floor((double)width/tileSize);
                y = floor((double)height/tileSize);
                assert(x*y >= tileCount);
            }
        }
    }
}

Answer 3

This is a packing problem. Optimal solutions are hard to find. See for example Packing N squares in a square.

You can compute an (optimistic) upper bound by dividing the total surface by the number of squares: sqrt(width*height/n).