Graham Scan 凸包算法

算法

Graham Scan 是一种计算平面点集凸包的高效算法,通过先找出最低点,再按极角排序其他点,然后使用栈结构迭代构建凸包。

算法讲解

Graham Scan 凸包算法

介绍

Graham Scan是一种计算二维平面点集凸包(Convex Hull)的高效算法,由Ronald Graham于1972年提出。凸包是包含给定点集的最小凸多边形,可以想象成用一根橡皮筋包围所有点后的形状。Graham Scan算法的核心思想是通过极角排序和逆时针转向判断,逐步构建凸包。其时间复杂度为O(n log n),n是点的数量,主要受到点排序步骤的限制。

算法步骤

  1. 找到y坐标最小的点P₀(如果有多个y坐标最小的点,则选择x坐标最小的那个)。这个点必定在凸包上,称为"锚点"
  2. 计算所有其他点相对于锚点P₀的极角,并按照极角升序排序
    • 如果两点极角相同,则按照到锚点的距离升序排序
  3. 建立一个栈S,将锚点P₀和排序后的第一个点P₁压入栈中
  4. 对于剩余的每个点Pᵢ(i≥2),执行以下操作:
    • 当栈S中至少有两个点,且栈顶的两个点与当前点Pᵢ不构成逆时针转向时,弹出栈顶点
    • 将当前点Pᵢ压入栈S
  5. 算法结束后,栈S中的点按顺序构成凸包的顶点

算法详解

为了更清晰地理解算法过程,下面通过一个具体例子来演示Graham Scan的执行过程。

假设有以下点集:[(0,3), (1,1), (2,2), (4,4), (0,0), (1,2), (3,1), (3,3)]

第1步:找到锚点

...