I want to divide a block into n number of smaller blocks, grouped in 4s. Something like this:

I'm not sure if I should be using a loop or recursion of some sort but the rules of the algorithm would be something like:

• if 1 dont split
• if 2 split in half
• if 3 split in half and then split 1 of the halves in half again
• if 4 split in half and then split both halves in half again
• if 5 split in half and then split both halves in half again then split one of the quarters in half
• etc

CodePudding user response：

This could be done with a queue -- iteratively -- much like you would do with a breadth-first traversal. A bit specific is that you want a block to be first split into 4 smaller blocks before moving to another block. So that means you'll have a loop over a fifo-queue (deque) in which one block will be popped from the deque, and three smaller ones will be pushed unto it. Only when the number of splits becomes less than 3, you'll have to produce fewer blocks.

Below you'll find a runnable JavaScript implementation, where the blocks are represented by instances of a Rectangle class (with coordinates of the top-left corner, and its dimensions). A split will create from one instance two new instances. This snippet will draw each rectangle once the requested number of splits have been performed:

class Rectangle {
    constructor(left, top, width, height) {
        Object.assign(this, {left, top, width, height});
    }
    splitVertically() {
        const width = this.width / 2;
        return [
            new Rectangle(this.left, this.top, width, this.height),
            new Rectangle(this.left   width, this.top, width, this.height)
        ];
    }
    splitHorizontally() {
        const height = this.height / 2;
        return [
            new Rectangle(this.left, this.top, this.width, height),
            new Rectangle(this.left, this.top   height, this.width, height)
        ];
    }
    draw(ctx) {
        ctx.rect(this.left 0.5, this.top 0.5, this.width, this.height);
        ctx.stroke();
    }
}

function splitBlock(n, rect) {
    let deque = [rect];
    while (n-- > 0) {
        const rect = deque.shift();
        const arr = rect.splitVertically();
        if (n-- > 0) arr.push(...arr.shift().splitHorizontally());
        if (n-- > 0) arr.push(...arr.shift().splitHorizontally());
        deque.push(...arr);
    }
    return deque;
}

// Example run
const numSplits = 11;
const blocks = splitBlock(numSplits, new Rectangle(0, 0, 180, 180))
// Output the result on a canvas
const ctx = document.querySelector("canvas").getContext("2d");
for (const block of blocks) block.draw(ctx);

<canvas width="181" height="181"></canvas>