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

Como replicar compound leaves com ramificações alternantes usando Lindenmayer-Systems (L-Systems)?

+1 voto
24 visitas
perguntada Set 3 em Ciência da Computação por Rodrigo Stuckert (46 pontos)  

A imagem a ser replicada por meio de recursão é a Figura 5.12(a) do livro "The Algorithmic Beauty of Plants", de Przemyslaw Prusinkiewicz e Aristid Lindenmayer (1991).

A imagem será apresentada aqui.

Compartilhe

1 Resposta

+1 voto
respondida Set 3 por Rodrigo Stuckert (46 pontos)  
editado 2 dias atrás por Rodrigo Stuckert

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:

A imagem será apresentada aqui.

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:
A imagem será apresentada aqui.

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:

A imagem será apresentada aqui.


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?

comentou Set 13 por Renata Oliveira (46 pontos)  
Olá Rodrigo! A tua resposta está completa e bem explicada. A implementação em python está realmente muito interessante. Copiando e colando o código no meu editor, quando rodei acabei recebendo uma mensagem de erro na função "loadstate" (t_sety(previous_checkpoint[0][3]) IndexError: tuple index out of range). Para contornar este erro, fiz uma pequena alteração na função: no lugar de definir as coordenadas x e y, bastou definir a posição de t com "t.setposition(previous_checkpoint[0])". Desta forma o código rodou sem problemas e obtive a mesma imagem da tua resposta.   Abraço!
comentou Set 13 por Rodrigo Stuckert (46 pontos)  
Olá Renata! Obrigado pela observação, já fiz a correção. Forte abraço!
...