确定两个矩形是否重叠？

Question

我正在尝试编写一个C++程序，从用户那里获取以下输入来构建矩形（2到5个）：高度、宽度、x位置、y位置。所有这些矩形都将与x轴和y轴平行存在，也就是说它们的所有边缘都将具有0或无穷大的斜率。

我尝试实现了这个问题中提到的方法，但我运气不太好。

我的当前实现方式如下:

// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2

// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2]; 
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];

int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;  

然而，我不太确定我是否正确实现了我链接的算法，或者如果我确实实现了它，该如何解释它?

有什么建议吗？

- Rob Burke

---

我认为解决你的问题不需要进行任何乘法运算。 - Scott Evernden

如果您需要旋转矩形的答案，我已经创建了一个包含所有步骤的答案：https://dev59.com/D0wGtIcB2Jgan1znloNA（它是用Javascript编写的，但可以轻松地在C++中复制）。 - Arthur

Answer 1

if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
     RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) 

或者，使用笛卡尔坐标系

(其中X1为左坐标，X2为右坐标，从左到右递增，Y1为顶部坐标，Y2为底部坐标，从下到上递增 -- 如果您的坐标系统不是这样的[例如，大多数计算机的Y方向是反转的]，请交换以下比较)...

if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
    RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1) 

假设你有矩形A和矩形B。 证明是通过反证法的。以下四种情况中的任意一种都可以保证不存在重叠：

• 条件1。如果A的左边缘在B的右边缘右侧，     - 那么A完全在B的右边
• 条件2。如果A的右边缘在B的左边缘左侧，     - 那么A完全在B的左边
• 条件3。如果A的上边缘在B的下边缘下方，     - 那么A完全在B的下面
• 条件4。如果A的下边缘在B的上边缘上方，     - 那么A完全在B的上面

因此，不重叠的条件为

非重叠 => 条件1 或 条件2 或 条件3 或 条件4

因此，Overlap的充分条件是相反的。

Overlap => NOT (条件1 或 条件2 或 条件3 或 条件4)

德摩根定律说
Not (A or B or C or D)与Not A And Not B And Not C And Not D是一样的
因此使用De Morgan，我们有

Not 条件1 And Not 条件2 And Not 条件3 And Not 条件4

这等价于：

• A的左边缘在B的右边缘左侧，[RectA.Left < RectB.Right]，并且
• A的右边缘在B的左边缘右侧，[RectA.Right > RectB.Left]，并且
• A的顶部在B的底部之上，[RectA.Top > RectB.Bottom]，并且
• A的底部在B的顶部之下[RectA.Bottom < RectB.Top]

注意1：显然，这个原则同样适用于任意维度。
注意2：很明显，要计算重叠一个像素的情况，只需将该边界上的<和/或>更改为<=或>=。
注意3：当使用笛卡尔坐标（X，Y）时，此答案基于标准代数笛卡尔坐标（x从左到右增加，Y从底部到顶部增加）。 显然，如果计算机系统以不同的方式实现屏幕坐标（例如，从上到下递增Y或从右到左递增X），则语法将相应调整。

- Charles Bretana

---

如果您很难想象它是如何起作用的，我在http://silentmatt.com/intersection.html上制作了一个示例页面，您可以拖动矩形并查看比较。 - Matthew Crumley

你不觉得你正在使用硬约束吗？如果两个矩形恰好在边缘重叠，怎么办？难道你不应该考虑<=、>=吗？ - N. F.

根据你的链接中的语句“对于 A.Y1 < B.Y2 和 A.Y2 > B.Y1”，是否应该反转大于号和小于号？ - NikT

我不得不交换最后两个比较运算符的<和>，以使其正常工作。 - DataGreed

不，答案如所述是正确的。它基于使用标准笛卡尔坐标系。如果您使用了不同的系统（例如，垂直向下为Y轴正方向），则需要进行相应的调整。 - Charles Bretana

Answer 2

struct rect
{
    int x;
    int y;
    int width;
    int height;
};

bool valueInRange(int value, int min, int max)
{ return (value >= min) && (value <= max); }

bool rectOverlap(rect A, rect B)
{
    bool xOverlap = valueInRange(A.x, B.x, B.x + B.width) ||
                    valueInRange(B.x, A.x, A.x + A.width);

    bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
                    valueInRange(B.y, A.y, A.y + A.height);

    return xOverlap && yOverlap;
}

- eJames

---

@e.James 我猜最后的 B.height 应该是 A.height。 - mat_boy

"min"和"max"是<Windows.h>中的保留关键字。您可以通过执行#undef min和#undef max或使用不同的参数名称来解决此问题。 - mchiasson

如果您使用得很频繁，可以将valueInRange替换为#define BETWEEN(value,min,max) \ (\ value > max ? max : ( value < min ? min : value )\ )。 - Ratata Tata

@Nemo 实际上，检查 xOverlap 是一维的；rectOverlap 是二维的。可以使用循环将其扩展到 N 维。 - Justme0

我不是100%确定，但它看起来完全错误。我的情况下，rects：（3,0,2,3）和（3,3,2,2）。它们不重叠，但这个函数“说”它们是。第一个被接受的答案对这种情况很有效。（我使用基于网格的int矩形） - AvrDragon

@AvrDragon 在 valueInRange 函数中，如果我们使用 >= 和 <=，那么如果边缘接触，我们会计算重叠部分。如果我们想要"EdgeTouch 不重叠"，那么就用 > 和 < 替换它。 - b m gevariya

Answer 3

struct Rect
{
    Rect(int x1, int x2, int y1, int y2)
    : x1(x1), x2(x2), y1(y1), y2(y2)
    {
        assert(x1 < x2);
        assert(y1 < y2);
    }

    int x1, x2, y1, y2;
};

bool
overlap(const Rect &r1, const Rect &r2)
{
    // The rectangles don't overlap if
    // one rectangle's minimum in some dimension 
    // is greater than the other's maximum in
    // that dimension.

    bool noOverlap = r1.x1 > r2.x2 ||
                     r2.x1 > r1.x2 ||
                     r1.y1 > r2.y2 ||
                     r2.y1 > r1.y2;

    return !noOverlap;
}

- David Norman

---

不错！应用德摩根定律得到：r1.x1 <= r2.x2 && r2.x1 <= r1.x2 && r1.y1 <= r2.y2 && r2.y1 <= r1.y2。 - Borzh

Answer 4

检查一个矩形是否完全在另一个矩形外部更容易，因此如果它在左边...

(r1.x + r1.width < r2.x)

或者在右侧...

(r1.x > r2.x + r2.width)

或者在顶部...

(r1.y + r1.height < r2.y)

或者在底部...

(r1.y > r2.y + r2.height)

对于第二个矩形，它不可能与第一个矩形相撞。因此，要编写一个返回布尔值的函数来判断矩形是否相撞，我们只需通过逻辑或（logical OR）将条件组合起来并取反结果：

function checkOverlap(r1, r2) : Boolean
{ 
    return !(r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height);
}

为了在仅触摸时就能获得积极的结果，我们可以将“<”和“>”更改为“<=”和“>=”。

- Björn Kechel

---

将德摩根定律应用于它。 - Borzh

Answer 5

以下是使用C++快速检查两个矩形是否重叠的方法：

return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
    && std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

它通过计算相交矩形的左右边界，然后进行比较来工作：如果右边界等于或小于左边界，则意味着相交为空，因此矩形不重叠；否则，它将再次尝试使用上下边界。相对于传统的四次比较方法，这种方法的优点在于现代处理器的设计。当比较结果始终相同时，分支预测（branch prediction）可以有效发挥作用，但如果结果不同，则会有巨大的性能损失。然而，在缺少分支指令的情况下，CPU表现得相当好。通过计算相交边界而不是针对每个轴进行两个单独的检查，我们节省了两个分支，即每一对矩形一个分支。如果第一次比较有很高的假阳性概率，那么四次比较方法可能会胜过这种方法。不过，这种情况非常罕见，因为这意味着第二个矩形大多数时候在第一个矩形的左侧，而不是右侧或重叠；而且通常需要检查第一个矩形两侧的矩形，这通常会抵消分支预测的优势。这种方法可以根据期望的矩形分布进一步改进：如果您期望被检查的矩形主要在彼此左侧或右侧，则上述方法效果最佳。例如，在检查游戏碰撞时，游戏对象主要水平分布（例如类似于《超级马里奥兄弟》的游戏）可能会是这种情况。如果您期望被检查的矩形主要在彼此顶部或底部，则首先检查顶部/底部，然后最后检查左侧/右侧可能更快。

return std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom)
    && std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right);

• 如果相交的概率接近于不相交的概率，那么最好选择完全无分支的替代方案：

return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
     & std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

（请注意将&&更改为单个&）

- Pedro Gimeno

---

请大家将此回答置顶。 - InkGolem

Answer 6

假设您已经像这样定义了矩形的位置和大小：

我使用C++实现如下：

class Vector2D
{
    public:
        Vector2D(int x, int y) : x(x), y(y) {}
        ~Vector2D(){}
        int x, y;
};

bool DoRectanglesOverlap(   const Vector2D & Pos1,
                            const Vector2D & Size1,
                            const Vector2D & Pos2,
                            const Vector2D & Size2)
{
    if ((Pos1.x < Pos2.x + Size2.x) &&
        (Pos1.y < Pos2.y + Size2.y) &&
        (Pos2.x < Pos1.x + Size1.x) &&
        (Pos2.y < Pos1.y + Size1.y))
    {
        return true;
    }
    return false;
}

根据上面给出的图形，以下是一个示例函数调用：

根据上述图示的示例函数调用：

DoRectanglesOverlap(Vector2D(3, 7),
                    Vector2D(8, 5),
                    Vector2D(6, 4),
                    Vector2D(9, 4));

在 if 代码块内部的比较将会像下面这样:

if ((Pos1.x < Pos2.x + Size2.x) &&
    (Pos1.y < Pos2.y + Size2.y) &&
    (Pos2.x < Pos1.x + Size1.x) &&
    (Pos2.y < Pos1.y + Size1.y))
                 ↓  
if ((   3   <    6   +   9    ) &&
    (   7   <    4   +   4    ) &&
    (   6   <    3   +   8    ) &&
    (   4   <    7   +   5    ))

- hkBattousai

---

如果想要检查所有条件是否成立，请使用快速检查。如果想将矩形的接触计算为重叠，请将所有的<（小于）更改为<=（小于或等于）。 - b m gevariya

Answer 7

反过来问自己：如何确定两个矩形完全不相交？显然，如果矩形A完全在矩形B的左侧，则它们不相交。同样，如果A完全在右侧，或者完全在上方或下方，也是如此。在其他任何情况下，A和B都会相交。

接下来的内容可能存在错误，但我对算法非常有信心：

struct Rectangle { int x; int y; int width; int height; };

bool is_left_of(Rectangle const & a, Rectangle const & b) {
   if (a.x + a.width <= b.x) return true;
   return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
   return is_left_of(b, a);
}

bool not_intersect( Rectangle const & a, Rectangle const & b) {
   if (is_left_of(a, b)) return true;
   if (is_right_of(a, b)) return true;
   // Do the same for top/bottom...
 }

bool intersect(Rectangle const & a, Rectangle const & b) {
  return !not_intersect(a, b);
}

- coryan

Answer 8

以下是Java API中的实现方式：

public boolean intersects(Rectangle r) {
    int tw = this.width;
    int th = this.height;
    int rw = r.width;
    int rh = r.height;
    if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
        return false;
    }
    int tx = this.x;
    int ty = this.y;
    int rx = r.x;
    int ry = r.y;
    rw += rx;
    rh += ry;
    tw += tx;
    th += ty;
    //      overflow || intersect
    return ((rw < rx || rw > tx) &&
            (rh < ry || rh > ty) &&
            (tw < tx || tw > rx) &&
            (th < ty || th > ry));
}

- Lyle

---

请注意，在C++中，检测溢出的那些测试不起作用，因为有符号整数溢出是未定义的。 - Ben Voigt

Answer 9

在问题中，您链接到了矩形以任意角度旋转时的数学。然而，如果我理解问题中关于角度的部分，我认为所有矩形都彼此垂直。

一个通用的重叠面积公式是：

使用以下示例：

1 2 3 4 5 6

1 +---+---+ | | 2 + A +---+---+ | | B | 3 + + +---+---+ | | | | | 4 +---+---+---+---+ + | | 5 + C + | | 6 +---+---+

1）将所有x坐标（左和右）收集到列表中，然后对其进行排序并删除重复项。

1 3 4 5 6

2）将所有y坐标（上和下）收集到列表中，然后对其进行排序并删除重复项。

1 2 3 4 6

3）通过唯一x坐标之间的间隙数*唯一y坐标之间的间隙数创建一个二维数组。

4 * 4

4）将所有矩形绘制到此网格中，并递增它出现在的每个单元格的计数：

1 3 4 5 6

1 +---+ | 1 | 0 0 0 2 +---+---+---+ | 1 | 1 | 1 | 0 3 +---+---+---+---+ | 1 | 1 | 2 | 1 | 4 +---+---+---+---+ 0 0 | 1 | 1 | 6 +---+---+

5）在绘制矩形时，拦截重叠部分很容易。

- Will

Answer 10

struct Rect
{
   Rect(int x1, int x2, int y1, int y2)
   : x1(x1), x2(x2), y1(y1), y2(y2)
   {
       assert(x1 < x2);
       assert(y1 < y2);
   }

   int x1, x2, y1, y2;
};

//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
    return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
           r1.y1 < r2.y2 && r2.x1 < r1.y2;
}

//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
    return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
           r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}

- Adam Tegen