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