Objective-C check if subviews of rotated UIViews intersect?

Question

I don't know where to start with this one. Obviously CGRectIntersectsRect will not work in this case, and you'll see why.

I have a subclass of UIView that has a UIImageView inside it that is placed in the exact center of the UIView:

I then rotate the custom UIView to maintain the frame of the inner UIImageView while still being able to perform a CGAffineRotation. The resulting frame looks something like this:

I need to prevent users from making these UIImageViews intersect, but I have no idea how to check intersection between the two UIImageViews, since not only do their frames not apply to the parent UIView, but also, they are rotated without it affecting their frames.

The only results from my attempts have been unsuccessful.

Any ideas?

Answer 1

The following algorithm can be used to check if two (rotated or otherwise transformed) views overlap:

• Use [view convertPoint:point toView:nil] to convert the 4 boundary points of both views to a common coordinate system (the window coordinates).
• The converted points form two convex quadrilaterals.
• Use the SAT (Separating Axis Theorem) to check if the quadrilaterals intersect.

This: http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf is another description of the algorithm containing pseudo-code, more can be found by googling for "Separating Axis Theorem".

---

Update: I have tried to create a Objective-C method for the "Separating Axis Theorem", and this is what I got. Up to now, I did only a few tests, so I hope that there are not too many errors.

- (BOOL)convexPolygon:(CGPoint *)poly1 count:(int)count1 intersectsWith:(CGPoint *)poly2 count:(int)count2;

tests if 2 convex polygons intersect. Both polygons are given as a CGPoint array of the vertices.

- (BOOL)view:(UIView *)view1 intersectsWith:(UIView *)view2

tests (as described above) if two arbitrary views intersect.

Implementation:

- (void)projectionOfPolygon:(CGPoint *)poly count:(int)count onto:(CGPoint)perp min:(CGFloat *)minp max:(CGFloat *)maxp
{
    CGFloat minproj = MAXFLOAT;
    CGFloat maxproj = -MAXFLOAT;
    for (int j = 0; j < count; j++) {
        CGFloat proj = poly[j].x * perp.x + poly[j].y * perp.y;
        if (proj > maxproj)
            maxproj = proj;
        if (proj < minproj)
            minproj = proj;
    }
    *minp = minproj;
    *maxp = maxproj;
}

-(BOOL)convexPolygon:(CGPoint *)poly1 count:(int)count1 intersectsWith:(CGPoint *)poly2 count:(int)count2
{
    for (int i = 0; i < count1; i++) {
        // Perpendicular vector for one edge of poly1:
        CGPoint p1 = poly1[i];
        CGPoint p2 = poly1[(i+1) % count1];
        CGPoint perp = CGPointMake(- (p2.y - p1.y), p2.x - p1.x);

        // Projection intervals of poly1, poly2 onto perpendicular vector:
        CGFloat minp1, maxp1, minp2, maxp2;
        [self projectionOfPolygon:poly1 count:count1 onto:perp min:&minp1 max:&maxp1];
        [self projectionOfPolygon:poly2 count:count1 onto:perp min:&minp2 max:&maxp2];

        // If projections do not overlap then we have a "separating axis"
        // which means that the polygons do not intersect:
        if (maxp1 < minp2 || maxp2 < minp1)
            return NO;
    }

    // And now the other way around with edges from poly2:
    for (int i = 0; i < count2; i++) {
        CGPoint p1 = poly2[i];
        CGPoint p2 = poly2[(i+1) % count2];
        CGPoint perp = CGPointMake(- (p2.y - p1.y), p2.x - p1.x);

        CGFloat minp1, maxp1, minp2, maxp2;
        [self projectionOfPolygon:poly1 count:count1 onto:perp min:&minp1 max:&maxp1];
        [self projectionOfPolygon:poly2 count:count1 onto:perp min:&minp2 max:&maxp2];

        if (maxp1 < minp2 || maxp2 < minp1)
            return NO;
    }

    // No separating axis found, then the polygons must intersect:
    return YES;
}

- (BOOL)view:(UIView *)view1 intersectsWith:(UIView *)view2
{
    CGPoint poly1[4];
    CGRect bounds1 = view1.bounds;
    poly1[0] = [view1 convertPoint:bounds1.origin toView:nil];
    poly1[1] = [view1 convertPoint:CGPointMake(bounds1.origin.x + bounds1.size.width, bounds1.origin.y) toView:nil];
    poly1[2] = [view1 convertPoint:CGPointMake(bounds1.origin.x + bounds1.size.width, bounds1.origin.y + bounds1.size.height) toView:nil];
    poly1[3] = [view1 convertPoint:CGPointMake(bounds1.origin.x, bounds1.origin.y + bounds1.size.height) toView:nil];

    CGPoint poly2[4];
    CGRect bounds2 = view2.bounds;
    poly2[0] = [view2 convertPoint:bounds2.origin toView:nil];
    poly2[1] = [view2 convertPoint:CGPointMake(bounds2.origin.x + bounds2.size.width, bounds2.origin.y) toView:nil];
    poly2[2] = [view2 convertPoint:CGPointMake(bounds2.origin.x + bounds2.size.width, bounds2.origin.y + bounds2.size.height) toView:nil];
    poly2[3] = [view2 convertPoint:CGPointMake(bounds2.origin.x, bounds2.origin.y + bounds2.size.height) toView:nil];

    return [self convexPolygon:poly1 count:4 intersectsWith:poly2 count:4];
}

---

Swift version. (Added this behaviour to UIView via an extension)

extension UIView {

func projection(of polygon: [CGPoint], perpendicularVector: CGPoint) -> (CGFloat, CGFloat) {
    var minproj = CGFloat.greatestFiniteMagnitude
    var maxproj = -CGFloat.greatestFiniteMagnitude
    
    for j in 0..<polygon.count {
        let proj = polygon[j].x * perpendicularVector.x + polygon[j].y * perpendicularVector.y
        if proj > maxproj {
            maxproj = proj
        }
        
        if proj < minproj {
            minproj = proj
        }
    }
    
    return (minproj, maxproj)
}

func convex(polygon: [CGPoint], intersectsWith polygon2: [CGPoint]) -> Bool {
    //
    let count1 = polygon.count
    for i in 0..<count1 {
        let p1 = polygon[i]
        let p2 = polygon[(i+1) % count1]
        let perpendicularVector = CGPoint(x: -(p2.y - p1.y), y: p2.x - p1.x)
        
        let m1 = projection(of: polygon, perpendicularVector: perpendicularVector)
        let minp1 = m1.0
        let maxp1 = m1.1

        let m2 = projection(of: polygon2, perpendicularVector: perpendicularVector)
        let minp2 = m2.0
        let maxp2 = m2.1
        
        if maxp1 < minp2 || maxp2 < minp1 {
            return false
        }
    }
    //
    let count2 = polygon2.count
    for i in 0..<count2 {
        let p1 = polygon2[i]
        let p2 = polygon2[(i+1) % count2]
        let perpendicularVector = CGPoint(x: -(p2.y - p1.y), y: p2.x - p1.x)
        
        let m1 = projection(of: polygon, perpendicularVector: perpendicularVector)
        let minp1 = m1.0
        let maxp1 = m1.1

        let m2 = projection(of: polygon2, perpendicularVector: perpendicularVector)
        let minp2 = m2.0
        let maxp2 = m1.0
        
        if maxp1 < minp2 || maxp2 < minp1 {
            return false
        }
    }
    //
    return true
}

func intersects(with someView: UIView) -> Bool {
    //
    var points1 = [CGPoint]()
    let bounds1 = bounds
    let p11 = convert(bounds1.origin, to: nil)
    let p21 = convert(CGPoint(x: bounds1.origin.x + bounds1.size.width, y: bounds1.origin.y), to: nil)
    let p31 = convert(CGPoint(x: bounds1.origin.x + bounds1.size.width, y: bounds1.origin.y + bounds1.size.height) , to: nil)
    let p41 = convert(CGPoint(x: bounds1.origin.x, y: bounds1.origin.y + bounds1.size.height), to: nil)
    points1.append(p11)
    points1.append(p21)
    points1.append(p31)
    points1.append(p41)
    //
    var points2 = [CGPoint]()
    let bounds2 = someView.bounds
    let p12 = someView.convert(bounds2.origin, to: nil)
    let p22 = someView.convert(CGPoint(x: bounds2.origin.x + bounds2.size.width, y: bounds2.origin.y), to: nil)
    let p32 = someView.convert(CGPoint(x: bounds2.origin.x + bounds2.size.width, y: bounds2.origin.y + bounds2.size.height) , to: nil)
    let p42 = someView.convert(CGPoint(x: bounds2.origin.x, y: bounds2.origin.y + bounds2.size.height), to: nil)
    points2.append(p12)
    points2.append(p22)
    points2.append(p32)
    points2.append(p42)
    //
    return convex(polygon: points1, intersectsWith: points2)
}