Geometria

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.

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.

El algoritmo que se utilizaría es sería el siguiente:

Si 0<|m|<1 o:p="">

  *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 o:p="">

          *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

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

    }

  }

 }

Entonces  la imagen quedaría asi:

Bresenham 2D

Algoritmo de Bresenham clásico. El programa traza líneas, pixel a pixel, en cualquier sentido. La información teórica completa sobre métodos de trazar líneasclic aquí, y para aplicarlo a círculos, elipses y cuadráticas... clic aquí y especialmente aquí. El programa y código fuente que pongo para descargar podrás introducir valores para X entre 0 y 800, para Y entre 0 y 600. Puedes introducir cualquier valor, incluso números negativos, pero fuera del rango de 800x600 no podrás ver las líneas. Todos los algoritmos de Bresenham que encontrarás en esta web también funciona con números enteros negativos. Bresenham 3D El código fuente que está al final de esta página es el algoritmo de Bresenham para 3 dimensiones. Verás que tiene un código fuente un poco largo porque contiene tres "If..Then" y dentro de cada "If..Then" un "For..Next". Depende de los valores de entrada para que se determine por uno de los tres "If..Then". Esto significa que sólo se ejecuta una parte del programa. Teniendo en cuenta esto y que Bresenham sólo usa sumas y restas, el tiempo de ejecución es mínimo. Cuando lo ejecutes verás en el monitor los resultados de los números que se van sucediendo uno a uno. Los números que arroja forman parte de las coordenadasXYZ para trazar la trayectoria de una línea recta en las tres dimensiones del espacio.  El programa es de propósito general; sólo tendrás que hacer unas pequeñas modificaciones para adaptarlo a tus necesidades. Podrás tomar los resultados que te vaya dando el algoritmo para hacer traslaciones gráficas o posicionar un dispositivo mecánico en el mundo real. Cuando hagas las primeras pruebas trata de usar valores pequeños para que puedas ver los resultados cómodamente, como en la imagen de arriba. Podrás comprobar que puedes usar número enteros positivos y negativos. Has de introducir las tres coordenadas (X,Y,Z) separadas por comas y después pulsar 'Enter'. Cliquea aquí para bajarte el código fuente y ejecutable.  (Si usas antivirus Avast has de añadir una exclusión para poder ejecutarlo. Para analizar este o cualquier otro archivo puedes hacer clic aquí) Este es el programa:  Código fuente escrito en FreeBasic, compatible con Qbasic. The translation could modify the code. Use the code without translating or download the program clicking image above. Dim As Integer Cont, dx, dy, dz, Adx, Ady, Adz, x_inc, y_inc, z_inc,_                err_1, err_2, dx2, dy2, dz2, xxx, yyy, zzz, Xold, Yold, Zold,_                Xnew, Ynew, Znew                             While (1)    Input "X: ",  Xnew    Input "Y: ",  Ynew    Input "Z: ",  Znew    xxx=Xold    yyy=Yold    zzz=Zold       dx = xnew - Xold    dy = ynew - Yold    dz = znew - Zold        If (dx < 0) Then       x_inc = -1    Else      x_inc =  1    EndIf         If (dy < 0) Then       y_inc = -1    Else       y_inc =  1    EndIf          If (dz < 0) Then       z_inc = -1    Else      z_inc =  1    EndIf        Adx = Abs(dx)    Ady = Abs(dy)    Adz = Abs(dz)        dx2 = Adx*2    dy2 = Ady*2    dz2 = Adz*2        If ((Adx>= Ady) And (Adx>= Adz)) Then             err_1 = dy2 - Adx       err_2 = dz2 - Adx              For Cont = 0 To Adx-1                  If (err_1 > 0) Then              yyy+= y_inc              err_1 -= dx2          EndIf                     If (err_2 > 0) Then               zzz+= z_inc              err_2 -= dx2          EndIf                     err_1 += dy2          err_2 += dz2          xxx+= x_inc                    print xxx, yyy, zzz                 Next           EndIf       If ((Ady> Adx) And (Ady>= Adz)) Then            err_1 = dx2 - Ady      err_2 = dz2 - Ady             For Cont = 0 To  Ady-1                If (err_1 > 0) Then              xxx+= x_inc             err_1 -= dy2         EndIf                    If (err_2 > 0) Then              zzz+= z_inc             err_2 -= dy2         EndIf                   err_1 += dx2         err_2 += dz2         yyy+= y_inc              print xxx, yyy, zzz              Next    EndIf        If ((Adz> Adx) And (Adz> Ady)) Then             err_1 = dy2 - Adz       err_2 = dx2 - Adz              For Cont = 0 To Adz-1                    If (err_1 > 0) Then              yyy+= y_inc              err_1 -= dz2          EndIf                     If (err_2 > 0) Then               xxx+= x_inc              err_2 -= dz2          EndIf                     err_1 += dy2          err_2 += dx2          zzz+= z_inc                  print xxx, yyy, zzz             Next         EndIf        Xold=xnew    Yold=ynew    Zold=znew Wend Bresenham 6D Por último un Bresenham de 6 dimensiones. Verás que tiene un código un poco largo porque contiene seis "If..Then" y dentro de cada "If..Then" un "For..Next". Depende de los valores de entrada para que se determine por uno de los seis "If..Then". Esto significa que sólo se ejecuta una parte del programa. Teniendo en cuenta esto y que Bresenham sólo usa sumas y restas, el tiempo de ejecución es mínimo. Este algoritmo puede servirte para 2D, 3D, 4D, 5D y 6D. Las dimensiones que no uses has de dejarlas a cero o sin introducir cambios. La imagen de arriba es el programa en ejecución, donde puedes observar la sucesión de posiciones, uno por uno, hasta completar la trayectoria.   Para bajarte directamente el algoritmo de Bresenham 6D, cliquea aquí. Si quieres un Bresenham 4D y nada más, cliquea aquí. (Si usas antivirus Avast has de añadir una exclusión para poder ejecutarlo. Para analizar este o cualquier otro archivo puedes hacer clic aquí) En el interior del ZIP viene el código fuente y el programa ejecutable.   Código fuente escrito en FreeBasic, 99% compatible con QBasic. The translation could modify the code. Use the code without translating or download the program clicking image above. Dim As Integer   d1,   d2,   d3,   d4,   d5,   d6,_                 Ad1,  Ad2,  Ad3,  Ad4,  Ad5,  Ad6,_                inc1, inc2, inc3, inc4, inc5, inc6,_                d1x2, d2x2, d3x2, d4x2, d5x2, d6x2,_                dim1, dim2, dim3, dim4, dim5, dim6,_                old1, old2, old3, old4, old5, old6,_                new1, new2, new3, new4, new5, new6,_                err1, err2, err3, err4, err5, Cont3                While (1)            Input "Dim1: ", New1      Input "Dim2: ", New2      Input "Dim3: ", New3      Input "Dim4: ", New4      Input "Dim5: ", New5      Input "Dim6: ", New6  d1 = New1 - Old1  d2 = New2 - Old2  d3 = New3 - Old3  d4 = New4 - Old4  d5 = New5 - Old5  d6 = New6 - Old6     If (d1 < 0) Then    inc1 = -1  Else    inc1 =  1  EndIf     If (d2 < 0) Then    inc2 = -1  Else    inc2 =  1  EndIf      If (d3 < 0) Then    inc3 = -1  Else    inc3 =  1  EndIf     If (d4 < 0) Then    inc4 = -1  Else    inc4 =  1  EndIf  If (d5 < 0) Then    inc5 = -1  Else    inc5 =  1  EndIf     If (d6 < 0) Then    inc6 = -1  Else    inc6 =  1  EndIf     Ad1 = Abs(d1)  Ad2 = Abs(d2)  Ad3 = Abs(d3)  Ad4 = Abs(d4)  Ad5 = Abs(d5)  Ad6 = Abs(d6)     d1x2 = Ad1*2  d2x2 = Ad2*2  d3x2 = Ad3*2  d4x2 = Ad4*2  d5x2 = Ad5*2  d6x2 = Ad6*2     If(Ad1>=Ad2)And(Ad1>=Ad3)And(Ad1>=Ad4)And(Ad1>=Ad5)And(Ad1>=Ad6) Then       err1 = d2x2 - Ad1   err2 = d3x2 - Ad1   err3 = d4x2 - Ad1   err4 = d5x2 - Ad1   err5 = d6x2 - Ad1       For Cont3 = 1 To Ad1           If (err1 > 0) Then          dim2+= inc2          err1 -= d1x2      EndIf             If (err2 > 0) Then          dim3+= inc3          err2 -= d1x2      EndIf             If (err3 > 0) Then          dim4+= inc4          err3 -= d1x2      EndIf      If (err4 > 0) Then          dim5+= inc5          err4 -= d1x2      EndIf             If (err5 > 0) Then          dim6+= inc6          err5 -= d1x2      EndIf             err1 += d2x2      err2 += d3x2      err3 += d4x2      err4 += d5x2      err5 += d6x2             dim1+= inc1           Print dim1;" ";dim2;" ";dim3;" ";dim4;" ";dim5;" ";dim6          Next      EndIf     If(Ad2>Ad1)And(Ad2>=Ad3)And(Ad2>=Ad4)And(Ad2>=Ad5)And(Ad2>=Ad6) Then       err1 = d1x2 - Ad2   err2 = d3x2 - Ad2   err3 = d4x2 - Ad2   err4 = d5x2 - Ad2   err5 = d6x2 - Ad2       For Cont3 = 1 To  Ad2           If (err1 > 0) Then          dim1+= inc1          err1 -= d2x2      EndIf             If (err2 > 0) Then          dim3+= inc3          err2 -= d2x2      EndIf             If (err3 > 0) Then          dim4+= inc4          err3 -= d2x2      EndIf           If (err4 > 0) Then          dim5+= inc5          err4 -= d2x2      EndIf             If (err5 > 0) Then          dim6+= inc6          err5 -= d2x2      EndIf              err1 += d1x2      err2 += d3x2      err3 += d4x2      err4 += d5x2      err5 += d6x2             dim2+= inc2             Print dim1;" ";dim2;" ";dim3;" ";dim4;" ";dim5;" ";dim6        Next      EndIf     If(Ad3>Ad1)And(Ad3>Ad2)And(Ad3>=Ad4)And(Ad3>=Ad5)And(Ad3>=Ad6) Then       err1 = d2x2 - Ad3   err2 = d1x2 - Ad3   err3 = d4x2 - Ad3   err4 = d5x2 - Ad3   err5 = d6x2 - Ad3       For Cont3 = 1 To Ad3             If (err1 > 0) Then          dim2+= inc2          err1 -= d3x2      EndIf             If (err2 > 0) Then          dim1+= inc1          err2 -= d3x2      EndIf             If (err3 > 0) Then          dim4+= inc4          err3 -= d3x2      EndIf             If (err4 > 0) Then          dim5+= inc5          err4 -= d3x2      EndIf             If (err5 > 0) Then          dim6+= inc6          err5 -= d3x2      EndIf             err1 += d2x2      err2 += d1x2      err3 += d4x2      err4 += d5x2      err5 += d6x2             dim3+= inc3      Print dim1;" ";dim2;" ";dim3;" ";dim4;" ";dim5;" ";dim6        Next      EndIf     If(Ad4>Ad1)And(Ad4>Ad2)And(Ad4>Ad3)And(Ad4>=Ad5)And(Ad4>=Ad6) Then       err1 = d1x2 - Ad4   err2 = d2x2 - Ad4   err3 = d3x2 - Ad4   err4 = d5x2 - Ad4   err5 = d6x2 - Ad4       For Cont3 = 1 To Ad4             If (err1 > 0) Then          dim1+= inc1          err1 -= d4x2      EndIf             If (err2 > 0) Then          dim2+= inc2          err2 -= d4x2      EndIf             If (err3 > 0) Then          dim3+= inc3          err3 -= d4x2      EndIf             If (err4 > 0) Then          dim5+= inc5          err4 -= d4x2      EndIf             If (err5 > 0) Then          dim6+= inc6          err5 -= d4x2      EndIf             err1 += d1x2      err2 += d2x2      err3 += d3x2      err4 += d5x2      err5 += d6x2             dim4+= inc4               Print dim1;" ";dim2;" ";dim3;" ";dim4;" ";dim5;" ";dim6      Next      EndIf    If(Ad5>Ad1)And(Ad5>Ad2)And(Ad5>Ad3)And(Ad5>Ad4)And(Ad5>=Ad6) Then      err1 = d1x2 - Ad5   err2 = d2x2 - Ad5   err3 = d3x2 - Ad5   err4 = d4x2 - Ad5   err5 = d6x2 - Ad5       For Cont3 = 1 To Ad5             If (err1 > 0) Then          dim1+= inc1          err1 -= d5x2      EndIf             If (err2 > 0) Then          dim2+= inc2          err2 -= d5x2      EndIf             If (err3 > 0) Then          dim3+= inc3          err3 -= d5x2      EndIf             If (err4 > 0) Then          dim4+= inc4          err4 -= d5x2      EndIf             If (err5 > 0) Then          dim6+= inc6          err5 -= d5x2      EndIf             err1 += d1x2      err2 += d2x2      err3 += d3x2      err4 += d4x2      err5 += d6x2             dim5+= inc5             Print dim1;" ";dim2;" ";dim3;" ";dim4;" ";dim5;" ";dim6     Next     EndIf     If(Ad6>Ad1)And(Ad6>Ad2)And(Ad6>Ad3)And(Ad6>Ad4)And(Ad6>Ad5) Then       err1 = d1x2 - Ad6   err2 = d2x2 - Ad6   err3 = d3x2 - Ad6   err4 = d4x2 - Ad6   err5 = d5x2 - Ad6       For Cont3 = 1 To Ad6             If (err1 > 0) Then          dim1+= inc1          err1 -= d6x2      EndIf             If (err2 > 0) Then          dim2+= inc2          err2 -= d6x2      EndIf             If (err3 > 0) Then          dim3+= inc3          err3 -= d6x2      EndIf             If (err4 > 0) Then          dim4+= inc4          err4 -= d6x2      EndIf             If (err5 > 0) Then          dim5+= inc5          err5 -= d6x2      EndIf             err1 += d1x2      err2 += d2x2      err3 += d3x2      err4 += d4x2      err5 += d5x2             dim6+= inc6             Print dim1;" ";dim2;" ";dim3;" ";dim4;" ";dim5;" ";dim6     Next      EndIf     Old1=New1  Old2=New2  Old3=New3  Old4=New4  Old5=New5  Old6=New6    Wend   End