Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como construir o fractal conhecido como Sierpinski Gasket utilizando recursões?

+3 votos
916 visitas
perguntada Abr 3, 2017 em Ciência da Computação por João Gabriel Souza (81 pontos)  

Utilize a linguagem de sua escolha.

Compartilhe

1 Resposta

+1 voto
respondida Abr 3, 2017 por João Gabriel Souza (81 pontos)  
editado Jul 5, 2017 por João Gabriel Souza

Introdução

O fractal Sierpinski Gasket é uma figura geométrica obtida através de um processo recursivo. Este é uma das formas elementares da geometria fractal.

O Triângulo de Sierpinski, como é conhecido, é um conjunto auto-similar de um triângulo (na maioria das vezes equilátero). Se dividido em quatro outros triângulos congruentes entre si e entre o triângulo original, cujos vértices são os pontos médios do triângulo de origem, então os subconjuntos do fractal são três cópias escalonadas de triângulos derivados da iterada anterior. O triângulo do meio não pertence ao fractal. Esta separação do fractal em cópias escalonadas pode ser continuada recursivamente nos outros triângulos produzidos.

Uma das maneiras de se obter o o fractal de Sierpinski é através do seguinte algoritmo:

  • Comece com qualquer triângulo e um plano. O triângulo de Sierpinski canônico utiliza um triângulo equilátero \(S(0)\) com a base paralela ao eixo horizontal, mas qualquer triângulo pode ser utilizado.
  • Divida-o em 4 triângulos equiláteros utilizando os pontos médios (cada lado deve ter metade do tamanho original) do triângulo original e posicione cada triângulo de maneira que encoste nos outros dois em um canto. Remova o interior do triângulo médio, para se obter \(S(1)\).
  • Repita o passo anterior para cada figura obtida, indefinidamente.

Para realizar as resoluções dos fractais deste exercícios usaremos a biblioteca \(Turtle\) do Python. Uma boa explicação sobre a biblioteca você encontra aqui. As especificações de cada função podem ser vistas aqui.

Exemplo 1 - Triângulo de Sierpinski Construído de Forma Simples

Começamos com um exemplo simples de aplicação em Python do algoritmo de Sierpinski. Primeiramente importa-se a biblioteca \(Turtle\), que será utilizada para auxiliar na geração das figuras, bem como são definidos os parâmetros da função de criação do triângulo.

O código implementado em Python segue abaixo:

import turtle
def draw_sierpinski(length,depth):

Os parâmetros que são determinados são o \(lenght\) e o \(depht\). A função \(turtle.fd\) move a seta para uma distância específica, essa distância será um dos parâmetros do código (\(lenght\)) que realizará o algoritmo de Sierpinski. A função \(turtle.left\) direciona a seta para o ângulo estabelecido seguindo a direção esquerda. O mesmo ocorre com a função \(turtle.right\), porém esta direciona a seta para direita. Esse \(for\) fica dentro da condição de \(if\) que inicialmente reproduzirá o primeiro triângulo, caso contrário, o \(else\) determinará o processo recursivo, gerando os demais triângulos que compõem a figura.

O código implementado em Python segue abaixo:

  if depth==0:
        for i in range(0,3):
            turtle.fd(length)
            turtle.left(120)
    else:
        draw_sierpinski(length/2,depth-1)
        turtle.fd(length/2)
        draw_sierpinski(length/2,depth-1)
        turtle.bk(length/2)
        turtle.left(60)
        turtle.fd(length/2)
        turtle.right(60)
        draw_sierpinski(length/2,depth-1)
        turtle.left(60)
        turtle.bk(length/2)
        turtle.right(60)

Para finalizar, a última parte do código chama a janela de desenho do \(Turtle\) e gera a figura de Sierpinski, conforme os parâmetros selecionados gerando \(S(1)\).

O código implementado em Python segue abaixo:

window = turtle.Screen()
draw_sierpinski(200,1)
window.exitonclick()

A imagem será apresentada aqui.

Para gerar a imagem recursiva com \(depht = 4\), ou seja, com 4 triângulos, basta alterar a parte final do código.

O código implementado em Python segue abaixo:

window = turtle.Screen()
draw_sierpinski(200,4)
window.exitonclick()

A imagem será apresentada aqui.

Exemplo 2 - Triângulo de Sierpinski Construído de Forma Completa

No segundo exemplo utilizaremos mais recursos da biblioteca \(Turtle\). Na primeira parte do algoritmo definimos os vértices que irão compor o triângulo básico do algoritmo. A função \(goto\) da biblioteca \(Turtle\) move a seta para uma determinada posição absoluta (para um par de vetores). Neste caso a posição absoluta são os vértices definidos. Na segunda parte do código determina-se os pontos médios dos triângulos. Na terceira parte é feita a parte nos quais os triângulos menores são construídos. Conforme foi mencionado acima em \(S(1)\). O processo é feito recursivamente 4 vezes, \(level = 4\).

Também é feito na terceira parte do código uma coloração nos triângulos para facilitar a visualização destes. O novo código feito para calcular o algoritmo de Sierpinski é um pouco mais eficiente, pois não precisa retornar várias vezes para o mesmo ponto, diferentemente do código anterior.

O código implementado em Python segue abaixo:

import turtle


def draw_triangle(vertices,color,my_turtle):
    my_turtle.fillcolor(color)
    my_turtle.up()
    my_turtle.goto(vertices[0][0],vertices[0][1])
    my_turtle.down()
    my_turtle.begin_fill()
    my_turtle.goto(vertices[1][0],vertices[1][1])
    my_turtle.goto(vertices[2][0],vertices[2][1])
    my_turtle.goto(vertices[0][0],vertices[0][1])
    my_turtle.end_fill()


def midpoint(p1, p2):
    return [(p1[0] + p2[0])/2, (p1[1] + p2[1])/2]


def sierpinski(vertices,level,my_turtle):

    colors = [(0,150,189),(4,150,116),(216,95,30),(193,33,57),
                      (129,41,199),(102,205,135),(51,187,204)]
    draw_triangle(vertices,colors[level],my_turtle)

    if level > 0:

        sierpinski([vertices[0],
                      midpoint(vertices[0], vertices[1]),
                      midpoint(vertices[0], vertices[2])],
                      level - 1, my_turtle)
        sierpinski([vertices[1],
                      midpoint(vertices[0], vertices[1]),
                      midpoint(vertices[1], vertices[2])],
                      level - 1, my_turtle)
        sierpinski([vertices[2],
                      midpoint(vertices[2], vertices[1]),
                      midpoint(vertices[0], vertices[2])],
                      level - 1, my_turtle)

my_turtle = turtle.Turtle()
screen = turtle.Screen()
screen.colormode(255)
vertices = [[-200, -100], [0, 200], [200, -100]]
level = 4
sierpinski(vertices, level, my_turtle)
screen.exitonclick()

A imagem será apresentada aqui.

Exemplo 3 - Triângulo de Sierpinski Construído da Forma Caos Game

No terceiro exemplo utilizaremos a ideia de Jogo do Caos para gerar o Triângulo de Sierpinski. Essa é uma outra forma de algoritmo recursivo para calcular o Triângulo de Sierpinski.

Usando esta forma, desenha-se um triângulo equilátero com os vértices \(A\), \(B\), \(C\) e se escolhe um ponto aleatório dentro do triângulo. Agora, para cada passo deve-se escolher um vértice aleatório (as probabilidades para os cantos são iguais) e o ponto mental precisa ser conectado com o triângulo desenhado. A metade desta seção marca o ponto para a próxima iteração. Se repetido muitas vezes, os pontos criam uma aproximação ao Triângulo de Sierpinski.

Para construção deste código, inicialmente utiliza-se das bibliotecas \(numpy\), \(pylab\) e \(randint\). Pois neste caso necessitamos de gerar números aleatórios para encontrar os vértices. Define-se em primeiro plano os pontos médios, posteriormente os vértices iniciais. Tais vértices determinarão a criação do Triângulo Base. Posteriormente, de forma aleatória é encontrado os demais vértices que irão compor os demais triângulos.

Neste caso como não utilizamos a biblioteca \(Turtle\) temos que utilizar a funçao \(plot\) da biblioteca \(pylab\) para gerar a figura.

O código implementado em Python segue abaixo:

import numpy as np
import pylab
from random import randint

def midpoint(point1, point2):
    return [(point1[0] + point2[0])/2, (point1[1] + point2[1])/2]

curr_point = [0,0]

v1 = [0,0]
v2 = [1,0]
v3 = [.5,np.sqrt(3)/2]

for _ in range(5000):

    val = randint(0,2)
    if val == 0:
        curr_point = midpoint(curr_point, v1)
    if val == 1:
        curr_point = midpoint(curr_point, v2)
    if val == 2:
        curr_point = midpoint(curr_point, v3)

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

pylab.show()

A imagem será apresentada aqui.

comentou Jul 5, 2017 por Caue (231 pontos)  
A solução está ótima. Gostaria apenas de fazer um comentário:
Na chamada my_turtle.goto(vertices[0][0],vertices[0][5]), não seria vertices[0][1], por se tratar de um vetor (x,y)?
Você pode dar uma olhada em namedtuple para facilitar nesses casos: https://docs.python.org/3.6/library/collections.html#collections.namedtuple
comentou Jul 5, 2017 por João Gabriel Souza (81 pontos)  
Obrigado Cauê! Fiz as alterações no código, você estava correto havia um erro de digitação, não sei o que ocorreu que alterou os valores da função my_turtle.goto().
comentou Jul 7, 2017 por JoaoMaria (71 pontos)  
A resposta ficou bastante didática. O exercício está correto. O código implementado ficou bastante "Clean", o que facilitou o entendimento do assunto.
...