Simple circular gesture detection

Question

I'm looking at a simple, programmatic way of detecting whether or not the user has drawn a circular shape. I'm working in C, but am happy to work from pseudo-code. A bit of Googling brings up a number of (hopefully) overly-complex methods.

I'm tracking the mouse coordinates as floats, and have created an array of vectors to track the mouse movement over time. Essentially I'm looking to detect when a circle has been drawn and then disgard all movement data not associated with that circle.

I have a basic idea of how this might be accomplished:

Track all movements using a polling function. Each time the function is polled the current mouse position is stored. Here, we loop through the historic position data and do a rough 'snap to position' to compare the two locations. If the new location is within a close enough distance to an old position, we remove all historic data before the old location.

While this works in theory, it's a mess in practice. Does anyone have any suggestions? Bonus points if the method suggested can detect whether it's been drawn clockwise or counter-clockwise.

Answer 1

Based on your tracking/polling function, which pushes float pairs on a stack. This must be done on a regular timing interval.

1. Do a threshold-based search for two equal entries in the list. Now you have two indexes in your stack; the first and the second equal entries. Consider this as a line.
2. Get the absolute difference in indices. Then divide by two and get the coordinates of this point. (Center of the line.)
3. You've got two points: thus you can get the radius of the circle, by getting the distance between the two points divided by two.

4. Divide the number of step 2 by 2, now you've got the quarters.

   If the line at step 1 is vertical and the first point of the line is at the top: If the first quarter is left of the center-point, the circle was drawn counter-clockwise. If the first quarter is right of the center-point, the circle was drawn clockwise. If the first point of the line is at the bottom, reverse (i.e. ccw => cw and cw => ccw)

   If the line at step 1 is horizontal and the first point of the list is at the left: If the first quarter is above the center-point, the circle was drawn counter-clockwise. If the first quarter is below of the center-point, the circle was drawn clockwise. If the first point of the line is at the right, reverse.

5. Check if it was a circle: iterate over all pairs of coordinates and calculate the distance to the center-point. Tweak the threshold of allowed distances from the calculated distance and the actual distance to the center-point.

In step 2 and 4 you can tweak this algorithm further by taking the average of several indices if the timing interval is very low (fast polling). For instance: there are 30 pairs in the array, then you average pairs at 0, 1 and 28, 29 to get the upper point. Do the same for all other points.

I hope this is easy enough.

Answer 2

You are definitely on the right track IMHO. Basically you need to compare each mouse point with the previous mouse point and calculate the angle between them (as envisioned on a unit circle where the first point is at the origin). For this you can use the formula:

double angle = atan2(y2 - y1, x2 - x1) * 180 / PI;

if (angle < 0)
    angle += 360;

What you end up with is that for clockwise movement, the angle will cycle in a positive direction, whereas for counterclockwise movement the angle will cycle in a negative direction. You can figure out if the current angle is greater or less than the previous one with the following logic:

if (angle2 > 270 && angle1 < 90)
{
    angle1 += 360
}
else if (angle1 > 270 && angle2 < 90)
{
    angle2 += 360
}

bool isPositive = (angle2-angle1 > 0);

If you get a certain number of vectors all with angles that are increasing (isPositive is true, let's say, 10 times), you can assume a clockwise circle is being drawn; if the tendency is negative (isPositive is false 10 times) it's a counterclockwise circle. :)

Answer 3

Here's an algorithm to see if an array of points fits a circle:

1. calculate the centroid of the points (average of all the x and y coordinates)

2. calculate the distance of all points to the centroid

3. find the maximum and minimum distances

4. if maximum - minimum < tolerance, circular section detected

NB This will detect a section of a circle as well so you will need to determine that enough of an angle is swept through for it to be a full circle.

To do this:

1. calculate centroid as above
2. calculate angle between centroid and each point (use atan2 function)
3. map angles to segments (I find 12 30 degree segments works for me; just divide angle by 30 and round down to integer - assuming you are working in degrees here)

4. if all segments contain at least 1 point, then it is a circle (i.e. your mapped segments array contains all values between 0 and 11)

5. bonus: increasing angle is anti-clockwise; decreasing is clockwise