我们选择了迭代的方法，希望能够得到高效计算凸包的算法，如图9-8所示。首先，根据最后找到的两个凸包点连成的线段，在非凸包点中，计算出角度偏差最小的点，这就是下一个得到的凸包点。当计算出的部分凸包包含h个点时，我们需要计算n-h个点的夹角，然后才能找出哪个是下一个凸包点，很显然每一步都是必不可少的。
图 9-7 凸包扫描详解 图 9-8 凸包的增量式构建Andrew凸包扫描算法将整个问题分成两个部分，分别构建一个上部凸包和一个下部凸包。首先，点集P中所有的点按照x坐标排序（x坐标相同时，对y坐标进行排序）。图9-8中的点已经按照x坐标从左至右标上了数字。上部凸包从P中的最左边两个点开始构建。凸包扫描算法首先对上部凸包进行扩展，在P中找到这样一个点p，排序后，其前一个位置即上部凸包的最后一个点Li。
如果三个点Li-1、Li和p组成的两条线段形成了一个右折，那么凸包扫描算法将会把这个点p加入到这个凸包中。这里计算了一个叉积cp=(Li.x-Li-1.x)(p.y-Li-1.y)-(Li.y-Li-1.y)(p.x-Li-1.x)，等价于计算图9-9中的3×3的矩阵。如果cp＜0，那么这三个点组成的线段形成了一个右拐，凸包扫描算法继续进行。如果cp=0（也就是说三点共线）或者cp＞0（三点组成的线段形成了一个左拐），那么中间的点Li将会从凸包中删除，这是为了维护凸多边形的性质。凸包扫描算法计算出上部凸包之后，按照类似的方法计算出下部凸包（递减x来选择点），最后将这两个凸包合并在一起。
图 9-9 检查这三个点是否组成了一个右折凸包扫描算法的行为如图9-7所示。我们可以看到算法在从左到右访问P中的每个点时，还是做出了一些错误的决定。但是在最后一步，算法不断地删除掉最后三个点中不满足条件的中点，从而纠正了之前犯下的错误。
输入/输出
输入
平面上的二维点集P。
输出
一个有序的表L，其包含组成凸包的h个顶点，这些顶点的顺序是顺时针顺序。点L0，L1，……，Lh-1组成的多边形便是凸包，h是点的数目，这个凸包有h条边：＜L0，L1＞，＜L1，L2＞，……，＜Lh-1，L0＞。
假设
为了避免平凡解，我们假设|P|≥3。而且没有两个点会过于接近。如果两个点太过接近，而且如果一个点属于凸包，那么凸包扫描算法将会错误地选择一个无效的凸包点（或者抛弃一个有效的凸包点），但是这种误差可以忽略不计。