如何在 JavaScript 或伪代码中查看两个矩形是否相交？

Question

我有两个矩形，无论它们是否相交，我都必须在函数中返回它们。

它们由代表矩形左上角和右下角的

[ x0, y0, x1, y1 ]

对表示。或者，您的解决方案可能是

[ x0, y0, width, height ]

，如果它更简单，我可以通过它调整我的函数的参数输入。

我试图看看矩形A的两个角是否包含在矩形B中，但如果A大于B并且B部分包含在A中，它会说它不重叠。现在我可以尝试 A 和 B，但这似乎是一个糟糕的做法。

我无法预先制作一个大网格并用矩形占据单元格，因为不知道矩形是什么。我只能说它们是无符号整数，最小值为 0，最大值未知。

Answer 1

检查矩形绝对不相交的情况。如果这些情况都不成立，则矩形必须相交。即：

public boolean rectanglesIntersect( 
    float minAx, float minAy, float maxAx, float maxAy,
    float minBx, float minBy, float maxBx, float maxBy ) {
    boolean aLeftOfB = maxAx < minBx;
    boolean aRightOfB = minAx > maxBx;
    boolean aAboveB = minAy > maxBy;
    boolean aBelowB = maxAy < minBy;

    return !( aLeftOfB || aRightOfB || aAboveB || aBelowB );
}

这说明了这个概念，但可以通过内联布尔值来稍微加快速度，以便利用

||

的短路行为

Answer 2

更新

一段时间后，我决定重做一个关于检测两个旋转矩形之间的碰撞的完整答案：如何检测旋转矩形何时相互碰撞

---

原答案

如果你想检查两个旋转的矩形是否碰撞，你必须将一个矩形角投影到另一个矩形的轴上。 如果 rectA 的所有投影都击中了 rectB，并且 rectB 投影击中了 rectA，则两个矩形发生碰撞。

有些投影在这里不发生碰撞，两个矩形不发生碰撞。

4 个投影击中另一个矩形，2 个矩形发生碰撞。

我已经对此 JSFiddle 进行了演示，以便更好地理解。

您可以查看功能

is_collide

了解更多示例

Answer 3

从不同网站查看此事。

如果我们从另一个角度看问题（算法），那么事实证明非常简单。

这意味着我们不是回答“矩形是否重叠？”的问题，而是回答“矩形不重叠吗？”的问题。

最后，这两个问题都解决了同样的问题，但是第二个问题的答案更容易实现，因为只有当一个矩形位于另一个矩形下方或当一个矩形位于另一个矩形的左侧时才重叠（其中一种情况发生就足够了，但当然也可能发生两种情况同时发生——这里对逻辑条件“或”的良好理解很重要）。这减少了第一个问题需要考虑的许多情况。

通过使用适当的变量名称也简化了整个问题：

const doRectanglesOverlap = (rect1, rect2) => {
  let [left1, top1, right1, bottom1] = [rect1[0], rect1[1], rect1[2], rect1[3]],
      [left2, top2, right2, bottom2] = [rect2[0], rect2[1], rect2[2], rect2[3]];
  // The first rectangle is under the second or vice versa
  if (top1 < bottom2 || top2 < bottom1) {
    return false;
  }
  // The first rectangle is to the left of the second or vice versa
  if (right1 < left2 || right2 < left1) {
    return false;
  }
  // Rectangles overlap
  return true;
}

即使 如果我们有不同的矩形表示，也可以通过仅修改定义变量更改的部分来轻松地使上述函数适应它。函数的其他部分保持不变（当然，注释这里其实并不需要，但我添加了它们，以便每个人都能快速理解这个简单的算法）。

上述函数的等价，但可能可读性稍差一些形式可能如下所示：

const doRectanglesOverlap = (rect1, rect2) => {

  let [left1, top1, right1, bottom1] = [...rect1],
      [left2, top2, right2, bottom2] = [...rect2];
  
  return !(top1 < bottom2 || top2 < bottom1 || right1 < left2 || right2 < left1);
}

Answer 4

如果 x 和 y 区域重叠，则两个矩形重叠。如果任何 x 坐标与其他矩形重叠，则会出现重叠。

沿 x 轴，第一个点位于另外两个矩形内，第二个点位于另外两个矩形内，或者两个点位于其他点的相对侧。

function checkRectOverlap(rect1, rect2) {
    /*
     * Each array in parameter is one rectangle
     * in each array, there is an array showing the co-ordinates of two opposite corners of the rectangle
     * Example:
     * [[x1, y1], [x2, y2]], [[x3, y3], [x4, y4]]
     */

    //Check whether there is an x overlap
    if ((rect1[0][0] < rect2[0][0] && rect2[0][0] < rect1[1][0]) //Event that x3 is inbetween x1 and x2
        || (rect1[0][0] < rect2[1][0] && rect2[1][0] < rect1[1][0]) //Event that x4 is inbetween x1 and x2
        || (rect2[0][0] < rect1[0][0] && rect1[1][0] < rect2[1][0])) {  //Event that x1 and x2 are inbetween x3 and x4
        //Check whether there is a y overlap using the same procedure
        if ((rect1[0][1] < rect2[0][1] && rect2[0][1] < rect1[1][1]) //Event that y3 is between y1 and y2
            || (rect1[0][1] < rect2[1][1] && rect2[1][1] < rect1[1][1]) //Event that y4 is between y1 and y2
            || (rect2[0][1] < rect1[0][1] && rect1[1][1] < rect2[1][1])) { //Event that y1 and y2 are between y3 and y4
            return true;
        }
    }
    return false;
}

Answer 5

给出具有点 UL1 和 LR1 的矩形 1 和具有点 UR2 和 LR2 的矩形 2 -

检查 UL1 是否在 r2 中或 LR1 是否在 r2 中（图中的情况 1 和情况 2）。 最后检查 UR2 / LR2 之一是否在 r1 中（图中的情况 3）。

通过检查 x 和 y 是否在矩形 x 和 y 范围的最小值和最大值之间来检查点是否在矩形中。

清楚了吗？

蓝色是R1，紫色是R2