// Draw a line using Bresenham's algorithm.
// By David Turover, 6 September 2008.
// The performance advantages of an integer-based algorithm are probably lost
// by doing this in Javascript, but I just wanted to see if it could be done.


// This requires point.js be loaded beforehand. 


function bres_debug( strdata ){		// Print notices for debugging.
	var node = document.getElementById("printTarget");
	if(node){
		node.innerHTML += "<p>" + strdata + "</p>";
	}
}


// Use Bresenham's algorithm to draw a line.
// From Hearn Baker's _Computer Graphics_ pages 95-99.
// Modified by dturover to support any angle, not just 0 to pi/4. 
function bresenham(pt1, pt2){
	var originX = pt1.x;
	var originY = pt1.y;
	var targetX = pt2.x;
	var targetY = pt2.y;

	// Require origin be to the left of target (or y-aligned with it). 
	if(originX > targetX){ return bresenham(pt2, pt1); }

	var dx = targetX - originX;
	var dy = targetY - originY;

	var twicedx = 2 * dx; // Cached for efficiency
	var twicedy = 2 * dy; // Cached for efficiency

	// Support negative slopes.
	var yDir = 1;
	if(dy < 0){
		yDir = -1;
		twicedy = -twicedy; 	// Use the absolute value. 
	}

	var a = new Array();	// Array of points to return to caller. 
	var x = originX; // Current position for line-drawing algorithm.
	var y = originY;
	var p = twicedy - dx;	// Value for choosing whether to change y or not.

	while(x <= targetX){
		a.push(new point(x,y)); 
		if(p > 0 && y != targetY) {// '&&' Prevents inf loop on dx=0.
			y += yDir; 	// Not y++. We want negative slopes.
			p -= twicedx;
		} else {
			p += twicedy;
			x++;
		}
	}

	// bres_debug("Firing from [" + originX + "," + originY + "] to [" + targetX + "," + targetY + "], ended on [" + (x-1) + "," + y + "]");
	return a; 
}