【教程】矩形重叠检测 -- 分离轴定理的应用

假设现在提供了两个矩形的起始行，起始列，结束行和结束列（提供坐标点本质上也是一样的判断逻辑），要求判断两个矩形是否重叠。

这个问题乍一看似乎比较简单，无非就是判断两个矩形是否存在边的交叠，但是要完整判断所有情况，那么必须抽象出一个判断条件来涵盖所有可能性。

矩形重叠检测，换一个角度可以理解为图形的碰撞检测，而基于超平面分离的分离轴定理可以很好的用在矩形重叠检测上。

这里关于超平面定理和分离轴定理不进行赘述，仅说明分离轴定理如何用在矩形重叠检测中。

判断条件

从经验分析，两个矩形重叠无非也就是这四种情况（完全重叠为其极端场景）

我们规定矩形上面的边为起始行，矩形左边的列为起始列，矩形下面的行为结束行，矩形右边的列为结束列。

同时，这里我们规定两个矩形如果边重叠，也被视为重叠。

因此我们不难总结出当同时满足如下条件时，我们可以说两个矩形重叠了：

1. A 的起始行 <= B 的结束行
2. A 的起始列 <= B 的结束列
3. A 的结束行 >= B 的起始行
4. A 的结束列 >= B 的起始列

以上就是分离轴定理在矩形重叠检测中的应用。

代码实现

现在提供 A，B 两个矩形的起始行，起始列，结束行和结束列，我们来判断两个矩形是否重叠。

#include <iostream>
#include <vector>using namespace std;bool IsOverLap(vector<int>& A, vector<int>& B) {if (A[0] <= B[2] &&A[1] <= B[3] &&A[2] >= B[0] &&A[3] >= B[1]) return true;return false;
}int main() {vector<int> A = {0, 1, 3, 5}; // 起始行 起始列 结束行 结束列vector<int> B = {1, 3, 6, 6};cout << IsOverLap(A, B) << endl; // 重叠B = {2, 7, 4, 7};cout << IsOverLap(A, B) << endl; // 不重叠return 0;
}