用于枚举矩形可以分成n个较小矩形的所有可能方式的算法

Question

查看问题标题.唯一的另一个限制是较小的矩形必须通过将较大的矩形潜入一半而形成.我已将结果附加到n = 3和n = 4以下.希望这足以解释我的问题的含义.

目前,我有一个低效的递归算法,可以水平和垂直地划分每个矩形,并跟踪数组中所有可能的组合.我不喜欢这个算法.它是多项式时间,似乎不必要的复杂并给我重复,如n = 4图片中所示(提示:寻找四个相等的象限)

我想知道是否有更好的解决方案吗？我正在尝试使用4-ary树(每个孩子得到一个垂直或水平的部分),并且能够构建树,但从树中获得所有可能的组合似乎是在逃避我.我将在下面发布我的树锅炉板代码:

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])

欢迎任何建议/帮助!

注意:这不是课程作业.我正在尝试为我正在开发的自定义虚拟监视器工具创建UI.

Answer 1

一种策略是,当我们垂直切割时,不要让左半部分和右半部分都有水平切割.这涉及一些案例分析.

在Python 3中,我们首先使用数据类型来表示细分的矩形.

import collections

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

这是发电机.

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)

Answer 2

对于避免重复的递归或树构建算法的想法:
您从一个矩形开始,并且必须分割多次.将其划分为两个方向,并将数字减少一个,然后对于每个分区(垂直和水平),将数字划分为两个部分.

当分成4份(和1份重复)时,该方法产生39次分裂.

我无法避免的唯一重复是十字架.使用这种方法,每当你有一个需要再分割3次或更多次的矩形时,你就会遇到两次交叉.因此,您必须为此添加一些额外的检查.

您还会注意到,由初始2,0分区产生的4组8个解决方案彼此旋转90°,180°和270°.并且由初始1,1分割产生的2组4个溶液彼此成90°旋转.因此,您只能解决一个组,然后旋转以获取所有解决方案.

看起来重复的方法比我最初想的更难以避免.如果添加了2个师,看似非常不同的L3 R1和T2 B2主要的选择导致一些重复4个步骤进一步:

正如David Eisenstat在他的回答中提到的那样,你可以通过仅允许一个矩形的两个半部分(例如,第一个垂直,然后是水平)而不是另一个顺序来避免交叉双打.这意味着在处理矩形时,你必须知道它的"另一半"在哪里,以及是否以及如何分割这一半; 这使得使用此方法所需的代码变得复杂.