Algorithm to detect intersection of two rectangles?

Question

I'm looking for an algorithm to detect if two rectangles intersect (one at an arbitrary angle, the other with only vertical/horizontal lines).

Testing if a corner of one is in the other ALMOST works. It fails if the rectangles form a cross-like shape.

It seems like a good idea to avoid using slopes of the lines, which would require special cases for vertical lines.

Solution 1

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

Solution 2

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.

Solution 3

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;
}

Solution 4

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

Solution 5

The accepted answer about the separating axis test was very illuminating but I still felt it was not trivial to apply. I will share the pseudo-code I thought, "optimizing" first with the bounding circle test (see this other answer), in case it might help other people. I considered two rectangles A and B of the same size (but it is straightforward to consider the general situation).

1 Bounding circle test:

    function isRectangleACollidingWithRectangleB:
      if d > 2 * R:
         return False
      ...

Computationally is much faster than the separating axis test. You only need to consider the separating axis test in the situation that both circles collide.

2 Separating axis test

The main idea is:

• Consider one rectangle. Cycle along its vertices V(i).

• Calculate the vector Si+1: V(i+1) - V(i).

• Calculate the vector Ni using Si+1: Ni = (-Si+1.y, Si+1.x). This vector is the blue from the image. The sign of the dot product between the vectors from V(i) to the other vertices and Ni will define the separating axis (magenta dashed line).

• Calculate the vector Si-1: V(i-1) - V(i). The sign of the dot product between Si-1 and Ni will define the location of the first rectangle with respect to the separating axis. In the example of the picture, they go in different directions, so the sign will be negative.

• Cycle for all vertices j of the second square and calculate the vector Sij = V(j) - V(i).

• If for any vertex V(j), the sign of the dot product of the vector Sij with Ni is the same as with the dot product of the vector Si-1 with Ni, this means both vertices V(i) and V(j) are on the same side of the magenta dashed line and, thus, vertex V(i) does not have a separating axis. So we can just skip vertex V(i) and repeat for the next vertex V(i+1). But first we update Si-1 = - Si+1. When we reach the last vertex (i = 4), if we have not found a separating axis, we repeat for the other rectangle. And if we still do not find a separating axis, this implies there is no separating axis and both rectangles collide.

• If for a given vertex V(i) and all vertices V(j), the sign of the dot product of the vector Sij with Ni is different than with the vector Si-1 with Ni (as occurs in the image), this means we have found the separating axis and the rectangles do not collide.

In pseudo-code:

    function isRectangleACollidingWithRectangleB:
      ...
      #Consider first rectangle A:
      Si-1 = Vertex_A[4] - Vertex_A[1]
      for i in Vertex_A:
         Si+1 = Vertex_A[i+1] - Vertex_A[i]
         Ni = [- Si+1.y, Si+1.x ]
         sgn_i = sign( dot_product(Si-1, Ni) ) #sgn_i is the sign of rectangle A with respect the separating axis

         for j in Vertex_B:
            sij = Vertex_B[j] - Vertex_A[i]
            sgn_j = sign( dot_product(sij, Ni) ) #sgnj is the sign of vertex j of square B with respect the separating axis
            if sgn_i * sgn_j > 0: #i.e., we have the same sign
                break #Vertex i does not define separating axis
            else:
                if j == 4: #we have reached the last vertex so vertex i defines the separating axis
                   return False
        
        Si-1 = - Si+1

      #Repeat for rectangle B
      ...

      #If we do not find any separating axis
      return True 

You can find the code in Python here.

Note: In this other answer they also suggest for optimization to try before the separating axis test whether the vertices of one rectangle are inside the other as a sufficient condition for colliding. However, in my trials I found this intermediate step to actually be less efficient.

View more solutions

Comments

[Wes P]

what if you add to your corner check, a check to see if the second rectangle is inside the bounds (rectangular) of the angled rectangle?

[Martijn]

What language are you gonna do this in? Because in Java there are built-in classes that let you do this.

[l_39217_l]

I think graphics api and most GUI libraries(like swing) has this implemented.

[Florian Bösch]

that can miss cases where they overlap but no corner is inside any rectangle

[freespace]

2D or 3D? I realised I just posted a 3D solution which made assumptions about what you meant by "intersection".

[user20493]

Unfortunately I don't think .NET has this.

[Sebastian Krysmanski]

I've created a C# implementation for this; see here.

[V Krishan]

What are these built-in classes?

[Silver Gonzales]

This question is almost the same as: stackoverflow.com/questions/306316/…. Although, this is looking for a solution that is particularly for C++. The accepted answer is also pretty simple and straightforward.

[Pitarou]

Careful! Don't forget the case where one rectangle completely encloses another

[user20493]

I like this approach; it's simple and logical. It seems if one rect is inside the other, all edges of the containing rect will appear to be separating edges. In this case, testing if a single point from the (possibly) contained rect is in the containing rect would tell if it's entirely contained.

[user20493]

Unfortunately I'm using C#. The Rectangle class has a Contains () method, but it's only for non-rotated rectangles.

[user20493]

The problem with equations is when you have a vertical line, which has infinite slope.

[Skizz]

This algorithm doesn't work for all cases. It is possible to place the second rectangle rotated 45 degrees to the first rectangle and offset along the diagonal so that it fulfills the above intersection tests but doesn't intersect.

[Nils Pipenbrinck]

Skizz, check all eight edges. If the objects don't intersect one of the eight edges will separate them. Why don't you post an image showing your case? I can show you the axis..

[Skizz]

My mistake, it does cope with that condition.

[Adam Davis]

There are corner cases for every solution.

[MSalters]

Obviously, as two squares (0,0,1,1) and (0,3,1,4) do not overlap but their projections on the x axis completely overlap. Both tests are necessary, the combination is sufficient.

[Aaron Digulla]

Please edit the original post; I was wondering the same thing and it's not obvious to look in the comments.

[iecanfly]

It is not sufficient for the x and y projections to overlap : take eg the rectangles [(0,0), (0,3), (3,3), (3,0)] and [(2,5), (5,2), (7,4), (4,7)].

[Scottie T]

I agree with @Joel in Gö. This method misses a large set of cases where the rectangles do not overlap, yet their projected radii do in both x and y.

[Satish]

As said before, this is not a full nor accurate solution

[matt burns]

This answer is not wrong, but it is misleading. It is true that: If the two boxes collide, the lines A and B will overlap. but it is also true that: If the lines A and B overlap, the two boxes may or may not be colliding

[BlueRaja - Danny Pflughoeft]

@floater: I would say it's not only wrong, but also misleading, which is even worse.

[phkahler]

For 3d polyhedrons you need some additional tests, the possible separating axis are the face normals and the cross products of all pairs of edges (one taken from each object). These cross products are all "through the paper" in 2d so they don't need to be checked.

[baskin]

How about this? event O: lines the lines A and B will overlap for X and Y axis; event P: at least one of the rectangle A's corner is in rectangle B. The 2 rectangles overlap if P || O&P.

[sinelaw]

I may be wrong, but doesn't that just check if the vertices of one rectangle are inside another? If yes, it's not enough because rectangles may overlap without any vertices inside.

[shaman.sir]

My adaptation of this algorithm to JS: gist.github.com/3007244 (Thank you, its great!)

[John Dvorak]

The image is dead now (nov 2012)

[AlexWien]

Why do you need Math.abs() in "Math.abs(rectA.width + rectB.width)", to handle negative widths?

[Lee Louviere]

You missed the part where if you find the planar intersect line, you have to ensure that a portion of it exists within both rectangles.

[Robotbugs]

You are missing that he wants one to be rotated by an arbitrary angle.

[Duncan C]

That code only works for rectangles that are square to the screen. That's a trivial case. The assumption is that we're dealing with rectangles that are not at 90 degree angles to the screen or each other.

[Duncan C]

Can they, with rectangles? How? It seems to me that in order for 2 rectangles to intersect, at least one vertex of one of the rectangles must lie on the other rectangle.

[GoldenJoe]

I'm not quite clear on what v(n-1) is supposed to be in the last part. A point from the edge of what? The rotated edge?

[Nils Pipenbrinck]

Just walk around the points of your rectangle, in clockwise or counter-clockwise order. v(n) is the current point, v(n-1) is the previous point. Easy as that.

[Leonardo]

As I have checked and used in my applications, that code works on any rotated rectangle. No matter the rotation degree.

[Ben Voigt]

This doesn't describe the algorithm, though, it just mentions a library that already uses it.

[Ben Voigt]

The separating axis is not necessarily a compass direction, it can have any angle.

[Ben Voigt]

@DuncanC: Yes, they can. The counterexample is a cross, and it was even listed in the original question.

[Duncan C]

@BenVoigt This is a very old thread, but you're absolutely right.

[Rjdlee]

I had a lot of trouble visualizing this so I re-created what I think the image being referenced looked like. imgur.com/bNwrzsv

[ZZ 5]

intersects() method is pretty useless since it returns boolean instead of intersection I guess.

[Kagami Sascha Rosylight]

Non-rotated rectangles rectA(x=0, y=0, width=1, height=1) and rectB(x=2, y=0, width=100, height=1) don't intersect but your method says they intersect. Am I doing something wrong?

[Puco4]

This answer is also wrong. If both projections in x and y axis overlap, that does not imply the rectangles overlap. See for example: imgur.com/a/HyorpQc

[Puco4]

In case it helps other people, I wrote an answer below applying this idea in pseudo-code.