Desenhar Reta em Java – Algoritmo de Bresenham/DDA Inteiro

Habilidades de SEO e Web Analytics à parte, a programação também está no meu skill set e é uma área que eu também gosto, até porque é bastante útil no marketing digital também. Então lá vai: Algoritmo de Bresenham ou DDA Inteiro – o algoritmo para desenhar retas “na raça” – código em Java.

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.

Algoritmo DDA Inteiro em Java (Bresenham)

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); } }

Mais programação e JAVA?

Nunca é demais estudar um pouco mais, mas antes de tentar se aprofundar no JAVA mesmo, vale muito a pena dominar a lógica de programação. Aí, programar em JAVA (ou qualquer linguagem), vai ficar bem mais fácil. Veja este ebook que pode te ajudar:

Curso Lógica Programação

Aí, depois de dominar a lógica de programação, vai valer a pena entrar de cabeça e ir fundo no JAVA:

Ebook Desenvolvimentos de Sistemas em JAVA

Comece investindo leve, depois que estiver mais desenvolvido, aí sim procure cursos, livros e certificações renomadas (e provavelmente caras).

Leitura recomendada:

8 thoughts on “Desenhar Reta em Java – Algoritmo de Bresenham/DDA Inteiro

  • Não entendi como que funcionou esse seu projeto.
    Vc tem os arquivos, pois nao entendi a ligação entre eles

  • Felipe, vc precisa criar uma classe para o objeto Reta com os atributos p1, p2. A Reta “sabe” se desenhar, portanto ela tem o método draw() q é onde fica o algoritmo DDA Inteiro.

    Crie tb uma classe para ser o painel desenho, onde vc instancia a reta e chama o método draw() da reta.

  • Não cheguei a fazer muitos testes mas acredito haver um erro em algumas linhas, segue o que acho que seria uma correção:
    linha 47: if(Math.abs(deltaX)Math.abs(deltaX);i–){
    linha 61: for(int i=1;i>Math.abs(deltaY);i–){

    para testar faça uma linha do ponto (50,-50) até o ponto(-50,-50).
    se eu estiver enganado me avisa.
    Vlw

  • Sei que já faz um tempo…rs… mas usei o código e blz, estou com problema para chamar em um jpanel como no código abaixo, quando aperto um boatão. na classe jFrame quero colocar o desenho da reta no jpanel, mas está dando erro no g do metodo draw… alguma ideia?

    codigo:
    p1 = new Ponto(Integer.parseInt(tfX1.getText()), Integer.parseInt(tfY1.getText()));
    p2 = new Ponto(Integer.parseInt(tfX2.getText()), Integer.parseInt(tfY2.getText()));
    r = new Reta(p1, p2);
    jPanel1.add(r.draw(g));

  • Alguem pode me enviar o projeto com o código, estou tendo problemas, nao consigo fazer funcionar. 🙄

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *