本文主要分析 aplollo 代码中关于障碍物碰撞检测相关算法，该算法通过将车辆抽象成二维矩形盒 (Box)，建立点与矩形盒、线段与矩形盒、矩形盒与矩形盒的碰撞检测算法。

1.点与矩形盒

关于点与矩形盒子的位置关系，可能情况为点在矩形盒内，点在矩形边框上和点在矩形盒外部，如果点在矩形盒的外部，可以求取点到矩形盒的距离值.

1.1 判定点是否在矩形盒内

如下图所示，红色圆点与矩形盒的关系如下图左侧，为了便于判定红点是否在矩形盒内，将下图左侧整体按照航向角顺时针旋转 \theta 角度，得到下图右侧状态。此时，只需要判定红点的坐标 (d x, d y) 是否满足 |d x|<=\text { length }_{half} 或者 /|d y|<=\text { width }_{helf} ，则说明红点位于矩形盒内.

1.2 判定点是否在矩形盒边界上

如下图所示，红色圆点与矩形盒的关系如下图左侧，为了便于判定红点是否在矩形盒内，将下图左侧整体按照航向角顺时针旋转 \theta 角度，得到下图右侧状态。此时，只需要判定红点的坐标 (d x, d y) 是否满足 \left||d x|-\text { length }_{half}\right|==0 或者 \left||d y|-\text { width }_{h}\right|==0 则说明点红点位于矩形盒边界上。

1.3 计算点到矩形盒的距离

如下图所示，点到矩形盒的距离可以分为如下三种情况:

2.线段与矩形盒

2.1 判定线段与矩形盒是否交叠

关于某线段与矩形盒关系的判定，先计算线段的长度，如果线段的长度为 0, 则可以把该线段当作一个点，利用点和矩形盒的距离来判断是否交叠；如果线段的长度不为 0, 则先进行线段与矩形盒的粗判定，即线段的起始点与终点是否落在矩形盒的一边，如下图所示，表示线段位于矩形盒一边的四种情况。如果线段不满足如下关系，则交叠关系可以通过距离来判断.

2.2 计算线段到矩形盒的距离

2.2.1 区域划分

如下图所示，将矩形盒的外围分成如下 8 个区域，关于区域的划分，可以根据线段起始点和终点分别在

x 轴和 y 轴投影得到 \left(p_x, p_y\right) 。以车辆中心作为坐标原点 o，四个角点可以计算表示为：

\left(b o x_x, b o x_y\right),\left.\left(b o x_x,-b o x_y\right),( -b o x_x, b o x_y\right),\left(-b o x_x,-b o x_y\right)其中，根据点在x 轴的投影，可以将区域值表示如下:

g_x= \begin{cases}1 & \text { if }\left(p_x>=b o x_x\right), \\ 0 & \text { if }\left(-b o x_x<p_x<b o x_x\right), \\ -1 & \text { if }\left(p_x<=-b o x_x\right),\end{cases}

根据上图，区域的值表示如下:

区域	gx	gy
1	1	1
2	0	1
3	-1	1
4	-1	0
5	-1	-1
6	0	-1
7	1	-1
8	1	0

其中，区域 (0,0) 位于矩形盒内，即线段中有一点位于矩形盒内，必定与矩形盒交叠。因此去除点位于区域 (0,0) 的情形，考虑线段两个端点与矩形盒的关系共有 8 \times 8 = 64种情况

2.2.2 对称变换

首先将起始点通过x 轴和 y 轴对称变换，将落在区域 3,4,5,6,7 的点变换到区域 1,2,8 中。对于区域 2 和 8, 进行 xy 轴对称变换，将区域 2 变换为区域 8. 所以经过三种轴对称转换后，起始点将会落在区域 1 和区域 8 两种区域状态.

区域1

当起始点位于区域 1, 则将终点进行 xy 轴对称变换，将位于区域 2,3,4 的终点，对称变换到区域 8,7,6 中。因此关于终点的所在区域的情况只需考虑落在区域 1,8,7,6,5, 这五个区域的情况；

区域8

当起始点位于区域 8, 对终点进行 y 轴对称变换，将位于轴下方的区域变换到 y 轴上方，即区域 5,6,7 对称变换到区域 3,2,1. 因此终点只需考虑区域 8,1,2,3,4 五个区域的请况.

通过上述对称变换，可以将原先的 64 种线段与矩形的关系减少到 10 种，从而减少相关计算量.

2.2.3 线段与矩形盒距离计算

如下图所示：

线段起始点与矩形盒边角点之间的向量表示为 \overrightarrow{s b}

起始点与终点之间的向量表示为 \overrightarrow{s g}

当 \overrightarrow{s b} \cdot \overrightarrow{s g}<=0 时，即下图浅绿色表示的区域，此时，线段与矩形盒的距离表示为 |\overrightarrow{s b}|

当 \overrightarrow{s b} \cdot \overrightarrow{s g}>=\overrightarrow{s g} \cdot \overrightarrow{s g} ，即下图浅绿色区域，线段与矩形盒的距离可以表示为 |\overrightarrow{s b}-\overrightarrow{s g}|

当上述条件都不满足时，即位于下图浅黄色区域，线段与矩形盒的距离可以表示为 |\overrightarrow{s b}| \sin \theta可使用向量叉乘得到 \frac{\overrightarrow{s b} \times \overrightarrow{s g}}{|\overrightarrow{s g}|}

起始点区域 1

当终点位于区域 1 时，直接使用上述方法计算距离值；
当终点位于区域 8 时，先判定起始点与终点的x 轴坐标的关系，当起始点坐标的 x 轴坐标大于终点的x 轴坐标，则距离值为 \left|g_x-b_x\right| , 否则按照上述方法计算距离值；
当终点位于区域 7 时，先判定起始点与终点的x 轴坐标的关系，选取不同的矩形盒的边角点；
当终点位于区域 6 时，先判定线段与矩形盒是否交叠，如下图所示，通过计算向量叉乘 \overrightarrow{s g} \times \overrightarrow{s b} , 判断线段是否与矩形盒交叠

当终点位于区域 5 时，矩形盒的边角点分两种，首先判断与右下角的边角点的关系，如果不交叠则直接按上述方法计算距离值，否则判断与左上角边角点的关系，如果无交叠则按上述方法计算距离值.

起始点区域 8

当终点位于区域 1 时，如下图所示，先判定起始点与终点的x 轴坐标的关系，如果起始点小于终点，则距离值为 \left|g_x-b_x\right| , 否则计算线段与矩形盒的距离；

当终点位于区域 8 时，选取起始点与终点中离矩形盒最近的点到矩形盒的距离，即 \left|\min \left(s_x, g_x\right)-b_x\right|
当终点位于区域 2 和 3 时，如下图所示，通过右上边角点与线段的起始点，终点形成的矢量，进行矢量叉乘，通过数值的正负判断线段是否与矩形盒交叠；