Algoritmo de Bresenham para trazar líneas.

Es un algoritmo creado para dibujar rectas en los dispositivos de graficos rasterizados, como por ejemplo un monitor de computadora, que determina que pixeles se rellenaran, en funcion de la inclinacion del angulo de la recta a dibujar.

Es un algoritmo preciso para la generacion de lineas de rastreo que convierte mediante rastreo las lineas al utilizar solo calculos 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 las columnas de pixel.

Es considerado uno de los algoritmos más efectivos para dibujar líneas mediante rastreo. Emplea cálculos incrementales con valores enteros. La forma de determinar el siguiente pixel a dibujar en la generación de una línea, se describe a continuación:

1.- Punto inicial  P1(Xinicial,Yinicial).
2.- Se desplaza una columna (incrementando la posición en X)
3.- Se traza el pixel cuyo valor de Y de la línea de rastreo se aproxima más a la trayectoria de la línea. Se capturan los dos extremos de la línea  P1(Xinicial,Yinicial) y P2(Xfinal,Yfinal)
4.- Se dibuja el primer pixel correspondiente al extremo izquierdo de la línea(P1)
5.- Se calculan los parámetros que permitien decidir cuál será el proximo pixel a dibujar (DeltaX, DeltaY y ConstanteP).
6.- Dependiendo del valor que tome el Parámetro ConstanteP se evalúa y determina la coordenada a dibujar que puede ser: 
       1.- (X+1,Y) para ConstanteP < 0
       2.- Sino (X+1,Y+1)
El proceso anterior debe repetirse 4DeltaX veces.

Algoritmo.

Leer Coordenadas P1(Xinicial, Yinicial)
Leer Coordenadas P2(Xfinal, Yfinal)
Asignar a  DeltaX el ABS( Xfinal - Xinicial)
Asignar a  DeltaY el ABS( Yfinal -Yinicial)
Asignar a ConstanteP  el resultado de 2*DeltaY - DeltaX
Si Xinicial > Xfinal
Asignar Xfinal a X
Asignar Yfinal a Y
Asignar Xinicial a Ultimo
De lo contrario
Asignar Xinicial a X
Asignar Yinicial a Y
Asignar a Xfinal a Ultimo
Iluminar pixel en coordenada X,Y
Hacer mientras X<Ultimo
Asignar X + 1 a X
Si ConstanteP < 0 
Asignar  ConstanteP + 2 *DeltaY a ConstanteP
De lo contrario
Asignar Y+1 a Y
Asignar a ConstanteP el resultado de ConstanteP+2 *(DeltaY-DeltaX)
Iluminar pixel en coordenada X,Y
Fin de Algoritmo (Bresenham)

Ejemplo.

#include <dos.h>
#include <stdio.h>
#include <graphics.h>
#include <math.h>
void BRESENHAM      (int Bx1, int By1, int Bx2, int By2)
{
   float e,ax,ay,temp;
   int s1,s2,intercambio,i,x,y;
   x=Bx1;
   y=By1;
   ax=abs(Bx2-Bx1);
   ay=abs(By2-By1);
   s1=signo(Bx2-Bx1);
   s2=signo(By2-By1);
   if(ay>ax)
   {
      temp=ax;
      ax=ay;
      ay=temp;
      intercambio=1;
   }
   else
   {
       intercambio=0;
   }
   e=2*ay-ax;
   for(i=1;i<=ax;i++)
   {
      putpixel((319+x),(239-y),4);
      if(e>=0)
      {
         if (intercambio==1)
         {
             x=x+s1;
         }
         else
         {
             y=y+s2;
         }
            e=e-(2*ax);
      }
      if (intercambio==1)
      {
          y=y+s2;
      }
      else
      {
          x=x+s1;
      }
      e=e+2*ay;
   }
}

int signo(int num)
{
    int resultado;
    if(num<0)
       resultado=-1;
   if(num>0)
       resultado=1;
   if(num==0)
       resultado=0;
   return(resultado);
}