打开主菜单

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

算法步骤与图解编辑

 
葛立恒扫描法的示意图。

第一步:找到最下边的点,如果有多个点纵坐标相同的点都在最下方,则选取最左边的。在右图中这个点是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)

然后结果存在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.

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

引用编辑

  1. ^ Graham, R.L. (1972).An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133