Grid packing algorithm

Question

Given a rectangle of size w x h, and a requirement to fit n equally sized rectangles within that larger rectangle, pick the size dx and dy for those smaller rectangles that optimally fills the original rectangle.

The primary constraint is that all numbers must be integers.

My current (JS) algorithm is this:

function pack(n, w, h) {

    var nx, ny;
    var dx = w, dy = h;  // initally try one rectangle that fills the box

    while (true) {
        nx = ~~(w / dx); // see how many times this fits in X
        ny = ~~(h / dy); // and in Y

        if (nx * ny >= n) break;   // they all fit!

        if (dx * h >= w * dy) {    // look at the aspect ratio
            dx = ~~(w / (nx + 1)); // try fitting more horizontally
        } else {
            dy = ~~(h / (ny + 1)); // or try more vertically
        }

        if (dx < 1 || dy < 1) {
            return;                // they can't fit
        }
    };

    return [nx, ny, dx, dy];
};

Is there a better algorithm?

[NB: this is not homework - I'm trying to solve the problem of how to draw "n" items in a matrix on a canvas, but where each item must only use whole pixels].

Answer 1

function pick(tiles, grid_width, grid_height)
{
    var max_area = ~~(grid_width * grid_height / tiles);

    for (var area = max_area; area > 0; area--)
    {
        var result = [grid_width * grid_height - area * tiles];

        divisors_do(area,
            function (tile_width)
            {

                var tile_height = area / tile_width;
                if (tile_width > grid_width) return true;
                if (tile_height > grid_height) return true;

                var count_horizontal = ~~(grid_width / tile_width);
                var count_vertical = ~~(grid_height / tile_height);
                if (count_horizontal * count_vertical < tiles) return true;

                result.push([
                    tile_width, tile_height,
                    count_horizontal, count_vertical
                ]);
            });
        if (result.length > 1) return result;
    }
    return null;
}

function divisors_do(x, f)
{
    var history = [1];
    if (f(1) === false) return false;

    // for each prime factor
    return prime_factors_do(x,
        function(prime, primePower)
        {
            var len = history.length;

            for (var iHistory = 0; iHistory < len; iHistory++)
            {
                var divisor = history[iHistory];

                for (var power = 1; power <= primePower; power++)
                {
                    divisor *= prime;
                    history.push(divisor);

                    if (f(divisor) === false) return false;
                }
            }

            return true;
        });
}

function prime_factors_do(x, f)
{
    for (var test = 2; test*test <= x; test++)
    {
        var power = 0;
        while ((x % test) == 0)
        {
            power++;
            x /= test;
        }

        // If we found a prime factor, report it, and
        // abort if `f` returns false.
        if (power > 0 && f(test, power) === false)
            return false;
    }

    if (x > 1) return f(x,1);
    return true;
}

Example:

> pack(5, 12, 8);
[16, [2, 8, 6, 1], [4, 4, 3, 2]]
> pack(47,1024,768);
[16384, [64, 256, 16, 3], [128, 128, 8, 6], [256, 64, 4, 12], [512, 32, 2, 24]]

The first example produces two equivalent results:

• 2x8 tiles packed in one row of 6
• 4x4 tiles packed in two rows of 3

In each case, one slot is left unused, leaving a total of 16 cells unused.

### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .

Answer 2

It looks like you're basically trying to calculate GCD, which you can do efficiently using the Euclidean algorithm. I think the following works - try it out!

First, calculate gwn = GCD(w,n) and ghn = GCD(h,n). If either of these is n, you're done - if gwn = n, it means each rectangle can be w/n by h pixels. Otherwise, you can only fit the rectangles if h is divisible by n/gwn or w is divisible by n/ghn.