一切从leetcode836. 矩形重叠说起
给出两个矩形rec1/rec2的左下角和右上角坐标,如rec1 = [0, 0, 3, 3]表示左下角顶点坐标(0, 0)和右上角坐标(3, 3)
判断两个矩形是否存在重叠
我一开始的解法是从边与边的位置关系入手,先判断水平方向上是否有重叠,再判断垂直方向上是否有重叠:
class Solution:
def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
# 先找出两个矩形的相对位置,分出左矩形和右矩形
if rec1[0] <= rec2[0]:
left_rec = rec1
right_rec = rec2
else:
left_rec = rec2
right_rec = rec1
# 如果左矩形的右边小于等于右矩形的左边,显然不可能重叠
if left_rec[2] <= right_rec[0]:
return False
# 否则,再观察上下边的关系
else:
# 上下边互相错开,不重叠
if left_rec[1] >= right_rec[3] or left_rec[3] <= right_rec[1]:
return False
# 否则重叠
else:
return True
进阶
这题实际上使用了分离轴定理
分离轴定理:设平面内存在2个凸多边形图形,如果从任意角度对这两个图形进行投影,得到的投影都不存在间隙,则它们存在重叠(发生碰撞);若任一角度下的投影存在间隙,则它们不重叠(不发生碰撞),而这个间隙恰好能够塞入一条直线,这条直线就是所谓的分离轴
定理的算法伪代码:
设这两个图形分别有m和n条边,遍历这(m+n)条边,每条边的方向就是可能放置分离轴的方向;取每条边的法线,将这两个图形投影在对应的法线上,如果投影存在间隙,则说明可以在对应边的方向放置一条分离轴,2者不发生碰撞。若顺利遍历完所有边而投影没有空隙,则发生碰撞
如图所示:
就本题而言,因为2个图形都是矩形,虽然共有8条边,但在方向上不是x方向就是y方向,因此我们只需要检查这两个方向是否能够塞入分离轴即可
class Solution:
def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
# 通过x轴投影来检查y方向是否能插入分离轴
# 通过y轴投影来检查x方向是否能插入分离轴
if min(rec1[2], rec2[2]) - max(rec1[0], rec2[0]) > 0 and min(rec1[3], rec2[3]) - max(rec1[1], rec2[1]) > 0:
return True
return False
写到这里,可以看到,在最开始的方法中,先通过边关系判断y轴方向是否分离,在通过边关系判断x轴方向是否分离,已然是“分离轴定理”的雏形,但未成系统
注:另外,还可以通过两矩形中心的距离关系判断是否碰撞,不再赘述