Bresenhams Line Algorithm

Example source code


<!DOCTYPE html>
<html>
<head>

<script type="text/javascript">
var ctx = null, game = null;
var mouseX = -1, mouseY = -1;
var currentLine = null, point1 = [10,20], point2 = [50,20], whichPoint = 1;

window.onload = function() {
	game = document.getElementById('game');
	ctx = game.getContext('2d');
	ctx.font = "bold 10pt sans-serif";

	currentLine = bresenhamsLine(point1[0], point1[1], point2[0], point2[1]);

	game.addEventListener('mouseup', function(e) {
		// Get the position of the mouse click on the page
		mouseX = e.pageX;
		mouseY = e.pageY;

		// Find the offset of the Canvas relative to the document top, left,
		// and modify the mouse position to account for this
		var p = game;
		do
		{
			mouseX-= p.offsetLeft;
			mouseY-= p.offsetTop;

			p = p.offsetParent;
		} while(p!=null);

		// fit the real mouse position to our 10x10 grid
		mouseX = Math.floor(mouseX / 10);
		mouseY = Math.floor(mouseY / 10);

		// Which line end are we changing?  Alternate each time the mouse is clicked.
		if(whichPoint==1)
		{
			point1 = [mouseX, mouseY];
			whichPoint = 2;
		}
		else
		{
			point2 = [mouseX, mouseY];
			whichPoint = 1;
		}

		// Calculate the points on the new line
		currentLine = bresenhamsLine(point1[0], point1[1], point2[0], point2[1]);

		// Show a list of points for information
		var htm = '';
		for(p in currentLine)
		{
			htm+= '<li>' + currentLine[p][0] + ', ' + currentLine[p][1] + '</li>';
		}
		document.getElementById('pointList').innerHTML = htm;
	});

	requestAnimationFrame(drawGame);
};

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

function drawGame()
{
	if(ctx==null) { return; }

	// Clear the Canvas
	ctx.fillStyle = "#ffffff";
	ctx.fillRect(0, 0, 600, 400);

	// Draw the grid
	ctx.strokeStyle = "#999999";
	ctx.beginPath();
	for(y = 0; y < (400/10); ++y)
	{
		for(x = 0; x < (600/10); ++x)
		{
			ctx.rect((x*10), (y*10), 10, 10);
		}
	}
	ctx.closePath();
	ctx.stroke();
	
	// Draw the line
	ctx.fillStyle = "#ff9999";
	ctx.strokeStyle = "#ff3333";
	ctx.beginPath();
	for(p in currentLine)
	{
		ctx.rect(currentLine[p][0] * 10, currentLine[p][1] * 10, 10, 10);
	}
	ctx.closePath();
	ctx.fill();
	ctx.stroke();

	// Show some information...
	ctx.fillStyle = "#ff0000";
	ctx.fillText("Line from " + point1[0] + "," + point1[1] + " to " + point2[0] + "," + point2[1], 10, 20);

	// Ask for the next animation frame
	requestAnimationFrame(drawGame);
}
</script>
</head>
<body>

<p></p>

<canvas id="game" width="600" height="400"></canvas>
<ul id="pointList" style="font-family:monospace;"></ul>

</body>
</html>

Page loaded in 0.013 second(s).