凸包(Andrew/Graham)

What · 是什么

凸包是包含点集中所有点的最小凸多边形。求解思路是把点按序扫描，用单调栈维护'一路左转'的凸壳：Andrew 单调链按 x 为第一关键字、y 为第二关键字排序，先扫出下凸壳再扫出上凸壳合并；Graham 扫描则取最低点（y 最小、x 次小）为极，其余点按极角排序后逐个压栈，遇到右转就弹栈。两者均为 O(n log n)（瓶颈是排序），且被证明是渐近最优的。凸包是旋转卡壳、凸包优化(CHT)、半平面交、闵可夫斯基和等几乎所有计算几何高级算法的前置结构。

Why · 为什么

How · 实现

伪代码

# Andrew 单调链
pts.sort() by (x, y)
lower = []
for p in pts:
    while len(lower)>=2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop()
    lower.append(p)
upper = []
for p in reversed(pts):
    while len(upper)>=2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop()
    upper.append(p)
hull = lower[:-1] + upper[:-1]   # 逆时针，含所有凸包顶点

# cross(o,a,b) = (a-o)×(b-o)
# 用 <= 0 弹栈 → 不保留共线边界点；用 < 0 → 保留

Python 实现

# -*- coding: utf-8 -*-


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


def convex_hull(points, keep_collinear=False):
    """Andrew 单调链。返回逆时针凸包顶点（首尾不重复）。
    keep_collinear=True 时保留共线边界点。
    """
    cmp = lambda x: x <= 0 if not keep_collinear else x < 0
    pts = sorted(set(points))
    if len(pts) <= 1:
        return pts
    lower = []
    for p in pts:
        while len(lower) >= 2 and cmp(cross(lower[-2], lower[-1], p)):
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(pts):
        while len(upper) >= 2 and cmp(cross(upper[-2], upper[-1], p)):
            upper.pop()
        upper.append(p)
    hull = lower[:-1] + upper[:-1]
    # 去掉拼接处的连续重复点（全共线/退化时会出现）
    res = []
    for p in hull:
        if not res or res[-1] != p:
            res.append(p)
    return res


def polygon_area(poly):
    s = 0.0
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1) % n]
        s += x1*y2 - x2*y1
    return abs(s) / 2.0


def pip_ray(p, poly):
    x, y = p
    inside = False
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1) % n]
        if (y1 > y) != (y2 > y):
            xi = x1 + (x2-x1)*(y-y1)/(y2-y1)
            if x < xi:
                inside = not inside
    return inside


if __name__ == '__main__':
    sq = [(0, 0), (1, 0), (1, 1), (0, 1)]
    h = convex_hull(sq)
    assert len(h) == 4 and abs(polygon_area(h) - 1.0) < 1e-9
    # 共线点只保留两端
    col = [(0, 0), (1, 1), (2, 2)]
    h2 = convex_hull(col)
    assert len(h2) == 2, h2
    # 矩形边界上有内部共线点：keep_collinear 时保留
    rect = [(0, 0), (2, 0), (1, 0), (2, 2), (0, 2), (1, 2)]
    h3 = convex_hull(rect)
    assert len(h3) == 4, h3
    h3c = convex_hull(rect, keep_collinear=True)
    assert (1, 0) in h3c and (1, 2) in h3c and len(h3c) == 6, h3c
    # 随机点全部被覆盖
    import random
    pts = [(random.randint(-50, 50), random.randint(-50, 50)) for _ in range(300)]
    hull = convex_hull(pts)
    for p in pts:
        ok = True
        for i in range(len(hull)):
            if cross(hull[i], hull[(i+1) % len(hull)], p) < -1e-9:
                ok = False
                break
        assert ok, p
    for i in range(len(hull)):
        assert cross(hull[i], hull[(i+1) % len(hull)], hull[(i+2) % len(hull)]) >= -1e-9
    print('convex-hull all tests passed')

易错点

• 排序后未去重导致栈内重复点/退化（先 set 去重）
• 弹栈条件 <= 与 < 的选择决定是否保留共线边界点，题目语义要提前确认
• 上下壳拼接时去掉重复的首尾点，否则周长/面积会算错
• 浮点坐标直接比较 == 判重会误判，整点问题用整数或 eps 判重
• Graham 的极角排序需处理极角相等时按距离排序
• 凸包顶点数 < 3 时（退化）调用旋转卡壳等算法要特判

例题

信源

• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/geometry/convex-hull.md
• CP-Algorithms✓ https://cp-algorithms.com/geometry/convex-hull.html
• 书籍✓ CPH ch29