平面上两个轴对齐矩形,如何判断是否相交?
哪些公司问过
答案要点
- 用两个对角点表示矩形,先规整成 min/max 坐标
- 不相交条件:x3>x2 或 x4<x1 或 y3>y2 或 y4<y1,取反即相交
- 等价于两个轴上的投影区间都重叠
- 边或角接触是否算相交要确认,决定用 < 还是 <=
- 规整坐标后与 y 轴方向无关,复杂度 O(1)
易错点
- 没规整对角点顺序,输入反过来时判断出错
- 只检查一个矩形的顶点是否在另一个内部,漏掉十字交叉的情况
- 边界接触的处理没和面试官确认
面试官常见追问
- 如何求两个矩形的相交面积?
- 如果矩形可以旋转怎么判断?
- 大量矩形两两求交怎么优化?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。