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.