3

给定一个大小为wx的矩形h，并要求在n该较大的矩形中放置相同大小的矩形，选择大小以及那些最适合填充原始矩形的较小矩形。dxdy

主要限制是所有数字都必须是整数。

我当前的（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，您可以使用Euclidean algorithm有效地进行计算。我认为以下工作 - 试试吧！

首先，计算 gwn = GCD(w,n) 和 ghn = GCD(h,n)。如果其中任何一个是 n，你就完成了 - 如果 gwn = n，这意味着每个矩形可以是 w/n 乘以 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]]

第一个示例产生两个等效结果：

  • 2x8 块，每排 6 块
  • 4x4 瓷砖，每排 3 块

在每种情况下，都有一个插槽未使用，总共有 16 个单元未使用。

### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###        ####### ####### #######
### ### ### ### ### . .    ####### ####### #######
### ### ### ### ###
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
### ### ### ### ###        ####### ####### 
### ### ### ### ### . .    ####### ####### .  .  .
于 2012-05-11T16:29:49.703 回答