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

我正在尝试编写一个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或Cond2或Cond3或Cond4 

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

 不是（Cond1或Cond2或Cond3或Cond4） 

德摩根定律说
Not (A or B or C or D)与Not A And Not B And Not C And Not D
所以使用德摩根，我们有

 不是Cond1而不是Cond2而不是Cond3而不是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）的情况下，语法将需要相应地调整/

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(Ax, Bx, Bx + B.width) || valueInRange(Bx, Ax, Ax + A.width); bool yOverlap = valueInRange(Ay, By, By + B.height) || valueInRange(By, Ay, Ay + 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) 

的第二个矩形，它不可能碰撞它。 所以要有一个函数返回一个布尔表示矩形碰撞的天气，我们简单地通过逻辑或组合条件并且否定结果：

 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

问自己相反的问题：如何确定两个矩形是否完全不相交？ 显然，完全在矩形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 (ax + a.width <= bx) 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 6

以下是在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 = rx; int ry = ry; 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)); } 

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

Answer 8

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

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）当你画矩形，它很容易拦截重叠。

Answer 10

最简单的方法是

 /** * 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加上其一半的宽度。 那么意味着他们会去碰碰一半。 并以同样的方式向下+一半的高度。 它会碰撞..

Answer 11

我已经实现了一个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; } 

Answer 12

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

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

Answer 13

假设这两个矩形是矩形A和矩形B.设中心为A1和B1（A1和B1的坐标很容易找到），让高度为Ha和Hb，宽度为Wa和Wb，让dx为宽度（x）A1和B1之间的距离，dy是高度（y）A1和B1之间的距离。
现在我们可以说，我们可以说A和B重叠：何时

如果（！（dx> Wa + Wb）||！（dy> Ha + Hb））返回true

Answer 14

我有一个非常简单的解决方案

令x1，y1 x2，y2，l1，b1，l2分别为它们的坐标及其长度和宽度

考虑条件（（x2

现在这些矩形重叠的唯一方法就是如果与x1，y1对角的点位于另一个矩形内，或者类似地与x2，y2对角的点位于另一个矩形内。 这正是上述情况所暗示的。

Answer 15

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) 

它照顾所有可能的情况。

Answer 16

这是从Java程序设计综合版入门的练习3.28开始的。 代码测试两个矩形是否是indenticle，一个是否在另一个之内，另一个是否在另一个之外。 如果没有满足这些条件，则两者重叠。

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

Answer 17

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

Answer 18

Java代码来确定矩形是否彼此接触或重叠
…

  for (int i = 0;i < n;i++) { for (int j = 0;j < n; j++) { if (i != j) { Rectangle rectangle1 = rectangles.get(i); Rectangle rectangle2 = rectangles.get(j); int l1 = rectangle1.l; //left int r1 = rectangle1.r; //right int b1 = rectangle1.b; //bottom int t1 = rectangle1.t; //top int l2 = rectangle2.l; int r2 = rectangle2.r; int b2 = rectangle2.b; int t2 = rectangle2.t; boolean topOnBottom = t2 == b1; boolean bottomOnTop = b2 == t1; boolean topOrBottomContact = topOnBottom || bottomOnTop; boolean rightOnLeft = r2 == l1; boolean leftOnRight = l2 == r1; boolean rightOrLeftContact = leftOnRight || rightOnLeft; boolean leftPoll = l2 <= l1 && r2 >= l1; boolean rightPoll = l2 <= r1 && r2 >= r1; boolean leftRightInside = l2 >= l1 && r2 <= r1; boolean leftRightPossiblePlaces = leftPoll || rightPoll || leftRightInside; boolean bottomPoll = t2 >= b1 && b2 <= b1; boolean topPoll = b2 <= b1 && t2 >= b1; boolean topBottomInside = b2 >= b1 && t2 <= t1; boolean topBottomPossiblePlaces = bottomPoll || topPoll || topBottomInside; boolean topInBetween = t2 > b1 && t2 < t1; boolean bottomInBetween = b2 > b1 && b2 < t1; boolean topBottomInBetween = topInBetween || bottomInBetween; boolean leftInBetween = l2 > l1 && l2 < r1; boolean rightInBetween = r2 > l1 && r2 < r1; boolean leftRightInBetween = leftInBetween || rightInBetween; if ( (topOrBottomContact && leftRightPossiblePlaces) || (rightOrLeftContact && topBottomPossiblePlaces) ) { path[i][j] = true; } } } } 

…

Answer 19

对于那些正在使用中心点和半角尺寸的矩形数据，而不是典型的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)); } 

Answer 20

“如果对每个矩形所面对的两个顶点执行减法x或y坐标，如果结果是相同的符号，那么两个矩形不会重叠”（对不起，我不确定我的翻译是否正确）

资料来源： http : //www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-c​​hong-nhau.html

Answer 21

这个答案应该是最好的答案：

如果矩形重叠，则重叠区域将大于零。 现在让我们找到重叠区域：

如果它们重叠，那么overlap-rect的左边将是max（r1.x1，r2.x1），右边将是min（r1.x2，r2.x2）。 所以重叠的长度将是min（r1.x2，r2.x2）-max（r1.x1，r2.x1）

（r1.x1，r2.x1） – min（r1.x2，r2.x2））*（max（r1.y1，r2.y1） – min（r1.y2， r2.y2））

如果面积= 0，那么他们不重叠。 简单不是吗？