Graham 扫描法(Graham Scan)

Graham 扫描法(Graham Scan)是一种计算平面点集凸包的算法,由美国数学家葛立恒(Ronald Graham)于 1972 年提出。凸包是包含所有给定点的最小凸多边形,Graham 扫描法以 O(n log n) 的时间复杂度求出凸包顶点序列,是最早达到这一效率的凸包算法之一。

概述

凸包问题是计算几何中最基础的问题之一,可以类比为用一根橡皮筋套住平面上所有钉子后形成的形状。葛立恒当年在贝尔实验室为处理大规模点集数据提出了这一方法,其排序加栈扫描的框架此后被大量几何算法借鉴。常见变体是安德鲁单调链算法,用坐标排序代替极角排序,实现更简洁、数值更稳健。

核心原理

算法分三步进行:

• 选基准点:取纵坐标最小(相同时横坐标最小)的点,它必然是凸包顶点。
• 极角排序:其余点按相对基准点的极角从小到大排序,极角相同时按距离排序,该步是复杂度瓶颈 O(n log n)。
• 栈扫描:依次考察排序后的点,用栈维护当前凸壳;若新点使栈顶两点构成非左转(通过叉积判断),则弹出栈顶,直到恢复左转性,再压入新点。

扫描阶段每个点至多入栈出栈一次,因此是线性时间。叉积判断避免了计算角度带来的浮点误差,是实现中的关键技巧。

应用场景

凸包是许多几何计算的第一步:碰撞检测与包围体计算、图形学中的形状简化、地理信息系统中求区域轮廓、模式识别中的特征提取,以及旋转卡壳求直径、最小包围矩形等后续算法都以凸包为输入。

常见问题

问:Graham 扫描法与 Jarvis 步进法(礼品包装法)如何取舍？答:Jarvis 步进法复杂度为 O(nh),h 是凸包顶点数,只有当凸包顶点极少时才占优;一般情况下 Graham 扫描法的 O(n log n) 更稳定。

问:遇到三点共线怎么处理？答:取决于需求,若凸包边上不允许保留共线点,扫描时把叉积为零的情形也弹栈即可;排序时还需对极角相同的点按距离规则处理,避免结果出错。

问:该算法能推广到三维吗？答:不能直接推广,三维凸包需要增量法或分治法等专门算法,复杂度同样可达 O(n log n)。