Pular para o conteúdo principal

Algoritmo de Bresenham


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

Comentários

Postagens mais visitadas deste blog

Computação Gráfica: Fundamentos básicos

Caos e hackers perseguem investidores nas bolsas de criptomoedas

Dan Wasyluk descobriu da forma mais difícil que as negociações de criptomoedas como bitcoins ocorrem em um ambiente online similar ao Velho Oeste, com os xerifes em grande parte ausentes.

Wasyluk e seus colegas levantaram bitcoins para uma nova empresa de tecnologia e hospedaram-nos como garantia em uma administradora de bolsa de moedas virtuais chamada Moolah. Poucos meses depois, o bolsa quebrou e o homem responsável está aguardando julgamento no Reino Unido, sob acusações de fraude e lavagem de dinheiro. Ele se declarou inocente.

O projeto de Wasyluk perdeu 750 bitcoins, que atualmente valem cerca de 3 milhões de dólares, e ele acredita que tem poucas chances de recuperar dinheiro.


"Realmente o projeto foi um tiro no pé", disse Wasyluk sobre o colapso de três anos atrás. "Se você está começando uma bolsa e você perde o dinheiro dos clientes, você ou sua empresa devem ser 100 por cento responsáveis por essa perda."
As criptomoedas deveria…

As 7 principais linguagens de programação usadas em desenvolvimento mobile

A multiplicidade de linguagens para a criação de softwares e aplicativos é gigantesca. Inserido nesse universo recheado de idiomas, digno de séries e filmes cultuados como “Star Trek” e “Star Wars”, o programador deve escolher precisamente a opção mais adequada ao objetivo final.
Não somos tão sábios quanto Mestre Yoda e Spock, mas vamos te dar uma força e explicar quais as linguagens de programação mais usadas em desenvolvimento mobile. Siga-nos nessa jornada!
Java Adquirida pela Oracle, é a linguagem mais utilizada por programadores ao redor do mundo. Orientado a objetos, o Java é compilado e flexível, podendo ser executada tanto numa janela de navegador quanto em aparelhos sem browser.
Outra grande vantagem da linguagem Java é a capacidade multiplataforma, cujo código é executado com especial sucesso em sistemas Android e Windows. Ainda assim, quando fala-se em desenvolvimento mobile no Brasil, com a salada mista de SO nos smartphones e tablets, dependendo dos seus …