View
103
Download
0
Category
Preview:
Citation preview
Componentes:Alessandro OliveiraGiovanni ComarelaLeonel FonsecaTatiana PontesYuri 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:
• Ângulo: 90°• “F”, “+” e “-” representam ações de desenho• X e Y são usados apenas para controlar a evolução da curva.
)( YFXX
)( YFXY
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: R2nd iteration: R R L3rd iteration: R R L R R L L4th
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• Para tal, primeiro expressa-se n sob a forma 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 + 3so 9547 mod 4 = 3so turn 76376 is L
mk2
Curva do dragão:• Dimensões
Curva do dragão:• Dimensões• Seu perímetro é infinito, uma vez que é incrementado
por um fator de 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:
2
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):
AA → I[IF0]AFi → Fi+1
Onde I representa ramos e Fi o crescimento de uma flor
Aplicando as regras da gramática:
AI[IF0]AI[IF1]I[IF0]AI[IF2]I[IF1]I[IF0]AI[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 interactionin development I. Filaments with one-sided inputs. Journal of Theoretical Biology 18:280-289
Prusinkiewicz P, Lindenmayer A (1990). The Algorithmic Beauty ofPlants. Springer-Verlag:New York
Recommended