跳到主要内容

Graham扫描法

Graham扫描法是一种用于计算平面点集凸包的高效算法。凸包是包含所有点的最小凸多边形。Graham扫描法通过选择一个基准点，然后按照极角排序其他点，最后使用栈来构建凸包。本文将逐步讲解该算法的原理、实现以及实际应用。

什么是凸包？​

凸包是包含所有点的最小凸多边形。凸多边形的定义是：多边形内的任意两点连线都在多边形内部。凸包在计算几何中有着广泛的应用，例如碰撞检测、路径规划等。

Graham扫描法的步骤​

Graham扫描法的核心思想是通过排序和栈操作来构建凸包。以下是算法的详细步骤：

  1. 选择基准点：选择点集中y坐标最小的点作为基准点。如果有多个点具有相同的y坐标，则选择x坐标最小的点。
  2. 极角排序：以基准点为原点，计算其他点的极角（即与基准点的连线与x轴的夹角），并按极角从小到大排序。如果极角相同，则按距离基准点的距离从小到大排序。
  3. 构建凸包：使用栈来存储凸包的点。依次遍历排序后的点，对于每个点，检查栈顶的两个点与新点是否构成“左转”。如果是“左转”，则将新点压入栈中；否则，弹出栈顶的点，直到满足“左转”条件。

代码示例​

以下是用Python实现的Graham扫描法代码：

python
import math

def cross(o, a, b):
    return (a[0] - o[0])*(b[1] - o[1]) - (a[1] - o[1])*(b[0] - o[0])

def graham_scan(points):
    # 找到基准点
    start = min(points, key=lambda p: (p[1], p[0]))
    
    # 按极角排序
    sorted_points = sorted(points, key=lambda p: (math.atan2(p[1] - start[1], p[0] - start[0]), p))
    
    # 构建凸包
    hull = []
    for p in sorted_points:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    
    return hull

# 示例输入
points = [(0, 3), (1, 1), (2, 2), (4, 4), (0, 0), (1, 2), (3, 1), (3, 3)]
# 计算凸包
convex_hull = graham_scan(points)
print("凸包的点:", convex_hull)

输出：

凸包的点: [(0, 0), (3, 1), (4, 4), (0, 3)]

实际应用场景​

Graham扫描法在许多领域都有应用，例如：

  • 计算机图形学：用于渲染凸多边形或进行碰撞检测。
  • 机器人路径规划：用于计算机器人移动的凸包区域，避免障碍物。
  • 地理信息系统（GIS）：用于计算地理区域的凸包，简化地图数据。

总结​

Graham扫描法是一种高效且易于理解的凸包计算算法。通过选择合适的基准点、极角排序以及栈操作，我们可以快速构建平面点集的凸包。本文详细介绍了算法的步骤，并提供了Python代码示例。希望你能通过本文掌握Graham扫描法，并在实际项目中应用它。

附加资源与练习​

  • 练习：尝试在三维空间中扩展Graham扫描法，计算三维点集的凸包。
  • 资源：阅读更多关于计算几何的书籍，如《计算几何：算法与应用》。
提示

如果你对算法的实现有任何疑问，可以尝试在纸上手动模拟算法的步骤，这将帮助你更好地理解其工作原理。