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?

I was looking for the same exact thing, and recently stumbled on this interactive implementation of the [bresenham's line algorithm in javascript](https://web.archive.org/web/20191104140129/http://www.javascriptteacher.com/bresenham-line-drawing-algorithm.html) -- move mouse around to also move the line. Kind of neat to see it in action, rather than just algorithm source code. Neat explanation too. — InfiniteStack, Dec 08 '18 at 06:44

score 66 · Accepted Answer · edited Apr 13 '19 at 14:33

66

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.

edited Apr 13 '19 at 14:33

Neuron

5,141
5
38
59

answered Jan 12 '11 at 18:12

Phrogz

296,393
112
651
745

4

Brasenham is only supposed to work on integers anyways. It is used to calculate which pixels to color to draw a line. – Null Set Jan 12 '11 at 18:29
1

I like this one, but I think it can be further improved by removing the break in favor of real loop condition and doing the multiplication by two with shift. – Boris Hamanov Jan 13 '11 at 20:23
3

The bit shift might be a hair faster, but I doubt that changing the loop would affect performance. You could easily change it to `while(x0!=x1 || y0!=y1)` and remove the `if/break`, but you would need to pull out another call to `setPixel` before/after the loop to handle the end point of the line correctly and the edge case. – Phrogz Jan 13 '11 at 21:20
Quite right, I also noticed that about the edge conditions. Thanks! – Boris Hamanov Jan 13 '11 at 22:45

Neuron · Answer 2 · 2021-01-03T11:01:53.510

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

Bresenham algorithm in Javascript

2 Answers2

Answer provided by Boris Hamanov:

Linked

Related