Check if drawn path/CGPath intersects itself in an iPhone game

Question

I have a path drawn in OpenGL ES. I can convert it to a CGPath if needed.

How would I check if it intersects itself (If the user created a complete loop)?

Answer 1

Note: This answer is to an earlier version of the question, where I thought the problem was to determine if the path was closed or not.

I think a path is considered closed iff the current point == the starting point.

The easiest way I know of to check this is to keep track of these two points on your own, and check for equality. You can also use CGPathGetCurrentPoint, and only track the starting point to compare with this.

Here's a roundabout way to find the starting point, if it's hard to just keep track of it directly:

• make a copy of the path
• store its current point
• call CGPathCloseSubpath
• check to see if the current point changed

If it did change, the original path was open; otherwise closed.

Answer 2

Graham Cox has some very interesting thoughts on how to detect the intersection of a CGPathRef and a CGRect, which is similar to your problem and may be educational. The underlying problem is difficult, and most practical solutions are going to be approximations.

You may also want to look at this SO article on CGPathRef intersection, which is also simliar to your problem, and some of the proposed solutions are in the same space as Graham's above.

Answer 3

Here's a solution that does pattern recognition... It focuses on any type of pattern, so a circle, a S shape, etc... Anything a user might draw with their finger...

http://giraffelab.com/code/GLGestureRecognizer/

Answer 4

This is a way to check if a path composed of a single continuous segment is self-intersecting.

I'm sure that if you wanted a faster implementation, you could get one by using some good thinking and full access to the CGPath internal data. This idea focuses on quick coding, although I suspect it will still be reasonably fast:

Basically, take two copies of the path, and fill it in two different ways. One fill uses CGContextEOFillPath, while the other uses CGContextFillPath. The results will be different iff the path is self-intersecting.

You can check if the result is different by blending the results together in difference blend mode, and testing if the resulting raw image data is all 0 (all black).

Hacky, yes. But also (relatively) easy to code.

** Addendum ** I just realized this won't work 100% of the time - for example, it won't detect a figure eight, although it will detect a pretzel.