Check if two rectangles overlap

Question

This questions have asked multiple times and i have seen many threads but my query is very specific. How to see if two rectangles overlap. The test case which finds bug in my code is :

l2 = new RectanglePoint(0, 7);
r2 = new RectanglePoint(6, 10);
l1 = new RectanglePoint(0, 7);
r1 = new RectanglePoint(6, 0);
Function call: isOverlap(new Rectangle(l1, r1), new Rectangle(l2, r2));

My Code:

class RectanglePoint {
    int x;
    int y;

    public RectanglePoint(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Rectangle {
    RectanglePoint topLeft;
    RectanglePoint bottomRight;

    public Rectangle(RectanglePoint topLeft, RectanglePoint bottomRight) {
        this.topLeft = topLeft;
        this.bottomRight = bottomRight;
    }
}

public class RectangleOverlap {
    public boolean isOverlap(Rectangle rect1, Rectangle rect2) {
        return isOverlapHelper1(rect1.topLeft, rect1.bottomRight, rect2.topLeft,
                rect2.bottomRight);
    }


    private boolean isOverlapHelper1(RectanglePoint topLeftA,
            RectanglePoint bottomRightA, RectanglePoint topLeftB,
            RectanglePoint bottomRightB) {
        if (topLeftA.y < bottomRightB.y || topLeftB.y < bottomRightA.y) {
            return false;
        }
        if (topLeftA.x > bottomRightB.x || topLeftB.x > bottomRightA.x) {
            return false;
        }
        return true;
    }

The bug is in the condition: if (topLeftA.y < bottomRightB.y || topLeftB.y < bottomRightA.y)

Please help. I already spent lots of time in this.

Answer 1

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.

Answer 2

You are assuming that inputs l1 and l2 are gonna be always the topLeft co-ordinates and r1 and r2 are gonna be always bottomRight co-ordinates. To adhere to that assumption, I recommend you use some kindda condition/validation to make sure the inputs are consistent with your assumption,

Use this code before inside isOverlap() before calling isOverlapHelper1()

if ((rect1.topLeft.x > rect1.bottomRight.x) ||
(rect1.topLeft.y < rect1.bottomRight.y) ||
(rect2.topLeft.x > rect2.bottomRight.x) || 
(rect2.topLeft.y < rect2.bottomRight.y))
  throw new IllegalArgumentException("Wrong co-ordinates");

Simplification of above conditions:

1. X co-ordinate of TopLeft should be less than that of BottomRight
2. Y co-ordinate of TopLeft should be greater than that of BottomRight

Or you can check this in the constructor Rectangle()

For simpler and language independent explanation, checkout my answer on a similar thread