Algorithm to detect intersection of two rectangles?

Question

The standard method would be to do the separating axis test (do a google search on that).

In short:

• Two objects don't intersect if you can find a line that separates the two objects. e.g. the objects / all points of an object are on different sides of the line.

The fun thing is, that it's sufficient to just check all edges of the two rectangles. If the rectangles don't overlap one of the edges will be the separating axis.

In 2D you can do this without using slopes. An edge is simply defined as the difference between two vertices, e.g.

  edge = v(n) - v(n-1)

You can get a perpendicular to this by rotating it by 90°. In 2D this is easy as:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

So no trigonometry or slopes involved. Normalizing the vector to unit-length is not required either.

If you want to test if a point is on one or another side of the line you can just use the dot-product. the sign will tell you which side you're on:

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

Now test all points of rectangle A against the edges of rectangle B and vice versa. If you find a separating edge the objects don't intersect (providing all other points in B are on the other side of the edge being tested for - see drawing below). If you find no separating edge either the rectangles are intersecting or one rectangle is contained in the other.

The test works with any convex polygons btw..

Amendment: To identify a separating edge, it is not enough to test all points of one rectangle against each edge of the other. The candidate-edge E (below) would as such be identified as a separating edge, as all points in A are in the same half-plane of E. However, it isn't a separating edge because the vertices Vb1 and Vb2 of B are also in that half-plane. It would only have been a separating edge if that had not been the case http://www.iassess.com/collision.png

Basically look at the following picture:

If the two boxes collide, the lines A and B will overlap.

Note that this will have to be done on both the X and the Y axis, and both need to overlap for the rectangles to collide.

There is a good article in gamasutra.com which answers the question (the picture is from the article). I did similar algorithm 5 years ago and I have to find my code snippet to post it here later

Amendment: The Separating Axis Theorem states that two convex shapes do not overlap if a separating axis exists (i.e. one where the projections as shown do not overlap). So "A separating axis exists" => "No overlap". This is not a bi-implication so you cannot conclude the converse.

In Cocoa you could easily detect whether the selectedArea rect intersects your rotated NSView's frame rect. You don't even need to calculate polygons, normals an such. Just add these methods to your NSView subclass. For instance, the user selects an area on the NSView's superview, then you call the method DoesThisRectSelectMe passing the selectedArea rect. The API convertRect: will do that job. The same trick works when you click on the NSView to select it. In that case simply override the hitTest method as below. The API convertPoint: will do that job ;-)

- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
    NSRect localArea = [self convertRect:selectedArea fromView:self.superview];

    return NSIntersectsRect(localArea, self.bounds);
}


- (NSView *)hitTest:(NSPoint)aPoint
{
    NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
    return NSPointInRect(localPoint, self.bounds) ? self : nil;
}

m_pGladiator's answer is right and I prefer to it. Separating axis test is simplest and standard method to detect rectangle overlap. A line for which the projection intervals do not overlap we call a separating axis. Nils Pipenbrinck's solution is too general. It use dot product to check whether one shape is totally on the one side of the edge of the other. This solution is actually could induce to n-edge convex polygons. However, it is not optmized for two rectangles.

the critical point of m_pGladiator's answer is that we should check two rectangles' projection on both axises (x and y). If two projections are overlapped, then we could say these two rectangles are overlapped. So the comments above to m_pGladiator's answer are wrong.

for the simple situation, if two rectangles are not rotated, we present a rectangle with structure:

struct Rect {
    x, // the center in x axis
    y, // the center in y axis
    width,
    height
}

we name rectangle A, B with rectA, rectB.

    if Math.abs(rectA.x - rectB.x) < (Math.abs(rectA.width + rectB.width) / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(rectA.height + rectB.height) / 2))
    then
        // A and B collide
    end if

if any one of the two rectangles are rotated, It may needs some efforts to determine the projection of them on x and y axises. Define struct RotatedRect as following:

struct RotatedRect : Rect {
    double angle; // the rotating angle oriented to its center
}

the difference is how the width' is now a little different: widthA' for rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB' for rectB: Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)

    if Math.abs(rectA.x - rectB.x) < (Math.abs(widthA' + widthB') / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(heightA' + heightB') / 2))
    then
        // A and B collide
    end if

Could refer to a GDC(Game Development Conference 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

Check to see if any of the lines from one rectangle intersect any of the lines from the other. Naive line segment intersection is easy to code up.

If you need more speed, there are advanced algorithms for line segment intersection (sweep-line). See http://en.wikipedia.org/wiki/Line_segment_intersection