17

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

它们由[ x0, y0, x1, y1 ]代表矩形左上角和右下角的对表示。或者，您的解决方案可能是[ x0, y0, width, height ]如果它更简单，我可以通过它调整我的函数的参数输入。

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

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

4

5 回答 5

25

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

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

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

于 2013-04-15T10:05:35.227 回答
15

更新

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

原始答案

如果要检查 2 个旋转的矩形是否发生碰撞，则必须在另一个矩形的轴上投影一个矩形角。如果 rectA 的所有投影都命中了 rectB，并且 rectB 投影命中了 rectA，那么这两个矩形就会发生碰撞。

一些投影在这里没有碰撞，两个矩形没有碰撞。 在此处输入图像描述

4 个投影碰到另一个矩形，这 2 个矩形发生碰撞。 在此处输入图像描述

我已经在这个JSFiddle上做了一个演示，以便更多地理解。

您可以检查功能is_collide以获取更多示例

于 2015-04-13T20:31:36.753 回答
5

从另一个网站看这个问题。

如果我们从另一面来看问题（算法），情况就会变得非常简单。

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

最后，两个问题都解决了同一个问题，但第二个问题的答案更容易实现，因为矩形不会重叠仅当一个在另一个下方或一个在另一个更左侧时（对于一个就足够了）在这些情况下会发生，但当然可能会发生两者同时发生 - 这里对逻辑条件“或”的良好理解很重要）。这减少了许多需要在第一个问题上考虑的情况。

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

const areRectanglesOverlap = (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 areRectanglesOverlap = (rect1, rect2) => {

  let [left1, top1, right1, bottom1] = [...rect1],
      [left2, top2, right2, bottom2] = [...rect2];
  
  return !(top1 < bottom2 || top2 < bottom1 || right1 < left2 || right2 < left1);
}
于 2019-01-23T09:19:33.333 回答
3

用点 UL1 和 LR1 给出矩形 1，用点 UR2 和 LR2 给出矩形 2 -

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

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

清除？

在此处输入图像描述

蓝色是 R1，紫色是 R2

于 2013-04-14T22:44:04.573 回答
3

如果 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;
}
于 2014-03-17T13:28:45.990 回答