Java如何检查两个矩形是否有交集？

Question

我有多个矩形和一个特殊的选择矩形：选中矩形。我想检查每个矩形是否包含至少一个在选中矩形内的点。以下是一张图片以便清晰理解：

- user2190492

---

Rectangle::intersects 对你可能会有帮助。 - Jeffrey

https://javarevisited.blogspot.com/2016/10/how-to-check-if-two-rectangle-overlap-in-java-algorithm.html - Vishrant

Answer 1

背景：

一个矩形可以通过其对角线来定义。
假设第一个矩形的对角线是(x1, y1)到(x2, y2)。
而另一个矩形的对角线是(x3, y3)到(x4, y4)。

过程：

现在，如果以下任何一种情况为真，则我们可以得出结论：这些矩形不重叠:

1. x3 > x2（或）
2. y3 > y2（或）
3. x1 > x4（或）
4. y1 > y4

否则，它们将重叠！

或者：

如果

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

Leetcode上的样例解法： https://leetcode.com/problems/rectangle-overlap/discuss/468548/Java-check-if-two-rectangles-overlap-at-any-point

- ThePatelGuy

---

这个答案肯定比被接受的答案解释得更好！ - mathakoot

需要一个代码示例来完善答案，让它更加优秀。 - Edd

Answer 2

这将找出矩形是否与另一个矩形重叠:

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

- CodeCamper

---

@ahitt6345 是的，它可以。唯一的问题是如果你尝试旋转你的矩形，那么你需要一个多边形重叠方法。 - CodeCamper

尽管这个解决方案是正确的，我建议查看下面的答案（https://dev59.com/5mAg5IYBdhLWcg3ws8no#32088787）以获得更好的理解。 - mathakoot

Answer 3

我会创建矩形对象，然后使用Rectangle.intersects和Rectangle.contains方法来确定它们是否相交或其中一个是否包含另一个。

由于您有一个大矩形，即选择矩形，这比我想象的还要容易。运行Rectangle.contains，并对所有未被包含的矩形运行Rectangle.intersects，即可得到所需结果。

- Marshall Tigerus

Answer 4

这里有另一个更简单的解决方案：

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

- ThePatelGuy

Answer 5

如果第一个实现了 RectangularShape，第二个是 Rectangle2D，那么你可以简单地使用 RectangularShape.intersects：

selectionRectangle.intersects(otherRectangle)

---

测试形状的内部是否与指定的Rectangle2D的内部相交。

^{来自Oracle Java文档}

- Ky -

Answer 6

我有一个通用的多边形实现，适用于GPS坐标系统，在矩形（简单多边形）上可能有点小题大做；但它可以工作。如果由于某种原因不想使用AWT，那么应该很容易地将此方法适应于您的用例。 https://github.com/jillesvangurp/geogeometry/blob/master/src/main/java/com/jillesvangurp/geo/GeoGeometry.java#L753 (重叠方法)

我的做法就是检查多边形是否有任何被其他多边形包含的点。

对于点的多边形包含，我有一个简单的算法，遍历多边形的边缘来检查点是在内部还是外部O(n)。对于矩形，运行起来应该很便宜。

这种方法的好处是，它适用于任何矩形，也适用于旋转的矩形或更复杂的形状。

- Jilles van Gurp

Answer 7

如果以下条件之一成立，则两个矩形不会重叠。
1）一个矩形在另一个矩形的顶部边缘上方。
2）一个矩形位于另一个矩形左侧边缘的左侧。

请注意，一个矩形可以由两个坐标表示，即左上角和右下角。因此，通常我们会给出以下四个坐标。
l1：第一个矩形的左上角坐标。
r1：第一个矩形的右下角坐标。
l2：第二个矩形的左上角坐标。
r2：第二个矩形的右下角坐标。

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

- GorvGoyl

Answer 8

这个类假设顺序为 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;        
}
}

- user1300214

Answer 9

java.awt.Rectangle 已经内置了 intersects 方法来实现这一点。

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

- Unmitigated