Algoritmo Bresenham en Javascript

algorithm

Question

Necesito un algoritmo rápido para calcular coordenadas para una línea entre dos puntos. Traté de encontrar una buena implementación de Bresenham en JavaScript, pero hay demasiadas publicaciones bastante confusas. En wikipedia, here la forma más rápida y simple (sin divisiones y cálculo de errores para ambas direcciones) se presenta en un pseudocódigo como este:

 function line(x0, y0, x1, y1)
   dx := abs(x1-x0)
   dy := abs(y1-y0) 
   if x0 < x1 then sx := 1 else sx := -1
   if y0 < y1 then sy := 1 else sy := -1
   err := dx-dy

   loop
     setPixel(x0,y0)
     if x0 = x1 and y0 = y1 exit loop
     e2 := 2*err
     if e2 > -dy then 
       err := err - dy
       x0 := x0 + sx 
     if e2 <  dx then 
       err := err + dx
       y0 := y0 + sy 
   end loop

¿Conoces una implementación de JavaScript Bresenham simple y robusta basada en este pseudocódigo?

EDITAR

¡Gracias a todos! Esto es con lo que vine al final:

  function calcStraightLine (startCoordinates, endCoordinates) {
    var coordinatesArray = new Array();
    // Translate coordinates
    var x1 = startCoordinates.left;
    var y1 = startCoordinates.top;
    var x2 = endCoordinates.left;
    var y2 = endCoordinates.top;
    // Define differences and error check
    var dx = Math.abs(x2 - x1);
    var dy = Math.abs(y2 - y1);
    var sx = (x1 < x2) ? 1 : -1;
    var sy = (y1 < y2) ? 1 : -1;
    var err = dx - dy;
    // Set first coordinates
    coordinatesArray.push(new Coordinates(y1, x1));
    // Main loop
    while (!((x1 == x2) && (y1 == y2))) {
      var e2 = err << 1;
      if (e2 > -dy) {
        err -= dy;
        x1 += sx;
      }
      if (e2 < dx) {
        err += dx;
        y1 += sy;
      }
      // Set coordinates
      coordinatesArray.push(new Coordinates(y1, x1));
    }
    // Return the result
    return coordinatesArray;
  }

Answer 1

Reescribiendo su pseudocódigo suministrado en JavaScript:

function line(x0, y0, x1, y1){
   var dx = Math.abs(x1-x0);
   var dy = Math.abs(y1-y0);
   var sx = (x0 < x1) ? 1 : -1;
   var sy = (y0 < y1) ? 1 : -1;
   var err = dx-dy;

   while(true){
     setPixel(x0,y0);  // Do what you need to for this

     if ((x0==x1) && (y0==y1)) break;
     var e2 = 2*err;
     if (e2 >-dy){ err -= dy; x0  += sx; }
     if (e2 < dx){ err += dx; y0  += sy; }
   }
}

Tenga en cuenta que la comparación directa de flotantes puede fallar a medida que avanza (aunque no debería al avanzar por cantidades enteras, puede ser que si el punto final no es entero), así que en lugar de comparar directamente los puntos finales, puede usar un épsilon:

if (Math.abs(x0-x1)<0.0001 && Math.abs(y0-y1)<0.0001) break;

Sin embargo, esto necesariamente lo hará más lento, así que solo haga esto si está tratando con números enteros.