【算法题】矩形重叠

56 阅读 0 评论 37 点赞

我是靠谱客的博主爱笑未来，最近开发中收集的这篇文章主要介绍【算法题】矩形重叠，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

矩形以列表 [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 之间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rectangle-overlap
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：
根据题意可得当两个矩阵重叠时，其对应边投影到X、Y轴的投影区间必然会相交，因此，我们可由题目所述得出以下结论:

设矩阵一坐标[x1,y1,x2,y2]，矩阵二坐标：[x3,y3,x4,y4]
当
x1 <= x3 < x2 || x3 <= x1 < x4
且
y1 <= y3 < y2 || y3 <= y1 < y4
则两个矩阵X、Y轴投影区间均重叠，即可判断两个矩阵是否重叠

根据思路可写出如下代码：
Go

func isRectangleOverlap(rec1 []int, rec2 []int) bool {
if (rec1[0] <= rec2[0] && rec2[0] < rec1[2]) ||
(rec2[0] <= rec1[0] && rec1[0] < rec2[2]) &&
(rec1[1] <= rec2[1] && rec2[1] < rec1[3]) ||
(rec2[1] <= rec1[1] && rec1[1] < rec2[3]) {
return true
}
return false
}

可以看到以上代码看上去稍微有点复杂。然而，我们需要判断的只是两组矩阵对应的两个区间是否相交，参考：

https://leetcode-cn.com/problems/rectangle-overlap/solution/tu-jie-jiang-ju-xing-zhong-die-wen-ti-zhuan-hua-we/

可得证明两个区间是否相交可以先通过判断两个区间不相交，然后对结果取反即可。

设矩阵一坐标[x1,y1,x2,y2]，矩阵二坐标：[x3,y3,x4,y4]
当
(得出的是矩阵投影到X轴区间不相交的判断结果，对其取反即可判断两个区间是否相交，Y轴同理)
!(x2 <= x3 || x4 <= x1)且!(y2 <= y3 || y4 <= y1)
即可判断两个矩阵是否重叠

func isRectangleOverlap(rec1 []int, rec2 []int) bool {
coverX := !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0])
coverY := !(rec1[3] <= rec2[1] || rec2[3] <= rec1[1])
return coverX && coverY
}

同时，根据德·摩根定律

非(P 或 Q)=(非 P)且(非 Q)

可将上述代码等价转换成以下代码（基本减少一次取反运算）
Go

func isRectangleOverlap(rec1 []int, rec2 []int) bool {
coverX := rec1[2] <= rec2[0] || rec2[2] <= rec1[0]
coverY := rec1[3] <= rec2[1] || rec2[3] <= rec1[1]
return !(coverX || coverY)
}

再去除临时存储变量得：
Go

func isRectangleOverlap(rec1 []int, rec2 []int) bool {
return !(rec1[2] <= rec2[0] ||
rec2[2] <= rec1[0] ||
rec1[3] <= rec2[1] ||
rec2[3] <= rec1[1])
}