“MooseGesture” – Python Mouse Gestures Module

A “segment” has a starting point, and then continues to include subsequent points until it meets a minimum segment length (and no longer). (The minimum segment length is adjustable. A smaller minimum segment length lets strokes be shorter but increases the odds of misidentified strokes.) So say the gesture has 10 points (which we’ll call 0 to 9) altogether. The first segment starts at point 0 and goes on for some number of points until it is at least the minimum segment length. The second segment starts at point 1. This means that the second segment overlaps the first for a bit. (This depends on the lengths of the segments, which depends on how close together/far apart the points are.)

The last segment will start at the latest point that we can get a segment that meets the minimum segment length. So if the distance between points 7 to 8 to 9 is less than the minimum segment length, there won’t be a segment that starts at point 7 (or, logically, at point 8).

Note that the length of a segment is the sum of lengths of its point pairs, not the distance between the first and last points in the segment. For example, the distance between points 0 and 1, 1 and 2, and 2 and 3. It would not be the distance between points 0 and 3.

Here’s an animated gif that shows a gesture with 8 points (0 to 7), with the segments highlighted in turn:

The Algorithm:

  1. Split up the gesture’s points into segments that meet the minimum segment length.
  2. For each segment: Calculate the slope of each point pair and categorize them into one of the eight directions based which “zone” the slope falls in.
  3. If all of the point pairs in the segment agree on the direction, then this segment is considered consistent and the direction is added to the list of identified strokes. See the animated gif below for an example of consistent/inconsistent segments, the R stands for “right direction point pair” and the UR for “upright direction point pair”.
  4. The list of identified strokes is returned as the identified gesture.

(There is one exception to adding a consistent segment: if the previously identified stroke is in the same direction as this one, then we don’t add the direction. This prevents multiple sequential strokes in the same direction, i.e. up-up-up-left-left is just considering up-left.)

This algorithm lets us ignore tiny deviations because they will create an inconsistent segment (i.e. a segment wit pair points going in different directions. So we drop that segment from being considered an identified stroke. But there is bound to be some segments before and after it that are consistent.

One limitation is that MooseGesture can only identify direction. It can’t identify lengths or specific shapes. So these two paths are both interpreted as the same gesture by MooseGesture (upright, downright, left):

This is just an algorithm that I came up with literally over a weekend. Even for gestures with an absurd number of points in them, it seems to run in a couple milliseconds. It can probably be improved, but will work just fine for most Python games. I’ll be converting the module to JavaScript in the future. Email me any questions you might have. Enjoy!

Page 2 of 2 | Previous page

2 comments on this post.
  1. Daniel Pope:

    There’s a more complicated algorithm I used once, based on Hidden Markov Models, that would distinguish between the latter cases. Basically each model encodes the probability that you’d receive a given stroke direction assuming the user is drawing some part of a symbol.

    As you receive input you iterate the model and it chucks out a probability – how likely it was that this particular model described what the user was drawing.

    The latter two gestures would be differentiated by the fact that in the second gesture the state transition from the second stroke to the third stroke is more probable so more likely to be seen sooner.

  2. Al Sweigart:

    Hey Daniel. One of the benefits of MooseGesture is that it simply returns what gesture the user drew as a freeform gesture. It doesn’t have to match a predefined pattern. (Though there is a function provided to do a Levenshtein distance calculation to find the closest matching gesture from a list of predefined gestures.)

    But yes, on the downside MooseGesture can’t do some of the things that the Markov model algorithms can do.

Leave a comment