Algoritmo de Bresenham

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Ejemplo de aplicación del algoritmo de Bresenham.


Descripción[editar]

Es un algoritmo preciso para la generación de líneas de rastreo que convierte mediante rastreo las líneas al utilizar solo cálculos incrementales con enteros que se pueden adaptar para desplegar circunferencias y curvas. Los ejes verticales muestran las posiciones de rastreo y los ejes horizontales identifican columnas de pixel.

Algoritmo[editar]

El algoritmo sería el siguiente:

Si 0<|m|<1
  *Se capturan los extremos de la línea y se almacena el extremo izquierdo en (x0,y0).
  *Se carga (x0,y0) en el bufer de estructura (se traza el primer punto)
  *Se calculan las constantes Δx,Δy, 2Δy y 2Δy-Δx y se obtiene el valor inicial para el 
    parametro de decisión p0=2Δy-Δx.
  Para j=0 mientras j<Δx
  *En cada xk a lo largo de la línea, que inicia en k=0 se efectúa la prueba siguiente:
      Si pk<0
          *Trazamos (xk+1,yk). 
          *Asignamos pk+1= pk+2Δy.
      Sino
          *Trazamos (xk+1,yk+1). 
          *Asignamos pk+1= pk+2Δy-2Δx.
  Fin Para
Si |m|>1
   *Recorremos la dirección en pasos unitarios y calculamos los valores sucesivos    
     de x que se aproximen más a la trayectoria de la línea.

Implementación en Java[editar]

Esta es la implementación del algoritmo:

public void Bresenham(Graphics g,int x0, int y0, int x1, int y1) { 
  int x, y, dx, dy, p, incE, incNE, stepx, stepy;
  dx = (x1 - x0);
  dy = (y1 - y0);
 
 /* determinar que punto usar para empezar, cual para terminar */
  if (dy < 0) { 
    dy = -dy; 
    stepy = -1; 
  } 
  else {
    stepy = 1;
  }
 
  if (dx < 0) {  
    dx = -dx;  
    stepx = -1; 
  } 
  else {
    stepx = 1;
  }
 
  x = x0;
  y = y0;
  g.drawCircle( x0, y0, x0, y0);
 /* se cicla hasta llegar al extremo de la línea */
  if(dx>dy){
    p = 2*dy - dx;
    incE = 2*dy;
    incNE = 2*(dy-dx);
    while (x != x1){
      x = x + stepx;
      if (p < 0){
        p = p + incE;
      }
      else {
        y = y + stepy;
        p = p + incNE;
      }
      g.drawLine( x, y, x, y);
    }
  }
  else{
    p = 2*dx - dy;
    incE = 2*dx;
    incNE = 2*(dx-dy);
    while (y != y1){
      y = y + stepy;
      if (p < 0){
        p = p + incE;
      }
      else {
        x = x + stepx;
        p = p + incNE;
      }
      g.drawLine( x, y, x, y);
    }
  }
 }

Véase también[editar]

Referencias[editar]

Bibliografía[editar]

  • Watt, Alan (2000). «Rasterizing edges». 3D Computer Graphics (3ª edición). p. 184. ISBN 0-201-39855-9. 

Enlaces externos[editar]