算法步骤与图解

葛立恒扫描法的示意图。

第一步：找到最下边的点，如果有多个点纵坐标相同的点都在最下方，则选取最左边的。在右图中这个点是P。这一步只需要扫描一遍所有的点即可，时间复杂度为。

第二步：将所有的点按照相对于第一步中的得到的点P的极角大小进行排序。注意这一步并不需要真的通过计算反三角函数来获取与x轴夹角的大小。可以直接使用该点与P点连线的斜率，或者由P点到该点向量的与沿x轴单位向量的点积来减少计算量。可以使用诸如快速排序、堆排序之类的算法进行排序，时间复杂度为。

第三步：维护一个栈，以保存当前的凸包。按第二步中排序得到的结果，依次将点加入到栈中，如果正在考虑的点与栈顶的两个点不是“向左转”的，就表明当前栈顶的点并不在凸包上，而我们需要将其弹出栈，重复这一个过程直到正在考虑的点与栈顶的两个点是“向左转”的。右边的图解给出了“向左转”和“向右转”的示意：

刚开始的两个点P、A直接入栈。

在点B加入时，P->A->B就构成左转，因此直接加入点B即可。

接下来加入点C，A->B->C还是构成左转，因此直接加入点C。

继续加入点D时，B->C->D就变成右转了，此时可以观察到如果将BD连线，C将被包含在多边形的内部，因此点C出栈。注意需要继续检查A->B->D是左转还是右转，如果还是右转的话B点需要继续出栈，以此类推。这个例子比较简单，A->B->D已经是左转了，D点可以入栈。

最后回到P点，B->D->P是左转，算法完成，所求凸包为四边形PABD。

另外，如果发现三点共线的情况，算法可以考虑将其视为左转或者右转。这取决于究竟只是要求凸包的边界，还是要找到在凸包边界上所有的点。

我们需要简单地计算两个向量的有向面积，即两个向量的叉乘的结果来判断两个向量的相对位置。

假设三个点分别是 ，则它们的有向面积为 。如果其结果为0，这三个点是共线的；如果其结果为正，这三个点是向左转的；如果其结果为负，则它们是向右转的。

时间复杂度

排序的复杂度为。尽管它的主循环看起来是的时间复杂度，但由于每个点要多次在栈中查找当且仅当其相对与栈顶的点是“向右转”的，这个过程实际上是的时间复杂度，并且每一个点至多被考虑两次，而每个点只在点产生一个“向左转”时被访问一次（因为算法进行到点之后，点由于产生了一个“右转”而被删去），因此，总的时间复杂度由排序时间决定，即

伪代码

定义：

# 当ccw函数的值为正的时候，三个点为“左转”（counter-clockwise turn），如果是负的，则是“右转”的，而如果 # 为0，则三点共线，因为ccw函数计算了由p1,p2,p3三个点围成的三角形的有向面积 function ccw(p1, p2, p3): return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)

然后结果存在数组内：