判断两个矩形是否互相重叠?

我试图写一个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)我是否已经正确地实现了我链接的算法，或者如果我确实如何解释这一点?

有什么建议吗?

323056 次浏览
小开
最佳答案 
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。 反证法是证明。四个条件中的任何一个保证不存在重叠:

    <李> Cond1。如果A的左边在B的右边的右边， -那么A完全在B的右边 <李> Cond2。如果A的右边在B的左边的左边， -则A完全在B的左边 <李> Cond3。如果A的上边在B的下边之下， -则A完全低于B <李> Cond4。如果A的下边在B的上边上面， -则A完全大于B

不重叠的条件是

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

Therefore, a sufficient condition for Overlap is the opposite. 

Overlap => 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
相同 所以用De Morgan，我们有

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]

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/

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

我已经实现了c#版本，它很容易转换为c++。

public bool Intersects ( Rectangle rect )
{
float ulx = Math.Max ( x, rect.x );
float uly = Math.Max ( y, rect.y );
float lrx = Math.Min ( x + width, rect.x + rect.width );
float lry = Math.Min ( y + height, rect.y + rect.height );


return ulx <= lrx && uly <= lry;
}
小开

问你自己一个相反的问题:我如何确定两个矩形是否完全不相交?显然，矩形a完全在矩形B的左边不相交。如果A完全在右边。同样，如果A完全高于B或完全低于B，在任何其他情况下，A和B相交。

以下内容可能有bug，但我对算法相当有信心:

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

在问题中，你链接到矩形旋转角度任意时的数学。然而，如果我理解了问题中关于角度的部分，我就会理解为所有的矩形都是相互垂直的。

一般已知重叠面积的公式为:

举个例子:

   1   2   3   4   5   6


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

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

1 2 3 4 6

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

4 * 4

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

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)当你绘制矩形时，很容易截取重叠部分。

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

不要认为坐标表示像素的位置。把它们想象成像素之间。这样，2x2矩形的面积应该是4，而不是9。

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

如果矩形重叠，那么重叠面积将大于零。现在让我们求出重叠区域:

如果重叠，则overlap-rect的左边缘将是max(r1.x1, r2.x1)，右边缘将是min(r1.x2, r2.x2)。所以重叠的长度是min(r1.x2, r2.x2) - max(r1.x1, r2.x1)

所以面积是:

area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))

如果area = 0，则它们不重叠。

很简单，不是吗?

小开

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

在左边……

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

如果只在触摸时得到阳性结果，我们可以将“<”和“>”改为“<=”和“>=”。

小开

下面是如何在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));
}
小开

设这两个矩形是矩形A和矩形b，设它们的中心为A1和B1 (A1和B1的坐标很容易求出来)，设高为Ha和Hb，宽为Wa和Wb，设dx为A1和B1之间的宽度(x)， dy为A1和B1之间的高度(y)。

现在我们可以说我们可以说A和B重叠，当

if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
小开

我有一个很简单的解决办法

设x1, y1x2,y2,l1,b1,l2分别为它们的坐标和长、宽

考虑条件((x2 .

现在，这两个矩形重叠的唯一方式是，如果点(x1,y1)的对角线在另一个矩形内或者类似地，点(x2,y2)的对角线在另一个矩形内。这正是上面的条件所暗示的。

小开

A和B是两个矩形。C是它们的覆盖矩形。

four points of A be (xAleft,yAtop),(xAleft,yAbottom),(xAright,yAtop),(xAright,yAbottom)
four points of A be (xBleft,yBtop),(xBleft,yBbottom),(xBright,yBtop),(xBright,yBbottom)


A.width = abs(xAleft-xAright);
A.height = abs(yAleft-yAright);
B.width = abs(xBleft-xBright);
B.height = abs(yBleft-yBright);


C.width = max(xAleft,xAright,xBleft,xBright)-min(xAleft,xAright,xBleft,xBright);
C.height = max(yAtop,yAbottom,yBtop,yBbottom)-min(yAtop,yAbottom,yBtop,yBbottom);


A and B does not overlap if
(C.width >= A.width + B.width )
OR
(C.height >= A.height + B.height)

它考虑到所有可能的情况。

小开

最简单的方法是

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

首先要记住在计算机中坐标系统是颠倒的。x轴与数学中的相同，但y轴向下增大，向上减小。 如果矩形是从中心画的。 如果x1坐标大于x2加上它的一半宽。然后这意味着他们会互相接触。用同样的方法向下+一半高。它会碰撞..

小开

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

enter image description here

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

这是来自《Java编程入门-综合版》中的练习3.28。该代码测试两个矩形是否缩进，一个矩形是否在另一个矩形内，一个矩形是否在另一个矩形外。如果这些条件都不满足，则两者重叠。

**3.28(几何:两个矩形)编写一个程序，提示用户进入 中心x, y坐标，宽度和高度的两个矩形，并确定 第二个矩形是在第一个矩形的内部还是与第一个矩形重叠，如图所示 如图3.9所示。测试您的程序以覆盖所有情况。 下面是示例运行:

输入r1的中心x坐标，y坐标，宽度和高度:2.5 4 2.5 43 输入r2的中心x坐标，y坐标，宽度和高度:1.5 5 0.5 3 R2在r1

输入r1的中心x坐标，y坐标，宽度和高度:1 2 3 5.5 输入r2的中心x坐标，y坐标，宽度和高度:3 4 4.5 5 R2重叠r1

输入r1的中心x坐标，y坐标，宽度和高度:1 2 3 3 输入r2的中心x坐标，y坐标，宽度和高度:40 45 3 2 R2不重叠r1

import java.util.Scanner;


public class ProgrammingEx3_28 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);


System.out
.print("Enter r1's center x-, y-coordinates, width, and height:");
double x1 = input.nextDouble();
double y1 = input.nextDouble();
double w1 = input.nextDouble();
double h1 = input.nextDouble();
w1 = w1 / 2;
h1 = h1 / 2;
System.out
.print("Enter r2's center x-, y-coordinates, width, and height:");
double x2 = input.nextDouble();
double y2 = input.nextDouble();
double w2 = input.nextDouble();
double h2 = input.nextDouble();
w2 = w2 / 2;
h2 = h2 / 2;


// Calculating range of r1 and r2
double x1max = x1 + w1;
double y1max = y1 + h1;
double x1min = x1 - w1;
double y1min = y1 - h1;
double x2max = x2 + w2;
double y2max = y2 + h2;
double x2min = x2 - w2;
double y2min = y2 - h2;


if (x1max == x2max && x1min == x2min && y1max == y2max
&& y1min == y2min) {
// Check if the two are identicle
System.out.print("r1 and r2 are indentical");


} else if (x1max <= x2max && x1min >= x2min && y1max <= y2max
&& y1min >= y2min) {
// Check if r1 is in r2
System.out.print("r1 is inside r2");
} else if (x2max <= x1max && x2min >= x1min && y2max <= y1max
&& y2min >= y1min) {
// Check if r2 is in r1
System.out.print("r2 is inside r1");
} else if (x1max < x2min || x1min > x2max || y1max < y2min
|| y2min > y1max) {
// Check if the two overlap
System.out.print("r2 does not overlaps r1");
} else {
System.out.print("r2 overlaps r1");
}


}
}
小开 
bool Square::IsOverlappig(Square &other)
{
bool result1 = other.x >= x && other.y >= y && other.x <= (x + width) && other.y <= (y + height); // other's top left falls within this area
bool result2 = other.x >= x && other.y <= y && other.x <= (x + width) && (other.y + other.height) <= (y + height); // other's bottom left falls within this area
bool result3 = other.x <= x && other.y >= y && (other.x + other.width) <= (x + width) && other.y <= (y + height); // other's top right falls within this area
bool result4 = other.x <= x && other.y <= y && (other.x + other.width) >= x && (other.y + other.height) >= y; // other's bottom right falls within this area
return result1 | result2 | result3 | result4;
}
小开

对于那些使用中心点和一半大小的矩形数据的人，而不是典型的x,y,w,h或x0,y0,x1,x1，下面是你可以这样做:

#include <cmath> // for fabsf(float)


struct Rectangle
{
float centerX, centerY, halfWidth, halfHeight;
};


bool isRectangleOverlapping(const Rectangle &a, const Rectangle &b)
{
return (fabsf(a.centerX - b.centerX) <= (a.halfWidth + b.halfWidth)) &&
(fabsf(a.centerY - b.centerY) <= (a.halfHeight + b.halfHeight));
}
小开 
struct point { int x, y; };


struct rect { point tl, br; }; // top left and bottom right points


// return true if rectangles overlap
bool overlap(const rect &a, const rect &b)
{
return a.tl.x <= b.br.x && a.br.x >= b.tl.x &&
a.tl.y >= b.br.y && a.br.y <= b.tl.y;
}
小开

这是一个用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);

(注意将&&更改为单个&)


提交答案