Como implementar o triângulo de Sierpinski recursivamente?

Question

O enunciado desta questão segue o exercício 7.8 do livro Introduction to Recursive Programming, de Manuel Rubio-Sánchez.

Implementar um método recursivo que desenha o triângulo de Sierpinski (ver figura 1):
A partir de uma perspectiva top-down, o triângulo de Sierpinski pode ser gerado começando com um triângulo equilátero de forma △, que é dividido em quatro pequenos triângulos equiláteros, de metade do tamanho do original. Um deles terá a forma ▽, mas três serão triângulos △. O processo é repetido iterativamente para estes três triângulos (ver Figura 2). O método deve receber as coordenadas de um ponto bidimensional de referência (por exemplo, o vértice inferior esquerdo do triângulo), o comprimento da base do triângulo, e o número de iterações N para ser executado.
Utilize os pacotes numpy e matplotlib.

Figura 1:

Figura 2:

Answer 1

Para resolver este problema, utilizaremos o Jogo do Caos. Para tal, seguiremos as seguintes regras:

1) Escolha 3 pontos em um plano que representam os vértices de um triângulo;
2) Selecione aleatoriamente um ponto que esteja dentro da área do triângulo;
3) Selecione aleatoriamente dos 3 vértices;
4) Mova para o ponto que está diretamente entre os dois pontos escolhidos;
5) Desenhe o ponto;
6) Usando o ponto atual, repita os passos 3-6.

A fim de implementar o código do problema (também como sugerido pelo enunciado do exercício), utilizaremos as bibliotecas: numpy, matplotlib e randint. Esta última será necessária para que seja possível gerar números aleatórios.

Deste modo, a solução do problema inicia-se com a importação das bibliotecas necessárias e, também, com a definição do que é um ponto médio:

import numpy as np
import pylab
from random import randint

def pontoMedio(ponto1, ponto2):
    return [(ponto1[0]+ponto2[0])/2, (ponto1[1]+ponto2[1])/2]

Adiante, o ponto inicial para o Jogo do Caos é escolhido - ele pode cair em qualquer lugar dentro do triângulo. Define-se também os três vértices do triângulo:

ponto_atual = [0,0]

vertice_1 = [0,0]
vertice_2 = [1,0]
vertice_3 = [.5,np.sqrt(3)/2]

Por fim, é preciso que se escolha um vértice do triângulo aleatoriamente - a biblioteca randint é utilizada aqui. Depois basta definir o ponto atual para ser o ponto médio entre o ponto atual anterior e o vértice escolhido aleatoriamente. Concluí-se com o plot - a partir da biblioteca matplotlib - do Triângulo de Sierpinski gerado pelo processo recursivo.

for _ in range(5000):

    val = randint(0,2)
    if val == 0:
        ponto_atual = pontoMedio(ponto_atual, vertice_1)
    if val == 1:
        ponto_atual = pontoMedio(ponto_atual, vertice_2)
    if val == 2:
        ponto_atual = pontoMedio(ponto_atual, vertice_3)

    pylab.plot(ponto_atual[0], ponto_atual[1], 'm.', markersize=2)    

pylab.show()

O Triângulo de Sierpinski gerado pelo processo acima é apresentado nas seguintes imagens. Observe que se tratam de triângulos gerados a partir de 1.000, 5.000 e 10.000 repetições, respectivamente.

Desta maneira, observa-se que quanto maior o número de repetições melhor será a visualização do Triângulo de Sierpinski.