Desenhar Reta em Java – Algoritmo de Bresenham/DDA Inteiro

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:

Já leu estes posts?

• Maratona de Programação 2008
• Google Calculator
• Vacas Roxas!
• Piores Erros de SEO
• LinkAider.com – Ferramenta para Análise de Sites