• Desenhar Reta em Java – Algoritmo de Bresenham/DDA Inteiro

    Programação 31.07.2009

    Hail! É verdade, o objetivo é fazer deste, um blog de SEO, mas programação também está no sangue e eu gosto de variar o tema, 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 algortimo 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)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    
    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<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;
    					}
    				}
    			}
    		}
    		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:

    1
    2
    3
    
    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:

    1
    2
    3
    4
    
    public void draw(Grahpics 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):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    
    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);
    	}
    }

    Em caso de erros, dúvidas e sugestões, deixe um comentário.

    Gostou? Então assine o feed ou divulgue este excelente post:

    Enviar para o del.icio.us Enviar para o Link Ninja Votar neste post no Rec6 Votar neste post no diHiTT Adicionar artigo ao Linkk

    Já leu estes posts?



    Posted by frankmarcel @ 17:54

  • Comentários neste Post


    2 Comentários

    WP_Modern_Notepad
    • Felipe disse:

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

    • frankmarcel disse:

      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.

    Deixe um Comentário

    Importante: Os comentários são moderados e não aparecem imediatamente.

Follow up!

    Translate