碰撞检测算法之包围形法

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

碰撞检测算法在实际应用中，一般可分为两步：

• 粗略碰撞检测
• 精细碰撞检测

粗略碰撞检测用来将明显不相交的两个物体快速排除，精细碰撞检测则用来准确判断两个物体是否相交。
直接对两个物体进行精细碰撞检测是一个十分耗时的工作，且感知模块对物体的检测，通常以矩形（box）或多边形（polygon）的形式用来描述物体的轮廓，因此，在进行精细碰撞检测之前，通常先用包围形的方式来进行粗略碰撞检测。
包围形方法的基本思想是用一个简单的包围形状（圆、矩形）将复杂不规则的物体包围住，当两个包围形不相交时，则两个物体肯定不相交。包围形可分为：

• 外接圆形
• 轴对齐包围矩形（Axis Aligned Bounding Box，AABB）

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