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.