Subject: Re: Intersection of CGPath and CGRect




On 28/06/2009, at 4:43 AM, Martin Hewitson wrote:

Does anyone know a good way to test if a CGPathRef intersects a CGRect at any point?


This can be a hard problem.

First, naturally discard the trivial case of the bounding rect of the path not intersecting the rect you're testing. The further approach you take will probably best be dictated by what you're trying to actually do.

If the purpose is to simply test whether a rect has hit a path, for hit-testing purposes, I've found one of the fastest general methods is to render the path into a 1 x 1 bitmap context with only an alpha channel. Using the rect for hit-testing against as a source rect, the portion of the path bounding rect that intersects that is scaled down using a suitable transform into the bitmap. If the outcome is some non- transparent alpha value, you got a hit, otherwise, you didn't. Somewhat surprisingly, I found this technique faster than any other I tried and very nice for hit-testing, as it takes i...

nto account what was actually rendered - strokes, fills, alpha and anti-aliasing. (Thanks due here to Ken Ferry who first suggested this approach to me).

If on the other hand you actually need to find the points at which the rect intersects the path, you'll need a very different approach. In this case testing a line segment against the path can be done, so you'd need to break the rect down into four line segments then test each one. It's hard to quickly find the intersection of a line segment with an arbitrary bezier curve, but somewhat easier if the curve is first flattened so you're just testing line segments against other l...

ine segments. It can still be an expensive operation though - it's well worth breaking a path down into its elements and first finding the bounding rects of each element, and trivially eliminating all those that don't intersect, then doing the more brute-force intersection test on what remains.

DrawKit ( http://apptree.net/drawkitmain.htm ) contains code for doing both kinds of testing - feel free to use what's there.

--Graham


_______________________________________________

Cocoa-dev mailing list ([email protected])

Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com

Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/maillists%40codeha.us

This email sent to [email protected]



Programming list archiving by: Enterprise Git Hosting