Algoritmo Bresenham - Dibujar línea - Programación C

Si el otro día publiqué un post sobre el algoritmo DDA, hoy os traigo el algoritmo Bresenham para dibujar una línea, al igual que en el anterior puedes tomártelo como un ejercicio de C o simplemente ir a la solución.

Explicación del algoritmo

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.

Pseucodigo

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)




Ejercicio:
Escribe un programa que dibuje una línea en pantalla usando el algoritmo Bresenham.

Sigue leyendo para ver el resultado:

Para ejecutar el ejemplo es necesario tener la librería "graphics.h" de Borland.



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

}



Artículos relacionados