在 window 中是否有自动调整大小和分配 squares/rectangles 的算法？

Question

我试图找到这样的算法，但到目前为止我没有成功，希望你能帮助我。提前致谢！

所以我的问题是：我有一个 canvas。通过单击一个按钮，我可以创建一个矩形。当我有一个矩形时，它被绘制以占据大部分canvas。当我再次按下它时，会出现一个新的矩形，然后重新绘制两个矩形以占据几乎一半的可用区域 canvas。然后创建第三个矩形，三个矩形分布在两行，每个矩形的长宽保持一定的比例，尽可能占据canvas。依此类推，对于 n 个矩形，请参见图片：

是否有任何众所周知的算法可以做到这一点？

谢谢！

Answer 1

您的矩形都是相同大小的，因此您的任务是为您的布局找到最佳的行数和列数。布局由边界矩形、矩形数 k 和首选宽高比 α* 加上间隙 d 矩形之间：

const box = {
    count: 7,
    alpha: 1.2,
    gap: 8,
    nrow: 0,        // to be determined ...
    ncol: 0,        // ...
    width: 0,       // ...
    height: 0,      // ...
};

一个非常简单的算法会根据输入找到列数 m 的第一个猜测，然后尝试几个 m在保持合理纵横比的同时找到最大面积。

您的总面积是 A = W · H。一个盒子的面积是 a = w · h 或者 a = h / α 其中 α = w / h。理论上的最大面积（如果间隙为 0）为 a* = A / k，其中k是矩形的个数。您可以使用它来估计 w 的第一个猜测，因此对于列数 m.

我们优化的"score"是面积，必须最大化。为了不允许不愉快的宽高比，我们通过将分数除以误差的平方来合并当前的宽高比 α (α − α*)².

可以通过以下方式实现：

function layout(canvas) {
    let A = canvas.width * canvas.height;
    let a = A / box.count;
    let x = Math.sqrt(a * box.alpha);
    let m = (canvas.width / x) | 0 - 2;

    if (m < 1) m = 1;

    let best = 0.0;

    for (;;) {
        let n = (((box.count - 1) / m) | 0) + 1;
        let w = (canvas.width - (m - 1) * box.gap) / m;  
        let h = (canvas.height - (n - 1) * box.gap) / n;

        if (h < 0) h = 0;
        if (w < 0) w = 0;

        let alpha = w / h;
        let area = box.count * (w + box.gap) * (h + box.gap);
        let dalpha = alpha - box.alpha;
        let score = area / (dalpha * dalpha);

        if (score < best) break;

        box.width = w;
        box.height = h;
        box.ncol = m;
        box.nrow = n;

        best = score;
        m++;
    }
}

当然还有改进的余地，例如在猜测第一枪时。你可以在jsbin上play with a rough implementation。

在 window 中是否有自动调整大小和分配 squares/rectangles 的算法？

Is there an algorithm for automatic sizing and distributing squares/rectangles in a window?

algorithm

2d

representation

bin-packing