442 字
2 分钟
二维凸包 (Convex Hull - Andrew 算法)

二维凸包 (Convex Hull - Andrew 算法)#

1. 概念与性质#

在二维平面点集中,凸包是能够包含所有点的最小凸多边形。其顶点集是平面点集的子集,多边形内部角均小于 180 度。

2. Andrew 算法流程#

Andrew 算法是 Graham 扫描法的变种,常数更优、鲁棒性更强:

  1. 坐标排序:优先按 xx 升序排序,若 xx 相同则按 yy 升序排序。
  2. 构建下凸壳:从左往右扫描点,用单调栈维护向量叉积 v1⃗×v2⃗>0\vec{v_1} \times \vec{v_2} > 0(向左拐)。若出现顺时针拐弯或共线(视是否严格凸包而定),则弹出栈顶。
  3. 构建上凸壳:从右往左倒序扫描剩余点,同样用单调栈维护左拐关系。
  4. 闭合多边形:合并上下凸壳,注意去重起点与终点。

时间复杂度:排序 O(Nlog⁡N)O(N \log N),单调栈扫描 O(N)O(N),总复杂度 O(Nlog⁡N)O(N \log N)。

3. 核心模板代码 (C++)#

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Point {
ll x, y;
Point operator-(const Point &o) const { return {x - o.x, y - o.y}; }
ll operator^(const Point &o) const { return x * o.y - y * o.x; } // 叉积
bool operator<(const Point &o) const { return x == o.x ? y < o.y : x < o.x; }
};
ll cross(Point a, Point b, Point c) {
return (b - a) ^ (c - a);
}
vector<Point> get_convex_hull(vector<Point> &pts) {
int n = pts.size();
if (n <= 1)
return pts;
sort(pts.begin(), pts.end());
vector<Point> hull;
// 下凸壳
for (int i = 0; i < n; i++) {
while (hull.size() >= 2 && cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
hull.pop_back();
}
hull.push_back(pts[i]);
}
// 上凸壳
int t = hull.size();
for (int i = n - 2; i >= 0; i--) {
while ((int)hull.size() > t && cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
hull.pop_back();
}
hull.push_back(pts[i]);
}
hull.pop_back(); // 起点重复计算一次
return hull;
}
二维凸包 (Convex Hull - Andrew 算法)
https://sanzenin.top/posts/obsidian/凸包/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取