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:
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).
Deixe um comentário