scriptNode / Bresenham’s Line Algorithm In JavaScript

Bresenham’s Line Algorithm In JavaScript

Intermediate

Published July 6th, 2008 by Matt Hackett

Today for Script Sunday I implemented Bresenham's line algorithm in the web browser. If you've got JavaScript enabled, you should see a red square in the upper-left hand corner of the box below. Clicking anywhere within the box should send the square to that location.

Here's the source code:

/**
 * Bresenham's line algorithm function
 * by Matt Hackett [scriptnode.com]
 * @param {Object} el The element to target (accepts both strings for id's and element objects themselves)
 * @param {Number} x1 The starting X coordinate
 * @param {Number} y1 The starting Y coordinate
 * @param {Number} x2 The finishing X coordinate
 * @param {Number} y2 The finishing Y coordinate
 * @param {Object} params Additional parameters [delay, onComplete, speed]
 */
var bresenham = function(el, x1, y1, x2, y2, params) {

var
		interval,
		b,
		m,
		sx,
		y;

var init = function() {

var dx, dy, sy;

// Default parameters
		params = params || {};
		params.delay = params.delay || 10;
		params.onComplete = params.onComplete || function(){};
		params.speed = params.speed || 5;

// No point in doing anything if we're not actually moving
		if ((x1 == x2) && (y1 == y2)) {
			plot(x1, y);
			params.onComplete();
			return;
		}

el = ((typeof el === 'string') ? document.getElementById(el) : el);

// Initalize the math
		dx = x2 - x1;
		sx = (dx < 0) ? -1 : 1;
		dy = y2 - y1;
		sy = (dy < 0) ? -1 : 1;
		m = dy / dx;
		b = y1 - (m * x1);

interval = setInterval(next, params.delay);

};

/**
	 * Execute the algorithm and move the element
	*/
	var next = function() {
	
		y = Math.round((m * x1) + b);
		plot(x1, y);
		x1 += (sx * params.speed);

if (x1 >= x2) {
			clearInterval(interval);
			params.onComplete();
		}

};

/**
	 * Move the target element to the given coordinates
	 * @param float x The horizontal coordinate
	 * @param float y The vertical coordinate
	*/
	var plot = function(x, y) {
		el.style.left = x + 'px';
		el.style.top = y + 'px';
	};

init();

};

The parameters are self-explanatory except for the (optional) params object. Here's a breakdown:

delay: The interval that the setInterval call uses [default: 10]
onComplete: An optional function to call when the algorithm is finished
speed: How quickly to move the element down the line [default: 5]

I'm not sure how much use this has in the "real world" but it's typically pretty neat to see elements dancing around the page, and I always love to see classic algorithms put to good use. Enjoy!

[Download bresenhams-line-algorithm.js] (1,769 bytes)
[Download bresenhams-line-algorithm-min.js] (516 bytes; compressed)

Read other articles tagged: javascript, just-for-fun, math, script-sunday

Comments (2)

July 12th, 2008 Donald Forrester said…

Cool! This takes me back. I wrote something like this a few years back, but ended up hacking the heck out of it to try to make it remember starting positions, and then giving up and using Flash.

In your version, the more vertical the line is, the faster the box moves; also, lots of clicking eventually seems to break it. And a purely vertical click to the bottom left corner does nothing at all; which makes sense, because the original algorithm has to have x!=0, otherwise it’s dividing by 0.

The increasing/decreasing speed behavior based on slope is fascinating. There has to be some kind of use for that.
October 27th, 2008 Scarlett said…

Good post.

scriptNode

Bresenham’s Line Algorithm In JavaScript

Comments (2)

Thoughts?

Social Web

Tags

Links