碰撞检测(碰撞检测算法)干货满满

碰撞检测这个词通常有两种含义，一种是物理含义，用来判断物体之间是否发生接触，从而模拟物体与物体之间的相互作用力;

碰撞检测这个词通常有两种含义，一种是物理含义，用来判断物体之间是否发生接触，从而模拟物体与物体之间的相互作用力；还有一种是数学含义，用来判断物体之间是否相交，即是否有重合的部分这里我们主要讨论自动驾驶运动规划中用到的一些二维碰撞检测方法。

碰撞检测算法在实际应用中，一般可分为两步：粗略碰撞检测精细碰撞检测粗略碰撞检测用来将明显不相交的两个物体快速排除，精细碰撞检测则用来准确判断两个物体是否相交直接对两个物体进行精细碰撞检测是一个十分耗时的工作，且感知模块对物体的检测，通常以矩形（box）或多边形（polygon）的形式用来描述物体的轮廓，因此，在进行精细碰撞检测之前，通常先用包围形的方式来进行粗略碰撞检测。

包围形方法的基本思想是用一个简单的包围形状（圆、矩形）将复杂不规则的物体包围住，当两个包围形不相交时，则两个物体肯定不相交包围形可分为：外接圆形轴对齐包围矩形（Axis Aligned Bounding Box，AABB）。

1、外接圆形使用外接圆的方式来粗略判断是否碰撞是非常快的。只要两个圆形的圆心距离 大于 两个圆的半径之和，则这两个圆不相交。

当然，由于车体通常是一个长方形，使用一个外接圆是非常粗略的，如下图所示，两个车体实际未发生碰撞，但两个外接圆已相交。

为了提高判断的准确度，可以使用多个圆来覆盖长方形，在覆盖长方形的前提下，尽可能减少多余的覆盖区域，如下图所示。

2、轴对齐包围矩形轴对齐包围矩形（Axis Aligned Bounding Box，AABB），即用一个矩形包围车体，且矩形的边与某个坐标轴平行，如下图所示。

采用轴对齐包围矩形的方式用来判断两个车体是否相交，有一个非常好的特性，即对于矩形A 和 矩形B，采用（x_min, x_max, y_min, y_max）的方式来描述该矩形，只要在 X 轴 或 Y 轴上没有重合，则这两个矩形不相交。

在轴对齐包围矩形（Axis Aligned Bounding Box，AABB）基础之上，更为准确的是 转向包围矩形（Oriented Bounding Box，OBB），如下图所示。

OBB 与 AABB 的差别在于物体旋转之后，AABB 的大小会发生改变，保证每条边与某个坐标轴平行；OBB 的大小则不会改变，且将随物体一起旋转OBB 相比 AABB 更接近物体本身的形状，其用到的碰撞检测的算法也要比 AABB 复杂，如分离轴定理（Separating Axis Theorem，SAT）、GJK（Gilbert–Johnson–Keerthi）算法，接下来在精细碰撞检测部分会有详细介绍。