两个矩形相交

Question

我有两个矩形，每个矩形由4个值描述：

左侧位置X、顶部位置Y、宽度W和高度H：

X1, Y1, H1, W1
X2, Y2, H2, W2

矩形不会旋转，就像这样：

+--------------------> X axis
|
|    (X,Y)      (X+W, Y)
|    +--------------+
|    |              |
|    |              |
|    |              |
|    +--------------+
v    (X, Y+H)     (X+W,Y+H)

Y axis

如何最好地确定两个矩形的交集是否为空？

- Majid Laissi

---

可能是检测两个矩形相交的算法？的重复问题。 - Perception

这是一个解决方案的开端：http://gamedev.stackexchange.com/questions/25818/how-to-implement-a-2d-collision-detection-for-android#40235 - Ray Tayek

在另一个问题中，涉及到“以任意角度”的感知问题。而我的问题更简单，因此我正在寻找一个更简单的答案。 - Majid Laissi

@RayTayek 这确实是一个开始，谢谢 :) - Majid Laissi

可能是重复的问题：如何确定两个矩形是否重叠？ - Dakusan

Answer 1

if (X1+W1<X2 or X2+W2<X1 or Y1+H1<Y2 or Y2+H2<Y1):
    Intersection = Empty
else:
    Intersection = Not Empty

如果您有四个坐标 - ((X,Y),(A,B)) 和 ((X1,Y1),(A1,B1)) - 而不是两个加上宽度和高度，它会像这样：

if (A<X1 or A1<X or B<Y1 or B1<Y):
    Intersection = Empty
else:
    Intersection = Not Empty

- Tao Peng

---

如果一个矩形完全在另一个矩形内部，则不起作用。 - Ankesh Anand

@AnkeshAnand，你能详细说明一下吗？当我运行这个算法时，它似乎可以很好地处理“完全内部”的情况。 - Topher Hunt

@TopherHunt 在这种情况下它检测到了一个不存在的交叉点。 - Ankesh Anand

好的，明白了。谢谢你澄清。我之前没有注意到这一点，因为在我的情况下，我关心的是重叠，而这个算法完美地处理了它。 - Topher Hunt

“@AnkeshAnand的意思是交集指布尔交集——即矩形1的某个区域是否与矩形2的某个区域重叠，而不是矩形的“边界线”是否相交。” - d7samurai

Answer 2

最佳实例...

/**
 * Check if two rectangles collide
 * x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle
 * x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle
 */
boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2)
{
  return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2);
}

还有一种方法可以查看这个链接...并自己编写代码。

- Zar E Ahmer

Answer 3

如果两个矩形具有相同的尺寸，您可以执行以下操作：

if (abs (x1 - x2) < w && abs (y1 - y2) < h) {
    // overlaps
}

- user8246772

Answer 4

如果矩形的左下角和右上角的坐标为：
(r1x1，r1y1)，（r1x2，r1y2）对于rect1 和
(r2x1，r2y1)，（r2x2，r2y2）对于rect2
（Python代码如下）

    intersect = False
    for x in [r1x1, r1x2]:
        if (r2x1<=x<=r2x2):
            for y in [r1y1, r1y2]:
                if (r2y1<=y<=r2y2):
                    intersect = True
                    return intersect
                else:
                    for Y in [r2y1, r2y2]:
                        if (r1y1<=Y<=r1y2):
                            intersect = True
                            return intersect
        else:  
            for X in [r2x1, r2x2]:
                if (r1x1<=X<=r1x2):
                    for y in [r2y1, r2y2]:
                        if (r1y1<=y<=r1y2):
                            intersect = True
                            return intersect
                        else:
                            for Y in [r1y1, r1y2]:
                                if (r2y1<=Y<=r2y2):
                                    intersect = True
                                    return intersect
    return intersect

- jepaljey

Answer 5

Rectangle = namedtuple('Rectangle', 'x y w h')

def intersects(rect_a: Rectangle, rect_b: Rectangle):
    if (rect_a.x + rect_a.w < rect_b.x) or (rect_a.x > rect_b.x + rect_b.w) or (rect_a.y + rect_a.h < rect_b.y) or (rect_a.y > rect_b.y + rect_b.h):
        return False

    else:
        return True

- Marina

---

你的答案可以通过添加更多支持信息来改进。请[编辑]以添加进一步详细信息，例如引文或文献资料，以便其他人可以确认你的答案是否正确。您可以在帮助中心找到有关编写好答案的更多信息。 - Community

Answer 6

圆形方法更为直观。我是指当您将一个圆定义为中心点和半径时。这里的情况也是一样的，除了您有一个水平半径（宽度/2）和一个垂直半径（高度/2），以及水平距离和垂直距离各有两个条件。

abs(cx1 – cx2) <= hr1 + hr2 && abs(cy1 - cy2) <= vr1 + vr2

如果您需要排除不相交的边的情况，请过滤掉那些一个矩形在两个维度上都更小且与更大的矩形之间距离不足（在中心之间）以到达其边缘的情况。

abs(cx1 – cx2) <= hr1 + hr2 && abs(cy1 - cy2) <= vr1 + vr2 &&
!(abs(cx1 – cx2) < abs(hr1 - hr2) && abs(cy1 - cy2) < abs(vr1 - vr2) && sign(hr1 - hr2) == sign(vr1 – vr2))

- Stepan Smirnov

Answer 7

我刚刚尝试了一个C程序并写了以下内容。

#include<stdio.h>

int check(int i,int j,int i1,int j1, int a, int b,int a1,int b1){
    return (\
    (((i>a) && (i<a1)) && ((j>b)&&(j<b1))) ||\ 
    (((a>i) && (a<i1)) && ((b>j)&&(b<j1))) ||\ 
    (((i1>a) && (i1<a1)) && ((j1>b)&&(j1<b1))) ||\ 
    (((a1>i) && (a1<i1)) && ((b1>j)&&(b1<j1)))\
    );  
}
int main(){
    printf("intersection test:(0,0,100,100),(10,0,1000,1000) :is %s\n",check(0,0,100,100,10,0,1000,1000)?"intersecting":"Not intersecting");
    printf("intersection test:(0,0,100,100),(101,101,1000,1000) :is %s\n",check(0,0,100,100,101,101,1000,1000)?"intersecting":"Not intersecting");
    return 0;
}

- Balamurugan A

Answer 8

使用坐标系，其中（0,0）是左上角。

我考虑了垂直和水平滑动窗口的术语，并想出了以下内容：

(B.Bottom > A.Top && B.Top < A.Bottom) && (B.Right > A.Left && B.Left < A.Right)

如果将DeMorgan定律应用于以下内容，则会得到上述内容：

Not (B.Bottom < A.Top || B.Top > A.Bottom || B.Right < A.Left || B.Left > A.Right)

1. B在A上方
2. B在A下方
3. B在A左侧
4. B在A右侧

- Darrel Lee

Answer 9

如果( X1<=X2+W2 && X2<=X1+W1 && Y1>=Y2-H2 && Y2>=Y1+H1 ) 相交

在问题中，Y是顶部位置。

注意：此解决方案仅适用于矩形与X/Y轴对齐的情况。

- Suresh

---

这意味着它不是一个通用解决方案。 - Enamul Hassan