Lodes Computer Graphics Tutorial Sierpinski Fractals Índice Introdução Existem muitos fractores com o nome de Waclaw Sierpinski, um matemático polonês que morava de 1882 a 1969. Estes incluem o Triângulo Sierpinski, o Tapete Sierpinski, a Pirâmide Sierpinski (a versão 3D de O Triângulo Sierpinski) e o Cubo Sierpinski (a versão 3D do Tapete Sierpinski). As figuras 2D serão descritas aqui. Triângulo Sierpinski O Triângulo Sierpinski, também chamado de Sierpinski Gasket e Sierpinski Sieve, pode ser desenhado manualmente da seguinte forma: Comece com um único triângulo. Este é o único triângulo nessa direção, todos os outros estarão de cabeça para baixo: dentro deste triângulo, desenhe um triângulo de baixo para baixo. Seus cantos devem estar exatamente nos centros dos lados do grande triângulo: agora, desenhe 3 triângulos menores em cada um dos 3 triângulos que estão apontando para cima, novamente com os cantos nos centros dos lados dos triângulos que apontam para cima: Agora, existem 9 triângulos apontando para cima. Em cada um desses 9, desenhe novamente triângulos mais baixos: os 27 triângulos apontando para cima, desenham novamente 27 triângulos apontando para baixo: depois de passos infinitos e se todos os triângulos apontando para cima forem preenchidos, você terá o peneiro Sierpinski. Cada passo, mais triângulos devem ser desenhados. Este é um processo recursivo, e pode ser desenhado da mesma maneira com um computador. Com Recursão Bem, agora, programa que o que foi desenhado manualmente no computador, ao fazer uma função de desenho de triângulo, ela se recomeça novamente 3 vezes, até que n etapas de recursões sejam alcançadas. Este programa é feito para que ele funcione para qualquer triângulo inicial, ele não precisa ser simétrico, a única condição é que os cantos estejam dentro da tela. A função principal configura a tela e chama a função drawSierpinski. A função drawSierpinski em si desenha apenas um triângulo: o inicial que aponta para cima. Então, ele chamará a função subTriangle, e essa é a função recursiva real, que irá desenhar todos os triângulos invertidos. A função subTriangle desenha um único triângulo de cabeça para baixo, com os 3 cantos que você dá com seus parâmetros. Então, ele se chama 3 vezes novamente, para desenhar 3 triângulos menores. Para estes 3 triângulos, são usados novos cantos, é claro, e estes devem ser calculados. Na seguinte imagem, se o triângulo preto é o grande triângulo, a função subTriângulo desenhou, então os três triângulos vermelhos são os novos que precisam ser calculados: os cantos do grande triângulo são a1, a2 e a3. Os cantos de um dos triângulos mais pequenos são b1, b2 e b3 como você pode ver na imagem. Se vemos todos esses pontos como vetores, as fórmulas para os pontos b (com os pontos a sendo conhecidos) são: b3 (a1 a2) 2, porque b3 está no centro entre a1 e a2, esse ponto é a média de A1 e a2 b1 b3 (a1 - a3) 2: se você examinar bem, você verá que o ponto b1 é a soma do ponto b3 e do vetor (a1 - a3) 2, dividido em 2 porque o lado correspondente do O triângulo menor é metade tão grande. B2 b3 (a2 - a3) 2: isso é muito semelhante à outra fórmula, mas com o outro lado. Para os outros 2 pequenos triângulos, algo parecido é feito. No código, não usamos uma classe de vetores, então x e y são variáveis separadas e, por causa da adição de vetores funcionam, simplesmente temos que fazer o mesmo duas vezes, uma vez para x e uma vez para y, com o mesmo Fórmulas. Para as coordenadas dos cantos triangulares, os números de ponto flutuante são usados para mais precisão. Com esse conhecimento, o programa pode ser feito, os comentários no código abaixo explicam como isso funciona: Heres o que você vê depois de executar o programa: Com AND O método dado acima é apenas uma das muitas maneiras de desenhar os Triângulos Sierpinski. Uma dessas maneiras é com o operador AND. Se você tomar um pixel a coordenada x como um número inteiro, e a coordenada y como um número inteiro, e use o operador AND neles, se o resultado for 0, desenhe um pixel de uma cor, caso contrário, outro. Você verá então um Triângulo Sierpinski exibir o operador AND em dois inteiros, leva ambos os números inteiros como um número binário e usa AND em cada um dos bits correspondentes. O operador AND em bits funciona da seguinte forma: Isto é feito para cada bit do inteiro, e somente se o número inteiro resultante for no 0000000000000000 binário, o pixel recebe outra cor. O código é um loop duplo muito simples que passa por cada pixel e verifica se o amplificador x é 0 ou não, onde o amplificador é o operador AND binário em C. Ao usar o amplificador x dentro de uma condição if, ele só será falso no Case x amp y é 0, e em todos os outros casos, um pixel branco é desenhado, então o resultado será um triângulo sierpinski preto sobre um fundo branco. O resultado parece melhor se os tamanhos de tela forem de 2, caso contrário, você verá apenas uma parte do triângulo. Com uma Função Aleatória Outra maneira totalmente diferente de desenhar uma aproximação do Triângulo Sierpinski funciona da seguinte forma: 1) defina 3 pontos com coordenadas: a (ax, ay), b (bx, by) e c (cx, cy). Estes se tornarão os cantos do grande triângulo exterior. 2) definir outro ponto, p (px, py) e colocá-lo em um canto do triângulo (por exemplo px ax e py ay). 3) desenhe um ponto no local (px, py) com um lápis 4) roote uma matriz teórica com 3 lados (lado 0, lado 1 e lado 2), ou apenas faça uma escolha aleatória entre 0, 1 e 2. 5) Agora altere as coordenadas do ponto p, dependendo do número de roteamento: se você rolar 0, p (pa) 2, se você rolou 1, p (pb) 2 se você rolar 2, p (pc) 2 6) volte para Passo 2, coloque o ponto na nova posição de p e continue fazendo isso até ficar cansado. No entanto, todo o processo é randomizado, depois de passos suficientes, o resultado ficará cada vez mais parecido com um Triângulo Sierpinski. Isso não é muito difícil Código, os comentários explicam como tudo funciona: quanto maior for o valor numSteps, mais pixels serão desenhados. Essas imagens mostram o resultado para 1000, 10000 e 100000 etapas: Ao jogar um pouco com as fórmulas, você pode obter outras formas, como por exemplo esta: conseguiu mudar algumas das divisões através de 2.0 em divisões até 3.0. Com Recorrência Retangular Mais uma maneira de desenhar um Triângulo Sierpinski é com uma função recursiva que usa retângulos. O processo de recursão funciona da seguinte maneira: Mude cada retângulo em uma forma de L: A própria forma de L consiste em 3 retângulos, que são novamente convertidos em forma de L, etc. Se você continuar fazendo isso o tempo suficiente, parece mais E mais como um Triângulo Sierpinski. Isso é novamente algo que pode ser programado com uma função recursiva, bastante semelhante ao código recursivo dado maior, mas esses retângulos de tempos são desenhados e novas coordenadas para 3 novos retângulos devem ser calculadas de cada vez. Heres o resultado para 3, 5 e 8 recursões: Para estudar o recursão um pouco melhor, tente ver o que acontece quando a função drawSierpinski se chama apenas 1 vez em vez de 3 (as outras 2 chamadas são comentadas): agora, se maxRecursões É 8, apenas 8 retângulos são desenhados, cada um menor do que o anterior: agora, habilitamos duas chamadas para si mesmas, e já estão sendo desenhados mais quadrados, mas a forma ainda não é complexa. Agora à direita está 1 quadrado grande, à esquerda disto 2 meias praças, à esquerda desses 4 quadrados 14, à esquerda daqueles 8 18 quadrados, e assim por diante, com a linha mais à esquerda 128 quadrados que são 128 vezes menores do que o grande quadrado a direita. E, finalmente, se ativarmos todas as 3 chamadas para si, obtemos o Triângulo Sierpinski, e tantos quadrados são desenhados que quase tudo é branco: há ainda outra maneira de obter um Triângulo Sierpinski: com um autômato celular, mas isso pode ser coberto Em um artigo posterior. Sierpinski Carpet With Rectangle Recursion Um fractal diferente é o Sierpinski Carpet. Para desenhar um à mão, comece com um quadrado branco e, em seguida, desenhe um quadrado preto no centro com cada lado 13 do tamanho do quadrado original: agora, ao redor do quadrado preto, são 8 quadrados brancos. Em cada um destes 8, desenhe novamente um quadrado preto que é o 18 mais pequeno e, nos 8864 novos quadrados brancos, faça-o novamente: continue fazendo isso até o infinito, e você obtém um tapete sierpinski. Para desenhá-lo, podemos usar um recursivo Função que é muito semelhante à usada para o triângulo sierpinski com retângulos, mas agora a função precisa se chamar 8 vezes em vez de apenas 3 e usar coordenadas diferentes. As coordenadas x1, y1-x2, y2 são divididas em 9 seções, no centro, o retângulo é desenhado com rect e os outros 8 são usados como parâmetros para as chamadas DrawCarpet do próximo passo de recursão. E heres o resultado para 6 passos de recursão: se você quiser um maior, use uma resolução de 729729 pixels e 7 recursões. Com Ternary Numbers Theres também um método para desenhar o Sierpinski Carpet que é semelhante ao método AND para desenhar o triângulo sierpinski. Ou seja, você faz um cálculo para cada pixel para verificar se ele deve ou não ser colorido. Este método é um pouco mais complexo, porém, porque você precisa trabalhar na base 3, ou seja, com números ternários. Os números Ternários têm dígitos que podem ser 0, 1 ou 2. O método funciona da seguinte maneira: Pegue as coordenadas do pixel como números inteiros escritos na notação ternária. Para cada dígito, verifique se NÃO, ambos os dígitos correspondentes são 1. Se isso nunca acontecer, o ponto pertence ao tapete. Para encontrar o primeiro dígito ternário (mais à direita) de um número, o módulo dividi-lo por 3 (a divisão de módulo a 3 funciona da seguinte forma: 030, 131, 232, 330, 431, 532, 630, 731, etc.). Para encontrar o segundo dígito ternário, primeiro divida o número através de 3 (divisão inteira, ou seja, retire os números por trás do ponto) e, em seguida, modulo dividi-lo até 3. Para encontrar o terceiro dígito ternário, divida-o através de 9, então o módulo divide através 3. Para encontrar o quarto, divida-se até 27, então o módulo divide através de 3, etc. O exemplo abaixo usa uma resolução de 243 por 243 pixels, portanto, temos que verificar apenas os primeiros 5 dígitos ternários das coordenadas de pixels, pois com 5 Dígitos ternais, você pode representar todos os números de 0 a 242. A condição no if, é escrita em muitas linhas, ea condição verifica para cada um dos 5 dígitos, se NÃO, tanto a partir da coordenada x quanto a da y As coordenadas estão juntas 1. Se a condição for verdadeira, um pixel branco é desenhado em x, y. O resultado é exatamente o mesmo do programa anterior, mesmo que este use um método totalmente diferente: se você quiser aumentar a resolução, você deve adicionar uma condição extra para o 6º dígito (onde você divide 243), etc. . Para cada vez que você triplica a resolução. A condição que verifica o 5º dígito (o 5º dígito ternário da direita) é aquele que é responsável pelo grande quadrado preto no centro. A condição que verifica o 4º dígito é a responsável pelos 8 quadrados menores ao redor do quadrado central, etc. Se você remover a condição para o 5º dígito, o quadrado preto do centro desapareceu e, em vez disso, você obtém isso: se você Remova, em vez disso, por exemplo, a condição que verifica o 3º dígito, todos os quadrados pretos da terceira ordem desapareceram enquanto todos os outros são deixados: então, se você triplicar a resolução, o quadrado que é agora o quadrado central se tornará um quadrado no Na parte superior esquerda, e você precisa de um quadrado preto ainda maior no novo centro, e é por isso que você precisa de uma nova condição que verifique o 6º dígito então. Última edição: 2004 Copyright (c) 2004-2007 por Lode Vandevenne. Todos os direitos reservados. Benoit B. Mandelbrot Waclaw Sierpinski Mandelbrot e Sierpinski são dois matemáticos que fizeram contribuições importantes no campo dos fractals. Waclaw Sierpinski viveu de 1882 a 1969. Ele era um dos mais famosos matemáticos polacos. Vamos ver uma descoberta que recebeu o nome dele do Triângulo Sierpinski. Ele encontrou isso enquanto estava em busca de topologia. O Triângulo Sierpinski tem todas as propriedades de um fractal: habilite o script java e obtenha flash para visualizar esta animação. Um fractal é uma forma geométrica que é auto-similar e que tem uma dimensão fractal. Selfsimilar significa que quando você olha para uma parte menor do fractal, ele ainda parece o mesmo. Por exemplo, você pode ampliar o Triângulo Sierpinski tanto quanto você quiser e ainda parecerá o mesmo. Uma dimensão fractal significa que não é apenas uma, duas ou mais dimensões, mas algo intermediário. Um exemplo perfeito disso é a borda do triângulo Sierpinski. Dê uma olhada na animação que mostra como ela é criada. Para desenhar um triângulo Sierpinski, comece com um triângulo equilátero. Então, um triângulo é cortado, que tem seus cantos no ponto médio das bordas originais dos triângulos. O que você deixou são três triângulos menores. Agora faça o mesmo novamente com os triângulos menores. O corte é chamado de iteração. Uma iteração é um passo que faz uma pequena parte do trabalho e é feito repetidas vezes para obter o resultado final. A forma com a qual você termina, o triângulo Sierpinski, tem uma borda que possui um comprimento infinito: sempre que você repete o processo acima, você aumenta o comprimento da borda por metade mais do que acabou de fazer na última iteração (experimente Em papel). Agora, se você tem um triângulo regular, você pode descrever facilmente cada ponto que se encontra na borda do triângulo com um número: por exemplo, a distância que você deve percorrer ao longo da borda começando em um dos cantos vai no sentido horário. Mas como você pode fazer isso com o triângulo Sierpinski Existem algumas maneiras de seguir a borda do triângulo Sierpinski de uma só vez, que você pode ver abaixo, que é executado em um triângulo Sierpinski que foi desenhado em 5 iterações: ative o script java E obtenha flash para ver esta animação. Mas é claro, um triângulo Sierpinski desenhado para cinco iterações não é um fractal real, porque quando você começa a aumentar o zoom, você verá muito mais a si mesmo, mas apenas grandes áreas de preto e branco. Para obter um fractal real, são necessárias infinitas iterações. Então, como você pode descrever um ponto que fica à beira do triângulo Sierpinski. Você pode tentar fazê-lo como no triângulo regular: use um número que diz até onde você tem que se mover no caminho - como você vê acima - para Chegar ao ponto. Mas há um problema: a distância para um determinado ponto depende de quantas iterações foram usadas ao desenhar o triângulo. A distância pode facilmente dobrar se você fizer mais algumas iterações. E para um triângulo Sierpinski com iterações infinitas, a distância que você tem para ir será infinita para qualquer ponto. Então, você pode tentar dois números para mostrar a localização de um ponto, por exemplo, usando um sistema de coordenadas. Assim, é a borda do triângulo Sierpinski dois ou um bem dimensional, para descrever um ponto, você precisa de pelo menos dois números, de modo que, de certa forma, é de duas dimensões, mas ainda, uma borda é apenas uma linha sem espessura, então, em Essa sensação tem uma dimensão de 1. Desta forma, é claro que a borda do triângulo Sierpinski não tem uma dimensão de um ou dois, mas uma dimensão não intergerente em algum lugar entre um e dois. Você pode encontrar muitas estruturas fractal na natureza. Um bom exemplo é a couve-flor. Um pedaço de tudo parece o mesmo. Você pode notar fractals em litorais, montanhas, nuvens, árvores e até mesmo em samambaias Benoit B. Mandelbrot nasceu em 1924 na Polônia, mas se mudou para a França quando tinha doze anos. Ele pesquisou sobre estruturas fracturas e foi o único a definir suas propriedades e a introduzir o Mandelbrot Set. Também conhecido como Mandelbrot Bug, que é um dos fractals mais populares. Você pode fazer fractals de qualquer forma. Um fractal é feito copiando e alterando a imagem de entrada. Um exemplo muito simples é uma árvore pitagórica. Como a imagem de entrada, tomamos um quadrado e anexamos um triângulo direito que compartilha seu hipotênio com um lado do quadrado. Então, adicionamos um quadrado para cada um dos outros lados do triângulo. Agora, fazemos o mesmo para os quadrados menores como fizemos para o primeiro. Desta forma, podemos continuar para sempre e para sempre. Podemos repetir isso até o infinito. Como resultado, obtemos a Árvore de Pitágoras Leafed. Vamos mudar agora um pouco: em cada novo quadrado vamos virar o triângulo direito. Como resultado, obtemos a Árvore de Pitágoras Conífera. Você sabia que, para cada iteração, a soma da área dos quadrados adicionados é igual à área do quadrado original Você pode facilmente provar isso com o teorema de Pitágoras. O teorema de Pitágoras prova que o quadrado A mais o quadrado B é igual ao quadrado C. Então sabemos que os quadrados A e B têm a mesma área que o quadrado C à direita. Agora, desde asup2bsup2csup2, sabemos que, na imagem à direita, os dois quadrados verdes A e B adicionados devem ter a mesma área que o quadrado correspondente C. E como os quadrados vermelhos A e B (os quadrados C verdes) são iguais aos Grande quadrado C, podemos concluir que todos os quadrados verdes adicionados juntos têm a mesma área que o quadrado grande C. A partir disso, podemos concluir que isso é verdade para cada passo adicional que fazemos cada linha de quadrados da mesma cor somados É igual ao grande quadrado C.
No comments:
Post a Comment