凸包 - Andrew算法【计算几何】

算法简介

Andrew算法（单调链算法）是一种高效的凸包求解算法，时间复杂度为O(n log n)，适用于平面上点集的凸包计算。

算法步骤

1. 排序点集：将所有点按x坐标升序排序，若x坐标相同则按y坐标升序排序。
2. 构建下凸包：从左到右遍历排序后的点，维护一个栈。每次加入新点后，检查当前栈顶三个点是否构成非左拐（即右拐或共线），若是则弹出中间点，直至满足凸包条件。
3. 构建上凸包：从右到左遍历排序后的点，同样维护一个栈。每次加入新点后，检查当前栈顶三个点是否构成非右拐（即左拐或共线），若是则弹出中间点，直至满足条件。
4. 合并凸包：下凸包和上凸包合并，去除重复点（下凸包最后一点与上凸包第一点相同，上凸包最后一点与下凸包第一点相同）。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
    bool operator<(const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
    bool operator==(const Point& p) const {
        return x == p.x && y == p.y;
    }
};

// 计算向量ab与向量ac的叉积
int cross(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// Andrew算法求凸包
vector<Point> convexHull(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; hull.push_back(pts[i++])) 
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
    
    // 构建上凸包
    int lowerSize = hull.size();
    for (int i = n-2; i >= 0; hull.push_back(pts[i--]))
        while (hull.size() > lowerSize && cross(hull[hull.size()-2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
    
    // 去除重复点（最后一个点与第一个点相同）
    if (hull.size() > 1) hull.pop_back();
    return hull;
}

// 示例用法
int main() {
    vector<Point> pts = {{0,0}, {1,1}, {2,0}, {1,2}, {3,1}};
    vector<Point> hull = convexHull(pts);
    for (auto& p : hull) {
        cout << "(" << p.x << "," << p.y << ") ";
    }
    return 0;
}

说明

• 叉积用于判断三点位置关系：>0表示左拐，<0表示右拐，=0表示共线。
• 算法通过两次遍历（下凸包和上凸包）确保所有凸包顶点被包含，且无冗余点。
• 适用于处理平面点集的凸包问题，可直接扩展至处理浮点数坐标（需修改叉积计算为浮点数运算）。

G52 凸包 Andrew算法【计算几何】