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

Como gerar, em Python, uma "Ilha de Koch" utilizando L-Systems (Lindenmayer-Systems)?

+1 voto
157 visitas
perguntada Abr 29, 2017 em Ciência da Computação por Alexandre Costa (6 pontos)  
editado Abr 29, 2017 por Alexandre Costa
Compartilhe

1 Resposta

0 votos
respondida Abr 29, 2017 por Alexandre Costa (6 pontos)  
selecionada Mai 1, 2017 por Alexandre Costa
 
Melhor resposta

Ilhas de Koch

Uma "Ilha de Koch" é um fractal geométrico construído de forma recursiva. Sua construção depende de um iniciador e um gerador, e esse algoritmo para gerar fractais foi proposto por Helge Von Koch, matemático sueco, em seu trabalho Une Méthode Géométrique Élémentaire pour l'Étude de Certaines Questions de la Théorie des Courbes Plane, publicado em 1906.

A ideia dessa recursão é transformar, em cada estágio, todas os segmentos de reta do iniciador em uma cópia do gerador, reduzida e deslocada, de forma a iniciar e terminar nos mesmos pontos do segmento antes da transformação.

Imagem 1: Construção de Ilhas de Koch
A imagem será apresentada aqui.
Extraída do livro "The Algorithmic Beauty of Plants", de Prusinkiewicz e Lindenmayer

L-Systems

É possível gerar "Ilhas de Koch" através de Sistemas de Lindenmayer, ou L-Systems. Esse sistema é uma Gramática Formal capaz de gerar fractais auto-similares.

Sua estrutura é definida por uma Tupla:
G = ⟨V,ω,P⟩

Onde:
V = alfabeto do sistema. É um conjunto de símbolos contendo elementos constantes (ou terminais) e variáveis (que serão substituídos).
ω = axioma. É a string inicial, não vazia, cujos símbolos pertecem ao alfabeto V.
P = conjunto de regras de produção. É o conjunto de regras que determina como os elementos variáveis do axioma serão substituídos por outros elementos do alfabeto V, constantes ou variáveis.

Gerando "Ilhas de Koch" em Python através de L-Systems

O módulo que será utilizado para gerar a figura é o Turtle. Apenas dois métodos serão necessários, e serão associados aos símbolos do alfabeto.

Abaixo apresentamos os códigos utilizados para importar o módulo e os métodos utilizados:

import turtle as tp
tp.forward(distance)
tp.right(angle)

O alfabeto do sistema consiste dos seguintes símbolos: F, - e +.

"F" representa o método turtle.forward(d), onde d é o parâmetro do tamanho do segmento de reta.
"-" representa o método turtle.left(-δ), onde δ é o parâmetro do ângulo formado com o próximo segmento (no sentido horário).
"+" representa o método turtle.left(δ), onde δ é o parâmetro do ângulo formado com o próximo segmento (no sentido anti-horário).

O código usado para traduzir do L-System para Turtle, em Python, foi:

#L-System -> Turtle    
for element in axiom:
    if element == "F":
        tp.forward(10)
    elif element == "-":
        tp.left(-angle)
    elif element == "+":
        tp.left(angle)

Para a recursão, necessitamos um iniciador (ou axioma), um gerador (ou conjunto de regras de produção), e um parâmetro n, finito, de recursões. Dados tais parâmetros, a recursão é escrita em Python pelo seguinte código:

#recursão L-System
def koch(axiom, generator, n):    
    while(n>0):
        new_string = ""    
        for element in axiom:
            if element == "F":
                new_string = new_string + generator
            else:
                new_string = new_string + element
        axiom = new_string
        koch(axiom,generator,n-1)

Como exemplo, geraremos a figura 1.9(f) do livro "The Algorithmic Beauty of Plants", de Prusinkiewicz e Lindenmayer.

O axioma será uma string em Python, contendo apenas os símbolos do alfabeto. Nesse exemplo utilizaremos a figura de um quadrado, ou seja, a string "F-F-F-F".

Como gerador, usaremos F --> F-F+F-F-F.

Por fim, o ângulo será de 90° e realizaremos n = 4 recursões.

[Obs: o tamanho d do segmento foi definido como constante por comodidade, mas é possível defini-lo como uma variável dependente de n para que o tamanho da figura não cresça exponencialmente]

O resultado obtido é mostrado a seguir:

Figura 1.9(f)

A imagem será apresentada aqui.

Código Completo

import turtle as tp
tp.speed(0)
tp.hideturtle()

axiom = "F-F-F-F"
generator = "F-F-F+F-F"
angle = 90
n = 4

#recursão L-System    
def koch(axiom, generator, n):    
        while(n>0):
            new_string = ""    
            for element in axiom:
                if element == "F":
                    new_string = new_string + generator
                else:
                    new_string = new_string + element
            axiom = new_string
            koch(axiom,generator,n-1)
    #L-System -> Turtle
        for element in axiom:
            if element == "F":
                tp.forward(10)
            elif element == "-":
                tp.left(-angle)
            elif element == "+":
                tp.left(angle)
        tp.done()

#Gerando a figura
koch(axiom,generator,n)

Colaborações

Essa seção foi incluída após discutir o código acima com meu amigo Ricardo Viana, que sugeriu brilhantes simplificações e melhorias:

Em primeiro lugar, separando as funções para que tenham propósitos específicos, como deve ser. Em seguida, substituindo dois condicionais (for e if) pelo elegante .replace(). E, por fim, deixando que a função faça todo o trabalho da recursão. O código completo é transcrito a seguir:

import turtle as tp
### Globals ###
#inicializa a tartagura
tp.speed(0)
tp.hideturtle()

### Functions ###
#movimentos da tartaruga
def turtle_moves(element,angle):
    if(element == "F"):
        tp.forward(d)
    elif(element == "-"):
        tp.left(-angle)
    elif(element == "+"):
        tp.left(angle)

#recursão L-System    
def koch(axiom, generator, n):
    if(n==0):
        return axiom
    else:
        return koch(axiom,generator,n-1).replace("F", generator)

### Code ### 
#instruções para a tartaruga
d = 10    
axiom = "F-F-F-F"
generator = "F-F-F+F-F"
angle = 90
n = 4

#L-System -> Turtle
for element in koch(axiom,generator,n):
    turtle_moves(element,angle)
tp.done()
comentou Abr 30, 2017 por Alexandre Costa (6 pontos)  

Variando o parâmetro n de recursões

A imagem será apresentada aqui.
(n=1,2,3 e 4)

comentou Abr 30, 2017 por Alexandre Costa (6 pontos)  
editado Mai 4, 2017 por Alexandre Costa

n=6

A imagem será apresentada aqui.

comentou Jun 19, 2017 por Peng Yaohao (101 pontos)  
Muito boa a solução: bem estruturada, com várias referências externas que permitem um aprofundamento sobre os temas e conceitos discutidos a quem interessar. As imagens também ajudam a entender melhor o que está acontecendo.

Só para complementar, dois adendos rápidos:

- As ilhas de Koch, da maneira como apresentada nessa questão, são particularmente elegantes pelo fato de a figura "oca" que se forma no centro do fractal possuir a mesma estrutura de autossimilaridade das figuras "periféricas" que o rodeiam - por exemplo, no caso em que \(n=2\), é possível enxergar a figura como quatro cruzes que se rodeiam em torno de uma quinta "cruz" ao centro, definida pelo contorno das quatro que estão por fora; o mesmo se repete para qualquer \(n\);

 - É importante frisar que o Python é *case-sensitive* - ou seja, diferencia maiúsculas de minúsculas. Então na hora de definir o axioma e o gerador, o usuário teria que digitar com "F" maiúsculo.
...