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

Replicar a figura 3.12 do livro The Algorithmic Beauty of Plants - Przemyslaw Prusinkiewicz and Aristid Lindenmayer (1991)

0 votos
24 visitas
perguntada Dez 7, 2020 em Ciência da Computação por JOAO PAULO (26 pontos)  

Replicar a figura 3.12 do livro The Algorithmic Beauty of Plants - Przemyslaw Prusinkiewicz
and Aristid Lindenmayer (1991) utilizando L-systems (Lindenmayer-Systems)

Compartilhe

1 Resposta

0 votos
respondida Dez 7, 2020 por JOAO PAULO (26 pontos)  

O livro apresenta um algoritmo chamado de “L systems” bastante útil para replicar as inúmeras figuras de árvores, galhos e tudo que envolve planta e botânica. O sistema L é um algoritmo que possui um alfabeto de símbolos que podem ser usados para fazer uma cadeia de caracteres.
Em termos gerais o sistema L pode ser definido como um algoritmo desenhado para modelar o crescimento de sistemas biológicos. Nesse caso, poderíamos pensar o sistema L como um algoritmo contendo instruções (utilizando letras do alfabeto) de como uma simples célula, por exemplo, pode crescer (ou se reproduzir) a fim de se tornar parte de um organismo mais completo.
A construção de um algoritmo do sistema L cumpre basicamente duas etapas que podem ser aplicadas em muitas figuras mostradas no livro. As etapas são definidas da seguinte maneira:

  1. Determinar um conjunto de regras de crescimento a serem aplicadas. Esse conjunto de regras são derivados de um axioma que representa o ponto inicial de crescimento.

  2. Dado esse conjunto de regras, traçar o desenho do ser vivo em questão.

Naturalmente, cada planta, folha, árvore, possui suas características e para desenhá-las podem ser necessárias pequenas alterações das 2 etapas passadas acima; no entanto, o “core” permanece o mesmo.
Em relação ao exercício, temos que replicar a seguinte gravura:
A imagem será apresentada aqui.

A minha estratégia para replicá-la foi em um primeiro momento dividi-la em partes. Podemos notar que a árvore é composta de ramos laterais, que por sua vez possuem sub ramos laterais com frutos redondos (ou folhas). Logo, tomei o seguinte sub ramo e tentei descrevê-lo:

A imagem será apresentada aqui.

Como esse ramo é mais simples de se escrever, escrevi as instruções da seguinte maneira:
Primeiro criei uma função para criar o sistema L.

def createLSystem(numIters,axiom):
    startString = axiom
    endString = ""
    for i in range(numIters):
        print('iterações',i)
        endString = processString(startString)
        print('endString',endString)
        startString = endString
        print(' startString',endString)
    return endString

Depois escrevi uma função para juntar as instruções (letras do alfabeto).

def processString(oldStr):
            newstr = ""
            for ch in oldStr:
                newstr = newstr + applyRules(ch)

            return newstr

Essas instruções chamam uma função que aplica o conjunto de regras necessárias para construir a muda. As definições de algumas dessas letras serão dadas no decorrer da explicação:

def applyRules(ch):
        newstr = ""

        if ch == 'W':
            newstr = 'FF[+A][+FF[Z]FF[+A][+FC]F[-B][-FC]F[+A][+FC]F[-B][-FC]F[+A][+FC]FFC] '   # Rule 1

        elif ch == 'D':
            newstr = 'FF[-B][-F[X]F[Z]F[-B][-FC]F[+A][+FC]F[-B][-FC]F[+A][+FC]F[-B][-FC]FFC]'   # Rule 2

        elif ch == 'Y':
            newstr = 'FF[+A][+FC]F[-B][-FC]F[+A][+FC]F[-B][-FC]F[+A][+FC]FFC]'   # Rule 3        
        else:
            newstr = ch    # no rules apply so keep the character

        return newstr

E por fim, escrevo uma função que traça as linhas da árvore utilizando a biblioteca Turtle. Aqui vale chamar a atenção de um ponto: como o galho possui ramificações e folhas, foram necessários inserir comandos específicos para essas características, quando necessários. Por exemplo: a letra L desenha os mini-galhos que o cabo principal apresenta, enquanto a letra Z desenha o mini-galhos que o sub-ramo apresenta.

def drawLsystem(aTurtle, instructions, angle, distance):
    aTurtle_state = Stack() 
    for cmd in instructions:
        if cmd == 'F':  # internode. É o pauzinho q liga um nó no outro
            aTurtle.forward(distance)
        elif cmd == '[': # guarda posição na pilha para retormar depois
            aTurtle_state.push(get_turtle_state(aTurtle))

        elif cmd == 'L': # desenha a folha curva (ramo principal)
            aTurtle.circle(0.70,110)
        elif cmd == 'Z': # desenha a folha curva (ramo 2)
            aTurtle.circle(0.40,110)
        elif cmd == 'N': # desenha a folha curva (ramo 3)
            aTurtle.circle(0.20,110)    
        elif cmd == 'A': # desenha as mini folhas curvas (antes da bifurcação)
            aTurtle.circle(0.40,60)

        elif cmd == 'R': # desenha a folha curva (ramo principal)
            aTurtle.circle(-0.70,110)
        elif cmd == 'X': # desenha a folha curva (ramo 2)
            aTurtle.circle(-0.40,110)
        elif cmd == 'M': # desenha a folha curva (ramo 3)
            aTurtle.circle(-0.20,110)    
        elif cmd == 'B': # desenha as mini folhas curvas (antes da bifurcação)
            aTurtle.circle(-0.40,60)    


        elif cmd == 'C': # desenha o círculo (pode ser feito também com ".circle")
            aTurtle.dot(8)


        elif cmd == '+': # gira a direção da tartaruga em 45 graus à direita
            aTurtle.left(angle)
        elif cmd == '-': # gira a direção da tartaruga em 45 graus à direita
            aTurtle.right(angle)


        elif cmd == ']':  # busca a última posição guardada na pilha para retomar o ramo pendente
            aTurtle.penup()
            set_turtle_state(aTurtle, aTurtle_state.pop())
            aTurtle.pendown()          

Como complemento, também criamos uma classe para estocar as posições da Turtle. Para construir essa classe utilizei a classe disponível em: como-replicar-graficos-usando-modelagem-systems-no-python.

class Stack:
    # Construtor da classe
    def __init__(self):
        self.items = []
    # Método: acrescenta o item à pilha
    def push(self, item):
        self.items.append(item)
    # Método: retira item da pilha
    def pop(self):
        return self.items.pop()

# Função que recupera a tupla (direção/sentido, posição)
def get_turtle_state(t_obj):
    return t_obj.heading(), t_obj.position()

# Função que modifica a direção/sentido e a posição da turtle
def set_turtle_state(t_obj, state):
    t_obj.setheading(state[0])
    t_obj.setposition(state[1][0], state[1][1])

O código completo pode ser visto a seguir

import turtle



def createLSystem(numIters,axiom):
        startString = axiom
        print('primeiro de tudo',startString)
        endString = ""
        for i in range(numIters):
            print('iterações',i)
            endString = processString(startString)
            print('endString',endString)
            startString = endString
            print(' startString',endString)
        return endString

def processString(oldStr):
            newstr = ""
            for ch in oldStr:
                newstr = newstr + applyRules(ch)

            return newstr
#
def applyRules(ch):
        newstr = ""

        if ch == 'W':
            newstr = 'FF[+A][+FF[Z]FF[+A][+FC]F[-B][-FC]F[+A][+FC]F[-B][-FC]F[+A][+FC]FFC] '   # Rule 1

        elif ch == 'D':
            newstr = 'FF[-B][-F[X]F[Z]F[-B][-FC]F[+A][+FC]F[-B][-FC]F[+A][+FC]F[-B][-FC]FFC]'   # Rule 2

        elif ch == 'Y':
            newstr = 'FF[+A][+FC]F[-B][-FC]F[+A][+FC]F[-B][-FC]F[+A][+FC]FFC]'   # Rule 3        
        else:
            newstr = ch    # no rules apply so keep the character

        return newstr

# Classe pilha (somente com os métodos utilizados neste exemplo)
class Stack:
    # Construtor da classe
    def __init__(self):
        self.items = []
    # Método: acrescenta o item à pilha
    def push(self, item):
        self.items.append(item)
    # Método: retira item da pilha
    def pop(self):
        return self.items.pop()

# Função que recupera a tupla (direção/sentido, posição)
def get_turtle_state(t_obj):
    return t_obj.heading(), t_obj.position()

# Função que modifica a direção/sentido e a posição da turtle
def set_turtle_state(t_obj, state):
    t_obj.setheading(state[0])
    t_obj.setposition(state[1][0], state[1][1])



def drawLsystem(aTurtle, instructions, angle, distance):
    aTurtle_state = Stack() 
    for cmd in instructions:
        if cmd == 'F':  # internode. É o pauzinho q liga um nó no outro
            aTurtle.forward(distance)
        elif cmd == '[': # guarda posição na pilha para retormar depois
            aTurtle_state.push(get_turtle_state(aTurtle))

        elif cmd == 'L': # desenha a folha curva (ramo principal)
            aTurtle.circle(0.70,110)
        elif cmd == 'Z': # desenha a folha curva (ramo 2)
            aTurtle.circle(0.40,110)
        elif cmd == 'N': # desenha a folha curva (ramo 3)
            aTurtle.circle(0.20,110)    
        elif cmd == 'A': # desenha as mini folhas curvas (antes da bifurcação)
            aTurtle.circle(0.40,60)

        elif cmd == 'R': # desenha a folha curva (ramo principal)
            aTurtle.circle(-0.70,110)
        elif cmd == 'X': # desenha a folha curva (ramo 2)
            aTurtle.circle(-0.40,110)
        elif cmd == 'M': # desenha a folha curva (ramo 3)
            aTurtle.circle(-0.20,110)    
        elif cmd == 'B': # desenha as mini folhas curvas (antes da bifurcação)
            aTurtle.circle(-0.40,60)    


        elif cmd == 'C': # desenha o círculo (pode ser feito também com ".circle")
            aTurtle.dot(8)


        elif cmd == '+': # gira a direção da tartaruga em 45 graus à direita
            aTurtle.left(angle)
        elif cmd == '-': # gira a direção da tartaruga em 45 graus à direita
            aTurtle.right(angle)


        elif cmd == ']':  # busca a última posição guardada na pilha para retomar o ramo pendente
            aTurtle.penup()
            set_turtle_state(aTurtle, aTurtle_state.pop())
            aTurtle.pendown()                     



if __name__ == '__main__':            
    aTurtle = turtle.Turtle()
    wn = turtle.Screen()
    turtle.setworldcoordinates(-25, -1, 20, 20)
    inst=createLSystem(2, "[FF[L]DWDY")
    aTurtle.penup()
    aTurtle.setheading(90)
    aTurtle.pendown()
    aTurtle.width(2)
    drawLsystem(aTurtle, inst, 45, 0.8)                       

    turtle.done()

Terminado esse código, o que temos que fazer agora é adaptá-lo para a figura 3.12. Note que essa árvore é uma extensão da árvore construída anteriormente; na verdade é uma árvore contendo 5 estruturas iguais a do código anterior (2 a esquerda, 2 a direita e uma central). Portanto teremos o seguinte código:

import turtle

def createLSystem(numIters,axiom):
        startString = axiom
        endString = ""
        for i in range(numIters):
            print('iterações',i)
            endString = processString(startString)
            print('endString',endString)
            startString = endString
            print(' startString',endString)
        return endString

def processString(oldStr):
            newstr = ""
            for ch in oldStr:
                newstr = newstr + applyRules(ch)

            return newstr

def applyRules(ch):
        newstr = ""
        if ch == 'K':
            newstr = 'FF[X]'      # Rule 1 

        elif ch == 'S':
            newstr = 'FF[Z]'   # Rule 2        

        elif ch == 'U':
            newstr = 'WDWY'   # Rule 3

        elif ch == 'W':
            newstr = 'FF[+A][+F[N]F[M]F[+A][+FC]F[-B][-FC]F[+A][+FC]F[-B][-FC]F[+A][+FC]FFC] '   # Rule 4

        elif ch == 'D':
            newstr = 'FF[-B][-F[M]F[N]F[-B][-FC]F[+A][+FC]F[-B][-FC]F[+A][+FC]F[-B][-FC]FFC] '   # Rule 5

        elif ch == 'Y':
            newstr = 'FF[+A][+FC]F[-B][-FC]F[+A][+FC]F[-B][-FC]F[+A][+FC]FFC]'   # Rule 6        

        elif ch == 'P':
            newstr = 'DWDY'       # Rule 7   

        elif ch == 'H':
            newstr = '    FFFFFFF[-X][-'  # Rule 8   

        elif ch == 'J':
            newstr = 'FFFFFFF[+Z][+'   # Rule 9     

        elif ch == 'V':
            newstr = '    FFFFFFFF'   # Rule 10      

           # Rule 1
        else:
            newstr = ch    # no rules apply so keep the character

        return newstr

# Classe pilha (somente com os métodos utilizados neste exemplo)
class Stack:
    # Construtor da classe
    def __init__(self):
        self.items = []
    # Método: acrescenta o item à pilha
    def push(self, item):
        self.items.append(item)
    # Método: retira item da pilha
    def pop(self):
        return self.items.pop()

# Função que recupera a tupla (direção/sentido, posição)
def get_turtle_state(t_obj):
    return t_obj.heading(), t_obj.position()

# Função que modifica a direção/sentido e a posição da turtle
def set_turtle_state(t_obj, state):
    t_obj.setheading(state[0])
    t_obj.setposition(state[1][0], state[1][1])



def drawLsystem(aTurtle, instructions, angle, distance):
    aTurtle_state = Stack() 
    for cmd in instructions:
        if cmd == 'F':  # internode. É o pauzinho q liga um nó no outro
            aTurtle.forward(distance)
        elif cmd == '[': # guarda posição na pilha para retormar depois
            aTurtle_state.push(get_turtle_state(aTurtle))

        elif cmd == 'L': # desenha a folha curva (ramo principal)
            aTurtle.circle(0.70,110)
        elif cmd == 'Z': # desenha a folha curva (ramo 2)
            aTurtle.circle(0.40,110)
        elif cmd == 'N': # desenha a folha curva (ramo 3)
            aTurtle.circle(0.20,110)    
        elif cmd == 'A': # desenha as mini folhas curvas (antes da bifurcação)
            aTurtle.circle(0.40,60)

        elif cmd == 'R': # desenha a folha curva (ramo principal)
            aTurtle.circle(-0.70,110)
        elif cmd == 'X': # desenha a folha curva (ramo 2)
            aTurtle.circle(-0.40,110)
        elif cmd == 'M': # desenha a folha curva (ramo 3)
            aTurtle.circle(-0.20,110)    
        elif cmd == 'B': # desenha as mini folhas curvas (antes da bifurcação)
            aTurtle.circle(-0.40,60)    

        elif cmd == 'C': # desenha o círculo (pode ser feito também com ".circle")
            aTurtle.dot(5)

        elif cmd == '+': # gira a direção da tartaruga em 40 graus à direita
            aTurtle.left(angle)
        elif cmd == '-': # gira a direção da tartaruga em 40 graus à direita
            aTurtle.right(angle)

        elif cmd == ']':  # busca a última posição guardada na pilha para retomar o ramo pendente
            aTurtle.penup()
            set_turtle_state(aTurtle, aTurtle_state.pop())
            aTurtle.pendown()                     



if __name__ == '__main__':            
    aTurtle = turtle.Turtle()
    wn = turtle.Screen()
    turtle.setworldcoordinates(-25, -1, 20, 20)
    aTurtle.penup()
    aTurtle.setheading(90)
    aTurtle.pendown()
    aTurtle.width(0.9)
    aTurtle.speed(9)
    inst=createLSystem(2, "[FFF[L]FFF[-X][-KUJSPHKUJSPVP")
    drawLsystem(aTurtle, inst, 40, 0.4)                       

    turtle.done()

Com o seguinte resultado:
A imagem será apresentada aqui.

comentou Dez 15, 2020 por Fernando Fellows (16 pontos)  
Olá, João. Achei interessante a estratégia de tomar primeiro um ramo, destrinchá-lo e partir para toda a imagem, tendo em vista que o L System é utilizado para árvores e botânicos em geral especialmente pela similaridade entre suas partes.
Uma coisa que poderia fazer é utilizar o instrumental de regras do L System para as folhas curvas, por exemplo, para não ter que reescrever o código para cada trecho. Ficaria muito mais enxuta a solução e poderia usufruir o que há de mais eficiente no L System.
...