Geek asks and answers

Mesh packing algorithm

Given the size of the rectangle is wx h, and the requirement to place nsquares of the same size within this larger rectangle, select the size dx, and dyfor those little rectangles that are optimally filled with the original box.

The primary limitation is that all numbers must be integers.

My current (JS) algorithm:

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 am trying to solve the problem of drawing "n" elements in a matrix on the canvas, but where each element should use only integer pixels].

+3
source share
2 answers

, GCD, . , - !

gwn = GCD (w, n) ghn = GCD (h, n). n, - gwn = n, , w/n h . , h n/gwn w n/ghn.

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

:

> 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]]

:

  • 2x8 , 6
  • 4x4 , 3

, 16 .

### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
+1

More articles:


All Articles