Home > Articles > Mobile Application Development & Programming

  • Print
  • + Share This
This chapter is from the book

Recipe: Detecting Circles

In a direct manipulation interface like iOS, you’d imagine that most people could get by just pointing to items onscreen. And yet, circle detection remains one of the most requested gestures. Developers like having people circle items onscreen with their fingers. In the spirit of providing solutions that readers have requested, Recipe 1-10 offers a relatively simple circle detector, which is shown in Figure 1-5.

Figure 1-5

Figure 1-5. The dot and the outer ellipse show the key features of the detected circle.

In this implementation, detection uses a multistep test. A time test checks that the stroke was not lingering. A circle gesture should be quickly drawn. There’s an inflection test checking that the touch did not change directions too often. A proper circle includes four direction changes. This test allows for five. There’s a convergence test. The circle must start and end close enough together that the points are somehow related. A fair amount of leeway is needed because when you don’t provide direct visual feedback, users tend to undershoot or overshoot where they began. The pixel distance used here is generous, approximately a third of the view size.

The final test looks at movement around a central point. It adds up the arcs traveled, which should equal 360 degrees in a perfect circle. This example allows any movement that falls within 45 degrees for not-quite-finished circles and 180 degrees for circles that continue on a bit wider, allowing the finger to travel more naturally.

Upon these tests being passed, the algorithm produces a least bounding rectangle and centers that rectangle on the geometric mean of the points from the original gesture. This result is assigned to the circle instance variable. It’s not a perfect detection system (you can try to fool it when testing the sample code), but it’s robust enough to provide reasonably good circle checks for many iOS applications.

Recipe 1-10. Detecting Circles

// Retrieve center of rectangle
CGPoint GEORectGetCenter(CGRect rect)
{
    return CGPointMake(CGRectGetMidX(rect), CGRectGetMidY(rect));
}

// Build rectangle around a given center
CGRect GEORectAroundCenter(CGPoint center, float dx, float dy)
{
    return CGRectMake(center.x - dx, center.y - dy, dx * 2, dy * 2);
}

// Center one rect inside another
CGRect GEORectCenteredInRect(CGRect rect, CGRect mainRect)
{

    CGFloat dx = CGRectGetMidX(mainRect)-CGRectGetMidX(rect);
    CGFloat dy = CGRectGetMidY(mainRect)-CGRectGetMidY(rect);
    return CGRectOffset(rect, dx, dy);
}

// Return dot product of two vectors normalized
CGFloat dotproduct (CGPoint v1, CGPoint v2)
{
    CGFloat dot = (v1.x * v2.x) + (v1.y * v2.y);
    CGFloat a = ABS(sqrt(v1.x * v1.x + v1.y * v1.y));
    CGFloat b = ABS(sqrt(v2.x * v2.x + v2.y * v2.y));
    dot /= (a * b);

    return dot;
}

// Return distance between two points
CGFloat distance (CGPoint p1, CGPoint p2)
{
    CGFloat dx = p2.x - p1.x;
    CGFloat dy = p2.y - p1.y;

    return sqrt(dx*dx + dy*dy);
}

// Offset in X
CGFloat dx(CGPoint p1, CGPoint p2)
{
    return p2.x - p1.x;
}

// Offset in Y
CGFloat dy(CGPoint p1, CGPoint p2)
{
    return p2.y - p1.y;
}

// Sign of a number
NSInteger sign(CGFloat x)
{
    return (x < 0.0f) ? (-1) : 1;
}

// Return a point with respect to a given origin
CGPoint pointWithOrigin(CGPoint pt, CGPoint origin)
{

    return CGPointMake(pt.x - origin.x, pt.y - origin.y);
}

// Calculate and return least bounding rectangle
#define POINT(_INDEX_) [(NSValue *)[points     objectAtIndex:_INDEX_] CGPointValue]

CGRect boundingRect(NSArray *points)
{
    CGRect rect = CGRectZero;
    CGRect ptRect;

    for (int i = 0; i < points.count; i++)
    {
        CGPoint pt = POINT(i);
        ptRect = CGRectMake(pt.x, pt.y, 0.0f, 0.0f);
        rect = (CGRectEqualToRect(rect, CGRectZero)) ?
            ptRect : CGRectUnion(rect, ptRect);
    }

    return rect;
}

CGRect testForCircle(NSArray *points, NSDate *firstTouchDate)
{
    if (points.count < 2)
    {
        NSLog(@"Too few points (2) for circle");
        return CGRectZero;
    }

    // Test 1: duration tolerance
    float duration = [[NSDate date]
        timeIntervalSinceDate:firstTouchDate];
    NSLog(@"Transit duration: %0.2f", duration);

    float maxDuration = 2.0f;
    if (duration > maxDuration)
    {
        NSLog(@"Excessive duration");
        return CGRectZero;
    }

    // Test 2: Direction changes should be limited to near 4
    int inflections = 0;
    for (int i = 2; i < (points.count - 1); i++)
    {

        float deltx = dx(POINT(i), POINT(i-1));
        float delty = dy(POINT(i), POINT(i-1));
        float px = dx(POINT(i-1), POINT(i-2));
        float py = dy(POINT(i-1), POINT(i-2));

        if ((sign(deltx) != sign(px)) ||
            (sign(delty) != sign(py)))
            inflections++;
    }

    if (inflections > 5)
    {
        NSLog(@"Excessive inflections");
        return CGRectZero;
    }

    // Test 3: Start and end points near each other
    float tolerance = [[[UIApplication sharedApplication]
        keyWindow] bounds].size.width / 3.0f;
    if (distance(POINT(0), POINT(points.count - 1)) > tolerance)
    {
        NSLog(@"Start too far from end");
        return CGRectZero;
    }

    // Test 4: Count the distance traveled in degrees.
    CGRect circle = boundingRect(points);
    CGPoint center = GEORectGetCenter(circle);
    float distance = ABS(acos(dotproduct(
        pointWithOrigin(POINT(0), center),
        pointWithOrigin(POINT(1), center))));
    for (int i = 1; i < (points.count - 1); i++)
        distance += ABS(acos(dotproduct(
            pointWithOrigin(POINT(i), center),
            pointWithOrigin(POINT(i+1), center))));

    float transitTolerance = distance - 2 * M_PI;

    if (transitTolerance < 0.0f) // fell short of 2 PI
    {
        if (transitTolerance < - (M_PI / 4.0f)) // under 45
        {
            NSLog(@"Transit too short");
            return CGRectZero;
        }
    }


    if (transitTolerance > M_PI) // additional 180 degrees
    {
        NSLog(@"Transit too long ");
        return CGRectZero;
    }

    return circle;}
@end
  • + Share This
  • 🔖 Save To Your Account