葛立恆掃描法

葛立恒扫描法（Graham's scan）是一种计算一组的平面点的凸包的算法，时间复杂度为。以在1972年发表该算法的葛立恒命名。

时间复杂度

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

伪代码

定义：

   # 当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)
然后结果存在points数组内：

   let N           = number of points
   let points[N+1] = the array of points
   swap points[1] with the point with the lowest y-coordinate
   sort points by polar angle with points[1]
   # points[0] 是结束循环的标记点let points[0] = points[N]
   # M 是围成凸包的点的个数let M = 1
   for i = 2 to N:
       # Find next valid point on convex hull.
       while ccw(points[M-1], points[M], points[i]) <= 0:
           if M > 1:
               M -= 1
           # All points are collinear
           else if i == N:
               break
           else
               i += 1
           # 更新M，并把points[i]放到正确的位置M += 1
       swap points[M] with points[i]
上面的这段伪代码摘抄自Sedgewick and Wayne's Algorithms, 4th edition.
在循环中应该检查以避免共线的情况