442 字
2 分钟
二维凸包 (Convex Hull - Andrew 算法)
二维凸包 (Convex Hull - Andrew 算法)
1. 概念与性质
在二维平面点集中,凸包是能够包含所有点的最小凸多边形。其顶点集是平面点集的子集,多边形内部角均小于 180 度。
2. Andrew 算法流程
Andrew 算法是 Graham 扫描法的变种,常数更优、鲁棒性更强:
- 坐标排序:优先按 升序排序,若 相同则按 升序排序。
- 构建下凸壳:从左往右扫描点,用单调栈维护向量叉积 (向左拐)。若出现顺时针拐弯或共线(视是否严格凸包而定),则弹出栈顶。
- 构建上凸壳:从右往左倒序扫描剩余点,同样用单调栈维护左拐关系。
- 闭合多边形:合并上下凸壳,注意去重起点与终点。
时间复杂度:排序 ,单调栈扫描 ,总复杂度 。
3. 核心模板代码 (C++)
#include <bits/stdc++.h>#define ll long longusing 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/凸包/分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
最后更新于 ,距今已过 74 天
部分内容可能已过时