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

Question

我正在尝试编写一个C++程序,它从用户那里获取以下输入来构造矩形(2到5之间):高度,宽度,x-pos,y-pos.所有这些矩形将平行于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;  

但是我不太确定(a)我是否实现了我正确链接的算法,或者我是否确实如何解释这个？

有什么建议？

Answer 1

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

或者,使用笛卡尔坐标

(X1为左坐标,X2为右坐标,从左到右增加,Y1为顶部坐标,Y2为底部坐标,从下到上增加)......

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

注意:对于所有具有编辑权限的用户.请停止使用此信息.

假设您有Rect A和Rect B.证明是矛盾的.四个条件中的任何一个都保证不存在重叠:

• COND1.如果A的左边缘位于B的右边缘的右边,那么A就完全在B的右边
• COND2.如果A的右边缘位于B左边缘的左边,那么A则完全在B的左边
• COND3.如果A的上边缘低于B的下边缘,则A完全低于B
• COND4.如果A的下边缘高于B的上边缘,那么A完全高于B

所以非重叠的条件是

Cond1 Or Cond2 Or Cond3 Or Cond4

因此,重叠的充分条件恰恰相反.

Not (Cond1 Or Cond2 Or Cond3 Or Cond4)

De Morgan的法律说
Not (A or B or C or D)与Not A And Not B And Not C And Not D
使用De Morgan一样,我们有

Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4

这相当于:

• 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:计算一个像素的重叠,将该边界<和/或>边界更改为a <=或a 也应该是相当明显的>=.
注3:当使用笛卡尔坐标(X,Y)时,这个答案基于标准代数笛卡尔坐标(x从左到右增加,Y从下到上增加).显然,在计算机系统可能以不同方式机械化屏幕坐标的情况下(例如,从上到下增加Y,或从右到左增加X),语法将需要相应地调整/

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

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

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)

第二个矩形,它不可能与它碰撞.因此,要有一个返回布尔说明天气与矩形冲突的函数,我们只需通过逻辑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);
}

仅在触摸时已经收到肯定结果,我们可以通过"<="和"> ="更改"<"和">".

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

它的工作原理是计算相交矩形的左右边框，然后比较它们：如果右边框等于或小于左边框，则说明交集为空，因此矩形不重叠；如果右边框等于或小于左边框，则说明交集为空，因此矩形不重叠。否则，它会再次尝试使用顶部和底部边框。

与传统的 4 次比较相比，该方法有什么优势？这是关于现代处理器的设计方式。他们有一种叫做分支预测的东西，当比较结果始终相同时，它的效果很好，但否则会带来巨大的性能损失。然而，在没有分支指令的情况下，CPU 的性能相当不错。通过计算交叉点的边界，而不是对每个轴进行两次单独的检查，我们可以保存两个分支，每对一个。

如果第一次比较很可能是错误的，那么四次比较方法的性能可能会优于此方法。不过，这种情况非常罕见，因为这意味着第二个矩形通常位于第一个矩形的左侧，而不是右侧或与之重叠；大多数情况下，您需要检查第一个矩形两侧的矩形，这通常会抵消分支预测的优势。

该方法还可以进一步改进，具体取决于矩形的预期分布：

• 如果您希望检查的矩形主要位于彼此的左侧或右侧，那么上面的方法效果最好。例如，当您使用矩形交集来检查游戏的碰撞时，游戏对象主要水平分布（例如，类似 SuperMarioBros 的游戏），情况可能就是这种情况。
• 如果您希望检查的矩形主要位于彼此的顶部或底部，例如在冰塔类型的游戏中，那么首先检查顶部/底部，最后检查左/右可能会更快：

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

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

Answer 6

问自己相反的问题:我怎样才能确定两个矩形是否完全不相交？显然,矩形B左侧的矩形A不相交.如果A完全在右边.并且类似地,如果A完全在B之上或完全在B之下.在任何其他情况下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);
}

Answer 7

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

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