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);
}
}
Queen Casino - Free Slots, No Deposit Bonus & Review - Konicasino
ResponderExcluirQueen Casino Review. Casino Welcome Bonus. 100% 더킹카지노 Welcome bonus up rb88 to $300 plus 100 free spins. Free Spins for New クイーンカジノ players. No Deposit Required.