Tuesday, April 28, 2009

Detecting a Circle Gesture

In Beginning iPhone Development, we have a chapter on gestures. While I think we covered the topic fairly well, I would have liked to have included a few more custom gestures in that chapter. By that point in writing, however, we were already way over on page count. Back then, we also just didn't have a good idea of what other gestures would become common.

I did experiment some with detecting circles back then, but didn't include the code in the book for two reasons. One reason is because the method is really quite long and would have taken a lot of explanation, which we didn't really have spare pages for. The second reasons is that I have a feeling there's a much easier and more efficient way to go about detecting a circle gesture. Because you need to build a certain amount of tolerance into gesture detection, I'm not sure that there is, but there's a least a decent chance there are better ways to detect a circle.

But, since a google search didn't turn up any sample code out there to do this, I decided I'd update the code and post it.

Please, if you see an easier way to do this and want to point it out, by all means, go for it.

You can download the sample project right here.

The sample app is very basic, it just traces the shape you draw and tells you either that it detected a circle, or tells you why it doesn't think the shape counts as a circle. I have not encapsulated this to be re-usable (yet, at least), but the technique is pretty self contained, requiring just three instance variables and overriding three of the touch handling methods. In the sample, the touch-handling code is in the view subclass, which made it easier to do the drawing, but the touch-handling should work in a view controller class as well.

circle.jpg


Here's a basic description of the algorithm I've used. You can download the code to see the exact implementation.


  1. In touchesBegan:withEvent: store the point where the user first tapped the screen

  2. In touchesMoved:withEvent: store off each additional touch point that comes in, storing them in order

  3. in touchesEnded:withEvent:, store the final point, then do a number of checks, doing the computationally cheap ones first so as to avoid having to do any of the more computationally expensive ones by ruling out obvious non-circles. Most of these checks are based on a variance or threshold defined in a constant:

    1. If the end point is too far away from the start point, it's not a circle.

    2. If the drawing operation took more than two seconds, it's not a circle. Okay, it might be a circle, but if it took too long, it's probably not an intentional gesture. You can remove this check if you don't want it.

    3. If there are not a certain number of stored points, it can't be a circle. This is to avoid false positives from lingering taps.

    4. Loop through the stored touches and determine the top-most, bottom-most, left-most, and right-most points, and use that to determine an approximate center and an approximate average radius.

    5. Loop through the stored points in order, making sure:

      1. Each point's distance from the center is within a certain variance of the approximate average radius.

      2. That the angle formed from the start point, to the radius, to the current point flows in a natural order. The angle should continuously increase or decrease. If it doesn't go in sequence, then it's probably a more complex shape than a circle.





As I stated earlier, there's probably an easier, more accurate way to detect a circle, but until one comes to light, this is at least functional.



17 comments:

hjaltij said...

Nice.

Just a few notes. For those of you who are not running 3.0 beta you'll have to fiddle with the build settings because older XCode doesn't recognize the 3.0 SDK.

Also there seems to be a typo, it doesn't build unless you change fabs(angle) to fabs(currentAngle) in line #174 and #183. Once fixed it works nicely.

Thanks.
- Hjalti

Jeff LaMarche said...

Whoops! Okay, fixed it, it's now set to use SDK 2.2.1, and I fixed the angle. Not sure how that last one happened, but it's fixed now, thanks Hjaltij!

Edison's Labs said...

You are awesome! I bought your book and I frequently come by your blog, and I am soooo glad I did so :)

Thank you sooooo much for posting all your sample codes! Your blog is pretty much the first source I come to when I have some questions in mind :P

Greg said...

Hi Jeff,

I did some circle testing a while back and also did it this way... however you may want to check that the radius doesn't change too much to rule out triangles, squares etc.

Personally I don't think you need to check start/end distance, just make sure the user has been through at least 360°. The gesture feels like a circle even when I end up drawing 540°, for me the 'feeling' is the most important aspect of gestures.

Keep up the great posts,
Looking forward to your next OpenGL ES post on matrixes and transforms. hint hint ;)

Greg

Jeff LaMarche said...

Greg:

I actually do check the radius. There's a variance (defaults to 25%), and all the points have to fall within that percentage of the calculated radius based on the start point.

The reasoning behind the start and end points is simply that it's an easy, computationally cheap thing to check. Depending on your purposes, you might choose not to check that. But why go through all the various math functions - acosf and atanf are somewhat costly - if they haven't made it back around to somewhere near the starting point.

I probably wouldn't require 360°, though, I'd probably do more like 345° because I find I personally don't always quite close the circle. The check in this code also has a tolerance, which is by default fairly tolerant.

Thanks for the feedback.
Jeff

Ryan Booker said...
This comment has been removed by the author.
Ryan Booker said...

Testing tangents could work, but without doing lots of faffing about trying to test tolerances against the arc you've started describing, you still have to store the entire gesture, so It's probably no different to you method.

Daro Rupiawan said...

you good blog, interesting to read for me

Edison's Labs said...

Interestingly, someone made an open source of a gesture library. Haven't had the time to check it out though; it's at http://giraffelab.com/code/GLGestureRecognizer/

Jeff LaMarche said...

Edison's Lab:

Thanks for the link - that looks awesome!

Jeff LaMarche said...

Hmm..... it's a neat algorithm, but a lot of misses and false positives in just a few minutes of testing. I think they might be trying to recognize too many gestures with the same code. My pigtails were just as likely to be picked up as arrows or deletes as they were pigtails.

Edison's Labs said...

That's a slight disappointment, but thanks for letting me know. When I'm done with finals after next week, I'll give it a try and see how it goes.

Innovation said...

Informative post
For cheapest Website developmnt & cheapest Web design visit
http://www.cheapestwebdevelopment.com/

Haille Selssie said...

This is great, how would I detect the drawing of a semi-circle?

Edwin said...

scrub m65 kamagra attorney lawyer body scrub field jacket lovegra marijuana attorney injury lawyer

JeansPilot said...

JeansPilot offers the chance to buy a large variety of men’s and women’s jeans clothing from the world famous Italian Brands.
Online jeans clothing store looks for original fashion clothing sales and clearances of worldwide known designers. We participate in fashion auctions to get the lowest possible price for Top quality Clothes, Shoes and Accessories.
Buy Jeans

Pavel said...

Mobile applications are consisted of software that runs on a mobile device as well as other hand-held devices and performs certain and custom task for the mobile user.java software company | software development company | java web development | blackberry application development | iphone application development | android application development | java outsourcing | it outsourcing services | http://www.tenaxtechnologies.com