Of Mice And Canvases

One of the best things about starting programming as a teenage APPLE ][ hacker was that the graphics subsystem was right there at your fingertips, only an HGR away.

HTML Canvas reminds me of those good old days: a simple (but slightly daft) programming language, a bunch of graphics primitives and you’re up and running. It is very easy to start grabbing mouse events and calling canvas drawing context methods, and before you know it you’ve written a sketching program. Pick up touch events instead of mouse events, and you can even run it on one of those newfangled tablet things.

source But at the end of the day scribbling all over a canvas isn’t all that useful. You could save it as a bitmap using BSAVE HELLO WORLD,$A2000,$L2000 … no wait, that was the Apple ][ talking. Yes, you can save the canvas to a bitmap, but it isn’t very elegant.

Instead, this article looks at how to reduce the actual gesture / stroke which made the line to a more convenient shorthand.

Splines & numeric.js

A spline is a smooth polynomial function which runs through a bunch of points. The maths is a bit hairy, but thankfully we don’t need to worry about it at all thanks to the excellent numeric.js, which includes a handy spline function.

A regular spline is a function of the form y = f(x). What we want is a 2D vector spline, which is a function of the form (x,y) = f(t). We can the draw the line by varying t.

In numeric.js, we construct this like:

``` {.sourceCode .javascript} var ts = [ 0, 0.2, 0.4, 0.6, 0.8, 1 ]; var xys = [ [ 0, 1 ], [ 1, 2 ], [ 2, 1 ], [ 1, 0 ], [ 0, 1 ] ];

var spline = numeric.spline(ts, xys);

We construct these lists by appending to them as the user moves the
mouse, and then 'normalizing' `ts` to the range *\[0,1\]* once the user
has stopped drawing.

And we can interate along the spline and plot a line using Canvas, like

``` {.sourceCode .javascript}
var xys = spline.at(numeric.linspace(0,1,100));
context.moveTo(xys[0][0], xys[0][1]);
for (var i=1; i<xys.length; i++) {
    context.lineTo(xys[i][0], xys[i][1]);

As well as drawing line segments on the screen, we can keep track of them in an array and then feed the array to the spline function, creating a handy vector spline which can be used to interpolate the line at any point.

source Because we’re interpolating, we can reduce the number of points we’re keeping track of and our result will still follow the user’s movements closely. In the above example, we only record a point when the pointer has travelled at least 10 pixels, giving the slightly jagged lines drawn in green. Once the stroke is finished, we go back and run a smooth spline through, shown in red.

Spline Simplification

But we can do better! A typical spline generated by the above has hundreds of control points, many of which are unnecessary.

It is easy enough to produce a simpler spline though. Start by making a new spline with only two control points: one for each end. Now look for places where it diverges from the original, and add a node whereever the divergence is worst. Repeat several times, and you’ve got a very close approximation.

source The above example has several flaws, but does fairly well on hand-drawn shapes of modest complexity. The original stroke is shown in green, then the initial spline in red and the simplified spline in blue. Blue dots show the control points for the simplified spline.

Splines can easily be limited to a set number of control points, the above example code limits them to 33 control points.


Because these control points can easily be scaled and transformed without loss of resolution, this would be a nice basis for a shared whiteboard app using Websocket or similar.

Having a few spline “handles” on a curve makes the curve editable, by clicking and dragging the handle.