Algoritmo de Bresenham

O algoritmo de Bresenham — em homenagem a Jack Elton Bresenham — é um algoritmo criado para o desenho de linhas, em dispositivos matriciais (como por exemplo, um monitor), que permite determinar quais os pontos numa matriz de base quadriculada que devem ser destacados para atender o grau de inclinação de um ângulo.

O Código

void bresenham1(int x1, int y1, int x2, int y2){        
        int slope;
        int dx, dy, incE, incNE, d, x, y;
        // Onde inverte a linha x1 > x2       
        if (x1 > x2){
            bresenham1(x2, y2, x1, y1);
             return;
        }        
        dx = x2 - x1;
        dy = y2 - y1;
    
        if (dy < 0){            
            slope = -1;
            dy = -dy;
        }
        else{            
           slope = 1;
        }
        // Constante de Bresenham
        incE = 2 * dy;
        incNE = 2 * dy - 2 * dx;
        d = 2 * dy - dx;
        y = y1;       
        for (x = x1; x <= x2; x++){
            putpixel(x, y);
            if (d <= 0){
              d += incE;
            }
            else{
              d += incNE;
              y += slope;
            }
        }
  }

Desenhar Reta em Java – Algoritmo de Bresenham/DDA Inteiro

O objetivo deste algoritmo é reduzir o esforço computacional para se 


desenhar uma reta, bem como reduzir erros de arredondamento e operações 
com ponto flutuante. E, de fato, o algoritmo de Bresenham consegue fazer
 isso – ele se desenvolve sem nenhuma operação de ponto flutuante, 
nenhuma variável numérica é do tipo float ou double e, também, o 
algoritmo não realiza divisões entre números inteiros.


Abaixo, o algoritmo para desenhar retas em Java e, na sequência, algumas explicações.



public void draw(Graphics g){
  int x, y, erro, deltaX, deltaY;
  erro = 0;
  x = p1.x;
  y = p1.y;
  deltaX = p2.x - p1.x;
  deltaY = p2.y - p1.y;
  
  if((Math.abs(deltaY)>=Math.abs(deltaX) && p1.y>p2.y)
   ||(Math.abs(deltaY)<Math.abs(deltaX) && deltaY<0)){
   
   x = p2.x;
   y = p2.y;
   deltaX = p1.x-p2.x;
   deltaY = p1.y-p2.y;
  }
  p1.draw(g);
  if(deltaX>=0){
   if(Math.abs(deltaX)>=Math.abs(deltaY)){
    for(int i=1;i<Math.abs(deltaX);i++){
     if(erro<0){
      x++;
      new Ponto(x,y).draw(g);
      erro += deltaY;
     }else{
      x++;
      y++;
      new Ponto(x,y).draw(g);
      erro += deltaY - deltaX;
     }
    }
   }else{
    for(int i=1;i<Math.abs(deltaY);i++){
     if(erro<0){
      x++;
      y++;
      new Ponto(x,y).draw(g);
      erro += deltaY - deltaX;      
     }else{
      y++;
      new Ponto(x,y).draw(g);
      erro -= deltaX;
     }
    }
   }
  }else{ // deltaX=Math.abs(deltaY)){
    for(int i=1;i<Math.abs(deltaX);i++){
     if(erro<0){
      x--;
      new Ponto(x,y).draw(g);
      erro += deltaY;
     }else{
      x--;
      y++;
      new Ponto(x,y).draw(g);
      erro += deltaY + deltaX;
     }
    }
   }else{
    for(int i=1;i<Math.abs(deltaY);i++){
     if(erro<0){
      x--;
      y++;
      new Ponto(x,y).draw(g);
      erro += deltaY + deltaX;      
     }else{
      y++;
      new Ponto(x,y).draw(g);
      erro += deltaX;
     }
    }
   }
  }
  p2.draw(g);
 }




Detalhes sobre o DDA Inteiro de Retas



Como eu uso esse método?
Normalmente eu crio uma classe “Reta” com os atributos Ponto p1 e p2 
(os pontos inicial e final da reta), o seu método construtor que recebe o
 ponto inicial e o final; e este método “draw” para desenhar a reta.


Importante notar que este método de desenho recebe como parâmetro o 
elemento Graphics g, onde o desenho de cada ponto da reta vai acontecer e
 o método tem a seguinte chamada:



Reta r;
r = new Reta(p1,p2);
r.draw(g);
O Ponto é definido com os atributos x e y e também possui um método 
para se desenhar, o draw(Graphics g). Neste método, uso o método default
 do java para desenhar retas, porém desenhando um ponto:



public void draw(Graphics g){
 g.setColor(Color.black);
 g.drawLine(x,y,x,y);
}




Variáveis no Bresenham
Nas primeiras linhas, apenas a definição das variáveis acontece. Os 
deltas servem para controlar os 4 possíveis casos do algoritmo de 
Bresenham; x e y vão definir os pontos da reta a ser desenhada; e erro é
 uma variável de controle sobre como proceder com x e y a cada ponto 
desenhado:




incrementar x?
incrementar y?
incrementar x e y?
decrementar…?

O seu valor muda somando ou subtraindo os deltas em seu valor atual. Mais explicações na sequência neste artigo.




Ordem dos Pontos
Nas linhas de 9 a 16, o algoritmo procura atender uma premissa para 
seu funcionamento correto: fazer com que os valores de y caminhem do 
menor para o maior entre os pontos da reta.




DDA Inteiro: Linhas 18~72
O algoritmo de Bresenham é dividido em 4 casos. O que define cada um é
 a identificação do maior delta (X ou Y), considerando também se deltaX é
 positivo ou negativo.



Por que procura-se o maior delta? O maior delta define em qual eixo 
(abcissas ou ordenadas) está o maior caminho a ser percorrido, pois o 
loop (for (…)) deverá conter tantas execuções quanto forem necessários 
pontos para se desenhar a reta percorrendo essa maior distância, pois 
cada loop desenha um único ponto.



E qual a importância do “sinal” do deltaX? Como nas linhas 9 a 16 o 
algoritmo força que a reta seja desenhada de tal forma que se vá do 
menor para o maior y, pode acontecer que o x varie do maior para o menor
 ao longo do desenho, e isso influi diretamente no incremento ou 
decremento de X, bem como no sinal do deltaX utilizado no cálculo do 
erro.



Ou seja, se o desenho da reta vai começar pelo maior x e ele é 
incrementado, nunca será alcançado o menor x e a reta seria desenhada de
 forma errada. E, quando deltaX>=0, significa que x1<x2 (então 
desenha-se do menor x para o maior x), enquanto deltaX<0 é resultado 
de x2<x1 (maior x para o menor x).



E por isso a diferença entre incrementar ou decrementar o valor de x nos casos do algoritmo DDA Inteiro:




Se x2>x1, x++;
Se x1>x2, x- -;

A variação do sinal do deltaX se define de modo análogo:




Se deltaX>=0, subtrai-se deltaX;
Se deltaX<0, soma-se o deltaX (no fim, está sendo somado um número negativo, ou seja, uma subtração);

O objetivo é que o deltaX seja sempre subtraído no valor do erro, mas
 se ele for negativo, a subtração de um valor negativo, resulta em uma 
soma, daí a variação no sinal de deltaX quando é calculado o erro. Como é
 sempre definido que y2>y1, deltaY será sempre positivo (ou zero) e 
basta sempre somar seu valor no erro.



O detalhe sobre a variação do erro é que ele decide quando variar x e
 y baseado nos deltas. A coordenada de maior delta deve variar 
(incrementar ou decrementar) mais vezes, pois tem um caminho maior a 
percorrer. O que o erro faz é controlar quantas vezes a mais uma 
variável é incrementada ou decrementada em relação a outra.



E assim mantém-se a coerência no algoritmo para o desenho de retas.



Detalhe importante: nas linhas 17 e 73 está o desenho do primeiro e último pontos, respectivamente.



Para finalizar, teste isso tudo em um JPanel no método paint(Graphics g):



public class Canvas extends JPanel{
  public Canvas(){
  ...
 }
 public void paint(Graphics g){
  super.paint(g);
  new Reta(new Ponto(15,10), new Ponto(400,200)).draw(g);
 }
}