Packing rectangles in a rectangle, generate grids coordinates

Question

Looking to generate some randoms grids of rectangles in a bigger rectangle.

This looks like a fairly easy problem, but it's not, seeking for advises here.

This is not a packing problem, since the inner rectangles can have any width and height.

But the amount of rectangles aren't always the same.

I have some results already with different kinds of loops, but none are really efficient.

For example, with 15 rectangles, a possible way to represent them could be:

  O          10                                            50         60
  +----------+---------------------------------------------+----------+-------+
  |          |                                             |          |       |
  |          |                                             |          |       |
  |          |                                             |          |       |
5 +----------+---------------------------------------------+----------+-------+
  |          |                                             |                  |
  |          |                                             |                  |
  |          |                                             |                  |
  |          |                                             |                  |
  |          |                                             |                  |
  |          |                                             |                  |
15+----------+---------------------------------------------+----------+-------+
  |          |                                             |          |       |
  |          |                                             |          |       |
  |          |                                             |          |       |
  +----------+---------------------------------------------+----------+-------+
  |          |                                             |          |       |
  |          |                                             |          |       |
  |          |                ↓                            |          |       |
  +----------+---------------------------------------------+----------+-------+

The coordinates would then be something like an array of [x,y] point of the top left corner (+) of each inner squares:

[[0,0],[10,0],[50,0],[60,0],[5,0],[5,10],[5,50], ...]

Or even better an array of [x,y,w,h] values (Top left x, top left y, width, height)

[[0,0,10,5],[10,0,40,5],[50,0,10,5],[60,0,10,5],[5,0,10,10],[5,10,40,10],[5,50,20,10], ...]

---

But the goal is to make a function that generate coordinates for any amount of inner squares:

For example, with 14 rectangles, a possible way to represent them could be:

  +----------+----------------------------------+---------------------+-------+
  |          |                                  |                     |       |
  |          |                                  |                     |       |
  |          |                                  |                     |       |
  |          |                                  |                     |       |
  |          |                                  |                     |       |
  +----------+----------------------------------+----------+----------+-------+
  |          |                                             |          |       |
  |          |                                             |          |       |
  +----------+--------+------------------------------------+----------+-------+
  |                   |                                    |          |       |
  |                   |                                    |          |       |
  +-------------------+-----------+------------------------+----------+-------+
  |                               |                                           |
  |                               |                                           |
  |                               |                                           |
  |                               |                                           |
  +-------------------------------+-----------------------------------+-------+

Related links:

Packing rectangular image data into a square texture

What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?

How to arrange N rectangles to cover minimum area

Answer 1

Your problem has two aspects: You want to create a regular grid with n rectangles that may span several cells and you want to distribute the coordinates of the cell borders randomly.

So I propose the foolowing algorithm:

• Determine the number of rows and columns in your grid so that each cell is more or less square.
• Create a rectangular grid of 1×1 cells. The number of cells will be greater than n.
• Conflate two adjacent cells until you have n cells.
• Now create random axes for the cell boundaries. If you have m columns, create an array of ncreasing values so that the first coordinate is 0 and the last coordinate is the width of the original ractangle. You can do this by creating a list of increasing random numbers and then normalizing with the overall width.
• Finally, create the actual rectangles, using the information of the cells (position, cell span) and the random axes.

This algorithm uses two representations of the rectangles: First, it creates "cells", which have information about their row and column indices and spans. The actual output are rectangles with left, top, width and height information.

I'm not familar with PHP, so here is an implementaion in Javascript. I think you can see how it works:

function tile(big, n) {
    // big: outer rectangle
    // n: number of subrectangles to create

    // determine number of rows and cols

    let l = Math.sqrt(big.height * big.width / n);
    let ncol = (big.width / l + 1) | 0;
    let nrow = (big.height / l + 1) | 0;
    let cells = [];

    // create grid of m*m cells

    for (let j = 0; j < nrow; j++) {        
        for (let i = 0; i < ncol; i++) {
            cells.push(new Cell(i, j, 1, 1));
        }
    }

    // conflate rectangles until target number is reached

    while (cells.length > n) {
        let k = (cells.length * Math.random()) | 0;
        let c = cells[k];

        if (c.col + c.colspan < ncol) {
            let cc = cells[k + 1];

            c.colspan += cc.colspan;

            cells.splice(k + 1, 1);
        }            
    }

    // generate increasing lists of random numbers

    let xx = [0];
    let yy = [0];

    for (let i = 0; i < ncol; i++) {
        xx.push(xx[xx.length - 1] + 0.5 + Math.random());
    }

    for (let i = 0; i < nrow; i++) {
        yy.push(yy[yy.length - 1] + 0.5 + Math.random());
    }

    // fit numbers to outer rectangle

    for (let i = 0; i < ncol; i++) {
        xx[i + 1] = (big.width * xx[i + 1] / xx[ncol]) | 0;
    }

    for (let i = 0; i < nrow; i++) {
        yy[i + 1] = (big.height * yy[i + 1] / yy[nrow]) | 0;
    }

    // create actual rectangles

    let res = [];
    for (let cell of cells) {
        let x = xx[cell.col];
        let w = xx[cell.col + cell.colspan] - x;
        let y = yy[cell.row];
        let h = yy[cell.row + cell.rowspan] - y;

        res.push(new Rect(x, y, w, h));
    }

    return res;
}

Notes:

• The code above conflates cells only horizontally. You can change this to conflate cells vertically or both, but as the algorithm is at the moment, you won't be able to create cells that are more than one cell wide and high without major modifications.
• The x | 0 is a cheap way to turn floating-point numbers into integers. I've used it to snap the final coordinates to integer values, but you can also snap them to any grid size s with s * ((x / s) | 0) or s * intval(x / s) in PHP.

The code doesn't care much about aesthetics. It picks the cell sizes and the cells to conflate randomly, so that you might get cross joints, which don't look nice. You can influence the regularity of the result a bit, though:

• When you determine the number of columns and rows, you must add one to the result, so that you get cells to conflate in every case. (Even if you have a square and pass a square number as n, you will get joined rectangles.) If you add more, you will get more joined rectangles and the result will look more irregular.
• Math.random() returns a random number between 0 and 1. When creating the axes, I've added 0.5 to the result, so that you don't get very narrow cells. If you add less, the coordinates will be more irregular, if you add more, they will be more evenly distributed.
• Perhaps you can get a good effect from making the row coordinates even and the clumns coordinates irregular.

You've mentioned good-looking properties in a comment. Perhaps it is easier to create a good-looking structure when you create the grid and placing the rectangles with constraints instead of first creating a grid and then remoing joints.