葛立恒扫描法

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

算法步骤与图解

葛立恒扫描法的示意图。

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

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

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

• 刚开始的两个点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。

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

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

假设三个点分别是 $p_{1}(x_{1},y_{1}),p_{2}(x_{2},y_{2}),p_{3}(x_{3},y_{3})$ ，则它们的有向面积为 $(x_{2}-x_{1})(y_{3}-y_{1})-(y_{2}-y_{1})(x_{3}-x_{1})$ 。如果其结果为0，这三个点是共线的；如果其结果为正，这三个点是向左转的；如果其结果为负，则它们是向右转的。

时间复杂度

排序的复杂度为$O(n\log n)$。虽然它的主循环看起来是$O(n^{2})$的时间复杂度，但由于每个点要多次在堆叠中查找当且仅当其相对与堆叠顶端的点是“向右转”的，这个过程实际上是$O(n)$的时间复杂度，并且每一个点至多被考虑两次，而每个点只在点$(x_{2},y_{2})$产生一个“向左转”时被访问一次（因为算法进行到点$(x_{3},y_{3})$之后，点$(x_{2},y_{2})$由于产生了一个“右转”而被删去），因此，总时间复杂度由排序时间决定，即$O(n\log n)$

伪代码

定义：

   # 当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.

在循环中应该检查以避免共线的情况

引用

• Cormen, Thomas H.;Leiserson, Charles E.,Rivest, Ronald L.,Stein, Clifford《算法导论》第33章计算几何学第三节“寻找凸包”