## 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]; var y1 = p[i]; var x2 = np; var y2 = np; // 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