836. 矩形重叠

• 难度：简单
• 本题涉及算法：
• 思路：检查位置 检查区域
• 类似题型:

题目 836. 矩形重叠

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。

如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。

给出两个矩形，判断它们是否重叠并返回结果

解题思路一 三种情况

• 1. rec1[0]>=rec2[2] 不可能相交
• 1. rec1[2]<=rec2[0] 不可能相交
• 1. x轴相交情况下 在判断 y 轴 y轴也有三种情况 判断方法一样

代码

python

class Solution(object):
    def isRectangleOverlap(self, rec1, rec2):
        """
        :type rec1: List[int]
        :type rec2: List[int]
        :rtype: bool
        """
        if rec1[0]>=rec2[2] or rec1[2]<=rec2[0]:
            return False
        else:
            if rec1[1]>=rec2[3] or rec1[3]<=rec2[1]:
                return False
            else:
                return True

java

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        return !(rec1[2] <= rec2[0] ||   // left
                 rec1[3] <= rec2[1] ||   // bottom
                 rec1[0] >= rec2[2] ||   // right
                 rec1[1] >= rec2[3]);    // top
    }
}

解题思路二 检查区域

• 当 min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]) 时，这两条线段有交集
• 同理可以得到，当 min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]) 时，这两条线段有交集

  class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        return (Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]) &&
                Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]));
    }
  }
  

解题思路三

矩形重叠要考虑的情况很多，两个矩形的重叠可能有好多种不同的形态。这道题如果用蛮力做的话，很容易遗漏掉某些情况，导致出错。

矩形重叠是二维的问题，所以情况很多，比较复杂。为了简化问题，我们可以考虑将二维问题转化为一维问题。既然题目中的矩形都是平行于坐标轴的，我们将矩形投影到坐标轴上：

矩形投影到坐标轴上，就变成了区间。稍加思考，我们发现：两个互相重叠的矩形，它们在 xx 轴和 yy 轴上投影出的区间也是互相重叠的。这样，我们就将矩形重叠问题转化成了区间重叠问题。

区间重叠是一维的问题，比二维问题简单很多。我们可以穷举出两个区间所有可能的 6 种关系：

可以看到，区间的 6 种关系中，不重叠只有两种情况，判断不重叠更简单。假设两个区间分别是 [s1, e1] 和 [s2, e2] 的话，区间不重叠的两种情况就是 e1 <= s2 和 e2 <= s1。

这样，我们就可以写出判断矩形重叠的代码了：

代码

java

public class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        boolean x_overlap = !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0]);
        boolean y_overlap = !(rec1[3] <= rec2[1] || rec2[3] <= rec1[1]);
        return x_overlap && y_overlap;
        // boolean s1 = (rec2[0]-rec1[2])*(rec2[2]-rec1[0])<0;
        // boolean s2 = (rec2[1]-rec1[3])*(rec2[3]-rec1[1])<0;
        // return  s1&&s2;
    }
}