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

Primeiro Exercício-Programa

Fractais

Entrega: 25 de agosto

O objetivo deste exercício-programa é utilizar recursão para gerar alguns fractais simples. Fractais são figuras geométricas que podem ser divididas em partes semelhantes à figura original. Por isso, a recursão é um recurso muito apropriado para gerar tais figuras.

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.

Entrada e saída do seu programa

Você deverá escrever um programa que:
  1. Leia do teclado um número inteiro, onde 0 indica anti-floco de neve de Koch, 1 indica o fractal canopy, 2 indica a curva do dragão, e 3 indica o seu fractal.
  2. Leia do teclado um segundo inteiro que representa a ordem da figura a ser gerada.
  3. Leia do teclado o nome de um arquivo de saída que conterá a imagem gerada.
  4. Gere um arquivo postscript com o anti-floco de neve de Koch, o fractal de canopy, a curva do dragão ou o seu fractal, de acordo com os dois inteiros dados. A imagem deve ter um tamanho semelhante às disponibilizadas abaixo.
Não modifique a ordem dos dados na entrada e nem faça seu programa ler algo além dos dados acima, pois o seu programa será submetido a um corretor automático. Haverá um desconto na nota do seu EP se for feita alguma modificação no formato de leitura.

Exemplos de saída

Aqui você encontra alguns arquivos pdf que foram obtidos dos arquivos ps gerados pelo meu programa.

Linguagem postscript

Postscript é uma linguagem completa cujos programas estão escritos em notação posfixa e são interpretados com a ajuda de uma pilha interna, exatamente como no cálculo de expressões aritméticas em notação posfixa. Cada operação obtém seus argumentos da pilha interna e deposita de volta nesta pilha seu valor de retorno.

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:

5 9 8 add 4 6 mul mul 7 add mul
Sim, esta linha é um programa em postscript! Interprete a linha acima como uma expressão em notação posfixa e pense em qual é o valor desta expressão. Você deve obter o valor 2075. Confira! Assim, ao final desse programa em postscript, este valor é o que fica na pilha interna.

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,

0 0 moveto 144 0 rlineto 60 rotate 144 0 rlineto stroke
corresponde à seguinte sequência de ações: chame moveto com argumentos 0 e 0, então chame rlineto com argumentos 144 e 0, depois rotate com argumento 60, etc. Algumas funções se referem diretamente à própria pilha. Por exemplo, o operador dup duplica a entrada do topo da pilha. Assim, por exemplo, o código
144 dup 0 rlineto 60 rotate dup 0 rlineto
corresponde a: chame rlineto com argumentos 144 e 0, depois rotate com argumento 60, então rlineto com argumentos 144 e 0. Um outro operador que atua na pilha diretamente é o pop, que remove o elemento do topo da pilha (desempilha).

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,

100 50 moveto 10 20 rmoveto
faz com que a caneta primeiro mova para a posição (100,50), e depois para a posição (110,70). A operação rotate remove um número da pilha e executa uma rotação do sistema de coordenadas deste número de graus no sentido anti-horário. Assim, após
100 50 moveto 90 rotate 10 20 rmoveto
a caneta estará na posição (80,60).

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 desenho.ps e visualize o resultado abrindo este arquivo, por exemplo, com o programa ghostview (gv) ou um equivalente.

150 250 moveto 200 400 lineto stroke
O operador stroke conclui e imprime o desenho. Experimente alternativamente
150 250 moveto 200 400 rlineto stroke
e perceba a diferença. No primeiro, o segmento desenhado e a caneta terminam na posição (200,400), enquanto que no segundo, terminam na posição (350,650).

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.

Recomendações

Utilize recursão no seu programa para gerar o arquivo ps dos desenhos. Se você não utilizar recursão, o seu EP receberá nota zero.

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!

Entrega, prazos e observações