🥇 Algoritmo de círculo de Minsky em Shoes.rb / Hackety Hack

Eu queria tentar implementar o Algoritmo de Círculo de Minsky do famoso HAKMEM . Conforme observado em muitos outros lugares online ( 1 , 2 , 3 ), o algoritmo não representa um círculo verdadeiro, mas sim uma elipse muito redonda. Aqui está o texto da entrada HAKMEM:

ITEM 149 (Minsky): ALGORITMO DO CÍRCULO Aqui está uma maneira elegante de desenhar quase círculos em uma tela de plotagem de pontos:
NOVO X = OLD X – epsilon * OLD Y
NOVO Y = ANTIGO Y + epsilon * NOVO (!) X
Isso torna uma elipse muito redonda centrada na origem com seu tamanho determinado pelo ponto inicial. épsilon determina a velocidade angular do ponto de circulação e afeta ligeiramente a excentricidade. Se épsilon é uma potência de 2, então nem precisamos da multiplicação, muito menos raízes quadradas, senos e cossenos! O “círculo” será perfeitamente estável porque os pontos logo se tornam periódicos.
O algoritmo de círculo foi inventado por engano quando tentei salvar um registro em um hack de exibição! Ben Gurley teve um incrível hack de exibição usando apenas seis ou sete instruções, e foi uma grande maravilha. Mas era basicamente orientado para a linha. Ocorreu-me que seria emocionante ter curvas, e eu estava tentando obter um hack de exibição de curvas com instruções mínimas.

O benefício de usar este algoritmo, na época, era que ele não usava cosseno / seno ou qualquer outra função complicada e, portanto, poderia ser implementado nos computadores bastante limitados da época para desenhar círculos rapidamente. (Eu acredito que foi usado para desenhar as órbitas de naves no início do jogo SpaceWar

Para implementá-lo sozinho, eu precisava ser capaz de traçar pontos em um monitor. Então, recorri ao Hackety-Hack, que vem com o Shoes para desenhar gráficos. A DSL Shoes para desenhar formas é bastante simples, o que significa que podemos pegar o pseudocódigo acima e transformá-lo em uma demonstração funcional com bastante facilidade:

Shoes.app do
  epsilon = 1.0/16
  offset = 250
  x = 20
  y = 20

  fill red
  shape do
    move_to(x + offset,y + offset)

    100.times do
      x = x - epsilon * y
      y = y + epsilon * x
      line_to(x + offset,y + offset)
    end
  end

  fill blue
  oval({top: 250, left: 320, radius: 25, center: true})
end

Epsilon é 1/16, conforme indicado por algumas pesquisas rápidas no Google – basicamente uma pequena potência de dois. Tenho que usar o deslocamento para aproximar o centro do círculo do centro da janela Shoes – sem o deslocamento, o círculo será apenas um quarto de círculo no canto superior esquerdo.

Como isso se compara a traçar um círculo real?

Se quisermos comparar a redondeza de nosso “círculo” a um círculo real desenhado por Shoes, podemos adicionar esta linha antes do fechamento end:

fill blue
oval({top: 250, left: 320, radius: 25, center: true})

Embora seus raios sejam ligeiramente diferentes.

Aqui está o que terminamos. Algoritmo de círculo de Minsky à esquerda em vermelho, um círculo real à direita em azul:

Hackety Hack

Como isso se compara a traçar um círculo real?

Related Posts