Java check if two rectangles overlap at any point

Question

I have multiple rectangles and one special rectangle: the selection rect. I want to check for each rectangle if the rectangle contains at least one point which is inside the selection rectangle. Here is an image for clarity:

Saylor

Rectangle::intersects would be of use to you. – Seaware

javarevisited.blogspot.com/2016/10/… – Cheap

Answer 1

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

Snowdrop

@ahitt6345 Yes, it does. The only issue is if you tried to rotate your rectangles in which case you would need a polygon overlap method. – Snowdrop

Though the solution is correct - I'd recommend this answer down below to get better understanding. – Whitehead

Answer 2

Background:

A rectangle can be defined by just one of its diagonal.
Let's say the first rectangle's diagonal is (x1, y1) to (x2, y2)
And the other rectangle's diagonal is (x3, y3) to (x4, y4)

Proceeding:

Now, if any of these 4 conditions is true, we can conclude that the rectangles are not overlapping:

1. x3 > x2 (OR)
2. y3 > y2 (OR)
3. x1 > x4 (OR)
4. y1 > y4

Otherwise, they overlap!

Alternatively:

The rectangles overlap if

(x1 < x4) && (x3 < x2) && (y1 < y4) && (y3 < y2)

Sample solution on Leetcode: https://leetcode.com/problems/rectangle-overlap/discuss/468548/Java-check-if-two-rectangles-overlap-at-any-point

Cerecloth

This one surely has better explanation than the accepted answer! – Whitehead

This could do with a code example to to make it a great answer – Albeit

Answer 3

I would make Rectangle objects and then use the Rectangle.intersects and Rectangle.contains methods to determine if they intersect or if one contains the other.

Since you have one big rectangle, that is the selection rectangle, this is even easier than I thought. Run Rectangle.contains, and for all rectangles that aren't contained, run Rectangle.intersects, and you have what you are seeking.

Burleson

Answer 4

Here's another simpler solution:

    // Left x 
    int leftX = Math.max(x1, x3);
    // Right x
    int rightX = Math.min(x2, x4);
    // Bottom y
    int botY = Math.max(y1, y3);
    // TopY
    int topY = Math.min(y2, y4);

    if (rightX > leftX && topY > botY)
       return true;

Cerecloth

Answer 5

If the first one implements RectangularShape and the second one is a Rectangle2D, you can simply use RectangularShape.intersects:

selectionRectangle.intersects(otherRectangle)

---

Tests if the interior of the Shape intersects the interior of a specified Rectangle2D

^{From the Oracle Java docs}

Erythroblast

Answer 6

I have a generic implemententation for polygons in the gps coordinate system, which may be a bit overkill for rectangles (which are simple polygons); but it will work. It should be fairly straightforward to adapt the approach to your usecase if for whatever reason you don't want to use AWT.

https://github.com/jillesvangurp/geogeometry/blob/master/src/main/java/com/jillesvangurp/geo/GeoGeometry.java#L753 (overlap method)

What I do there is simply check if the polygons have any points that are contained by the other polygon.

For polygon containment of points, I have a simple algorithm that walks the edges of the polygon to check if the point is inside or outside O(n). For rectangles it should be cheap to run.

The nice thing about this approach it will work for any rectangles and also rotated rectangles or more complex shapes.

Lasalle

Answer 7

Two rectangles do not overlap if one of the following conditions is true.
1) One rectangle is above top edge of other rectangle.
2) One rectangle is on left side of left edge of other rectangle.

Note that a rectangle can be represented by two coordinates, top left and bottom right. So mainly we are given following four coordinates.
l1: Top Left coordinate of first rectangle.
r1: Bottom Right coordinate of first rectangle.
l2: Top Left coordinate of second rectangle.
r2: Bottom Right coordinate of second rectangle.

class Point
{
    int x, y;
};

// Returns true if two rectangles (l1, r1) and (l2, r2) overlap
bool doOverlap(Point l1, Point r1, Point l2, Point r2)
{
    // If one rectangle is on left side of other
    if (l1.x > r2.x || l2.x > r1.x)
        return false;

    // If one rectangle is above other
    if (l1.y < r2.y || l2.y < r1.y)
        return false;

    return true;
}

Merchandising

Answer 8

This class assumes the ordering left<=right, top<=bottom, x1<=x2, y1<=y2:

public class Rect
{
int left, right, bottom, top;

Rect(int left, int top, int right, int bottom)
{
    this.left = left;
    this.right = right;
    this.top = top;
    this.bottom = bottom;
}

boolean overlap(int x1, int y1, int x2, int y2)
{
    // if one rectangle is to the left or right, then there can be no overlap
    if(x2 < left || right < x1)
        return false;

    // the x values overlap, but the y values may still lie outside the rectangle

    // if one rectangle is above or below, then there can be no overlap
    if(y2 < top || bottom < y1)
        return false;

    // otherwise we must overlap !
    return true;        
}
}

Illsorted

Answer 9

java.awt.Rectangle has a built-in intersects method for this.

import java.awt.Rectangle;
// ...
Rectangle r1 = new Rectangle(
    0 /* top left x */, 0 /* top left y */, 
    5 /* width */, 7 /* height */
);
Rectangle r2 = new Rectangle(4, 5, 3, 3);
System.out.println(r1.intersects(r2)); // true

Chincapin