Algoritmo de bresenham

Algoritmo de Bresenham para representação de linhas retas em dispositivos matriciais
Vinícius Leal Trindade

Resumo
Este artigo apresenta um resumo e a análise de complexidade do Algoritmo de
Bresenham, também conhecido como algoritmo do ponto médio, utilizado para representar linhas retas em dispositivos eletrônicos matriciais

Introdução
Algoritmos de computação gráfica tem como objetivo apresentar uma forma de fazer representações gráficas através de uma tela composta por pixels, (tal como monitores) de forma convincente e que utilize o mínimo de recursos possível . Essas representações são feitas através da combinação de primitivas, tais como linhas, círculos, pontos, etc, quem juntas formam uma imagem digital. O algoritmo de bresenham especificamente, trata de desenhar linhas retas, determinando quais pixels serão ligados dados um ponto inicial e um ponto final.

Descrição
Para determinar como será feita a representação da reta dados um ponto inicial e um ponto final como parâmetros, o algoritmo baseia-se no critério do ponto médio. Para exemplificar, considere a figura abaixo contendo uma reta interceptando uma matriz de pixels. Para cada coluna, encontram-se dois pixels mais próximos da reta, um abaixo e outo acima dela. Se localizarmos o ponto médio entre esses dois pixels em relação à reta, pode-se determinar qual dos pixels será escolhido. Se o ponto médio encontra-se abaixo da reta, deve-se escolher o pixel de cima. Caso contrário, será escolhido o de baixo.

linha reta interceptando uma matriz de pixels

Para calcular o ponto médio em relação à reta, considere a equação implícita de uma reta, que é:
F(x,y) = ax + by + c
Dado um ponto em um plano, se esse ponto pertence à reta, o valor dessa função é 0.
Caso contrário, se o valor for positvo, o ponto encontra-se abaixo da reta, e se for negativo o ponto encontra-se acima da reta. A escolha dos pixels é baseada exatamente nesses valores, através de uma variável de