Incremental Magic

This is the post where I spill some of my magician's tricks.

Graphite does not use Vista's new InkAnalysis APIs.  In fact, it doesn't really do true shape recognition.  The truth is almost embarassingly simple:

public float ProbabilityStrokeIsShape(Stroke stroke)
{
    Point start = Utils.EndpointOfStroke(stroke, EndPoint.Start);
    Point end = Utils.EndpointOfStroke(stroke, EndPoint.End);
    Rectangle bounds = stroke.GetBoundingBox();

    float diag = Utils.Distance(new Point(0, 0), new Point(bounds.Width, bounds.Height));
    float dist = Utils.Distance(start, end);

    return (1.0f - (dist / diag));
} // (adapted from the file Utilities\ShapeRecognizer.cs)

I'm taking a stroke, and calculating one minus the ratio of the distance between the stroke's start and end, and the length of the stroke's bounding box.  That's the core of it - the el-cheapo heuristic that motivated two years of development work in my spare time.  The key idea is that a typical shape's endpoints are near their starting points.  This is true of circles, squares, triangles, and pretty much any shape that was scrawled out in a single freehand stroke.  Contrast this with a line that connects two "boxes" - lines are drawn to connect two far-flung endpoints, so the starting points and ending points pretty much define the bounding box of the stroke.  Thus, if dist/diag is small, the stroke is a shape, and if dist/diag is large, it's a line.

Then, there's connectors.  If you draw a stroke that ends near a box, the way I calculate whether your stroke terminates inside that box is as follows: I create a small rectangle surrounding the box, and I see if that small rectangle intersects with the bounding rect of my "box" stroke.  If there's any intersection, then the stroke might be a line that terminates inside my box/  Then, I take the bounding rect of the box and the bounding rect of the stroke, and I compute their intersection.  I then calculate the area of that intersection divided by the area of the bounding box of the stroke.  This gives me a rough idea of what percentage of the stroke's bounds overlap with my pre-existing box. 

I then do the exact same calculation on the other endpoint of the stroke.

Truthfully, though, when I'm checking if your newly drawn stroke is a connecting line, I don't actually look at the endpoints.  Instead, I look for a "smart" endpoint.  Look at the connecting line in the picture, above.  The "endpoint" of the stroke was one of the edges of the arrowhead, which is not the behavior I want.  So, I use the stroke's PolylineCusps property to get a collection of all the cusps.  I then look at each cusp, and I find the distance between each cusp and the starting point of the stroke.  I then try to find a cust that is as early in the stroke as possible, and yet is as far away from the starting point as possible.  If you look at the five blue numbers in the picture, you'll see that cusps 2, 3, 4, and 5 are the possible candidates.  3 is too close to the start, and 4 and 5 are too late in the order, so my heuristic settles on Cusp 2.  The net result is that arrowheads work the way you'd expect them to.

Think you can do better?  Why not download the source and give it a shot?

You can download Graphite's full source code at the new Graphite Project homepage, courtesy of my friend (and Graphite contributor) Gordon McNaughton.  The code is made available under a BSD-style license, so you can use it for any purpose you want, as long as you attribute the portions I wrote to me.

Non-developers can join in the fun, too.  The site also has an already-compiled copy of the Graphite executable to play with.

So what are you waiting for?  Go grab it!  And if you do anything interesting with the source, do leave a comment or drop me an email.

Meanwhile, I'm off to find a new side-project...

It's been over four months since I decided to release the source code for Graphite.  Today, I finally found the time to prepare it for release.  I removed some utility files that weren't in use any more, I commented-out the Search Dialog (which I never got around to finishing), I wrote a "redistribution license" file (basically the BSD license, with some attribution notes) and I replaced my various "borrowed" icons with el-cheapo, hand-drawn icons that I whipped up using Paint.NET.  The Tango icons remain, thanks to their open-source license.

Behold my artistic talents.

Now, all that I need to do is find a place to host the source files, and then I'll put up a link.