Determine If Two Rectangles Overlap

Given two axis-aligned rectangles A and B. Write a function to determine if the two rectangles overlap.


Hint:
If you are coming up with a complicated set of conditionals, you might think too hard. There is an easier way. Try to think in the opposite direction.

Two overlapping rectangles. A rectangle can be defined by its upper left and lower right corner.

Solution:
Assume that the two rectangles are given as point (P1, P2) and (P3, P4) respectively. One direct way to attempt this problem is when two rectangles overlap, one rectangle’s corner point(s) must contain in the other rectangle. Do keep in mind of the following cases:

More overlapping rectangles cases to consider.

As you can see, the conditionals can be pretty complicated as there are a total eight of them. Can we simplify it further?

A much easier and better approach would be to think from the opposite. How about asking yourself how the two rectangles cannot overlap each other? Two rectangles do not overlap when one is above/below, or to the left/right of the other rectangle.

The condition’s expression is:

! ( P2.y < P3.y || P1.y > P4.y || P2.x < P3.x || P1.x > P4.x )

Using De Morgan’s law, we can further simplify the above expression to:

( P2.y = P3.y && P1.y = P4.y && P2.x = P3.x && P1.x = P4.x )

Further Thoughts:

  • What if the two rectangles are not necessarily axis-aligned? (That is, the rectangles can be rotated around its center at a certain angle.) Solving this problem requires more Math and understanding of linear algebra, so if you’re interested see my post on: How to determine if a point is inside a rectangle.
  • Given a list of rectangles, how would you determine the set of overlapping rectangles efficiently? Why would this be useful? Imagine you have a number of windows opened on your desktop. The operating system would need to know the overlapped windows in order to repaint the dirty region as windows are being moved around.
VN:F [1.9.22_1171]
Rating: 4.6/5 (40 votes cast)
Determine If Two Rectangles Overlap, 4.6 out of 5 based on 40 ratings

49 thoughts on “Determine If Two Rectangles Overlap

  1. battosai

    Given two rectangles consider their left bottom coordinates – (x1, y1) and (x2, y2) and their length and breadth – L1, B1 & L2, B2 respectively. Call rectangle with smaller x coordinate as rect A, the other one rect B.
    Now for A and B to intersect:
    segment (x1, y1) – (x1, y1+B1) must intersect with (x2, y2) – (x2, y2+B2)
    and
    segment (x1, y1) – (x1+L1, y1) must intersect with (x2, y2) – (x2 + L2, y2).

    VA:F [1.9.22_1171]
    0
  2. Sophie Che

    Suppose rect A is (X_A1, X_A2, Y_A1, Y_A2) and rect B is (X_B1, X_B2, Y_B1, Y_B2), where X_A1 < X_A2, Y_A1 < Y_A2, …

    Start from the basic idea: compare the x coordinates,
    bool x_ins = false;
    if (X_A1 X_B1);
    else x_ins = (X_A1 X_B1) && (X_A1 Y_B1) && (Y_A1 < Y_B2) );
    }

    VA:F [1.9.22_1171]
    +1
  3. Sophie Che

    Notice that we don’t need to compare X_A1 and X_B1 at all. Thus, we have:

    VA:F [1.9.22_1171]
    0
  4. jeff

    Your expression is wrong according to your graph, it should be:
    ! ( P2.y > P3.y || P1.y < P4.y || P2.x P4.x )

    =>

    ( P2.y ≤ P3.y && P1.y ≥ P4.y && P2.x ≥ P3.x && P1.x ≤ P4.x )

    VA:F [1.9.22_1171]
    +19
  5. jeff

    Ah, it eats my answer!

    Your expression is wrong according to your graph, it should be:

    ! ( P2.y > P3.y || P1.y < P4.y || P2.x P4.x )

    =>

    ( P2.y ≤ P3.y && P1.y ≥ P4.y && P2.x ≥ P3.x && P1.x ≤ P4.x )

    VA:F [1.9.22_1171]
    +13
  6. jeff

    VA:F [1.9.22_1171]
    +4
  7. cwy

    Consider the following example, the corner of one rectangle does not necessarily contain in another, does the solution work for this case?

    ____
    | |
    ___|___|___
    | | | |
    | | | |
    |___|___|___|
    | |
    |___|

    VA:F [1.9.22_1171]
    -3
    1. cwy

      sorry for the messed graph, the corners of the first rectangle is (0,1) and (10,0) and the second rectangle (3,3) (4,-4)

      VA:F [1.9.22_1171]
      -1
  8. Adam

    Another way to think about this:

    For two axis-aligned rectangles A and B, with axis-aligned bounding box C,
    A and B do NOT intersect if:

    C.width > (A.width + B.width)
    OR
    C.height > (A.height + B.height)

    VA:F [1.9.22_1171]
    +1
  9. Pingback: Overlapping of two rectangles. | I Live to Seek…

  10. chaos

    1337c0d3r, I don’t think the statement you made is correct:
    ” when two rectangles overlap, one rectangle’s corner point(s) must contain in the other rectangle”

    Try the following case:

    __
    ____|__|_____
    |___ |__|____|
    |__|

    VA:F [1.9.22_1171]
    -1
  11. Pingback: Amazon interview preparation | What I learn, I blog !

    1. Waqas

      #include
      #define LL long long int
      using namespace std;

      struct point
      {
      LL x,y;
      };

      int main()
      {
      point l1,r1,l2,r2;
      cin>>l1.x>>l1.y>>r1.x>>r1.y;
      cin>>l2.x>>l2.y>>r2.x>>r2.y;
      if(l1.x>r2.x||r1.x<l2.x)
      cout<<"No\n";
      else if(l1.yl1.y)
      cout<<"No\n";
      else
      cout<<"Yes\n";
      }

      VA:F [1.9.22_1171]
      0
  12. Profile photo of TerryTerry

    bool BoxesIntersect(const Box2D &a, const Box2D &b)
    {
    if (p2.x p4.x) return false; // a is right of b
    if (p1.y p3.y) return false; // a is below b
    return true; // boxes overlap
    }

    VN:F [1.9.22_1171]
    -1
  13. Mayank

    Here is a code that I believe should print ‘YES’ if rectangles overlap, otherwise ‘NO’…

    VA:F [1.9.22_1171]
    0
    1. Andreas Schuldei

      you write

      but clearly something was lost on the way.

      i assume you mean

      VA:F [1.9.22_1171]
      +1
  14. abhishek samanta

    The statement “two rectangles overlap, one rectangle’s corner point(s) must contain in the other rectangle. ” is clearly wrong.

    VA:F [1.9.22_1171]
    0
  15. Pranaya

    This is written in Java: Hope this will help

    ————————————————–
    import java.util.Arrays;

    public class Rectangle {

    public class Point {
    /*
    * This is a 2D point with coordinate (x,y)
    */
    double x;
    double y;

    Point() {
    this.x = 0;
    this.y = 0;
    }

    Point(double x, double y) {
    this.x = x;
    this.y = y;
    }

    public String show() {
    return “( ” + x + ” , ” + y + ” )”;
    }

    public boolean isEqual(Point p) {
    return this.x == p.x && this.y == p.y;
    }

    }

    /**
    * Rectangle is constructed by any two corner points p1 and p2
    */
    Point p1, p2;

    public Rectangle() {
    this.p1 = new Point();
    this.p2 = new Point();
    }

    public Rectangle(double x1, double y1, double x2, double y2) {
    this.p1 = new Point(x1, y1);
    this.p2 = new Point(x2, y2);

    }

    public Rectangle(Point p1, Point p2) {
    this.p1 = p1;
    this.p2 = p2;
    }

    public void show() {

    System.out.println(“———- ” + this + ” ————“);
    System.out.println(“Point p1 is : ” + p1.show());
    System.out.println(“Point p2 is : ” + p2.show());

    }

    public boolean validate() {

    if (this.p1.x != this.p2.x && this.p1.y != this.p2.y)
    return true;
    else
    return false;
    }

    public double getArea() {

    double height = Math.abs(p1.y – p2.y);
    double width = Math.abs(p1.x – p2.x);

    return height * width;
    }

    /**
    * This is like a utility method
    *
    * @param rect1
    * @param rect2
    * @return
    */
    public static Rectangle getIntersectedRectangle(Rectangle rect1,
    Rectangle rect2) {

    if (!hasCommonArea(rect1, rect2))
    return null;

    /*
    * If Common area exists then find Rectangle
    *
    * Two x-coordinate of intersected rectangle will be middle two
    * x-coordinate of four x-coordinates
    */
    double[] dXArr = new double[] { rect1.p1.x, rect1.p2.x, rect2.p1.x,
    rect2.p2.x };
    double[] dYArr = new double[] { rect1.p1.y, rect1.p2.y, rect2.p1.y,
    rect2.p2.y };

    Arrays.sort(dXArr);
    Arrays.sort(dYArr);

    Rectangle inRect = new Rectangle(dXArr[1], dYArr[1], dXArr[2], dYArr[2]);

    inRect.show();
    return inRect;
    }

    /**
    * This is like a utility method
    *
    * @param rect1
    * @param rect2
    * @return
    */
    public static boolean hasCommonArea(Rectangle rect1, Rectangle rect2) {

    boolean flag1 = true, flag2 = true;
    if ((Math.min(rect1.p1.x, rect1.p2.x) >= Math.max(rect2.p1.x,
    rect2.p2.x))
    || (Math.max(rect1.p2.x, rect1.p2.x) = Math.max(rect2.p1.y,
    rect2.p2.y))
    || (Math.max(rect1.p2.y, rect1.p2.y) <= Math.min(rect2.p1.y,
    rect2.p2.y))) {

    flag2 = false;
    }

    if (!(flag1 && flag2))
    System.out.println("Common Area doesnot exist");

    // System.out.println("flag1 😡 " + flag1 + " flag2 :y " + flag2);

    return flag1 && flag2;
    }

    public static void main(String[] args) {
    // TODO Auto-generated method stub

    Rectangle rect1 = new Rectangle(1, 1, 6, 6);
    Rectangle rect2 = new Rectangle(1, 16, 6, 20);

    if (null != getIntersectedRectangle(rect1, rect2))
    System.out.println("Area is : "
    + getIntersectedRectangle(rect1, rect2).getArea()
    + " sq unit");

    }

    }

    VA:F [1.9.22_1171]
    +1
  16. rong

    According to the graph, it should be:

    ! ( P2.y > P3.y || P1.y < P4.y || P2.x P4.x )

    That is I will compare the one’s lower point with the other’s higher point.

    VA:F [1.9.22_1171]
    0
  17. sabz

    The mathematical definition of two overlapped rectangles should be a part of one rectangle is within the other rectangle. The original declaration that one corner of a rectangle is in another rectangle is incorrect. The declaration that two non-overlapping rectangles are side by side or one on top of the other is incorrect either. Some replies have pointed out if the two rectangles form a cross, the can still overlap.

    A complete solution is to check if any point of one rectangle is completely inside another rectangle. To do this, find the lower left corner (min, min) and upper right corner (max, max) of the reference rectangle and use the expression, supposing the coordinates of point to be checked is (px, py) and the corners are (low, left) and (upper, right):
    lower<=py && py<=upper && left<=px && px<=py.

    One can iterate all the points in the rectangle to be checked and exit as soon as any point matches the predicate. A better approach is using binary search. One rectangle overlaps with another rectangle if either the left half or the right half or the upper half or the bottom half of the rectangle overlaps with the other rectangle.

    VA:F [1.9.22_1171]
    0
    1. sabz

      The mathematical definition of two overlapped rectangles should be a part of one rectangle is within the other rectangle. The original declaration that one corner of a rectangle is in another rectangle is incorrect. The declaration that two non-overlapping rectangles are side by side or one on top of the other is incorrect either. Some replies have pointed out if the two rectangles form a cross, the can still overlap.

      A complete solution is to check if any point of one rectangle is completely inside another rectangle. To do this, find the lower left corner (min, min) and upper right corner (max, max) of the reference rectangle and use the expression, supposing the coordinates of point to be checked is (px, py) and the corners are (low, left) and (upper, right):
      lower<=py && py<=upper && left<=px && px<=right.
      This works if the rectangles align with the axes,

      One can iterate all the points in the rectangle to be checked and exit as soon as any point matches the predicate. A better approach is using binary search. One rectangle overlaps with another rectangle if either the left half or the right half or the upper half or the bottom half of the rectangle overlaps with the other rectangle.

      VA:F [1.9.22_1171]
      0
  18. Richiban

    As others have pointed out, the given “solution” will only return true for pairs of rectangles where corners are contained within another rectangle. If we define a rectangle as a centre point combined with a width and a height (rather than a top left corner and bottom right corner) it is easy to calculate the distance between the centres of the two shapes. In order for the two rectangles to be overlapping the x-distance between their centres must be less than their average width AND the y-distance between their centres must be less than their average height. Here’s a solution in F#:

    type Point = { x : float; y : float }

    type Rectangle = { centre : Point; width : float; height : float }

    let overlapping r1 r2 =
    let deltaX = r1.centre.x – r2.centre.x |> Math.Abs
    let deltaY = r1.centre.y – r2.centre.y |> Math.Abs

    let averageWidth = (r1.width + r2.width) / 2.
    let averageHeight = (r1.height + r2.height) / 2.

    deltaX <= averageWidth && deltaY <= averageHeight

    VA:F [1.9.22_1171]
    +1
  19. Pingback: Finding overlapping rectangles « Richiban

  20. Michel Tosu

    I don’t get why all is whining about the solution provided. The statement that an overlapping rectangle has to have one corner inside another rectangle might be wrong, but the solution

    seems right to me? If any ot theese conditions are true, i can’t see a case when the rectangles overlap? And of none of them are true, then it’s overlapping. I can’t come up with any scenario that breaks that solution.

    VA:F [1.9.22_1171]
    0
  21. 指輪 ブランド 人気 ペア

    「ジバンシィ」のショーが開かれるのは9月11日。デザイナーのリカルド?ティッシ(Riccardo Tisci)をサポートするのは、既存の境界を超越する実験的なパフォーマンスで知られるセルビア出身のアーティスト、マリーナ?アブラモヴィッチ(Marina Abramovic)だ。
    指輪 ブランド 人気 ペア http://www.newkakaku.com/lz1.htm

    VA:F [1.9.22_1171]
    -1
  22. スーパーコピーブランド激安ショッピングモール!ブランドスーパーコピー品ごとにぱっと見て全然違わないほどの外観を持ち、手触りも同じである。当店スーパーコピーブランド商品とと

    スーパーコピーブランド激安ショッピングモール!ブランドスーパーコピー品ごとにぱっと見て全然違わないほどの外観を持ち、手触りも同じである。当店スーパーコピーブランド商品とともに、高品質と安心をお届けいたします!スーパーコピー 代引きN品をご 購入の方は、こちらへ.弊社は正規品と同等品質のコピー品を低価で お客様に提供します!すべての商品は品質2年無料保証です。100%実物写真ですし、品質が完璧です!”ブランド財布偽物財布コピー ルイヴィトン財布偽物良質なスーパーコピー品を創造します!当社のスーパーコピー代引き、スーコピー腕時計は他社のものより品質がよくて、価格も安いです http://www.brandiwc.com/brand-1-copy-0.html

    VA:F [1.9.22_1171]
    0
  23. シチズン時計登録(中国)有限会社のオフィシャルサイトで、細心の消費者が気になる「オンライン注文」欄の子。ブランドバッグスーパーコピー点撃進入、現在32項の異なるモデルのシチ

    シチズン時計登録(中国)有限会社のオフィシャルサイトで、細心の消費者が気になる「オンライン注文」欄の子。ブランドバッグスーパーコピー点撃進入、現在32項の異なるモデルのシチズン時計オンラインの注文は、価格から1620元から中元。2007年と試運転の時と比べてだけではなく、オンライン販売の時計はデザインの種類が増えて、さらに支払い方式は以前は単一の宝を支払って増えて宝を支払って、銀行振り込み、オンラインバンク3種。 http://www.gginza.com/%E3%82%A2%E3%83%90%E3%82%A6%E3%83%88/item_2.html

    VA:F [1.9.22_1171]
    0
  24. 時計は代々、光を金庫は明らかに足りない。ある時計業界関係者によると、腕時計を絶好調そして将来譲渡時いい売値定期掃除は非常に重要な一環。ブランド 時計コピー3年ごとの週波数メ

    時計は代々、光を金庫は明らかに足りない。ある時計業界関係者によると、腕時計を絶好調そして将来譲渡時いい売値定期掃除は非常に重要な一環。ブランド 時計コピー3年ごとの週波数メンテナンス時間、毎回約5000元の通常のメンテナンス価格ざっと計算して、30年の保養費用とは6万元を投入。 http://www.newkakaku.com/cq19.htm

    VA:F [1.9.22_1171]
    0
  25. 今年はスウェーデン隊に彼らの第3基のワールドカップ発起衝撃。ヘンリック・斯滕森はこのレースに最高の選手の世界ランキングで、現在は7位。彼のパートナーのロバート・卡尔森昨年ヨ

    今年はスウェーデン隊に彼らの第3基のワールドカップ発起衝撃。ヘンリック・斯滕森はこのレースに最高の選手の世界ランキングで、現在は7位。彼のパートナーのロバート・卡尔森昨年ヨーロッパツアー賞金ランキングで1位に位、一週間ばかりに日本で開かれた鳳凰高球技で準優勝し、ついに傷ついた影を出て行った。オメガ 時計コピーに加えて、彼らはこの球場の理解度や昨年の成功経験になって、スウェーデンチームの優勝チーム最高の声。 http://www.wtobrand.com/miumiu-wallet1.htm

    VA:F [1.9.22_1171]
    0
  26. 北斗衛星時計を採用し、中国が自主開発した北斗衛星ナビゲーションシステムの2世代の時報信号を時報、北斗衛星に覆われた範囲内で、すべての時計分秒違わない、時間精度で制御コンマ

    北斗衛星時計を採用し、中国が自主開発した北斗衛星ナビゲーションシステムの2世代の時報信号を時報、北斗衛星に覆われた範囲内で、すべての時計分秒違わない、時間精度で制御コンマ1秒以内に。北斗衛星時計は「1、2、3を測るかも」など何項のハイテク機能、即ち、衛星信号時刻合わせ、校正時計時間;二定、すなわち指向、位置決め、出力経緯度、高度の座標、地図区枚コード;三測、すなわち、高さを測る、温度を測る測気圧。BOTTEGA VENETA財布コピー未来の北斗衛星の時計を持ってショートメッセージ通信機能を使用することができ、この機能はユーザーの緊急援助、ときに、野外旅行者やアウトドア者に危険が警察に助けを求めに限り、腕時計のSOSキーをすることで、自分の位置情報や救難信号衛星で、事前設定の端末に送信して。世界の四大衛星ナビゲーションシステムは、中国の北斗衛星ナビゲーションシステムを備えているこの機能。 http://www.ooobag.com/watch/cartier/baig/30f5513206b999ec.html

    VA:F [1.9.22_1171]
    0
  27. John

    //The typical rectangle struct I imagine
    struct RECTANGLE{
    float left;
    float top;
    float right;
    float bottom;
    };

    //Set the rectangles to whatever coordinates
    RECTANGLE a={x, y, w, h};
    RECTANGLE b={X, Y, W, H};

    //…and in one quick line of code determine whether there was an intersection or not
    bool intersection=!(a.rightb.bottom || a.left>b.right || a.bottom<b.top);

    ==================== In plain English ================================

    a.rightb.bottom = the rectangle (a) is too far above rectangle (b) to intersect
    a.left>b.right = the rectangle (a) is too far to the right of rectangle (b) to intersect
    a.bottom<b.top = the rectangle (b) is too far below the rectangle (b) to intersect

    This should universally test for axis-aligned rectangle overlap (even in the case where none of the corners are within either rectangle) if my thinking is correct, you may need to modify this to fit whichever coordinate system you're working with. I haven't tested this code it just kinda popped up in my mind as I was reading this but I'm pretty sure it would work.

    VA:F [1.9.22_1171]
    0
  28. John

    //The typical rectangle struct I imagine
    struct RECTANGLE{
    float left;
    float top;
    float right;
    float bottom;
    };

    //Set the rectangles to whatever coordinates
    RECTANGLE a={x, y, w, h};
    RECTANGLE b={X, Y, W, H};

    //…and in one quick line of code determine whether there was an intersection or not
    bool intersection=!(a.right<b.left || a.top>b.bottom || a.left>b.right || a.bottom&ltb.top);

    ==================== In plain English ================================

    a.right<b.left = the rectangle (a) is too far to the left of rectangle (b) to intersect
    a.top>b.bottom = the rectangle (a) is too far above rectangle (b) to intersect
    a.left>b.right = the rectangle (a) is too far to the right of rectangle (b) to intersect
    a.bottom<b.top = the rectangle (b) is too far below the rectangle (b) to intersect

    This should universally test for axis-aligned rectangle overlap (even in the case where none of the corners are within either rectangle) if my thinking is correct, you may need to modify this to fit whichever coordinate system you’re working with. I haven’t tested this code it just kinda popped up in my mind as I was reading this but I’m pretty sure it would work.

    VA:F [1.9.22_1171]
    0
  29. John

    My bad for any previous posts, I had to fix this a few times because I didn’t notice the code tag before

    //The typical rectangle struct I imagine
    struct RECTANGLE{
    float left;
    float top;
    float right;
    float bottom;
    };

    //Set the rectangles to whatever coordinates
    RECTANGLE a={x, y, w, h};
    RECTANGLE b={X, Y, W, H};

    //…and in one quick line of code determine whether there was an intersection or not
    bool intersection=!(a.right<b.left || a.top>b.bottom || a.left>b.right || a.bottom<b.top);

    ==================== In plain English ================================

    a.right<b.left = the rectangle (a) is too far to the left of rectangle (b) to intersect
    a.top>b.bottom = the rectangle (a) is too far above rectangle (b) to intersect
    a.left>b.right = the rectangle (a) is too far to the right of rectangle (b) to intersect
    a.bottom<b.top = the rectangle (b) is too far below the rectangle (b) to intersect

    This should universally test for axis-aligned rectangle overlap (even in the case where none of the corners are within either rectangle) if my thinking is correct, you may need to modify this to fit whichever coordinate system you’re working with. I haven’t tested this code it just kinda popped up in my mind as I was reading this but I’m pretty sure it would work.

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.