Intersection of CGRect and CGPath

Question

Is there an efficient way to detect if a CGPath and a CGRect intersect?

I've thought about looping through every point inside the CGRect sort of like this:

for (CGPoint point in rect) {
   if (CGPathContainsPoint(path, nil, point, NO)) {
      intersects = YES;
      break;
}

But I wanted to know if there was a better way.

In my app there are many CGrects and one CGPath that may change its shape. I just need to check which rects are intersecting with the path, as shown in the image bellow.

Answer 1

The only completely accurate way that I've found of doing this is to loop through every point, something like this (I haven't tested this exact code):

for (NSValue *rectValue in rects) {
    CGRect rect = rectValue.CGRectValue;

    // Set the initial point values to the top left of the current rect
    CGFloat x = CGRectGetMinX(rect);
    CGFloat y = CGRectGetMinY(rect);

    BOOL intersects = NO;
    BOOL morePoints = YES;

    // Loop until there are no more points to check in this rect
    while (morePoints) {
        CGPoint point = CGPointMake(x, y);

        if (CGPathContainsPoint(path, nil, point, NO)) {
            intersects = YES;
            break;
        }

        // Adjust the x and y values to check all points
        if (x < CGRectGetMaxX(rect)) {
            x++;
        } else if (y < CGRectGetMaxY(rect)) {
            x = CGRectGetMinX(rect);
            y++;
        } else {
            morePoints = NO;
        }
    }

    if (intersects) {
        // The path intersects the current rect
    } else {
        // The path does not intersect the current rect
    }
}

But this is the most inefficient way.

You could optimize this solution by looping asynchronously:

[rects enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(NSValue * _Nonnull rectValue, NSUInteger idx, BOOL * _Nonnull stop) {
    CGRect rect = rectValue.CGRectValue;

    ...
}];

I only needed to know if the path intersected the edge of a rect so I did something similar to this:

for (NSValue *rectValue in rects) {
    CGRect rect = rectValue.CGRectValue;

    // Set the initial point values to the top left of the current rect
    CGFloat x = CGRectGetMinX(rect);
    CGFloat y = CGRectGetMinY(rect);

    BOOL intersects = NO;

    // top edge
    for (; x < CGRectGetMaxX(rect); x++) {
        CGPoint point = CGPointMake(x, y);

        if (CGPathContainsPoint(path, nil, point, NO)) {
            intersects = YES;
            break;
        }
    }

    if (intersects) {
        // The path intersects the current rect on the top edge
    }

    // right edge
    for (; y < CGRectGetMaxY(rect); y++) {
        CGPoint point = CGPointMake(x, y);

        if (CGPathContainsPoint(path, nil, point, NO)) {
            intersects = YES;
            break;
        }
    }

    if (intersects) {
        // The path intersects the current rect on the right edge
    }

    // bottom edge
    x = CGRectGetMinX(rect);
    for (; x < CGRectGetMaxX(rect); x++) {
        CGPoint point = CGPointMake(x, y);

        if (CGPathContainsPoint(path, nil, point, NO)) {
            intersects = YES;
            break;
        }
    }

    if (intersects) {
        // The path intersects the current rect on the bottom edge
    }

    // left edge
    x = CGRectGetMinX(rect);
    y = CGRectGetMinY(rect);
    for (; y < CGRectGetMaxY(rect); y++) {
        CGPoint point = CGPointMake(x, y);

        if (CGPathContainsPoint(path, nil, point, NO)) {
            intersects = YES;
            break;
        }
    }

    if (intersects) {
        // The path intersects the current rect on the left edge
    }
}

Answer 2

• Draw the path in a bitmap (white on alpha)
• then check the Rectangle part of bitmap. check if there is any white in that area which would mean overlapping

-- to make it more performant draw only the part of the bitmap that is in the rectangle.

---

I havent tried this and it wont offer real-time performance but it sounds ok to me