2.2 Funcionamento do Algoritmo de Bresenham

Veja ilustrado abaixo o procedimento através de um exemplo concreto. Mas, primeiro, faça uma análise geral. Considere dois pontos definidos por $$ ( x_{0} , y_{0}) $$ e $$ ( x_{1} , y_{1}) $$, a equação da reta a partir deles é:

Isolando o $$ y $$ da equação, você terá:

A parte da equação $$ \frac{(y_{1} - y_{0})}{ (x_{1} - x_{0})} $$ pode ser pré-calculada com as coordenadas dos pontos e representa o coeficiente angular, do qual pode-se calcular a inclinação da reta. Quanto maior for $$ ( y_{1} - y_{0}) $$ em relação a $$ ( x_{1} - x_{0}) $$, mais inclinada estará a reta. Consequentemente, uma maior inclinação indica que o valor de $$ y $$ será incrementado mais frequentemente no algoritmo. Assim, pode-se usar esse valor de inclinação para saber quando $$ y $$ será incrementado sem precisar ficar calculando distâncias entre os valores de $$ y $$.

Sabendo que a cada iteração do laço do algoritmo que está percorrendo os valores em $$ x $$, o valor de $$ y $$ cresce de acordo com sua inclinação, você pode ir somando essa inclinação até que ultrapasse o tamanho de um pixel. Quando isso ocorre, é sinal de que o $$ y $$ precisa ser incrementado.

Faça isso, em um caso concreto, já aplicado ao cálculo do caminho que um personagem deve realizar. Imagine que o personagem esteja na posição (3, 1) e precisa recolher um bônus na posição (13, 3), como ilustra a Figura 12.

O cálculo da inclinação é definido por:

Esse valor $$ m $$ será adicionado a uma variável a cada iteração do laço do algoritmo. Essa variável contém o erro (ou distância) que vai se acumulando ao longo das iterações. Quando o erro for “maior do que um” considere que as células tenham tamanho unitário, incremente o $$ y $$ e reajuste o erro novamente. O valor inicial do erro é 0,5 porque a linha começa na metade da célula. Então:

O algoritmo começa na posição onde o personagem se encontra (3, 1), com o valor de erro em 0,5. A cada iteração, o x é incrementado, pois você está percorrendo seus valores, e o erro é acrescentado de 0,2, que é o valor do coeficiente angular (inclinação da reta) calculado previamente. Na iteração 4, o valor do erro ultrapassa 1 (ele fica com 1,1), sinalizando que o y precisa ser incrementado, e é logo após reajustado, reduzindo seu valor de 1 (1,1 – 1 = 0,1). As iterações continuam até que na iteração 9 o valor do erro ultrapassa novamente 1, fazendo com que o y seja incrementado e o erro reajustado. Por fim, após a última iteração, o personagem se desloca para a posição destino, que no caso era (13, 3). A Figura 13 mostra o caminho calculado pelo personagem, de acordo com o Quadro 01.