矩阵重叠（Java实现）

矩阵重叠（Java实现）

题目：
矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
给出两个矩形，判断它们是否重叠并返回结果。
示例 1：
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true

示例 2：
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false

提示：
两个矩形 rec1 和 rec2 都以含有四个整数的列表的形式给出。
矩形中的所有坐标都处于 -10^9 和 10^9 之间。
x 轴默认指向右，y 轴默认指向上。
你可以仅考虑矩形是正放的情况。

我的解法是：穷举法，把所有的情况都考虑在内，写了蛮久的，考虑的情况好多~

package Day45;

/**
 * @Author Zhongger
 * @Description 矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
 * 如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
 * 给出两个矩形，判断它们是否重叠并返回结果。
 * @Date  2020.3.18
 */
public class IsRectangleOverlapSolution {

    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        int ax1=rec1[0],ay1=rec1[1],ax2=rec1[2],ay2=rec1[3]; //第一个矩形
        int bx1=rec2[0],by1=rec2[1],bx2=rec2[2],by2=rec2[3]; //第二个矩形
        if (bx1<=ax1&&by1<=ay1){
            if (bx2>ax1&&by2>ay1){
                return true;
            }else {
                return false;
            }
        }
        if (bx1<=ax1&&by1>ay1&&by1<ay2){
            if (by2>by1&&by2>ay1&&bx2>ax1){
                return true;
            }else {
                return false;
            }
        }
        if (bx1<=ax1&&by1>ay1) {
            return false;
        }
        if (bx1>ax1&&bx1<ax2&&by1<ay1){
            if (bx2>bx1&&by2>=ay1){
                return true;
            }else {
                return false;
            }

        }
        if (bx1>ax1&&bx1<ax2&&by1>ay1&&by2<ay2){
            return true;
        }
        if (bx1>ax1&&bx1<ax2&&by1>=ay2){
            return false;
        }
        if (bx1>=ax2){
            return false;
        }

        return true;
    }

}

一次提交就AC了，纪念一下。

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

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

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

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

我们就得到区间不重叠的条件：e1 <= s2 || e2 <= s1。将条件取反即为区间重叠的条件。

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

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