Determine if two rectangles are overlapping

Question

I am working on an algorithm problem to try to determine whether two rectangles overlap with each other.

Assume L1 and R1 are the top-left and bottom-right of the first rectangle, and L2 and R2 as the top left and bottom-right of the second rectangle.

I determined that it was easier to first determine when the rectangles don't overlap, and here are my rules:

L2.x >= R1.x // rectangle 2 is right of rectangle 1

R2.x <= L1.x // rectangle 2 is left of rectangle 1

R2.y <= L1.y // rectangle 2 is top of rectangle 1

L2.y >= R1.y // rectangle 2 is bottom of rectangle 1

So put together, we take the not of this, which means whenever the conditions for not overlapping are satisfied, then the rectangles are overlapping.

public static boolean isOverlap(L1, R1, L2, R2) {
    if(!(L2.x >= R1.x) || !(R2.x <= L1.x) || !(R2.y <= L1.y) || !(L2.y >= R1.y)) {
        return true;
    }
    return false;
}

I feel like I'm not doing this correctly. While I drew everything out on a piece of paper to solve this problem, I feel like I am missing something. What did I do wrong?

Test Cases:

    // Rectangle 2 is two x-units away from Rectangle 1
    // Should not overlap
    Point L1 = new Point(0, 0);
    Point R1 = new Point(2, 2);

    Point L2 = new Point(4, 0);
    Point R2 = new Point(6, 2);

    if(isOverlap(L1, R1, L2, R2)) {
        System.out.println("Overlapping");
    } else {
        System.out.println("Not overlapping");
    }

Output:

Overlapping

Looking at this answer, I am quite close, but it seems I flipped the top/bottom conditions: http://www.geeksforgeeks.org/find-two-rectangles-overlap/

Is there a reason you're not using the Polygon class and just calling Polygon.intersects(Rectangle2D)? — Kylar, Sep 25 '15 at 18:59
@Kylar I am studying for an interview and is more interested in the actual implementation — theGreenCabbage, Sep 25 '15 at 18:59
http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other?rq=1 contains the math and proof. You should be able to adapt it easily. — Kylar, Sep 25 '15 at 19:00
If the rectangles are not overlapping then either `L2.x >= R1.x` or `R2.x <= L1.x` is `true`, **but not both** (one rectangle can't be both to the left and to the right of the other), which means that at least one of `!(L2.x >= R1.x)` and `!(R2.x <= L1.x)` is `true`, which makes the `||` of them `true`. — Alex Hall, Sep 25 '15 at 19:03
@AlexHall That's what I gathered, and was the source of my issue. — theGreenCabbage, Sep 25 '15 at 19:04

silentsam · Answer 1 · 2015-09-25T19:23:07.180

Your criteria are right. The problem is with the boolean negation. NOT (A OR B) == (NOT A) AND (NOT B). So you want to do NOT (out on right || out on left || out on top || out on bottom). This translates to

(NOT (out on right)) AND (NOT (out on left)) ...

That is,

public static boolean isOverlap(L1, R1, L2, R2) {
  if(L2.x < R1.x && R2.x > L1.x && R2.y > L1.y && L2.y < R1.y) {
    return true;
  }
  return false;
}

which might have struck you as too long in the first place. Remember that Java has short-circuit evaluation for the && operator and will stop earlier returning "non-overlapping" but in order to return "overlapping" (true) all four conditions need to be evaluated and fulfilled.

failing in case of Point l1 = {1,4}, r1 = {5, 4}; Point l2 = {1,4}, r2 = {3,4}; — GorvGoyl, May 22 '17 at 19:31

score 0 · Answer 2 · answered Sep 25 '15 at 19:03

I think I figured it out..

public static boolean isOverlap(Point L1, Point R1, Point L2, Point R2) {
    // Check whether rectangle is left or right of each other
    // If it is, then it is not overlapping
    if((L2.x >= R1.x) || (R2.x <= L1.x)) {
        return false;
    }

    // Check whether the rectangle is top or bottom of each other
    // If it is, then it is not overlapping
    if((R2.y <= L1.y) || (L2.y >= R1.y)) {
        return false;
    }
    return true;
}

I basically took apart the four conditions and separated them into two if-statements. The first if-statement checks if the rectangle is left/right of each other. If they are, then they do not overlap.

The second if-statement checks if the rectangle is top/bottom of each other. If they are, then they do not overlap.

score 0 · Answer 3 · answered Sep 25 '15 at 19:21

I think, we should && instead of ||, please try below snippet

public static boolean isOverlap(Point L1, Point R1, Point L2, Point R2) {
    if((!(L2.x >= R1.x) && !(R2.x <= L1.x)) && (!(R2.y <= L1.y) && !(L2.y >= R1.y))) {
        return true;
    }
    return false;
}

Determine if two rectangles are overlapping

3 Answers3