10 几何算法之凸包算法

在上一篇中，我们探讨了几何算法中的最近点对问题，并了解了如何高效地寻找平面上两个最近的点。在本篇中，我们将深入研究凸包算法。这是计算几何中一个重要的基础问题，广泛应用于图形学、计算机视觉和模式识别等领域。

什么是凸包？

凸包 是给定点集的最小凸多边形。换句话说，如果你有一组点，凸包就是包围这些点的最小范围。如同在一组钉子上拉紧一根橡皮带，橡皮带的形状就代表了这些点的凸包。

凸包的性质

• 最小性：凸包是所有包含给定点集的凸多边形中，面积最小的一个。
• 凸性：凸包内部的任意两点之间的连线都位于凸包的内部。
• 包含性：凸包包含所有给定的点。

常见的凸包算法

在计算几何中，有几种经典的凸包算法。以下几种是最常用的：

1. 贪心算法：如 Graham 扫描法。
2. 分治法：如 Chan’s 算法。
3. 旋转卡壳：通过将点在极坐标中排序并处理。

在此，我们主要关注现代应用中使用最广泛的 Graham 扫描法 。

Graham 扫描法

Graham 扫描法的核心思想是将所有点绕着一个极小的“锚点”进行排序，从而构造出凸包。

算法步骤：

1. 选择锚点：选择一个点作为起始点，通常选择y值最小的点（如有相同y值则选择x值最小的）。
2. 极角排序：将其他点按锚点的极角进行排序。
3. 构建凸包：使用栈来构建凸包。遍历排序后的点，如果形成右转，则弹出栈顶元素，直到形成左转为止。

代码实现

以下是一个使用 Python 实现的 Graham 扫描法的示例：

import matplotlib.pyplot as plt

def orientation(p, q, r):
    # 计算点p, q, r的方向
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0  # collinear
    return 1 if val > 0 else 2  # clock or counterclock wise

def graham_scan(points):
    # 找到最底部的点
    start = min(points, key=lambda p: (p[1], p[0]))
    
    # 按极角排序
    sorted_points = sorted(points, key=lambda p: (atan2(p[1] - start[1], p[0] - start[0])))
    
    # 构建凸包
    hull = []
    for point in sorted_points:
        while len(hull) >= 2 and orientation(hull[-2], hull[-1], point) != 2:
            hull.pop()
        hull.append(point)
    
    return hull

# 示例
points = [(0, 3), (1, 1), (2, 2), (4, 4), (0, 0), (1, 2), (3, 1), (3, 3)]
hull = graham_scan(points)

# 绘制结果
plt.figure()
plt.scatter(*zip(*points), color='blue')
plt.scatter(*zip(*hull), color='red')
plt.plot(*zip(*hull, hull[0]), color='red')  # 连接所有点闭合凸包
plt.title("Graham Scan Convex Hull")
plt.show()

在这个代码中，我们定义了一个 graham_scan 函数，该函数接收一组点并返回构建的凸包顶点。我们还通过 matplotlib 库可视化了凸包结果。

应用实例

凸包在实际应用中发挥着至关重要的作用，尤其是在计算机图形学中。例如，许多 2D 游戏需要进行碰撞检测时，通常会先计算对象的凸包，然后使用它们进行更简化的碰撞检测，以提高性能。

在图像处理领域，凸包可以用来识别和提取形状。在一个物体的外边界提取过程中，通过凸包算法，我们能获得物体的外轮廓。

案例：计算几何在图形学中的应用

在下一篇中，我们将探讨计算几何在图形学中的应用，特别是在物体识别、碰撞检测等方面的重要性，进一步理解凸包算法在实际场景中的重要角色。

通过对凸包的理解，我们不仅能够打下一个坚实的基础，也能在后续的应用中游刃有余。希望这篇教程能为你的学习之旅提供帮助。