25 October, 2009

Hit testing for arbitrary paths on the iPhone

I'm doing something cool for the iPhone. Can't tell yet, but I'll be posting hacks and interesting code as I go.
For the first one all credit goes to Graham Cox of DrawKit (an awesome open-source project). I just ported his idea to the iPhone and tweaked it to match my problem.

I've been working on an algorithm for detecting a finger touch over a random, complex path. It was quickly clear that it's not a trivial problem and my requirement for the path to have a stroke (border) of significant width made it even harder.
So I was searching and reading forums and documentation and even had some ideas and rudimentary code when suddenly I found this post. Such a beautiful idea that I had to try it. And once I got the code to work I felt I should share it with everyone.

I represent the finger as a rectangle around the touch point, so my problem is reduced to checking for intersection between a rectangle and a path. Here is the algorithm:


  1. Filter all trivial cases to avoid unnecessary calculations.

  2. Get the intersection between the bounding box of the path and the rectangle (of the finger).

  3. If that's a non-zero rectangle, smaller than the bounding box (else the path and the rect intersect), draw the intersection into a 1x1 off-screen, alpha-only, bitmap buffer

  4. If the resulting pixel is non-zero the two intersect, i.e. the intersection contains at least one non-transparent pixel from the path.

  5. Integrate into your code, test and feel totally awesome ;)


And bellow is the code (the implementation part only, assuming the class name is GraphicsUtil!):



//check if the rect contains any non transparent part of the path
//as it is drawn on the screen
+ (BOOL)rect: (CGRect)rect
intersectsPath: (CGPathRef)path
strokeWidth: (CGFloat)strokeWidth
strokeColor: (UIColor *)strokeColor
fillColor: (UIColor *)fillColor;
{
CGRect bbox = [GraphicsUtil boundingBoxForPath: path
withStrokeWidth: strokeWidth
strokeColor: strokeColor
fillColor: fillColor];
CGRect intersection = CGRectIntersection(rect, bbox);
BOOL result = NO;

if (intersection.size.width > 0.0f && intersection.size.height > 0.0f)
{
// if the rect contains the path then we are sorted
if( CGRectEqualToRect(intersection, bbox))
{
return YES;
}
else
{
//Take the intersection rect and find out if it contains at least one
// non 0 pixel.
//Scale the pixels from the intersection into an 1x1
//image context

//cache these so they are created once and then cleared
static CGContextRef bitmap1x1 = NULL;
static uint8_t pixels[8]; //some unused padding
static CGRect rect1x1 = {{0, 0},{1, 1}};

if( bitmap1x1 == NULL )
{
bitmap1x1 = CGBitmapContextCreate(pixels, 1, 1, 8, 1, NULL,
kCGImageAlphaOnly);
CGContextSetInterpolationQuality(bitmap1x1, kCGInterpolationNone);
CGContextSetShouldAntialias(bitmap1x1, NO);
CGContextSetShouldSmoothFonts(bitmap1x1, NO);
}

pixels[0] = 0;

[self drawPath: path
fromRect: intersection
inRect: rect1x1
inContext: bitmap1x1
strokeWidth: strokeWidth
strokeColor: strokeColor
fillColor: fillColor];

result = ( pixels[0] != 0 );
}
}

return result;
}

//Draws a rectangular part of the path into another rectangular
//region scaling it to fit.
+ (void)drawPath: (CGPathRef)path
fromRect:(CGRect)srcRect
inRect: (CGRect)destRect
inContext: (CGContextRef)context
strokeWidth: (CGFloat)strokeWidth
strokeColor: (UIColor *)strokeColor
fillColor: (UIColor *)fillColor;
{
NSAssert( destRect.size.width > 0.0 && destRect.size.height > 0.0, @"destination rect has zero size");
CGRect bbox = [GraphicsUtil boundingBoxForPath: path
withStrokeWidth: strokeWidth
strokeColor: strokeColor
fillColor: fillColor];
if (CGRectEqualToRect(srcRect, CGRectZero))
{
srcRect = bbox;
}
else
{
srcRect = CGRectIntersection(srcRect, bbox);
}

if( CGRectEqualToRect(srcRect, CGRectZero))
{
return;
}

CGContextSaveGState(context);
CGContextClipToRect(context, destRect);

CGContextConcatCTM(context, [GraphicsUtil mapFrom: srcRect to: destRect]);
CGContextAddPath(context, path);

CGContextSetLineWidth(context, strokeWidth);

CGPathDrawingMode mode;
if(strokeColor)
{
CGContextSetStrokeColorWithColor(context, strokeColor.CGColor);
mode= kCGPathStroke;
}

if(fillColor)
{
CGContextSetFillColorWithColor(context, fillColor.CGColor);
if(strokeColor)
{
mode = kCGPathFillStroke;
}
else
{
mode = kCGPathFill;
}
}

CGContextDrawPath(context, mode);
CGContextRestoreGState(context);
}

//The strokes on the iPhone are drawn so that half of the stroke is on
//one side of the path edge and half is on the other
//So the actual bounding box is bigger than the one returned by the API
//Or I may be smoking something and there could be an official//better
//way to calcualate this.
//Worked for me!!!
+ (CGRect)boundingBoxForPath: (CGPathRef)path
withStrokeWidth: (CGFloat)strokeWidth
strokeColor: (UIColor *)strokeColor
fillColor: (UIColor *)fillColor
{
BOOL noStroke = (strokeColor == nil ||
strokeWidth <= 0 ||
[strokeColor isEqual:[UIColor clearColor]]);
if((fillColor == nil || [fillColor isEqual:[UIColor clearColor]]) &&
noStroke)
{
return CGRectZero;
}
else
{
CGRect bbox = CGPathGetBoundingBox(path);
if(!noStroke)
{
CGFloat border = ceil(strokeWidth/2.0f);
bbox = CGRectMake(bbox.origin.x - border,
bbox.origin.y - border,
bbox.size.width + 2*border,
bbox.size.height + 2*border);
}
return bbox;
}
}

//Create an affine transform that transitions the source rectangle
//into the destination one.
+ (CGAffineTransform) mapFrom:(CGRect)src to:(CGRect)dst
{
CGFloat a = (dst.size.width/src.size.width);
CGFloat b = 0.0;
CGFloat tX = dst.origin.x - a*src.origin.x;
CGFloat c = 0.0;
CGFloat d = (dst.size.height/src.size.height);
CGFloat tY = dst.origin.y - d*src.origin.y;
return CGAffineTransformMake(a, b, c, d, tX, tY);
}

No comments: