Algorithm for enumerating all possible ways a rectangle can be split into n smaller rectangles

Question

See title for question. The only other limitation is that the smaller rectangles have to be formed by diving bigger rectangles in half. I have attached the result for n=3 and n=4 below. Hopefully this will suffice to explain the meaning of my questions.

Currently, I have an inefficient recursive algorithm that divides each rectangle horizontally and vertically, and keeps track of all possible combinations in an array. I do not like this algorithm. It is polynomial time, seems unnecessarily complicated and gives me duplicates, as seen in the n=4 picture (hint: look for four equal quadrants)

I was wondering if there might be a better solution to this? I was expermenting with using a 4-ary tree (where each child gets a vertical or horizontal piece), and am able to construct the tree but getting all possible combinations from the tree seems to be eluding me. I'll post my tree boiler plate code below:

class Node:
    #value is an tuple (x0,y0,x1,y1)
    def __init__(self, value):
        self.horizontal = []
        self.vertical = []
        self.value = value
    def createTree(depth, currDepth, node):
        if currDepth == depth:
            return
        node.horizontal.append(Node(getLeftRect(node.value)))
        node.horizontal.append(Node(getRightRect(node.value)))
        node.vertical.append(Node(getTopRect(node.value)))
        node.vertical.append(Node(getBotRect(node.value)))
        createTree(depth, currDepth+1, node.horizontal[0])
        createTree(depth, currDepth+1, node.horizontal[1])
        createTree(depth, currDepth+1, node.vertical[0])
        createTree(depth, currDepth+1, node.vertical[1])

Any suggestions/help is welcome!

Note: This is not coursework. I'm trying to make a UI for a custom virtual monitor tool I'm working on.

Answer 1

One strategy is, when we cut vertically, don't let both the left half and the right half have a horizontal cut. This involves some case analysis.

In Python 3, we first have data types to represent subdivided rectangles.

import collections

H = collections.namedtuple('H', ('top', 'bottom'))  # horizontal cut
V = collections.namedtuple('V', ('left', 'right'))  # vertical cut
W = collections.namedtuple('W', ())                 # whole rectangle

Here are the generators.

def generate(n):
    assert isinstance(n, int) and n >= 0
    yield from generate_with_horizontal(n)
    yield from generate_without_horizontal(n)


def generate_with_horizontal(n):
    assert isinstance(n, int) and n >= 0
    for k in range(n):
        for top in generate(k):
            for bottom in generate(n - 1 - k):
                yield H(top, bottom)


def generate_without_horizontal(n):
    assert isinstance(n, int) and n >= 0
    if n == 0:
        yield W()
    for k in range(n):
        for left in generate_with_horizontal(k):
            for right in generate_without_horizontal(n - 1 - k):
                yield V(left, right)
        for left in generate_without_horizontal(k):
            for right in generate(n - 1 - k):
                yield V(left, right)