Para resolver o problema, utilizaremos de recursão e orientação a objetos, utilizando a biblioteca Turtle para representar os desenhos por meio de Sistemas de Lindenmayer. O uso de recursão é interessante devido à natureza de auto-similaridade da figura, em que cada ramo da árvore pode ser interpretado como uma versão menor dela mesma.
Sistemas de Lindenmayer, ou L-systems, são um tipo de gramática formal, bem como um sistema de reescrita, e são utilizados principalmente para representar figuras fractais e plantas. A grosso modo, eles são iniciados por um axioma \(w\), cujas letras serão, a cada etapa de derivação, reescritas obedecendo seu conjunto (finito) de regras de produção \(P \). No nosso caso, temos que \(P = \{p_{1}, p_{2}, p_{3}, p_{4}, p_{5}\}\).
Axioma e regras
Um elemento central de nosso sistema é o mecanismo de atraso \(d\), também chamado de delay. Ele determina que uma ramificação terá de esperar até \(D\) gerações (ou derivações) para criar ramificações novamente. Formalmente: \(d \in [0, D]\), com \(D \in \mathbb{N}\).
Abaixo, temos o axioma e as regras de produção de nosso sistema detalhados:
O axioma \(w\) dá origem a um ápice ou nó \(A\) com atraso zero, ou seja, já pronto para produzir novas ramificações. O comportamento das regras \(A(d)\) e \(B(d)\), por sua vez, depende do parâmetro \(d\). Caso \(d = 0\), novas ramificações serão criadas; do contrário, o nó \(A\) ou \(B\) em questão aguardará mais \(d\) gerações até se expandir novamente.
A regra \(F(a)\), por fim, conta com um fator de alongamento \(R\), que, no nosso exemplo, faz com que a distância \(a\), a ser percorrida, aumente por um fator \(R = 1.36\) a cada nova geração. Note que a regra \(F(a)\) tem um comportamento único, independente do valor de seu input \(a\).
Comandos
Alguns comandos que aparecem recorrentemente em L-systems, e que nos serão de valia, são:
- +: gire a tartaruga para a esquerda, a determinados graus
- -: gire a tartaruga para a direita, a determinados graus
- [: salve o estado da tartaruga (posição e direção) naquele momento
- ]: retorne ao último estado salvo da tartaruga
Classes e resolução do problema
Para resolver nosso problema, foram criadas duas classes. Na primeira, CompoundLeaves, logo de início recebemos os parâmetros desejados, como especificados anteriormente. Em seguida, chamamos o método "setup_configs", que leva a tartaruga para o ponto inicial desejado, e altera algumas configurações para aumentar sua velocidade.
Ainda, criamos um objeto deque, chamado "state", para salvar o estado da tartaruga em determinados pontos. Deques são objetos da biblioteca Collections que se assemelham a listas, e são otimizados para servirem tanto como pilhas, quanto como filas - aqui, usaremos como uma pilha. As tarefas de salvar e de retornar a determinado estado são feitas pelos métodos "savestate" e "loadstate", respectivamente.
import turtle
from collections import deque
class CompoundLeaves(object):
""" Compound leaves with alternating branching patterns objects from
Algorithm Beauty of Plants - page 130 """
def __init__(self, turtle, size = 0.125, D = 1, n = 20, R = 1.36, ang = 45):
""" Initiates the class. Also creates a stack for check-pointing
turtle's state.
turtle: turtle's name
size: length of the movement
D: apical delay
n: number of generations (a.k.a. derivation length)
R: internode elongation rate
ang: rotation angle
"""
# Parameters:
self.t = turtle
self.size = size
self.D = D
self.n = n
self.R = R
self.ang = ang
# Other resources
self.setup_configs(self.t) # Takes turtle to desired start position
self.state = deque() # Creates the stack
return None
def setup_configs(self, t):
""" Takes turtle to desired start position. Also improves performance."""
t.speed(0) # 0 = Highest speed
t.hideturtle() # Even more performance
# Turtle position
t.penup() # No drawing in-between
t.setheading(90) # Front-faced
t.setposition(0, -200) # (x, y) = (0, -200) -> arbitrary point, could be (0, 0) as well
t.pendown() # Drawing allowed once again
t.width(1.25) # Line's width
return None
def savestate(self, t):
""" Adds current state (position and heading) to a stack """
self.state.append([t.position(), t.heading()])
return None
def loadstate(self, t):
""" Return turtle to previous checkpoint"""
t.penup() # No drawing in-between current state and checkpoint.
previous_checkpoint = self.state.pop() # Gets previous checkpoint
# Moves turtle to previous checkpoint
t.setposition(previous_checkpoint[0])
t.setheading(previous_checkpoint[1])
t.pendown() # Drawing allowed from now on.
return None
Em seguida, criamos a classe Ex512a, que é uma classe filha da CompoundLeaves. Escreveremos o axioma e as regras de nossa produção como os métodos da classe filha; note ainda que ela herdará todos os métodos da classe mãe.
class Ex512a(CompoundLeaves):
""" Letter a) from Exercise nº 5.12, from Algorithm Beauty of Plants. """
def axiom(self):
""" Axiom: A(0)
d: current stage of apical delay (0 <= d <= D)
"""
# Takes off "self" from variable names, to keep it simple
t = self.t
n = self.n
if n == 0: # If it's the last generation, just move forward
t.forward(self.size)
else:
# A(0)
self.rule_a(t, d = 0, n = n - 1)
return None
def rule_a(self, t, d, n):
""" Rule:
A(d) : d > 0 -> A(d-1)
A(d) : d = 0 -> F(1) [+A(D)] F(1) B(0)
"""
if n == 0: # If it's the last generation, just move forward
t.forward(self.size)
return None
elif d > 0:
self.rule_a(t, d - 1, n - 1) # A(d-1): waits delay time
return None
else:
self.rule_f(t, n = n - 1, a = 1) # F(1)
# [+A(D)]
self.savestate(t)
t.left(self.ang)
self.rule_a(t, d = self.D, n = n - 1)
self.loadstate(t)
# F(1) B(0)
self.rule_f(t, n = n - 1, a = 1)
self.rule_b(t, d = 0, n = n - 1)
return None
def rule_b(self, t, d, n):
""" Rule:
B(d) : d > 0 -> B(d-1)
B(d) : d = 0 -> F(1) [-B(D)] F(1) A(0)
"""
if n == 0: # If it's the last generation, just move forward
t.forward(self.size)
return None
elif d > 0:
self.rule_b(t, d = d - 1, n = n - 1) # B(d-1): waits delay time
return None
else:
self.rule_f(t, n = n - 1, a = 1) # F(1)
# [-B(D)]
self.savestate(t)
t.left(-self.ang)
self.rule_b(t, d = self.D, n = n - 1)
self.loadstate(t)
# F(1) A(0)
self.rule_f(t, n = n - 1, a = 1)
self.rule_a(t, d = 0, n = n - 1)
return None
def rule_f(self, t, n, a):
""" Rule: F(a): * -> F(a * R)
a: size input
In other words, it keeps multiplying input value 'a' by parameter
'R' each time the function is called.
"""
if n == 0:
t.forward(self.size * a)
else:
self.rule_f(t, n = n - 1, a = a * self.R)
return None
Por fim, algumas chamadas de funções precisaram ser utilizadas no Python para garantir que o Spyder não travaria após a execução da biblioteca Turtle. Descrevo-as abaixo.
if __name__ == '__main__':
# Avoids crashing
try:
my_turtle = turtle.Turtle() # Generates the turtle
except:
my_turtle = turtle.Turtle() # Generates the turtle
wn = turtle.Screen() # Avoids crashing
# Draws the leaves
my_leaves = Ex512a(my_turtle, size = 0.125, n = 20, ang = 45, D = 1)
my_leaves.axiom()
# Saves image to your directory
turtle.getscreen().getcanvas().postscript(file='CompoundLeavesAlternating.ps')
# Avoids crashing. PS: remove if you're not using Windows OS.
from sys import platform
if platform=='win32':
wn.exitonclick()
Resultado final:
Note que é possível facilmente replicar as figuras "b" e "c" do exercício, apenas alterando os parâmetros \(D, R\) e \(n\) (derivation length) pelos especificados na tabela abaixo:
REFERÊNCIAS
Como desenhar árvores usando pilhas e recursões?
Como replicar gráficos usando modelagem L-systems no Python?
Como desenhar o fractal "Gosper Hexagonal Curve" com recursão usando o Python?
Como utilizar recursão para desenhar fractais no Python?