C++ 确定两个矩形是否相互重叠？

Determine if two rectangles overlap each other?

提问by Rob Burke

I am trying to write a C++ program that takes the following inputs from the user to construct rectangles (between 2 and 5): height, width, x-pos, y-pos. All of these rectangles will exist parallel to the x and the y axis, that is all of their edges will have slopes of 0 or infinity.

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

I've tried to implement what is mentioned in thisquestion but I am not having very much luck.

我已尝试实施此问题中提到的内容，但我运气不佳。

My current implementation does the following:

我当前的实现执行以下操作：

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

However I'm not quite sure if (a) I've implemented the algorithm I linked to correctly, or if I did exactly how to interpret this?

但是，我不太确定 (a) 我是否已经正确实现了链接到的算法，或者我是否确实如何解释它？

Any suggestions?

有什么建议？

回答by Charles Bretana

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

or, using Cartesian coordinates

或者，使用笛卡尔坐标

(With X1 being left coord, X2 being right coord, increasing from left to rightand Y1 being Top coord, and Y2 being Bottom coord, increasing from bottom to top-- if this is not how your coordinate system [e.g. most computers have the Y direction reversed], swap the comparisons below) ...

（X1 是左坐标，X2 是右坐标，从左到右增加，Y1 是顶坐标，Y2 是底坐标，从下到顶增加——如果这不是你的坐标系[例如大多数计算机都有Y 方向反转]，交换下面的比较）...

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

Say you have Rect A, and Rect B. Proof is by contradiction. Any one of four conditions guarantees that no overlap can exist:

假设你有矩形 A 和矩形 B。证明是矛盾的。四个条件中的任何一个都保证不存在重叠：

• Cond1. If A's left edge is to the right of the B's right edge, - then A is Totally to right Of B
• Cond2. If A's right edge is to the left of the B's left edge, - then A is Totally to left Of B
• Cond3. If A's top edge is below B's bottom edge, - then A is Totally below B
• Cond4. If A's bottom edge is above B's top edge, - then A is Totally above B

• 条件 1。如果 A 的左边缘在 B 的右边缘的右侧，那么 A 完全在 B 的右侧
• 条件 2。如果 A 的右边缘在 B 左边缘的左侧，则 - 则 A 完全在 B 的左侧
• 条件 3。如果 A 的顶部边缘低于 B 的底部边缘， - 那么 A 完全低于 B
• 条件 4。如果 A 的底边高于 B 的顶边， - 那么 A 完全高于 B

So condition for Non-Overlap is

所以非重叠的条件是

NON-Overlap => Cond1 Or Cond2 Or Cond3 Or Cond4

Therefore, a sufficient condition for Overlap is the opposite.

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

Overlap => NOT (Cond1 Or Cond2 Or Cond3 Or Cond4)

De Morgan's law says
Not (A or B or C or D)is the same as Not A And Not B And Not C And Not D
so using De Morgan, we have

德摩根定律说
Not (A or B or C or D)的和Not A And Not B And Not C And Not D
使用德摩根一样，我们有

Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4

This is equivalent to:

这相当于：

• A's Left Edge to left of B's right edge, [RectA.Left < RectB.Right], and
• A's right edge to right of B's left edge, [RectA.Right > RectB.Left], and
• A's top above B's bottom, [RectA.Top > RectB.Bottom], and
• A's bottom below B's Top [RectA.Bottom < RectB.Top]

• A 的左边缘到 B 的右边缘左侧，[ RectA.Left < RectB.Right]，和
• A 的右边缘在 B 的左边缘右侧，[ RectA.Right > RectB.Left]，和
• A 的顶部高于 B 的底部，[ RectA.Top > RectB.Bottom]，和
• A 的底部低于 B 的顶部 [ RectA.Bottom < RectB.Top]

Note 1: It is fairly obvious this same principle can be extended to any number of dimensions.
Note 2: It should also be fairly obvious to count overlaps of just one pixel, change the <and/or the >on that boundary to a <=or a >=.
Note 3: This answer, when utilizing Cartesian coordinates (X, Y) is based on standard algebraic Cartesian coordinates (x increases left to right, and Y increases bottom to top). Obviously, where a computer system might mechanize screen coordinates differently, (e.g., increasing Y from top to bottom, or X From right to left), the syntax will need to be adjusted accordingly/

注 1：很明显，同样的原则可以扩展到任意数量的维度。
注 2：计算仅一个像素的重叠，将该边界上的<and/或 the更改>为 a<=或 a也应该是相当明显的>=。
注 3：这个答案，当使用笛卡尔坐标 (X, Y) 时基于标准代数笛卡尔坐标（x 从左到右增加，Y 从下到上增加）。显然，如果计算机系统可能会以不同方式机械化屏幕坐标（例如，从上到下增加 Y，或从右到左增加 X），则需要相应地调整语法/

回答by e.James

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

回答by David Norman

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

回答by Bj?rn Kechel

It is easier to check if a rectangle is completly outside the other, so if it is either

检查一个矩形是否完全在另一个矩形之外更容易，所以如果它是

on the left...

在左边...

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

or on the right...

或者在右边...

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

or on top...

或者在上面...

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

or on the bottom...

或者在底部...

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

of the second rectangle, it cannot possibly collide with it. So to have a function that returns a Boolean saying weather the rectangles collide, we simply combine the conditions by logical ORs and negate the result:

的第二个矩形，它不可能与它碰撞。因此，要获得一个返回布尔值的函数，表示矩形发生碰撞，我们只需通过逻辑 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);
}

To already receive a positive result when touching only, we can change the "<" and ">" by "<=" and ">=".

为了仅在触摸时已经收到肯定的结果，我们可以将“<”和“>”更改为“<=”和“>=”。

回答by hkBattousai

Suppose that you have defined the positions and sizes of the rectangles like this:

假设您已经定义了矩形的位置和大小，如下所示：

My C++ implementation is like this:

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

An example function call according to the given figure above:

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

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

The comparisons inside the ifblock will look like below:

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    ))

回答by coryan

Ask yourself the opposite question: How can I determine if two rectangles do not intersect at all? Obviously, a rectangle A completely to the left of rectangle B does not intersect. Also if A is completely to the right. And similarly if A is completely above B or completely below B. In any other case A and B intersect.

问自己相反的问题：如何确定两个矩形是否根本不相交？显然，完全位于矩形 B 左侧的矩形 A 不相交。同样，如果 A 完全向右。同样，如果 A 完全高于 B 或完全低于 B。在任何其他情况下，A 和 B 相交。

What follows may have bugs, but I am pretty confident about the algorithm:

以下内容可能有错误，但我对算法非常有信心：

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

回答by Lyle

Here's how it's done in the Java API:

下面是它在 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));
}

回答by Will

In the question, you link to the maths for when rectangles are at arbitrary angles of rotation. If I understand the bit about angles in the question however, I interpret that all rectangles are perpendicular to one another.

在这个问题中，您链接到矩形处于任意旋转角度时的数学。但是，如果我理解问题中关于角度的一点，我会解释所有矩形都相互垂直。

A general knowing the area of overlap formula is:

一般知道重叠面积公式是：

Using the example:

使用示例：

   1   2   3   4   5   6

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

1) collect all the x coordinates (both left and right) into a list, then sort it and remove duplicates

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

1 3 4 5 6

2) collect all the y coordinates (both top and bottom) into a list, then sort it and remove duplicates

2）将所有y坐标（顶部和底部）收集到一个列表中，然后对其进行排序并删除重复项

1 2 3 4 6

3) create a 2D array by number of gaps between the unique x coordinates * number of gaps between the unique y coordinates.

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

4 * 4

4) paint all the rectangles into this grid, incrementing the count of each cell it occurs over:

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) As you paint the rectangles, its easy to intercept the overlaps.

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

回答by Adam Tegen

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

回答by Mike Dunlavey

Don't think of coordinates as indicating where pixels are. Think of them as being between the pixels. That way, the area of a 2x2 rectangle should be 4, not 9.

不要将坐标视为指示像素所在的位置。将它们视为在像素之间。这样，2x2 矩形的面积应该是 4，而不是 9。

bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
               && (A.Bottom >= B.Top || B.Bottom >= A.Top));