Voronoi Canvas Tutorial, Part III

In Part I, we wrote some code that enabled the user to draw points on a canvas (as long as they weren't too close to an existing point. In Part II we added the drawing of a horizontal line wherever the mouse is.

Next we're going to draw one more type of object which will be at the heart of Fortune's algorithm for Voronoi diagrams. Remember earlier this month in From Focus and Directrix to Bezier Curve Parameters I wanted to be able to calculate quadratic Bézier curve parameters from a focus and horizontal directrix. Now I can explain why :-)

A point (called the focus) and a line (called the directrix) are enough to define a parabola. For Fortune's algorithm, I need to, for each point and for the sweep line, draw the corresponding parabola. The canvas element doesn't have a parabola-drawing primitive. However, it does support Bézier curves.

A quadratic Bézier curve is actually a section of a parabola, so I what I wanted was a way of converting the focus and directrix into the parameters for a quadratic Bézier curve that canvas would understand. That was the motivation for the mathematics in that post.

Implementing those equations in Javascript gives us:

function drawParabola(fx, fy, dy) {
    var alpha = Math.sqrt((dy*dy)-(fy*fy));
    var p0x = fx - alpha;
    var p0y = 0;
    var p1x = fx;
    var p1y = fy + dy;
    var p2x = fx + alpha;
    var p2y = 0;

    context.strokeStyle = "rgb(100, 100, 100)";
    context.fillStyle = "rgba(0, 0, 0, 0.05)";
    context.beginPath();
    context.moveTo(p0x, p0y);
    context.quadraticCurveTo(p1x, p1y, p2x, p2y);
    context.stroke();
    context.fill();
}

This not only draws the parabola but fills the region above it (which is relevant to our purpose).

Now all we need to do is run that for each point:

function drawParabolae(dy) {
    $.each(points, function() {
        if (dy > this[1]) {
            drawParabola(this[0], this[1], dy);
        }
    });
}

and then add a call to that function to our mousemove handler:

    ...
    context.clearRect(0, 0, 600, 400);
    drawHorizontalLine(oy);
    drawParabolae(oy);
    redrawDots();
    ....

You can see the result here. I was actually surprised how snappy it is, even with a lot of points. Using the Bézier curve rather than drawing the points manually was definitely the way to go.

If you think about the fact that a parabola is the locus of points equidistance from the focus and the directrix you can start to see how Fortune's algorithm is going to work. I'll make that more explicit in the next and final post.