2008-09-22 15:15:53 8 Comments

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.

### Related Questions

#### Sponsored Content

#### 42 Answered Questions

### [SOLVED] Calculate distance between two latitude-longitude points? (Haversine formula)

**2008-08-26 12:50:45****Robin Minto****821117**View**933**Score**42**Answer- Tags: algorithm math maps latitude-longitude haversine

#### 23 Answered Questions

### [SOLVED] Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition

**2012-04-16 04:23:16****Charles Menguy****195715**View**1697**Score**23**Answer- Tags: c++ algorithm image-processing opencv

#### 7 Answered Questions

### [SOLVED] Ukkonen's suffix tree algorithm in plain English

**2012-02-26 11:30:09****Nathan Ridley****171161**View**1121**Score**7**Answer- Tags: string algorithm data-structures language-agnostic suffix-tree

#### 20 Answered Questions

### [SOLVED] What is the best algorithm for overriding GetHashCode?

**2008-11-04 20:53:19****bitbonk****220036**View**1481**Score**20**Answer- Tags: .net algorithm hashcode gethashcode

#### 35 Answered Questions

### [SOLVED] Determine Whether Two Date Ranges Overlap

**2008-11-28 14:48:35****Ian Nelson****430210**View**1300**Score**35**Answer- Tags: datetime math language-agnostic

#### 9 Answered Questions

### [SOLVED] How to find time complexity of an algorithm

**2012-06-14 11:21:15****Yasser Shaikh****715202**View**921**Score**9**Answer- Tags: algorithm time-complexity complexity-theory

#### 14 Answered Questions

### [SOLVED] What is the optimal algorithm for the game 2048?

**2014-03-12 05:37:21****nitish712****944563**View**1935**Score**14**Answer- Tags: algorithm logic artificial-intelligence 2048

#### 1 Answered Questions

### [SOLVED] How to find rectangle intersection in python?

**2014-01-07 11:27:03****mnowotka****4920**View**3**Score**1**Answer- Tags: python algorithm geometry gis computational-geometry

## 19 comments

## @Puco4 2020-10-01 19:28:14

The accepted answer about the

separating axis testwas very illuminating but I still felt it was not trivial to apply. I will share the pseudo-code I thought, "optimizing" first with thebounding 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:

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:

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.## @m_pGladiator 2008-09-22 15:25:54

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 shapesdo notoverlap if a separating axis exists (i.e. one where the projections as showndo notoverlap). So "A separating axis exists" => "No overlap". This is not a bi-implication so you cannot conclude the converse.## @MSalters 2008-10-03 11:30:16

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 2008-11-20 08:25:43

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

## @Joel in Gö 2009-01-19 09:18:41

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 2009-04-14 17:38:52

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.

## @Eliram 2009-07-29 15:07:07

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

## @matt burns 2010-01-20 10:58:44

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 2010-01-26 18:59:36

@floater: I would say it's

not onlywrong, butalsomisleading, which is even worse.## @baskin 2011-06-07 11:25:25

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.

## @Przemek 2018-06-18 23:05:51

Enough has been said in other answers, so I'll just add pseudocode one-liner:

## @BitFarmer 2017-06-15 21:38:27

I have a simplier method of my own, if we have 2 rectangles:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

They overlap if and only if:

Overlap = (max_x1 > min_x2) and (max_x2 > min_x1) and (max_y1 > min_y2) and (max_y2 > min_y1)

You can do it for 3D boxes too, actually it works for any number of dimensions.

## @Siva Srinivas Kolukula 2017-05-27 11:14:48

This is the conventional method, go line by line and check whether the lines are intersecting. This is the code in MATLAB.

the function InterX can be downloaded from: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

## @Jed 2017-05-26 21:18:25

Here is a matlab implementation of the accepted answer:

## @John Smith 2013-06-25 01:18:23

Here is what I think will take care of all possible cases. Do the following tests.

If the above 2 tests return false then these 2 rectangles do not overlap.

## @Robotbugs 2013-03-16 00:34:12

I implemented it like this:

The matrix mB is any affine transform matrix that converts points in the B space to points in the A space. This includes simple rotation and translation, rotation plus scaling, and full affine warps, but not perspective warps.

It may not be as optimal as possible. Speed was not a huge concern. However it seems to work ok for me.

## @user1517108 2013-01-03 19:30:40

Either I am missing something else why make this so complicated?

if (x1,y1) and (X1,Y1) are corners of the rectangles, then to find intersection do:

## @Robotbugs 2013-03-16 17:16:32

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

## @Leonardo 2012-12-14 12:19:13

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

## @Duncan C 2013-05-10 23:47:22

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.

## @Leonardo 2014-10-14 10:47:54

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

## @Ben Voigt 2014-12-04 19:34:23

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

## @tristan 2012-11-25 11:53:13

m_pGladiator's answer is right and I prefer to it.

Separating axis testis simplest and standard method to detect rectangle overlap. A line for which the projection intervals do not overlap we call aseparating axis. Nils Pipenbrinck's solution is too general. It usedot productto 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:

we name rectangle A, B with rectA, rectB.

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:

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)`

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

## @AlexWien 2013-02-06 21:52:06

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

## @Ben Voigt 2014-12-04 19:35:46

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

## @Kagami Sascha Rosylight 2017-10-11 00:32:08

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 2020-10-01 12:11:18

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

## @Nils Pipenbrinck 2008-09-22 15:28:21

The standard method would be to do the

separating axis test(do a google search on that).In short:

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.

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

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:

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## @user20493 2008-09-22 18:52:37

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.

## @Skizz 2008-09-22 21:22:12

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 2008-09-22 22:39:11

Skizz, check all eight edges. If the objects don't intersect one of the eight edges

willseparate them. Why don't you post an image showing your case? I can show you the axis..## @Skizz 2008-09-22 22:50:27

My mistake, it does cope with that condition.

## @phkahler 2010-02-17 02:20:02

For 3d polyhedrons you need some additional tests, the possible separating axis are the face normals

andthe 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.## @shaman.sir 2012-06-27 22:23:12

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

## @John Dvorak 2012-11-25 12:24:59

The image is dead now (nov 2012)

## @GoldenJoe 2014-04-22 21:45:09

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 2014-04-23 08:04:47

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.

## @Rjdlee 2015-06-22 04:17:53

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

## @Puco4 2020-10-01 19:37:44

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

pseudo-code.## @Mads 2011-03-26 16:43:35

Another way to do the test which is slightly faster than using the separating axis test, is to use the winding numbers algorithm (on quadrants only -

notangle-summation which is horrifically slow) on each vertex of either rectangle (arbitrarily chosen). If any of the vertices have a non-zero winding number, the two rectangles overlap.This algorithm is somewhat more long-winded than the separating axis test, but is faster because it only require a half-plane test if edges are crossing two quadrants (as opposed to up to 32 tests using the separating axis method)

The algorithm has the further advantage that it can be used to test overlap of

anypolygon (convex or concave). As far as I know, the algorithm only works in 2D space.## @sinelaw 2011-10-10 19:45:32

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.

## @Duncan C 2013-05-10 23:51:05

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.

## @Ben Voigt 2014-12-04 19:41:02

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

## @Duncan C 2014-12-04 21:21:06

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

## @Howard May 2008-10-15 11:56:24

One solution is to use something called a No Fit Polygon. This polygon is calculated from the two polygons (conceptually by sliding one around the other) and it defines the area for which the polygons overlap given their relative offset. Once you have this NFP then you simply have to do an inclusion test with a point given by the relative offset of the two polygons. This inclusion test is quick and easy but you do have to create the NFP first.

Have a search for No Fit Polygon on the web and see if you can find an algorithm for convex polygons (it gets MUCH more complex if you have concave polygons). If you can't find anything then email me at howard dot J dot may gmail dot com

## @freespace 2008-09-22 15:27:00

This is what I would do, for the

3Dversion of this problem:Model the 2 rectangles as planes described by equation P1 and P2, then write P1=P2 and derive from that the line of intersection equation, which won't exist if the planes are parallel (no intersection), or are in the same plane, in which case you get 0=0. In that case you will need to employ a 2D rectangle intersection algorithm.

Then I would see if that line, which is in the plane of both rectangles, passes through both rectangles. If it does, then you have an intersection of 2 rectangles, otherwise you don't (or shouldn't, I might have missed a corner case in my head).

To find if a line passes through a rectangle in the same plane, I would find the 2 points of intersection of the line and the sides of the rectangle (modelling them using line equations), and then make sure the points of intersections are with in range.

That is the mathematical descriptions, unfortunately I have no code to do the above.

## @Lee Louviere 2013-03-07 16:50:24

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.

## @HenryR 2008-09-22 15:25:37

You could find the intersection of each side of the angled rectangle with each side of the axis-aligned one. Do this by finding the equation of the infinite line on which each side lies (i.e. v1 + t(v2-v1) and v'1 + t'(v'2-v'1) basically), finding the point at which the lines meet by solving for t when those two equations are equal (if they're parallel, you can test for that) and then testing whether that point lies on the line segment between the two vertices, i.e. is it true that 0 <= t <= 1 and 0 <= t' <= 1.

However, this doesn't cover the case when one rectangle completely covers the other. That you can cover by testing whether all four points of either rectangle lie inside the other rectangle.

## @Louis Brandy 2008-09-22 15:23:28

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

## @Pitarou 2008-09-22 15:35:00

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

## @Adam Davis 2008-09-22 15:23:25

Well, the brute force method is to walk the edges of the horizontal rectangle and check each point along the edge to see if it falls on or in the other rectangle.

The mathematical answer is to form equations describing each edge of both rectangles. Now you can simply find if any of the four lines from rectangle A intersect any of the lines of rectangle B, which should be a simple (fast) linear equation solver.

-Adam

## @user20493 2008-09-22 18:56:21

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

## @Adam Davis 2008-09-23 05:36:24

There are corner cases for every solution.

## @Oliver Hallam 2009-01-16 19:14:08

and one square entirely enclosing the other.

## @Brendan Cashman 2008-09-22 15:22:10

If you're using Java, all implementations of the Shape interface have an intersects method that take a rectangle.

## @user20493 2008-09-22 18:53:57

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

## @ZZ 5 2015-10-27 15:02:36

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