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

Como desenhar uma curva de Hilbert de ordem n recursivamente?

+1 voto
102 visitas
perguntada Jun 15 em Ciência da Computação por Daniel Castro (46 pontos)  

Aula 3, Exercício 11. As questões abaixo pedem para você resolver um exercício usando recursão. Elas podem ser resolvidas com o apoio do livro “Introduction to recursive programming - Manuel Rubio Sanchez” [IRP2018]. Todas essas questões devem ser bem explicadas (e enunciadas), bem referenciadas e um código deve ser implementado na linguagem de sua escolha. Você pode e deve abusar a sua solução com o uso de figuras (quando for o caso).
b) (*) Exercise 7.9 of [IRP2018].

O Exercício 7.9 do livro [IRP2018] pede que se implemente um método recursivo que desenhe uma curva de Hilbert de ordem n, atentado para o fato de que a curva total é composta por quatro curvas de ordem inferior, desde que orientadas e conectadas da maneira apropriada. O enunciado do exercício é reproduzido abaixo:

A imagem será apresentada aqui.
A imagem será apresentada aqui.

Compartilhe

1 Resposta

+1 voto
respondida Jun 15 por Daniel Castro (46 pontos)  
editado Jun 15 por Daniel Castro

A solução mais genérica seria implementar a curva de Hilbert através de um L-System, em que objetos complexos são construídos pela substituição sucessiva de partes de um objeto inicial simples através de um conjunto de regras de reescrita ou produção (The Algorithmic Beauty of Plants - Przemyslaw Prusinkiewicz and Aristid Lindenmayer (1991)). Por exemplo, a pergunta Como replicar gráficos usando modelagem L-systems no Python? respondida recentemente implementa um L-System em Python. A pergunta Como replicar a Curva de Hilbert usando os conhecidos L-Systems (Lindenmayer-Systems)? implementa a curva de Hilbert através de um L-System. Diversas referências também apresentam a especificação da curva de Hilbert como um L-Sytem, como The Algorithmic Beauty of Plants p. 15, Mathematical Figures Using Mathematica, Wolfram MathWorld e Hilbert curves in 2 dimensions generated by L-systems.

Como o exercício não menciona L-Systems, a implementação abaixo foi específica para o problema da curva de Hilbert, como feito por exemplo em Hacker's Delight by Henry S. Warren (Cap 14) e Compu Phase. Para implementar a presente solução em Python, foi utilizado o módulo Turtle, relativamente simples e completo, utilizado também para ensinar programação a crianças.

A função hilbert recebe como parâmetros a ordem, o tamanho do segmento a desenha e a rotação a aplicar ao segmento. A cada chamada recursiva da função, a ordem é reduzida até o limite de zero, condição de parada da função. O tamanho do segmento não muda a cada chamada recursiva, ou seja, é fixo, sendo determinado na primeira chamada como uma função da ordem da curva. Quanto maior a ordem da curva, menor é o tamanho de cada segmento.

def hilbert(ordem, tamanho, rotacao):
"""
Desenha segmento da curva de hilbert com ordem e tamanho recebidos como
parâmetro; o parâmetro rotação indica para que direção a tartaruga virará
A cada chamada recursiva da função, a ordem é reduzida até a condição de
parada.
"""
if (ordem == 0):
    return

turtle.left(rotacao)
hilbert(ordem - 1, tamanho, -rotacao)

turtle.forward(tamanho) # conexão entre as curvas

turtle.left(-rotacao)
hilbert(ordem - 1, tamanho, rotacao)

turtle.forward(tamanho) # conexão entre as curvas

hilbert(ordem - 1, tamanho, rotacao)
turtle.left(-rotacao)

turtle.forward(tamanho) # conexão entre as curvas

hilbert(ordem - 1, tamanho, -rotacao)
turtle.left(rotacao)

Assim como sugere o enunciado do exercício, há quatro chamadas recursivas da função hilbert, cada uma responsável por desenhar determinado trecho da curva. As conexões são feitas entre as chamadas recursivas. Também entre as chamadas recursivas estão as chamadas para rotacionar a tartaruga, ou seja, para realizar as "viradas" na curva, sempre formando um ângulo reto (90° ou -90°).

A função desenha_quadrado, por sua vez, simplesmente desenha uma moldura ao redor da curva, como nos figuras do exercício:

def desenha_quadrado(lado):
"""
Desenha o quadrado que emoldura a curva de Hilbert
"""
for i in range(4):
    turtle.forward(lado)
    turtle.left(90)

O método main, por sua vez, configura o tamanho do lado do quadrado que envolve a curva, tamanho do segmento inicial, a ordem da curva, a rotação (no caso, deve ser sempre um ângulo reto, ou seja 90°), a direção inicial da figura (ou seja, se aponta para cima, para baixo, para a direita ou esquerda), a velocidade da tartaruga, a margem (distância da borda da janela a que a figura será desenhada), o tamanho da janela e a posição a partir da qual o desenho da curva se inicia, que varia de acordo com a direção inicial:

if __name__ == '__main__':

lado = 500 # lado do quadrado que envolve a curva de Hilbert
ordem_curva = 2 # ordem da curva de Hilbert
tamanho_segmento = lado / (2 ** ordem_curva) # quanto maior a ordem da curva,
# menor o tamanho do segmento; na figura do ex 7.9, o lado do quadrado é
# dividido por 2 elevado à ordem da curva para se chegar ao tamanho do
# segmento, incluindo as margens, correspondentes à metade de um segmento 
# em cada lado
margem = tamanho_segmento / 2   
rotacao = 90 # default da curva de Hilbert; a rigor, não seria um parâmetro
direcao_curva = 270 # define o direcionamento da curva; 
# opções são 0 (U para baixo), 90 (C), 180 (U) e 270 graus (C ao contrário)

turtle.home()
turtle.speed(5) # velocidade da tartaruga
# definição do tamanho da janela
largura_janela = 1.2 * lado
altura_janela = 1.2 * lado
turtle.screensize(canvwidth = largura_janela, canvheight = altura_janela)

turtle.penup()
# a janela é dividia em quatro por dois eixos cartesianos, com o zero na 
# interseção; o quadrado será centralizado 
turtle.setpos(-lado/2, -lado/2)
turtle.pendown()
desenha_quadrado(lado)
turtle.penup()

# define a posição para início do desenho da curva, com base na direção da 
# curva; a curva é desenhada dentro do quadrado, respeitando a margem
# definida
if direcao_curva == 0: # curva virada para baixo (U de cabeça para baixo)
    turtle.setpos(-(lado/2 - margem), -(lado/2 - margem)) # a curva é 
    # desenhada a partir do 3o. quadrante no sentido horário
elif direcao_curva == 90: # curva virada para a direita (como na letra C)
    turtle.setpos((lado/2 - margem), -(lado/2 - margem)) # a curva é 
    # desenhada a partir do 4o. quadrante no sentido horário
elif direcao_curva == 180: # curva virada para cima (como na letra U)
    turtle.setpos((lado/2 - margem), (lado/2 - margem)) # a curva é 
    # desenhada a partir do 1o. quadrante no sentido horário
elif direcao_curva == 270: # curva virada para a esqueda (letra C ao contrário)
    turtle.setpos(-(lado/2 - margem), (lado/2 - margem)) # a curva é
    # desenhada a partir do 2o. quadrante no sentido horário
else:
    turtle.done()
    raise ValueError("Opções devem ser 0, 90, 180 ou 270")

turtle.left(direcao_curva)
turtle.pendown()
hilbert(ordem_curva, tamanho_segmento, rotacao)
turtle.done()
turtle.exitonclick()

As figuras abaixo mostram quatro curvas de Hilbert de ordem 1 desenhadas para os quatro valores possíveis da direção inicial (0, 90, 180 e 270, respectivamente):

A imagem será apresentada aqui.

A imagem será apresentada aqui.

A imagem será apresentada aqui.

A imagem será apresentada aqui.

Abaixo seguem figuras como as do Exercício 7.9 do IRP2018, com ordens de 2 a 6 e direcionamento inicial sempre igual a 180:

A imagem será apresentada aqui.

A imagem será apresentada aqui.

A imagem será apresentada aqui.

A imagem será apresentada aqui.

A imagem será apresentada aqui.

O código foi disponibilizado também no script aula3_11b.py de repositório no GitHub.

Evoluções do script poderiam permitir que o usuário informasse os valores dos parâmetros, por exemplo a partir de uma GUI. Outra questão diz respeito ao desempenho, já que o tempo necessário para desenhar curvas aumenta substancialmente com a ordem.

comentou Jul 11 por Carlos A T Haraguchi (21 pontos)  
Daniel, muito bom seu post. Agradeço também a referência a um post meu.

As explicações estão claras, os gráficos ilustrativos e o código disponibilizado no GitHub facilita a replicação. Também gosto de bastante comentários no código. Útil para o programador e para quem irá utilizar/manter o código.

Complementando suas sugestões de evoluções do script, tenho mais uma. Me parece que a recursão também é utilizada para girar a "turtle" em "rotacao" graus, às vezes à direita, às vezes à esquerda, em um número "ordem" de vezes. Talvez haja ganho também se, antes de chamar a recursão, já fosse calculada a rotação final. Por exemplo, se "ordem" é 3, e se está passando "-rotacao" à função "hilbert", poderia ser passado -3*"rotacao".
...