自动驾驶领域在路径规划任务中会需要进行碰撞检测，以及在一些去重算法中，也经常会需要进行碰撞检测。
旋转矩阵
自动驾驶领域中，BEV视角下的车通常都会用一个旋转矩形来表示。目前笔者碰到一个需要是对于多个视角下（多个相机）的检测框，它们在BEV视角下用旋转矩形来表示，只要检测到它们有重叠，就要进行去重。
分离轴定律
两个凸多边形物体，如果我们能找到一个轴，使得两个在物体在该轴上的投影互不重叠，则这两个物体之间没有碰撞发生，该轴为 Separating Axis
一般会去检测垂直于多边形每条边的轴，此时分离轴定律变成：两个多边形在所有轴上的投影都发生重叠，则判定为碰撞；否则，没有发生碰撞。
因此可以使用分离轴定律来进行旋转矩形的碰撞检测。
实现思路
- 一个矩形有四条边，因此需要检测四个轴，但是四条边是两两平行的，所以检测两条轴即可。两两矩形都要互相判断，因此需要检测的轴是 4 个。
- 矩形在某个轴上的投影只需要将四个顶点投影到此轴上即可，将投影的最小值点和最大值点连线即为此矩形在此轴上的投影。
- 如果两个矩形在某个轴上的投影不重叠，则说明两个矩形不相交。
伪代码
def Project(point, axis):
return Dot(point, axis)
def Dot(point, axis):
return point.x * axis.x + point.y * axis.y
def Min(projs):
return min(projs)
def Max(projs):
return max(projs)
def Collision(rect1, rect2):
axes = [rect1.axis1, rect1.axis2, rect2.axis1, rect2.axis2]
for (axis in axes)
{
projs_1 = []
for (corner in rect1)
{
projs_1.append(Project(corner, axis))
}
projs_2 = []
for (corner in rect2)
{
projs_2.append(Project(corner, axis))
}
if (Max(projs_1) < Min(projs_2) || Max(projs_2) < Min(projs_1))
{
return false
}
}
return true