How to determine if NSBezierPaths intersect in Cocoa?

Question

I'm having a hard time figuring out how to determine the intersection of two NSBezierPath closed objects in cocoa. I did some research online and couldn't find the answer so far.

Here is what I have.

I need to write some kind of a method that would return true in all of these cases.

What I was thinking so far is to flatten the rectangle by using bezierPathByFlatteningPath and then take each element (as a line segment) using elementAtIndex: associatedPoints: to go through every point in it and checking if the second object (rectangle or ellipse) contains that point (using containsPoint:).

However, I don't know how to go through all the points of a segment...

If anyone has any hint or idea that might help I would really appreciate it!

Answer 1

If you have 2 bezier path rectangles and know each of their frames, then you can use NSIntersectsRect():

NSRect rect1 = NSMakeRect(20.0, 150.0, 300.0, 100.0);
NSRect rect2 = NSMakeRect(100.0, 100.0, 100.0, 200.0);

[[NSColor redColor] set];

[NSBezierPath strokeRect:rect1];
[NSBezierPath strokeRect:rect2];

BOOL intersects = NSIntersectsRect(rect1, rect2);

NSLog(@"intersects == %@", (intersects ? @"YES" : @"NO"));

Produces:

In this case, it would log intersects == YES.

Answer 2

Here is a quite fast and clean solution. It also works to test multiple paths vs one, which is fine, isn't it?

It works on CGBezier ( iOS and MacOS compatible )

• 1 - Create the necessaries contexts

Create a 16 bits, one component (no alpha) graphics port with the same size than the view.

• Don't recreate this context at each test, it's time consuming. Recreate it only when view is resized.
• Let's call this context computeContext

Create a 16 bits, one component (no alpha) graphics port of 1 pixel width and height.

• Let's call this context testContext

• 2 - When you need to test the paths intersection:

We work in computeContext for the following operations:

• Clear the context ( It will be full black )
• Clip the context to the path you want to test
• Fill all the paths versus which you want to test with white color
• ( From now, you don't need to be in the computeContext. ) Get the image and draw it in the testContext with something like :

CGImageRef clippedPathsImage = CGBitmapContextCreateImage(computeContext);
CGRect     onePixSquare = CGRectMake(0,0,1,1);
CGContextDrawImage(testContext, onePixSquare, clippedPathsImage);

( Don't worry, image creation function is fast. It does not malloc any memory since the bits are allocated in the bitmapContext )

We're done!

long*   data = CGBitmapContextGetData(testContext);  
BOOL    intersects = (*data!=0);

• This is much faster than doing some composition drawing with alpha values

• This is much faster than testing all the pixels in a big image The image scaling is made internally, hardware accelerated. So it is not a big deal.

If however you want to speed up even more and can afford less precision, you can create a smaller computeContext, for exemple 25% of view size, and render all the paths with a scale transform matrix.

The transfer in the 1 pixel context will then be faster, but you are not sure to detect intersections smaller than 4 pixels in size ( with a 25% scale, Logic ).

Don't use 8 bits gray. I don't think it speeds the process up, and you lose a lot of precision when reducing to 1 pixel. Enough to fail.

Don't forget that the first test to do before using the hard way is to test bounding boxes intersection !

That's all

Opened a GitHub with the library ;) https://github.com/moosefactory

Hope this helps, cheers ! ;)

---

Here is the code to create a 16bits gray context. It can be more concise, but I declare variables to make it clear. You don't need any bitmapInfo ( last parameter ), since there is no alphaValue, and we don't use float format.

-(CGContextRef)createComputeContext
{
    size_t  w = (size_t)self.bounds.size.width;
    size_t  h = (size_t)self.bounds.size.height;
    size_t  nComps = 1;
    size_t  bits   = 16;
    size_t  bitsPerPix  = bits*nComps;
    size_t  bytesPerRow = bitsPerPix*w;    
    CGColorSpaceRef  cs = CGColorSpaceCreateDeviceGray();

    CGContextRef bmContext = CGBitmapContextCreate(NULL, w, h, bits, bytesPerRow, cs, 0);

    return bmContext;
}