矩形重叠

标签: 几何 数学

难度: Easy

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

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

给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。

示例 1：

输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true

示例 2：

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

示例 3：

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

提示：

  • rect1.length == 4
  • rect2.length == 4
  • -109 <= rec1[i], rec2[i] <= 109
  • rec1 和 rec2 表示一个面积不为零的有效矩形

Submission

运行时间: 22 ms

内存: 15.9 MB

from typing import List

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        # 提取矩形rec1和rec2的坐标
        x1, y1, x2, y2 = rec1
        x3, y3, x4, y4 = rec2
        
        # 检查两个矩形是否在水平或垂直方向上分离
        if x1 >= x4 or x3 >= x2 or y1 >= y4 or y3 >= y2:
            return False
        
        # 如果两个矩形没有分离，则它们重叠
        return True

from typing import List

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        # 提取矩形rec1和rec2的坐标
        x1, y1, x2, y2 = rec1
        x3, y3, x4, y4 = rec2
        
        # 检查两个矩形是否在水平方向上重叠
        if x1 >= x4 or x3 >= x2:
            return False
        
        # 检查两个矩形是否在垂直方向上重叠
        if y1 >= y4 or y3 >= y2:
            return False
        
        # 如果两个矩形在水平和垂直方向上都重叠，则返回True
        return True

Explain

此题解的思路是通过判断两个矩形是否在水平或垂直方向上完全分离来确定它们是否重叠。对于两个矩形 rec1 和 rec2，它们分别由两个对角顶点坐标 (x1, y1, x2, y2) 和 (x3, y3, x4, y4) 定义。通过比较这些顶点的坐标，我们可以轻松判断出这两个矩形是否在任何一个方向上分离： 1. 如果 rec1 在 rec2 的左侧或右侧则不重叠，即当 x1 >= x4 或 x3 >= x2。 2. 如果 rec1 在 rec2 的上方或下方则不重叠，即当 y1 >= y4 或 y3 >= y2。 只有当这两个条件都不满足时，即矩形在水平和垂直方向上都存在重叠，我们才认为两个矩形重叠。

时间复杂度: O(1)

空间复杂度: O(1)

from typing import List

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        # Extract the coordinates of rectangles rec1 and rec2
        x1, y1, x2, y2 = rec1
        x3, y3, x4, y4 = rec2
        
        # Check if one rectangle is to the left or right of the other
        if x1 >= x4 or x3 >= x2:
            return False
        
        # Check if one rectangle is above or below the other
        if y1 >= y4 or y3 >= y2:
            return False
        
        # If neither condition is met, the rectangles overlap
        return True

Explore

在矩形的几何属性中，矩形的边总是与坐标轴平行或垂直。因此，两个矩形是否重叠可以完全通过它们在x轴和y轴上的投影来判断。如果两个矩形在x轴或y轴的投影都不重叠，那么这两个矩形在二维空间中也不会重叠。对角线方向的条件不需要单独考虑，因为它不会影响矩形在水平或垂直方向上的重叠情况。

是的，这个条件考虑了矩形边界重合的情况。在这种情况下，如果两个矩形的边缘恰好对齐（即x1等于x4或x3等于x2），它们在水平方向上没有内部空间重叠，因此被视为不重叠。这种定义通常用于处理矩形重叠的问题，确保仅当两个矩形在水平或垂直方向上有实际重叠时，才认为它们重叠。

是的，这个逻辑可以处理所有的垂直非重叠情况。这种判断方式确保了如果一个矩形完全在另一个矩形的上方或下方，它们在垂直方向上不会重叠。这里同样包括了边界接触的情况，即如果一个矩形的底部恰好与另一个矩形的顶部对齐，也被视为不重叠。

实际上，这个问题非常关键。通常，我们假设矩形的坐标是以规范的方式给出的，即第一个点是左下角，第二个点是右上角。如果坐标点的输入顺序不一致，我们需要在算法实现中先处理这些坐标，确保它们是规范的。这可能涉及到对每个矩形的坐标进行排序或调整，以确保x1、y1总是小于或等于x2、y2，这样才能正确地应用重叠判断逻辑。