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

Question

I tried to find such an algorithm but I did not succeed so far, I hope you can help me. Thanks in advance!

So my problem is: I have a canvas. By clicking a button I can create a rectangle. When I have one rectangle, it is drawn to occupy most of the canvas. When I push it again, a new rectangle appears and then the two rectangles are redrawn to occupy each almost half of the available canvas. Then a third rectangle is created, and the three rectangles are distributed in two rows, in order to maintain certain proportions between length and width of each rectangle, occupying as much canvas as possible. And so on for n rectangles see image:

Is there any well-known algortighm(s) for doing this?

Thank you!

Answer 1

Your rectangles are all of the same size, so your task is to find the optimal number of rows and columns for your layout. The layout consists of a bounding rectangle, the number of rectangles k and a preferred width-to-height ratio α* plus a gap d between the rectangles:

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

A very simple algorithm would find a first guess for the number of columns m based on the input and then try out several m to find the maxium area while maintaining a reasonable aspect ratio.

Your overall area is A = W · H. The area of one box is a = w · h or a = h / α where α = w / h. A theoretical maximum area (if the gap were 0) is a* = A / k, where k is the number of rectangles. You can use this to estimate a first guess for w and there fore for the number of columns, m.

The "score" for our optimization is the area, which must be maximized. In order not to allow unpleasant aspect ratios, we incorporate the current aspect ratio α by dividing the score by the square of the error (α − α*)².

Here's a way this could be implemented:

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

There's certainly room for improvement, for example when guessing the first shot. You can play with a rough implementation on jsbin.