Determine If Two Rectangles Overlap Each Other

Determine if two rectangles overlap each other?

if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
     RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) 

or, using Cartesian coordinates

(With X1 being left coord, X2 being right coord, increasing from left to right and Y1 being Top coord, and Y2 being Bottom coord, increasing from bottom to top -- if this is not how your coordinate system [e.g. most computers have the Y direction reversed], swap the comparisons below) ...

if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
    RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1) 

Say you have Rect A, and Rect B.
Proof is by contradiction. Any one of four conditions guarantees that no overlap can exist:

• Cond1. If A's left edge is to the right of the B's right edge,
  - then A is Totally to right Of B
• Cond2. If A's right edge is to the left of the B's left edge,
  - then A is Totally to left Of B
• Cond3. If A's top edge is below B's bottom edge,
  - then A is Totally below B
• Cond4. If A's bottom edge is above B's top edge,
  - then A is Totally above B

So condition for Non-Overlap is

NON-Overlap => Cond1 Or Cond2 Or Cond3 Or Cond4

Therefore, a sufficient condition for Overlap is the opposite.

Overlap => NOT (Cond1 Or Cond2 Or Cond3 Or Cond4)

De Morgan's law says

Not (A or B or C or D) is the same as Not A And Not B And Not C And Not D

so using De Morgan, we have

Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4

This is equivalent to:

• A's Left Edge to left of B's right edge, [RectA.Left < RectB.Right], and
• A's right edge to right of B's left edge, [RectA.Right > RectB.Left], and
• A's top above B's bottom, [RectA.Top > RectB.Bottom], and
• A's bottom below B's Top [RectA.Bottom < RectB.Top]

Note 1: It is fairly obvious this same principle can be extended to any number of dimensions.

Note 2: It should also be fairly obvious to count overlaps of just one pixel, change the < and/or the > on that boundary to a <= or a >=.

Note 3: This answer, when utilizing Cartesian coordinates (X, Y) is based on standard algebraic Cartesian coordinates (x increases left to right, and Y increases bottom to top). Obviously, where a computer system might mechanize screen coordinates differently, (e.g., increasing Y from top to bottom, or X From right to left), the syntax will need to be adjusted accordingly/

How to determine if two rectangles overlap (At angle)

First I'd like to thank user "prideout" for pointing me in the right direction. His notes, particularly only needed 4 normals, helped me optimise my code. Oddly, the code in the link provided seemed to not work right (Detecting if the "crushed" vertexes of the shapes overlapped). I found this useful example in C++ that pointed me in the right direction and now my code work great.

Here is my AABB-OBB overlap detector function + the SAT function (Language used is "Processing" which is Java based).

// True if overlap, False if they don't
boolean seperating_axis_theorem(float[] x1, float[] y1, float[] x2, float[] y2, float[] normal){
  float[] range = new float[4];  //minAlong1, maxAlong1, minAlong2, maxAlong2
  range[0] = Float.MAX_VALUE;
  range[1] = -Float.MAX_VALUE;
  range[2] = Float.MAX_VALUE;
  range[3] = -Float.MAX_VALUE;
  
  // Dot is projecting the points onto the seperating axis and then we get the max and min
  float dotVal;
  for(int i = 0; i < 4; i++){
    dotVal = dot(x1[i], y1[i], normal[0], normal[1]);
    if(dotVal < range[0]){range[0] = dotVal;}
    if(dotVal > range[1]){range[1] = dotVal;}
    
    dotVal = dot(x2[i], y2[i], normal[0], normal[1]);
    if(dotVal < range[2]){range[2] = dotVal;}
    if(dotVal > range[3]){range[3] = dotVal;}
  }
  
  if(range[1] < range[2] || range[0] > range[3]){
    return false;
  }
  
  return true;
}

// True if two shapes overlap, False otherwise
Boolean AABB_OBB_Overlap(float[] OBB_X, float[] OBB_Y, float[] AABB_X, float[] AABB_Y){
  
  // Checking the camera's normals, simplified since we know its axis aligned so no unit vector calculations needed
  float[] range = get_range(OBB_X);  // Returns min and max of array
  if(range[1] < AABB_X[0] || range[0] > AABB_X[1]){
    return false;
  }
  range = get_range(OBB_Y);
  if(range[1] < AABB_Y[0] || range[0] > AABB_Y[2]){
    return false;
  }
  
  // Checking the sprite's normals
  float[] normal1 = unit_vector(OBB_X[1] - OBB_X[0], OBB_Y[1] - OBB_Y[0]);  // Top side
  float[] normal2 = unit_vector(OBB_X[2] - OBB_X[0], OBB_Y[2] - OBB_Y[0]);  // Left side
  
  if(!seperating_axis_theorem(OBB_X, OBB_Y, AABB_X, AABB_Y, normal1)){
    return false;
  }
  
  if(!seperating_axis_theorem(OBB_X, OBB_Y, AABB_X, AABB_Y, normal2)){
    return false;
  }
  
  // They overlap
  return true;
}

Java check if two rectangles overlap at any point

This will find if the rectangle is overlapping another rectangle:

public boolean overlaps (Rectangle r) {
    return x < r.x + r.width && x + width > r.x && y < r.y + r.height && y + height > r.y;
}

Check if two rectangles overlap

Your conditions if (topLeftA.y < bottomRightB.y || topLeftB.y < bottomRightA.y) and (topLeftA.x > bottomRightB.x || topLeftB.x > bottomRightA.x) assume that the attribute topLeft really is the top-left vertex of the rectangle and that bottomRight really is the bottom-right vertex of the rectangle. However, your initialization code this.topLeft = topLeft; and this.bottomRight = bottomRight; does not actually guarantee this. If the initialization uses the wrong vertices for a rectangle, your code does not correct that and later methods may go wrong.

That is what happens in your test case. You do not make it clear whether your coordinates are Cartesian (increasing y-values go up) or graphical (increasing y-values go down). But in either case, one of your two test rectangles is badly defined. Your first rectangle goes from (0, 7) to (6, 0), which is correct in Cartesian coordinates but wrong in graphical coordinates. Your second rectangle goes from (0, 7) to (6, 10), which is correct in graphical coordinates but wrong in Cartesian coordinates. Whichever coordinates you use, one of those rectangles is wrong, so your overlap code fails.

Given your names, you should either correct the coordinates when creating a rectangle or return an error for bad coordinates. To correct for Cartesian coordinates, let the x-coordinate of topLeft be the minimum of the x-coordinates of the two given vertices, the y-coordinate of topLeft be the maximum of the y-coordinates of the two given vertices, the x-coordinate of bottomRight be the maximum of the x-coordinates of the two given vertices, and the y-coordinate of bottomRight be the minimum of the y-coordinates of the two given vertices. Then the caller could use any two opposing vertices of the rectangle and still get a valid result.

How do I see if two rectangles intersect in JavaScript or pseudocode?

Check for the cases where the rectangles are definitely not intersecting. If none of these cases are true then the rectangles must intersect. i.e.:

public boolean rectanglesIntersect( 
    float minAx, float minAy, float maxAx, float maxAy,
    float minBx, float minBy, float maxBx, float maxBy ) {
    boolean aLeftOfB = maxAx < minBx;
    boolean aRightOfB = minAx > maxBx;
    boolean aAboveB = minAy > maxBy;
    boolean aBelowB = maxAy < minBy;

    return !( aLeftOfB || aRightOfB || aAboveB || aBelowB );
}

This illustrates the concept but could be made slightly faster by inlining the booleans so as to take advantage of the short-circuiting behavior of ||

Checking whether two rectangles overlap in python using two bottom left corners and top right corners

You can use a simple version of the Separating Axis Theorem to test for intersection. If the rectangles do not intersect, then at least one of the right sides will be to the left of the left side of the other rectangle (i.e. it will be a separating axis), or vice versa, or one of the top sides will be below the bottom side of the other rectange, or vice versa.

So change the test to check if it is not true that they don't intersect:

def intersects(self, other):
    return not (self.top_right.x < other.bottom_left.x or self.bottom_left.x > other.top_right.x or self.top_right.y < other.bottom_left.y or self.bottom_left.y > other.top_right.y)

This code assumes that the "top" has a greater y value than the "bottom" (y decreases down the screen), because that's how your example seems to work. If you were using the other convention then you'd just flip the signs of the y comparisons.

How much do two rectangles overlap?

Compute the area of the intersection, which is a rectangle too:

SI = Max(0, Min(XA2, XB2) - Max(XA1, XB1)) * Max(0, Min(YA2, YB2) - Max(YA1, YB1))

From there you compute the area of the union:

SU = SA + SB - SI

And you can consider the ratio

SI / SU

(100% in case of a perfect overlap, down to 0%).

---

Related Topics