Voronoi Canvas Tutorial, Part I
Earlier in the month, I introduced Voronoi Diagrams with some Python code for brute-force calculation. There are a number of better algorithms and I'd like to talk about one discovered by Steven Fortune. Rather than implement it in Python, though, I wanted to use it as an opportunity to teach myself how to use the canvas element to build an interactive demonstration of Fortune's approach.
So this is part one (of three four) showing how to use the canvas element (in conjunction with jQuery) to demonstrate Fortune's algorithm for calculating Voronoi diagrams. In this part, we'll just do enough to let the user pick the points.
The canvas element was originally developed by Apple but is now implemented not only in Safari but also Firefox and Opera). It is part of the HTML5 effort.
So first of all, here's our HTML:
<canvas id="canvas" width="600" height="400"
style="border: 1px solid #999;"></canvas>
<div><button id="clear-button">clear</button></div>
Next, we'll declare an array called points which will store the (x, y) coordinates of our points.
var points = [];
We don't want the user to draw points too close to one another, so anyClose is a utility function that tells us if a given (x, y) is too close to an existing point. It in turn uses a utility function distance which calculates the distance between any two points. Note that anyClose uses jQuery's each to iterate over the points.
/* calculate distance between (x1, y1) and (x2, y2) */
function distance(x1, y1, x2, y2) {
return Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
/* are there any points close to (x, y) ? */
function anyClose(x, y) {
var result = false;
$.each(points, function() {
if (distance(x, y, this[0], this[1]) < 20) {
result = true;
return false; // break out of each
}
});
return result;
}
Now we get to the actual canvas bits. Operations are performed on a drawing context which we can get in jQuery with:
var context = $('#canvas')[0].getContext('2d');
Here is a function for drawing a black dot at (x, y):
function drawDot(x, y) {
context.fillStyle = "rgb(0,0,0)";
context.beginPath();
context.arc(x, y, 2, 0, Math.PI*2, true);
context.fill();
}
All that remains now is to hook up our event handlers. First, the click event on #canvas:
$('#canvas').click(function(e) {
/* e will give us absolute x, y so we need to
calculate relative to canvas position */
var pos = $('#canvas').position();
var ox = e.pageX - pos.left;
var oy = e.pageY - pos.top;
/* only draw dot and add to points list if
no other points are close */
if (!anyClose(ox, oy)) {
drawDot(ox, oy);
points.push([ox, oy]);
}
return false;
});
And second, the clear button:
$('#clear-button').click(function() {
points = [];
context.clearRect(0, 0, 600, 400);
});
You can see the result here.
prev « mathematics » next
prev « web » next
prev « javascript » next
prev « jquery » next
Comments (3)
James Tauber on Nov. 27, 2008:
Simon, you must be subscribed to the wrong feed address. The feed URL should NOT have the www in it.
That said, the www address should redirect -- it certainly used to. I'm going to fix that up now.
James Tauber on Nov. 27, 2008:
Okay www.jtauber.com now redirects to jtauber.com like it used to. Not sure what happened.
Last Modified: Nov. 27, 2008
Author: James Tauber
Simon on Nov. 27, 2008:
When following links in you blog from a feed reader (Google reader in this case) I am sent to a page saying site is coming soon. The links in the feed reader go to www.jtauber.com while the links on your website go to jtauber.com