Смотрите название вопроса. Единственным другим ограничением является то, что меньшие прямоугольники должны быть сформированы путем погружения больших прямоугольников пополам. Я приложил результат для n = 3 и n = 4 ниже. Надеюсь, этого будет достаточно, чтобы объяснить смысл моих вопросов.
В настоящее время у меня есть неэффективный рекурсивный алгоритм, который делит каждый прямоугольник по горизонтали и вертикали и отслеживает все возможные комбинации в массиве. Мне не нравится этот алгоритм. Это полиномиальное время, кажется излишне сложным и дает мне дубликаты, как видно на рисунке n = 4 (подсказка: ищите четыре равных квадранта)
Мне было интересно, может ли быть лучшее решение для этого? Я экспериментировал с использованием 4-арного дерева (где каждый ребенок получает вертикальный или горизонтальный кусок), и я могу построить дерево, но получение всех возможных комбинаций из дерева, похоже, ускользает от меня. Я выложу код дерева котельной плиты ниже:
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])
Любые предложения/помощь приветствуется!
Примечание: это не курсовая работа. Я пытаюсь создать пользовательский интерфейс для настраиваемого инструмента виртуального монитора, над которым я работаю.
