MAC0122 - Princípios de Desenvolvimento de Algoritmos
Departamento de Ciência da Computação do IME-USP
Turma da Engenharia da Computação - POLI
Segundo semestre de 2024
Começaremos apresentando um dos mais simples fractais: as curvas de Koch. Você pode ler mais sobre elas na wikipedia:
As curvas de Koch são definidas da seguinte maneira. A curva de Koch de ordem 0 consiste em um segmento de reta. A curva de Koch de ordem 1 é obtida a partir da curva de Koch de ordem 0 subdividindo o segmento em três segmentos de mesmo comprimento, e substituindo a parte do meio por dois outros segmentos do comprimento da parte do meio, formando um bico (como dois lados de um triângulo equilátero), conforme a figura abaixo. Esse processo se repete para cada segmento da curva de Koch de ordem 1, para obtermos a curva de Koch de ordem 2, etc.
![]() |
Uma variante da curva de Koch é o chamado floco de neve de Koch, que é obtido de três curvas de Koch, cada uma obtida a partir de um dos lados de um triângulo equilátero, e desenhadas para fora do triângulo.
![]() |
Uma outra variante da curva de Koch é o chamado anti-floco de neve de Koch, que também é obtido de três curvas de Koch, cada uma obtida a partir de um dos lados de um triângulo equilátero, mas desenhando-se as curvas para dentro do triângulo, ou seja, no outro sentido.
|
Você pode ler mais sobre os flocos de neve de Koch e suas variantes na wikipedia:
Dois outros conhecidos fractais são o fractal canopy, que se assemelha a uma árvore, e as curvas do dragão:
O fractal canopy é definido da seguinte maneira. O fractal canopy de ordem 0 é um traço vertical. O fractal canopy de ordem 1 é obtido desenhando-se um traço vertical, e adicionando-se dois fractais canopy de ordem 0 com 3/4 do tamanho, cada um desenhado a partir do final do traço inicial, um inclinado de 20 graus para um lado e o outro de 20 graus para o outro lado. Similarmente, um fractal canopy de ordem 2 é obtido desenhando-se um traço vertical, e adicionando-se dois fractais canopy de ordem 1, com 3/4 do tamanho, cada um desenhado a partir do final do traço inicial, um inclinado de 20 graus para um lado e o outro de 20 graus para o outro lado.Abaixo os fractais canopy de ordem 0 até 7.
![]() |
Finalmente, a curva do dragão... A curva do dragão de ordem 0 consiste de um traço horizontal. A curva do dragão de ordem 1 substitui o traço da curva do dragão de ordem 0 por dois traços a um ângulo de 45 graus do o traço original, formando um ângulo reto entre si, que nos referiremos como um bico. Veja o primeiro desenho na figura abaixo. A curva do dragão de ordem 2 substitui cada traço da curva do dragão de ordem 1 por um bico, ou seja, dois traços a um ângulo de 45 graus com o traço original, formando um ângulo reto entre si. Traços consecutivos são substituídos por bicos na direção oposta da curva. Veja abaixo as curvas do dragão de ordem 1 até 6.
|
Estes são alguns exemplos de construções recursivas. Você está convidado a pensar em uma construção sua, que dê origem a um fractal bonito como estes.
Nesta seção, descreveremos apenas o necessário desta linguagem para que você possa implementar esse EP. Esta descrição baseia-se numa parte da seção 4.3 do livro do Sedgewick, Algorithms in C.
Os operadores aritméticos básicos em postscript são add, sub, mul, div (divisão em float) e idiv (divisão inteira). Um exemplo de programa em postscript mostra como se pode utilizar estes operadores:
Além destes operadores aritméticos, você pode achar útil o operador neg, que reverte o sinal do número no topo da pilha.
A linguagem postscritp (ps) tem um número de funções primitivas que servem de instrução para um dispositivo abstrato para desenhar. A ação de cada função é em geral clara do seu nome. Estas funções são acionadas com argumentos que estejam na pilha. Por exemplo,
A seguir, descrevemos com precisão a ação das funções mais básicas, que devem ser suficientes para você gerar as figuras pedidas neste EP. Antes disso, vamos descrever o dispositivo abstrato para desenhar. O dispositivo consiste de uma página virtual, inicialmente em branco, com um sistema de coordenadas. A origem deste sistema fica no canto inferior esquerdo da página, o eixo x é o horizontal e o eixo y, o vertical. Além da página, temos uma caneta virtual.
A operação moveto remove dois números da pilha e trata-os como as coordenadas x e y para onde move a caneta. A operação rmoveto é como o moveto, porém o movimento é relativo à posição corrente da caneta. Por exemplo,
Até agora, não desenhamos nada. Apenas movemos a caneta.
O operador lineto remove dois números da pilha, tratando-os como as coordenadas x e y de um ponto,
e registra um segmento de reta do ponto onde está a caneta para o ponto (x,y).
A caneta termina no ponto (x,y).
O operador rlineto é semelhante, mas interpreta os dois números desempilhados como a posição relativa à posição corrente.
Vejamos um exemplo para entender melhor. Neste ponto, eu sugiro que você copie o programa ps abaixo
em um arquivo texto de nome
Para mais informações sobre a linguagem postscript, consulte o seu manual completo. No entanto, antes de usar no seu EP qualquer recurso da linguagem que não esteja entre os apresentados acima, por favor, me consulte.
Comece brincando um pouco com postscript. Escreva um programa ps que desenhe a curva de Koch de ordem 1. Uma vez que você tenha feito isso, tente escrever uma função recursiva em C que receba como parâmetro um inteiro n ≥ 0 e imprima um arquivo ps que desenhe a curva de Koch de ordem n. Depois disso, será fácil obter a estrela de Koch.
Passe para a árvore H apenas depois de ter conseguido gerar o arquivo da estrela de Koch. A árvore H dá um pouco mais de trabalho.
Para o seu fractal, você está liberado para usar outras funções da linguagem postscript, como por exemplo funções que desenham arcos, ou círculos, etc. Divirta-se xeretando o manual.
Há recursão na linguagem postscript, mas não a use para desenhar a estrela de Koch ou a árvore H. Se quiser, experimente no seu fractal.
Divirta-se com o EP!
programa
deve ser entregue até dia 25 de agosto, inclusive.