algorithm - 网格打包算法

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

有没有更好的算法？

[注意:这不是家庭作业 - 我正在尝试解决如何在 Canvas 上的矩阵中绘制“n”个项目的问题，但每个项目只能使用完整像素]。

Answer 1

看起来您基本上是在尝试计算 GCD ，您可以使用 Euclidean algorithm 高效地完成此操作.我认为以下方法有效 - 试试吧!

首先，计算 gwn = GCD(w,n) 和 ghn = GCD(h,n)。如果其中任何一个是 n，你就完成了——如果 gwn = n，这意味着每个矩形可以是 w/n x h 像素。否则，只有当 h 能被 n/gwn 整除或 w 能被 n/ghn 整除时，你才能拟合矩形。