Bresenham algorithm in Javascript

Question

I need a fast algorithm for calculating coordinates for a line between two points. I tried to find good JavaScript Bresenham implementation, but there are too many and quite confusing publications. In wikipedia - here the fastest and most simple form (no divisions and error calculation for both directions) is presented in pseudocode like this:

 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 

Do you know of a simple and robust JavaScript Bresenham implementation based on this pseudocode?

Answer 1

Rewriting your supplied pseudo-code into 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; }    } } 

Note that comparing floats directly may fail as you step (though it shouldn't when stepping by integer amounts, it might if either end point is non-integer), so instead of directly comparing the end points you might want to use an epsilon:

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

This will necessarily slow you down, however, so only do this if you are dealing with non-integers.

Answer 2

_{Disclaimer: I extracted this answer from the OPs question. Answers should not be contained in the question itself.}

---

Answer provided by Boris Hamanov:

Thanks everybody! This is what I came with at the end:

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