What is an algorithm to divide a rectangle into N number of square(ish) cells?

Question

I'm drawing images on a canvas. I need an algorithm that will help place the images.

I'm trying to keep the aspect ratios of the cells 1:1. This isn't always possible so the idea is that when dividing up a cell if the length is greater than the width then divide the length in half and if the width is greater than the length then divide the cell by its width.

Something like this:

This would NOT be an example of keeping cell aspect ratios 1:1:

How would I work out the cell sizes and their x and y offset?

number of cells = 6
rectangle height = 600
rectangle width = 400

for each cell
  calculate cell height, width, xOffset, yOffset ???

Then I can loop through the cells and draw them:

for each cell
  draw(xOffset, yOffset, width, height)

user18978409 · Accepted Answer

A systematic approach would be to use an integer partition algorithm to generate all possible layouts for a specific N and a goodness function to select the layout with the highest "squarishness."

For example, N=5 has the following 7 possible partitions,

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

The OP has selected partition 3+2 for the N=5 example layout. For N=10, it is 3+3+2+2 (out of 42). Note that there are two ways to apply a partition to a layout, straight or flipped. N=5 is the only OP example of a flipped layout.

The rectangle has a width of W and a height of H. It holds N rectangular cells, each with a width of w and a height of h. I suggest the following goodness function for the total squarishness,

SF = (w1-h1)^2 + ... + (wN-hN)^2.

The smaller the SF, the higher the squarishness. When SF is zero, all cells are squares.

Integer partition is a well-studied problem. There are many algorithms in different programming languages on the internet.

Here follows an implementation of my proposed solution with two tests related to the OP example. The rectangle is W=4.0 and H=6.0, the same aspect ratio the OP uses.

In the first test, N=5.

--- straight ---
5  (45.602)
4 1  (5.7125)
3 2  (3.3125)
3 1 1  (3.44556)
2 2 1  (1.52556)
2 1 1 1  (7.18812)
1 1 1 1 1  (14.45)

The integer sequences to the left are the possible partitions of 5. Each sequence represents one possible layout of cells in the rectangle. The number of integers in a partition sequence corresponds to the number of rows. Each integer is the number of cells in a row. The number within parentheses is the SF value for this layout on this rectangle. The lower the SF, the better the squarishness of the layout,

To cover all layout cases, we repeat the above with the rectangle flipped 90 degrees (by switching W and H),

--- flipped ---
5  (14.45)
4 1  (5.7125)
3 2  (0.608333)
3 1 1  (14.9833)
2 2 1  (10.9)
2 1 1 1  (27.875)
1 1 1 1 1  (45.602)

The winner is the 3 2 sequence with a flipped layout, as the OP also has it.

In the second test we repeat the above for all N between 1 and 12. But this time, we only keep the winner for each N,

--- straight ---
N=1: 1  (1.21)
N=2: 1 1  (0.845)
N=3: 2 1  (1.0275)
N=4: 2 2  (1.21)
N=5: 2 2 1  (1.52556)
N=6: 2 2 2  (0.00666667)
N=7: 3 2 2  (0.407778)
N=8: 3 3 2  (0.808889)
N=9: 3 2 2 2  (0.650625)
N=10: 3 3 2 2  (0.45625)
N=11: 3 3 3 2  (0.261875)
N=12: 3 3 3 3  (0.0675)

--- flipped --
N=1: 1  (1.21)
N=2: 2  (0.845)
N=3: 3  (4.56333)
N=4: 2 2  (1.21)
N=5: 3 2  (0.608333)
N=6: 3 3  (0.00666667)
N=7: 4 3  (0.425833)
N=8: 4 4  (0.845)
N=9: 3 3 3  (1.21)
N=10: 4 3 3  (0.829167)
N=11: 4 4 3  (0.448333)
N=12: 4 4 4  (0.0675)

As we can see, the SF goodness function judges the layouts as the OP did in the example, including the flipped N=5.

My code is in C++. The integer partition algorithm is from: "Generate all unique partitions of an integer" at geeksforgeeks.org:

#include 
#include 
#include 
#include 
#include 

struct Cell {
    double x,y,w,h;
};

using Cells = std::vector;

std::string toString(Cell c) { // string representation of Cell
    return "[" + std::to_string(c.x) + "," + std::to_string(c.y) + 
         "," + std::to_string(c.w) + "," + std::to_string(c.h) + "]";
}

double sf(const Cells& cells) { // the squarishness goodness function
    double sf = 0.0;
    for (const Cell& c : cells) sf += (c.w-c.h)*(c.w-c.h);
    return sf;
}

using Partition = std::vector;
using Partitions = std::vector;

std::string toString(const Partition& partition) { //  string representation of Partition
    std::string s{};
    for (const int i : partition) s += std::to_string(i) + " ";
    return s;
}

    // modified from: "Generate all unique partitions of an integer" (geeksforgeeks.org).
Partitions allPartitions(const int N) {
    Partitions partitions;
    std::vector p(N);
    int k = 0;

    p[k] = N;
    while (true) {
        partitions.push_back(Partition{});
        std::copy_n(p.begin(), k+1, std::back_inserter(partitions.back()));
        int rem_val = 0;
        while (k >= 0 && p[k] == 1) {
            rem_val += p[k];
            k--;
        }
        if (k < 0) return partitions;
        p[k]--;
        rem_val++;
        while (rem_val > p[k]) {
            p[k+1] = p[k];
            rem_val = rem_val - p[k];
            k++;
        }
        p[k+1] = rem_val;
        k++;
    }
}

     // layout the cubes of a certain partition in a W, H rectangle
Cells fixate_layout(const Partition& p, const double W, const double H) {
    Cells cells;
    const int j_cells = static_cast(p.size());
    const double h = H/j_cells; // height per cell
    for (int j=0; j best_partition(const int N, const double W, const double H) {
    const Partitions partitions = allPartitions(N);
    double min = std::numeric_limits::max();
    Partition best = {};
    for (const Partition& partition : partitions) {
        const Cells cells = fixate_layout(partition, W, H);
        const double SF = sf(cells);
        if (SF < min) {
            min = SF;
            best = partition;

        }
    }
    return std::make_pair(best, min);
}

    // Prints all partitions of N and the corresponding sf value for an W-H rectangle
void test1(const int N, const double W, const double H) {
    const Partitions partitions = allPartitions(N);
    for (const Partition& partition : partitions) {
        const Cells cells = fixate_layout(partition, W, H);
        const double SF = sf(cells);
        std::cout << toString(partition) << " (" << SF << ")" << std::endl;
    }
}
    // Prints the be partition (with the lowest sf value) for all N from 1 up to N
void test2(const int N, const double W, const double H) {
    for (int n=1; n<=N; ++n) {
        const auto& [best, SF] = best_partition(n, W, H);
        std::cout << "N=" << n << ": " << toString(best) << " (" << SF << ")" << std::endl;
    }
}

void main_squarish() { // the main function
    const double W = 4, H = 6;
    {
        std::cout << "test 1" << std::endl;
        const int N = 5; // partition N
        std::cout << "--- straight ---" << std::endl;
        test1(N,W,H);
        std::cout << "--- flipped ---" << std::endl;
        test1(N,H,W); // W and H are switched
    }
    {
        std::cout << "test 2" << std::endl;
        const int N = 12; // partitions 1 - 12
        std::cout << "--- straight ---" << std::endl;
        test2(N,W,H);
        std::cout << "--- flipped ---" << std::endl;
        test2(N,H,W); //W and H are switched
    }
}

What is an algorithm to divide a rectangle into N number of square(ish) cells?

Answers (2)

Related Questions