
_START_ARTICLE_
葛立恆掃描法
_START_PARAGRAPH_
葛立恒扫描法（Graham's scan）是一种计算一组的平面点的凸包的算法，时间复杂度为。以在1972年发表该算法的葛立恒命名。
_START_SECTION_
时间复杂度
_START_PARAGRAPH_
排序的复杂度为。尽管它的主循环看起来是的时间复杂度，但由于每个点要多次在栈中查找当且仅当其相对与栈顶的点是“向右转”的，这个过程实际上是的时间复杂度，并且每一个点至多被考虑两次，而每个点只在点产生一个“向左转”时被访问一次（因为算法进行到点之后，点由于产生了一个“右转”而被删去），因此，总的时间复杂度由排序时间决定，即
_START_SECTION_
伪代码
_START_PARAGRAPH_
定义：_NEWLINE__NEWLINE_   # 当ccw函数的值为正的时候，三个点为“左转”（counter-clockwise turn），如果是负的，则是“右转”的，而如果# 为0，则三点共线，因为ccw函数计算了由p1,p2,p3三个点围成的三角形的有向面积function ccw(p1, p2, p3):_NEWLINE_       return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)_NEWLINE_然后结果存在points数组内：_NEWLINE__NEWLINE_   let N           = number of points_NEWLINE_   let points[N+1] = the array of points_NEWLINE_   swap points[1] with the point with the lowest y-coordinate_NEWLINE_   sort points by polar angle with points[1]_NEWLINE_   # points[0] 是结束循环的标记点let points[0] = points[N]_NEWLINE_   # M 是围成凸包的点的个数let M = 1_NEWLINE_   for i = 2 to N:_NEWLINE_       # Find next valid point on convex hull._NEWLINE_       while ccw(points[M-1], points[M], points[i]) <= 0:_NEWLINE_           if M > 1:_NEWLINE_               M -= 1_NEWLINE_           # All points are collinear_NEWLINE_           else if i == N:_NEWLINE_               break_NEWLINE_           else_NEWLINE_               i += 1_NEWLINE_           # 更新M，并把points[i]放到正确的位置M += 1_NEWLINE_       swap points[M] with points[i]_NEWLINE_上面的这段伪代码摘抄自Sedgewick and Wayne's Algorithms, 4th edition._NEWLINE_在循环中应该检查以避免共线的情况