Sitio Web de Héctor E. Medellín Anaya

Algoritmo basado en la ecuación de la recta

Algoritmo básico

El algoritmo básico utiliza la ecuación de la recta expresada como

y = mx + b

Si la recta se dibuja desde el punto (x0, y0) hasta el punto (x1, y1), el algoritmo varia x desde x0 hasta x1 en incrementos de una unidad. El siguiente es el código en Java.

 

public void rectaSimple(int x0, int y0, int x1, int y1, Graphics g){
  int dx = x1 - x0;
  int dy = y1 - y0;

  g.drawLine( x0, y0, x0, y0);//funciona!!
  if (dx != 0){
    float m = (float) dy / (float) dx;
    float b = y0 - m*x0;
    if(x1 > x0)
      dx = 1;
    else
      dx = -1;
    while (x0 != x1) {
      x0 += dx;
      y0 = Math.round(m*x0 + b);
      g.drawLine( x0, y0, x0, y0);
   }
 }
}

El siguiente applet permite ver el proceso paso a paso. Seleccione dos puntos sobre la cuadrícula y presione el botón "Siguiente" para ejecutar cada paso. Para borrar presione el botón "Borrar". Note que para pendientes mayores de 45° o menores de -45° el algoritmo dibuja rectas discontinuas.

Algoritmo básico para cualquier pendiente

El siguiente algoritmo es una mejora sobre el anterior. el algoritmo dibuja rectas con cualquier pendiente.

    public void rectaSimple2(int x0, int y0, int x1, int y1, Grtaphics g)
    {
        int dx = x1 - x0;
        int dy = y1 - y0;

        g.drawLine( x0, y0, x0, y0);
        if (Math.abs(dx) > Math.abs(dy)) {          // pendiente < 1
            float m = (float) dy / (float) dx;
            float b = y0 - m*x0;
            if(dx<0)
                dx =  -1;
            else
                dx =  1;
            while (x0 != x1) {
                x0 += dx;
                y0 = Math.round(m*x0 + b);
                g.drawLine( x0, y0, x0, y0);
            }
        } else
        if (dy != 0) {                              // slope >= 1
            float m = (float) dx / (float) dy;      // compute slope
            float b = x0 - m*y0;
            if(dy<0)
                dy =  -1;
            else
                dy =  1;
            while (y0 != y1) {
                y0 += dy;
                x0 = Math.round(m*y0 + b);
                g.drawLine( x0, y0, x0, y0);
            }
        }
    }

 

Algoritmo de Bresenham

El algoritmo busca cual de dos píxeles es el que esta mas cerca según la trayectoria de la línea. Consideremos el proceso de conversión para líneas con pendiente positiva 0 < m < 1. Las posiciones de píxel a lo largo de la trayectoria de una línea se determinan al efectuar un muestreo de x en intervalos unitarios.

 

1. Se capturan los dos extremos de la línea y se almacena el extremo izquierdo en (x0,y0).

2. Se traza el primer punto (x0, y0).

3. Se calculan las constantes Dy, Dx, 2Dy, 2Dy-2Dx, y se obtiene el valor inicial para el parámetro de decisión como p0 = 2 Dy - Dx.

4. En cada xk a lo largo de la línea, que inicia en k = 0, se efectúa la prueba siguiente: 

si pk < 0, el siguiente punto que se debe trazar es (xk+1, yk) y pk +1 = pk + 2 Dy. De otro modo, el siguiente punto en trazarse es (xk+1, yk+1) y pk +1 = pk + 2 Dy - 2Dx.

5. Se repite el paso 4 otras Dx veces.

 

void LineBres(Graphics g, int x0, int y0, int x1, int y1){

  int x, y, dx, dy, xend, p, incE, incNE;

  dx = abs(x1 - x0);

  dy = abs(y1 - y0);

  p = 2*dy - dx;

  incE = 2*dy;

  incNE = 2*(dy-dx);

/* determinar que punto usar para empezar, cual para terminar */

  if (x0 > x1) {

    x = x1;

    y = y1;

    xend = x0;

  }

  else {

    x = x0;

    y = y0;

    xend = x1;

  }

  g.drawLine( x0, y0, x0, y0);
/* se cicla hasta llegar al extremo de la línea */

  while (x <= xend){

    g.drawLine(x,y,x,y);

    x = x + 1;

    if (p < 0)

      p = p + incE

    else {

      y = y + 1;

      p = p + incNE;

    }

    g.drawLine( x0, y0, x0, y0);
  }

}

El algoritmo de Bresenham se generaliza para líneas con una pendiente arbitraria al considerar la simetría entre los diversos octantes y cuadrantes del plano de xy. Para una línea con una pendiente m > 1, intercambiamos las funciones de las direcciones de x y y, o sea, pasamos a lo largo de y en pasos unitarios y calculamos los valores sucesivos de x que se aproximan mas a la trayectoria de la línea. Asimismo, podemos revisar el programa para trazar píxeles iniciando desde cualquier extremo.

 

El programa resultante es el siguiente:

 

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

}