Bresenham's line algorithm 09.16.2018

For the second time in a year I find myself writing an application that requires drawing a polygon on a canvas by hand and then determining if a given point falls inside the polygon. The drawing part is easy, but getting every point on the line doesn't always work out. I can create an array and add each set of coordinates as I draw sections of the line, but there are always gaps (presumably due to the time that it takes to recognize mouse movement?). For example, I may end up with a set of coordinates similar to:

...
[121,18],
[121,20],
[123,24]
...

Both times I've looked at this I had a bit of trouble finding a good way to 'fill in the gaps', and both times I eventually found Bresenham's line algorithm. Since I'd completely forgotten it after the first application and had to rediscover it for the second, I thought it may make sense to drop it in here for future reference.

One js implementation that I found looks like this...

    function plot(x0, y0, x1, y1) {
        let dots = [];
        let dx = Math.abs(x1 - x0);
        let dy = Math.abs(y1 - y0);
        let sx = (x0 < x1) ? 1 : -1;
        let sy = (y0 < y1) ? 1 : -1;
        let err = dx - dy;

        dots.push({ x: x0, y: y0 });

        while(!((x0 == x1) && (y0 == y1))) {
            let e2 = err << 1;

            if (e2 > -dy) {
                err -= dy;
                x0 += sx;
            }

            if (e2 < dx) {
                err += dx;
                y0 += sy;
            }

            dots.push({ x: x0, y: y0 });
        }

        return dots;
    }
( See here or here. )

My quick proof of concept application looks like this...

var p = points,
    op = [];
for(var i = 0; i < p.length-1; i++) {
    var np = p[i+1];
    // Translate coordinates
    var x1 = p[i][0];
    var y1 = p[i][1];
    var x2 = np[0];
    var y2 = np[1];
    // 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
    op.push(p[i]);
    // 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
      op.push([x1,y1]);
    }                        
}

Where points is an array of points that was created while drawing the line and op is my new 'filled in' array.

I hope this helps someone, or at the very least makes it easier for me the next time I'm in this situation.

Cheers