如何递归和迭代地在盒子内划分盒子？

Question

class Point:
    def __init__(self, x, y):
        self.x=x
        self.y=y
class Rect:
    def __init__(self, up, dw):
        self.up=up
        self.dw=dw
        self.next=[]
    def next_empty(self):
        return len(self.next)<=0



def inside(p1, p2, p3):
    return p3.x>=p1.x and p3.y<=p1.y and p3.x<=p2.x and p3.y>=p3.y

def create_box(root, parts):
    width=root.dw.x-root.up.x
    height=root.up.y-root.dw.y
    divx=width/parts
    divy=height/parts

    x=y=0
    for _y in range(parts):
        for _x in range(parts):
            rect=Rect(up=Point(x, y+divy), dw=Point(x+divx, y))
            root.next.append(rect)
            x+=divx
        x=0
        y+=divy
    return True

def create_tree(root, parts, n=2):
    pass
    
    

up=Point(0, 180)
dw=Point(360, 0)
root=Rect(up, dw)

#create_tree(root, 20)

上面的代码有两个class点和矩形。 Point表示图形上的一个点，Rect表示一个矩形，'Rect.up'属性是左上点，'Rect.dw'是右下点。

create_box 函数将给定的矩形对象分成 parts*parts 个矩形，并将其保存在 'Rect.next' 数组中。所以第一个 rect 是 up=(18, 0) dw=(18,0)，第二个 up=(18, 18) dw=(36, 0)。我有一个 create_tree 函数可以创建 n 个节点的树，但我在这里遇到了一些问题。例如：首先创建树会将根分成 x 个部分，这些 x 个部分将再次分成 x 个部分，类似地，这个过程将继续，直到达到 n 个节点。我希望 create_tree 函数在以下行为中起作用：-

def create_tree(root, parts, n=2):
    root_arr=[root]
    # when n=1
    if n==1:
        for r in root_arr:
            create_box(r, parts)

    #when n=2
    if n==2:
        for r in root_arr:
            create_box(r, parts)
        for r in root_arr:
            for j in r.next:
                create_box(j, parts)
    # when n=3
    if n==3:
        for r in root_arr:
            create_box(r, parts)
        for r in root_arr:
            for j in r.next:
                create_box(j, parts)
        for r in root_arr:
            for j in r.next:
                for q in j.next:
                    create_box(q, parts)
# N can be any number

我在添加这种循环时遇到了问题。使用递归和迭代应该如何解决？

Answer 1

使用 DFS 方法，您可以编写一个递归函数来包装盒子创建任务：

def create_boxes_recursively(root, parts, levels):
    root_arr = [root]
    create_box(root, parts)
    if levels==1:
        return
    if not root.next:
        return
    for j in root.next:
        create_boxes_recursively(j, parts, levels-1)

至于迭代，您可以使用 BFS 方法，它会跟踪下一级的所有节点：

def create_boxes_iteratively(root, parts, levels):
    next_nodes = [root]
    curr_level = 0
    while next_nodes and curr_level<levels:
        temp_array = []
        for node in next_nodes:
            create_box(node, parts)
            temp_array += node.next
        curr_level += 1
        next_nodes = temp_array

如何递归和迭代地在盒子内划分盒子？

How to keep dividing a box inside box recursively and iteratively?

python

algorithm

python-2.x

python-3.x