网格打包算法

Question

给定一个大小为w x h的矩形，和一个要求在这个大矩形内放置n个相同大小的小矩形，选择dx和dy的大小，使得小矩形最优地填满原始矩形。

主要限制条件是所有数字必须为整数。

我目前（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”个矩阵项，但每个项必须仅使用整像素的问题]。

- Alnitak

---

这可能会有所帮助。这是一个非常类似的问题，但不完全相同。它可能会给你一些思路。https://dev59.com/BnA75IYBdhLWcg3wBkS1 - Chris

还有，小矩形需要受到某种高度/宽度比例的限制吗？ - Chris

@Chris，比如说它们不应该是1像素宽，200像素高... - Alnitak

@Altinak：我希望得到的比那更具体一些。;-) 我不知道你的确切用例，但你可能最好不一定要追求最佳适配，而是以某种方式限制dx/dy的比率，这样即使浪费一个像素，也会得到更美观的结果，而不是使用所有像素但具有极端宽高比的东西... - Chris

@chris 从美学角度考虑，我会尽量让宽高比“大致”与原始网格相同。 - Alnitak

Answer 1

看起来你基本上是想计算GCD，你可以使用欧几里得算法高效地完成。我认为以下方式可行-试一下吧！

首先，计算gwn = GCD（w，n）和ghn = GCD（h，n）。如果其中任何一个是n，那么你就完成了-如果gwn = n，则意味着每个矩形可以是w / n乘以h像素。否则，只有当h可被n / gwn整除或w可被n / ghn整除时，您才能适合这些矩形。

- Martin Hock

---

听起来你在描述一个“精确”匹配，即在任何轴上都不能留下多余的像素？ - Alnitak

Alnitak：你说得对，我得考虑一下非精确情况。 - Martin Hock

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

第一个例子产生了两个等效的结果：

• 一行6个2x8瓷砖
• 两行3个4x4瓷砖

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

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

- Markus Jarderot

---

我使用因式分解重写了它。现在它会尝试越来越小的区域，直到得出结果。现在速度快多了，但我不知道它的复杂度是否有所改善。 - Markus Jarderot