凸包可视为碰撞集合体的早小包围体。这里介绍两种算法

1.Andrew算法

对于一个点集，首先选择点集中最靠左的两个点，产生当前凸包的第一条边。然后开始向右扩展，（分上下两条路向右扩展，这里先只介绍上半部分）

如果考察的下一个顶点位于边集当前边的右侧，则该点暂定为凸包上的顶点，并加入到边集中，如果下一个点位于当前边的左侧，则该店位于凸包的外部，并处于错误状态，此时剔除边集中的最后一个顶点，并开始下一个顶点，直到出现位于边集中当前边右侧的顶点。

2.Quickhull算法

Andrew算法在2D空间内工作良好，但是在3D空间内并不适用。

快包算法是先获取顶点集的包围和，一般情况下可以确定4个端点，分别位于包围盒的四条边上。作为断点，上述4个点位于凸包并构成了首次逼近。进一步考察在当前凸包外部的顶点，对于现在获得的四边形，计算边外部距离最远的顶点（如果存在），则此点必定是凸包上的顶点，那么此时边的两个顶点和这一个新的顶点构成了一个三角形。然后形成一个新的凸包，如此迭代下去，直到所有的顶点都在凸包内。