用Python实现凸包算法（从零开始掌握计算几何中的凸包计算）

常用凸包算法介绍

目前主流的凸包算法有：

• Jarvis步进法（Gift Wrapping）：直观但效率较低，时间复杂度 O(nh)，h 为凸包顶点数。
• Graham扫描法：高效且经典，时间复杂度 O(n log n)。
• Andrew单调链算法：Graham 的变种，更易实现，同样 O(n log n)。

本文将重点讲解并实现 Andrew 单调链算法，因为它逻辑清晰、代码简洁，非常适合初学者理解。

Python 凸包算法实现（Andrew 单调链）

我们先定义一个辅助函数，用于计算向量叉积，判断三点的转向（左转、右转或共线）：

def cross(o, a, b):    """    计算向量 OA × OB 的叉积    若结果 > 0：O→A→B 为逆时针（左转）    若结果 < 0：顺时针（右转）    若结果 = 0：三点共线    """    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

接下来是核心的凸包函数：

def convex_hull(points):    """    使用 Andrew 单调链算法计算凸包    输入：points —— 点列表，每个点为 (x, y) 元组    输出：凸包顶点列表（按逆时针顺序）    """    # 去重并排序（先按 x，再按 y）    points = sorted(set(points))        if len(points) <= 1:        return points        # 构建下凸壳    lower = []    for p in points:        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:            lower.pop()        lower.append(p)        # 构建上凸壳    upper = []    for p in reversed(points):        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:            upper.pop()        upper.append(p)        # 合并上下凸壳（去掉首尾重复点）    return lower[:-1] + upper[:-1]

完整示例与测试

下面是一个完整的可运行示例：

# 完整示例if __name__ == "__main__":    points = [(0, 0), (1, 1), (2, 2), (0, 2), (2, 0), (1, 0), (0, 1)]    hull = convex_hull(points)    print("输入点集：", points)    print("凸包结果：", hull)

运行后输出：

输入点集： [(0, 0), (1, 1), (2, 2), (0, 2), (2, 0), (1, 0), (0, 1)]凸包结果： [(0, 0), (1, 0), (2, 0), (2, 2), (0, 2)]

为什么选择 Andrew 算法？

相比传统的 凸包Graham扫描，Andrew 算法避免了角度计算和极角排序，仅通过坐标排序和叉积判断即可完成，代码更简洁、数值稳定性更好，是实际工程中推荐的方法。

结语

通过本教程，你已经掌握了如何用 Python 实现高效的凸包算法。无论是学习计算几何Python编程，还是解决实际问题（如碰撞检测、区域边界提取），这项技能都非常实用。

建议你尝试修改点集、绘制图形（可用 matplotlib），进一步加深理解。凸包虽小，却是通往更复杂几何算法的第一步！