Algoritmo de Bresenham

Algoritmo de Bresenham
Ejemplo de aplicación del algoritmo de Bresenham.

El algoritmo de Bresenham es un algoritmo creado para dibujar rectas en los dispositivos de gráficos rasterizados, como por ejemplo un monitor de ordenador, que determina qué pixeles se rellenarán, en función de la inclinación del ángulo de la recta a dibujar.

Contenido

Descripción

Es un algoritmo preciso para la generación de lineas de ratreo 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

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-Δ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

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.drawLine( 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( x0, y0, x0, y0);
    }
  }
  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( x0, y0, x0, y0);
    }
  }
 }

Véase también

Referencias

Sitio Web de Héctor E. Medellín Anaya http://galia.fc.uaslp.mx/~medellin/Applets/LineasRectas/Recta.htm

Bresenham 2D, 3D hasta 6D https://sites.google.com/site/proyectosroboticos/bresenham-4d


Publicaciones

  • Alan Watt: 3D Computer Graphics, 3rd edition 2000, p. 184 (Rasterizing edges). ISBN 0-201-39855-9

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Algoritmo del Punto Medio para Circunferencias — Plantilla:Acerca de Contenido 1 Introducción 2 Algoritmo 3 Rendimiento 4 Código Ejemplo Java 5 …   Wikipedia Español

  • Algoritmo del Punto Medio para Elipses — Plantilla:Acerca de Contenido 1 Introducción 2 Algoritmo 3 Rendimiento 4 Código Ejemplo Java 5 …   Wikipedia Español

  • Algoritmo del Punto Medio para Parábolas — Plantilla:Acerca de Contenido 1 Introducción 2 Algoritmo 3 Rendimiento 4 Código Ejemplo Java 5 …   Wikipedia Español

  • Algoritmo de Xiaolin Wu — Recta aliasinada dibujada con el algoritmo de Xiaolin Wu. El algoritmo de Xiaolin Wu es una mejora del algoritmo de Bresenham que permite dibujar rectas en dispositivos de gráficos rasterizados reduciendo el aliasing. El algoritmo se basa en… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”