Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como desenhar árvores usando pilhas e recursões?

+1 voto
35 visitas

1 Resposta

+1 voto
respondida Abr 16 por Pedro Antero (26 pontos)  
editado Jul 6 por Pedro Antero

Conforme descrito na publicação “The Algorithmic Beauty of Plants”, de Przemyslaw Prusinkiewicz e Aristid Lindenmayer, a estrutura de uma árvore pode ser representada por meio dos chamados Context-Free Lindenmayer Systems (ou simplesmente Sistemas-OL).

Vamos mostrar que a utilização de pilhas e recursões permite codificar Sistemas-OL deste tipo em simples sequências de caracteres (strings).

Tomemos a descrição de comandos de um sistema posicional típico (como o turtle), em que:

  • "F" denota mover-se para frente;
  • "+" denota virar à esquerda em "delta" graus;
  • " - " denota virar à direita em "delta" graus;
  • " [ " denota salvar a posição atual na pilha;
  • " ] " denota retornar a última posição salva na pilha.

Considere, agora, a sequência de caracteres abaixo:
F[+F][-F[-F]F]F[+F][-F]

É fácil ver que essa sequência representa a estrutura em árvore da Figura 1.

A imagem será apresentada aqui.
Figura 1

Quando associado à recursão, esse tipo de codificação viabiliza a representação de estruturas aparentemente complexas a partir da concatenação de poucos caracteres. Isso porque, recursivamente, é possível repetir diversas vezes o mesmo padrão da estrutura da árvore em diferentes escalas dentro da cadeia recursiva.

Como vimos na Figura 1, muitas vezes é necessário retornar a uma posição anterior da árvore para que se possa construir um novo “galho”. Sabe-se que estruturas em pilhas permitem o armazenamento (push) e a posterior recuperação de informações sobre posições anteriores (pop). Portanto, a utilização de pilhas aparece como uma solução bastante interessante para construção de árvores em Sistemas-OL.

Vejamos, por exemplo, a Figura 1.24.b da publicação “The Algorithmic Beauty of Plants” (apresentada na Figura 2). Nossa intenção é reconstruir a representação em árvore a partir da tradução do código em caracteres.

A imagem será apresentada aqui.
Figura 2

Para tanto, primeiramente, importa-se a biblioteca “turtle”, que nos permitirá plotar a estrutura da árvore em um sistema posicional de duas dimensões.

# Class 3 Exercise 9f: create the tree representation shown in Figure 1.24.b of The Algorithmic Beauty of Plants
# (Przemyslaw Prusinkiewicz, Aristid Lindenmayer)

from turtle import *  # imports Turtle library

Depois, definem-se duas funções e uma classe que serão essenciais para que possamos retornar a “ponta da caneta” para coordenadas que já tenham sido percorridas em etapas anteriores do processo de construção da árvore. Repare que na classe Stack (pilha), os métodos push e pop são definidos explicitamente.

def get_turtle_state(t_obj):  # gets turtle's current heading (in degrees) and position (in (x,y) 2-D coordinates)
    return t_obj.heading(), t_obj.position()


def set_turtle_state(t_obj, state):  # sets turtle's heading (in degrees) and position (in (x,y) 2-D coordinates)
    t_obj.setheading(state[0])
    t_obj.setposition(state[1][0], state[1][1])


class Stack:  # creates the Stack class
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):  # defines 'push' function explicitly
        self.items.append(item)

    def pop(self):
        return self.items.pop()  # defines 'pop' function explicitly

    def peek(self):
        return self.items[len(self.items) - 1]

    def size(self):
        return len(self.items)

Agora, constrói-se a função recursiva de geração dos galhos, para cada um dos níveis “n”, conforme indicação do código apresentado na Figura 2.

def build_branch_level_f(n):   # defines outer level building process recursively
    n = n - 1
    if n >= 0:   # while 'level' is greater than zero, do: (please refer to the process definition in Figure 1.24)
        build_branch_level_f(n)  # calls inner level building process
        t_s.push(get_turtle_state(turtle))  # saves turtle's current position in the stack
        turtle.left(delta)  # left turn of delta degrees
        build_branch_level_f(n)  # calls inner level building process
        turtle.penup()  # sets pen's state to 'up' so that no line is drawn when returning to saved position
        set_turtle_state(turtle, t_s.pop())  # return to saved position
        turtle.pendown()  # sets pen's state back to 'down'
        build_branch_level_f(n)  # calls inner level building process
        t_s.push(get_turtle_state(turtle))  # saves turtle's current position in the stack
        turtle.right(delta)  # left turn of delta degrees
        build_branch_level_f(n)  # calls inner level building process
        turtle.penup()  # sets pen's state to 'up' so that no line is drawn when returning to saved position
        set_turtle_state(turtle, t_s.pop())  # return to saved position
        turtle.pendown()  # sets pen's state back to 'down'
        t_s.push(get_turtle_state(turtle))  # saves turtle's current position in the stack
        build_branch_level_f(n)  # calls inner level building process
        turtle.penup()  # sets pen's state to 'up' so that no line is drawn when returning to saved position
        set_turtle_state(turtle, t_s.pop())  # return to saved position
        turtle.pendown()  # sets pen's state back to 'down'
    else:
        turtle.forward(8)  # when the level is equal to zero, returns the forward process

Por fim, declaram-se os parâmetros "delta" e "n" (conforme orientações da Figura 2) e invoca-se a rotina.

turtle = Turtle()  # creates turtle object of Turtle
t_s = Stack()  # t_s (= turtle position stack) is an object of the class "Stack"

turtle.color('dark olive green', 'dark olive green')  # tree-ish trace and fill colors
turtle.pensize(2) # adjust thickness to get a closer print of picture 1.24.b
level = 5  # number of steps
delta = 20  # tilt angle (in degrees)

turtle.penup()  # sets pen's state to 'up' so that no line is drawn when returning to saved position
turtle.right(90)  # takes turtle...
turtle.forward(260)  # ...to the bottom of the drawing palette
turtle.left(180)  # tilts 90 degrees (so that the turtle faces up at the beginning)
turtle.pendown()  # sets pen's state back to 'down'
build_branch_level_f(level)  # calls outer level building process
mainloop() # keeps palette on screen after the script is over

O resultado obtido (Figura 3) é bem similar àquele da Figura 2!

A imagem será apresentada aqui.
Figura 3

comentou Jul 5 por Caue (226 pontos)  
A solução está ótima. Gostaria apenas de fazer um comentário:
Na chamada t_obj.setposition(state[1][0], state[1][3]), não seria state[1][1], por se tratar de um vetor (x,y)?
Você pode dar uma olhada em namedtuple para facilitar nesses casos: https://docs.python.org/3.6/library/collections.html#collections.namedtuple
comentou Jul 6 por Pedro Antero (26 pontos)  
Olá Cauê!
Novamente foi um problema com o Prorum. Por algum motivo ele está incrementando automaticamente os números entre []'s.
Já corrigi o código.
Abs!
...