Bresenhams Line Algorithm

Raster line

Bresenhams Line Algorithm is a fantastic way to draw a line between 2 points. Unlike the line algorithm in our other pixel line article, this method does not include every point that would be touched by a line between the start and end points, but just those that are crossed by a reasonable amount.

This method is similar or the same as that which would be used by painting software to draw rasterized lines.

View example

This method takes four arguments: x1, y1, which is the starting point of the line, and x2, y2, the ending point of the line. The return value is an array containing the list of points used to create the line between the provided points.


function bresenhamsLine(x1, y1, x2, y2)
{
	line = new Array();
	
	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 error = dx - dy;
	
	var x = x1, y = y1;
	
	while(1)
	{
		line.push([x, y]);
		
		if(x==x2 && y==y2) { break; }
		
		var e2 = 2 * error;
		
		if(e2 >-dy) { error-= dy; x+= sx; }
		if(e2 < dx) { error+= dx; y+= sy; }
	}
	
	return line;
}

Page loaded in 0.01 second(s).