Componentes:
Alessandro Oliveira
Giovanni Comarela
Leonel Fonseca
Tatiana Pontes
Yuri Tavares
Fractais
• Introdução
• Motivação
• Dimensão fractal
L-systems
• Definição
• Histórico
• Estrutura
• Exemplos
• Aplicações
Surgimento dos fractais:
• Do latim fractus: quebrado, fraturado
• O termo “fractal” surgiu em 1975 (Benoît Mandelbrot)
• Inspirado no paradoxo da costa
Características dos fractais:
• Autossimilaridade e/ou autossimilaridade estatística
• Maneira bem definida de criação do fractal
• Pertencem a uma “dimensão fractal”
• Modelagem de estruturas naturais (árvores, flocos de neve,
etc)
• Modelagem de objetos que possuem uma natureza caótica
• Maneira relativamente simples de se representar estruturas
complexas
• Natureza aleatória de eventos naturais (crescimento de galhos
numa árvore)
• Problema da costa da Grã-Bretanha
• Quanto menor o instrumento de métrica, maior o
comprimento da costa
Contando ε-bolas (modelo simplificado):
• Cada ε-bola consiste em uma esfera de raio ε
• Considere que para cobrir os segmentos do objeto em
questão sejam necessárias N ε-bolas
• A análise da influência da diminuição do raio ε sobre o
número N necessário para cobrir o objeto estima a dimensão
do objeto
• L-System é uma variação de uma gramática formal, que
permite reescrita paralela;
• Sua aplicação mais famosa é a modelagem do crescimento de
plantas;
• Permite modelar crescimento morfológico de uma variedade
de organismos;
• Utilizada para gerar fractais auto-similares;
•
A principal diferença em relação em relação as gramáticas
de Chomsky está em como aplicar regras de produção:
sequencial x paralela;
•
Esta diferença reflete a motivação biológica. Produções
capturam divição das células de organismos multicelulares
(Várias divisões ocorrem simultaneamente);
• L-Systems = Lindenmayer Systems
Aristid Lindenmayer 1925–1989
Como biólogo, Lindenmayer trabalhou com leveduras e fungos
filamentosos e estudou os padrões de crescimento de vários
tipos de algas. Originalmente, L-Systems foram concebidas para
fornecer uma descrição formal do desenvolvimento de tais
simples organismos multicelulares. Posteriormente, esse
sistema foi estendido para descrever as plantas e estruturas
complexas de ramificação.
Existem vários tipos de L-Systems:
• Context-Free L-Systems;
• Stochastic L-Sytems;
• Branching Structures;
• 3D;
• Context-Sensitive L-Systems;
• ...
• Gramáticas geram strings. O que fazer com estas strings para
que elas tenham uma interpretação gráfica?
• A cada símbolo do alfabeto é dada uma semântica para que
cada string gerada possa ser mapeada em um “desenho”;
• Turtle Interpretation: Considere uma tartaruga andando no
espaço bidimensional. O estado da tartaruga é dado pela tripla
(x, y, a), onde (x,y) é uma coordenada no plano e a um ângulo
(direção do próximo passo da tartaruga);
• Turtle Interpretation: Considere o estado da tartaruga como a
tripla (x, y, a), onde (x,y) é uma coordenada no plano e a um
ângulo (direção do próximo passo da tartaruga).
Curva de Koch:
• Variável: F
• Constantes: + e –
• Axioma: F
• Produção: F -> F + F - F - F + F
• Ângulo delta: 90 graus
Fractal Planta:
• Variáveis: F e X
• Constantes: +, -, [ e ]
• Axioma: X
• Produções: X -> F−[[X]+X]+F[+FX]−X e F -> FF
• Ângulo delta: 25 graus
Fractal Planta (Estágio n = 6)
6 imagens produzidas pela mesma gramáticas. Todas
representam o 5 estágio.
Exemplo mais complexo (Flower Field)
Curva do dragão:
• Applet
Curva do dragão:
• O Heighway Dragon (também conhecido como Jurassic Park
Dragon) foi inicialmente estudado por físicos da NASA
• Apareceu na novela Jurassic Park, de Michael Crichton, a
qual deu origem ao filme
• Na história, o conhecido matemático e teórico do caos Ian
Malcon criou curvas do dragão para simular as ações que
seriam tomadas no parque
Curva do dragão:
• Descrição
• Começando por um segmento base, substitua cada
segmento por dois segmentos com um ângulo de 90°
entre eles e com uma rotação de 45° alternadamente
para a esquerda e para a direita.
Curva do dragão:
• Variáveis: X Y
• Constantes: F + • Axioma: FX
• Regras:
( X  X  YF )
(Y   FX  Y )
• Ângulo: 90°
• “F”, “+” e “-” representam ações de desenho
• X e Y são usados apenas para controlar a evolução da curva.
Curva do dragão:
• Também pode ser gerado pelo conjunto limite da seguinte
IFS (iterated function system), no plano Real
• Essa representação é mais usada em softwares como o
Aphophysis, da Microsoft
Curva do dragão:
• Dobrando o Dragão
• Para as primeiras iterações, a sequência de viradas é a
seguinte:
1st iteration: R
2nd iteration: R R L
3rd iteration: R R L R R L L
4th iteration: R R L R R L L R R R L L R L L
• Padrão: Pegue a iteração anterior e adicione um R ao fim
dela. Pegue a iteração original de trás para frente, mude
cada letra e adicione o resultado após o R
Curva do dragão:
• Dobrando o Dragão
• Esse padrão origina o método de dobramento conhecido
como “dobrando uma tira de papel”
Curva do dragão:
• Dobrando o Dragão
• Esse padrão também possibilita calcular a direção do nésimo giro da sequência
m
• Para tal, primeiro expressa-se n sob a forma k2 em
que k é um número ímpar. Depois, divide-se k por 4. Se o
resto da divisão for 1, então o giro é para a direita. Se for
3, o giro é para a esquerda.
• Exemplo: 76376º giro
76376 = 9547 x 8.
9547 = 2386x4 + 3
so 9547 mod 4 = 3
so turn 76376 is L
Curva do dragão:
• Dimensões
Curva do dragão:
• Dimensões
• Seu perímetro é infinito, uma vez que é incrementado
por um fator de 2 a cada iteração
• A curva nunca cruza ela mesma
• Sua dimensão fractal pode ser calculada:
• A dimensão fractal de sua fronteira foi aproximada
numericamente por Chang & Zhang:
Curva do dragão:
• Dimensões
• Possui muitas auto-similaridades, sendo a mais óbvia a
repetição do mesmo padrão rotacionado de 45° e com o
tamanho modificado por uma taxa de 2
Lírio-do-brejo (Convallaria majalis):
A
A → I[IF0]A
Fi → Fi+1
Onde I representa ramos e Fi o crescimento de uma flor
Aplicando as regras da gramática:
A
I[IF0]A
I[IF1]I[IF0]A
I[IF2]I[IF1]I[IF0]A
I[IF3]I[IF2]I[IF1]I[IF0]A
Lírio-do-brejo (Convallaria majalis)
Floco de neve de von Koch
1. Divide segmento de reta em 3 segmentos iguais.
2. Desenha triângulo equilátero com segmento central como base.
3. Apaga o segmento que serviu de base ao triângulo do passo 2.
Floco de neve de von Koch
1. Divide segmento de reta em 3 segmentos iguais.
2. Desenha triângulo equilátero com segmento central como base.
3. Apaga o segmento que serviu de base ao triângulo do passo 2.
Montanhas fractais
• Modelagem de relevo.
• Cada iteração estabelece uma altura para as medianas dos segmentos.
L-systems e Algoritmos Genéticos
• GA com genótipos inspirados em L-systems.
• Função de fitness baseada em hipóteses evolucionistas sobre fatores que
tiveram maior efeito sobre a evolução das plantas.
L-systems e Algoritmos Genéticos
• GA para construção de figuras simétricas.
• Função de fitness favorece estruturas com simetria bilateral.
Mitose Celular
• Processo de divisão celular conservativa.
• Célula inicial origina duas novas células com a mesma composição genética.
Iris do Olho Humano
• Iris do olho humano formada por interpolação de padrões.
Arquitetura de Plantas
• Crescimento de plantas representado por um l-systems.
Arte em L-systems
L-systems são úteis e importantes por vários motivos:
• Permitem modelagem da natureza com estruturas complexas de essência
caótica e aleatória.
• Possuem diversas aplicações práticas, uma vez que auxiliam na obtenção de
formatos mais próximos da realidade.
• Devido à sua utilidade, há vários códigos disponíveis na web (de fácil uso)
para a criação de novos L-systems.
http://jsxgraph.uni-bayreuth.de/wiki/index.php/Plant_generation_I
http://www.biologie.uni-hamburg.de/b-online/e28_3/lsys.html
http://www.generation5.org/content/2002/lse.asp
http://algorithmicbotany.org/papers/WebApps/LSystems/LSys.html
http://en.wikipedia.org/wiki/L-system
Lindenmayer A (1968). Mathematical models for cellular interaction
in development I. Filaments with one-sided inputs. Journal of
Theoretical Biology 18:280-289
Prusinkiewicz P, Lindenmayer A (1990). The Algorithmic Beauty of
Plants. Springer-Verlag:New York