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

2018-06-19 07:37:13

我正在尝试编写一个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）我已经实现了我正确链接的算法，或者如果我确实如何解释这个问题？

有什么建议么？

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. Proof是矛盾的。四个条件中的任何一个都可以保证不存在重叠 ：

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)

德摩根定律说
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

这相当于：

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 >= 。
注3 ：当使用笛卡尔坐标（X，Y）时，此答案基于标准代数笛卡尔坐标（x从左到右，Y从下到上）。显然，在计算机系统可能不同地机械化屏幕坐标的情况下（例如，从上到下或从右到左增加Y），语法将需要相应地调整/

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

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

链接地址: http://www.djcxy.com/p/54401.html

上一篇: Determine if two rectangles overlap each other?

下一篇: Why does my FFT gives a different visualizer output than Windows Media Player?