3

サイズwxの長方形があり、同じサイズの長方形をその大きな長方形hに収める必要がある場合は、サイズを選択し、元の長方形を最適に埋める小さな長方形を選択します。ndxdy

主な制約は、すべての数値が整数でなければならないということです。

私の現在の（JS）アルゴリズムは次のとおりです。

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

より良いアルゴリズムはありますか？

[注：これは宿題ではありません。キャンバス上のマトリックスに「n」個のアイテムを描画する方法の問題を解決しようとしていますが、各アイテムはピクセル全体のみを使用する必要があります]。

4

2 に答える 2

2

基本的にGCDを計算しようとしているように見えますが、これはユークリッド アルゴリズムを使用して効率的に実行できます。次のように動作すると思います - 試してみてください!

まず、gwn = GCD(w,n) と ghn = GCD(h,n) を計算します。これらのいずれかが n の場合、完了です。gwn = n の場合、各四角形は w/n x h ピクセルになる可能性があることを意味します。それ以外の場合、h が n/gwn で割り切れる場合、または w が n/ghn で割り切れる場合にのみ、四角形を合わせることができます。

于 2012-05-11T16:37:10.830 に答える
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;
}

例：

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

最初の例では、2 つの同等の結果が生成されます。

  • 2x8 のタイルが 1 行に 6 枚ずつ詰め込まれています
  • 4x4 タイルを 3 列 2 列に詰めたもの

いずれの場合も、1 つのスロットが未使用のままになり、合計 16 セルが未使用のままになります。

### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
于 2012-05-11T16:29:49.703 に答える