构建点集的边界轮廓（C++实现凸包算法详解）

本文将带你从零开始，使用C++语言实现两种经典的凸包算法：Graham扫描法和Andrew算法（也称为单调链算法）。即使你是编程小白，也能轻松理解！

什么是凸包？

凸包具有以下性质：

• 它是凸多边形（任意两点连线都在图形内部）
• 它包含所有给定点
• 它的顶点一定是原始点集中的点

准备工作：点的表示与叉积

在实现算法前，我们需要定义点的结构，并掌握判断三点转向的方法——这需要用到向量叉积。

#include <iostream>#include <vector>#include <algorithm>using namespace std;struct Point {    long long x, y;    Point() {}    Point(long long x, long long y) : x(x), y(y) {}        bool operator < (const Point& p) const {        return x == p.x ? y < p.y : x < p.x;    }};// 计算叉积：(B - A) × (C - A)long long 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);}  

叉积的结果可以告诉我们三点的转向：

• cross > 0：逆时针（左转）
• cross < 0：顺时针（右转）
• cross == 0：共线

方法一：Andrew算法（推荐）

Andrew算法是Graham扫描法的改进版，思路更清晰，代码更简洁。它先对点按x（再按y）排序，然后分别构建下凸壳和上凸壳。

vector<Point> convexHull(vector<Point>& points) {    int n = points.size();    if (n <= 1) return points;        sort(points.begin(), points.end()); // 按x升序，x相同时按y升序        vector<Point> hull;    hull.reserve(n + 1);        // 构建下凸壳    for (int i = 0; i < n; ++i) {        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), points[i]) <= 0) {            hull.pop_back();        }        hull.push_back(points[i]);    }        // 构建上凸壳    int lower_len = hull.size(); // 下凸壳的长度（包括最右点）    for (int i = n - 2; i >= 0; --i) {        while (hull.size() > lower_len && cross(hull[hull.size()-2], hull.back(), points[i]) <= 0) {            hull.pop_back();        }        hull.push_back(points[i]);    }        // 最后一个点和第一个点重复，去掉    if (hull.size() > 1) hull.pop_back();        return hull;}  

完整示例程序

int main() {    vector<Point> points = {        {0, 0}, {1, 1}, {2, 0}, {1, 2},        {0, 2}, {2, 2}, {1, 0}    };        vector<Point> hull = convexHull(points);        cout << "凸包顶点（按顺时针或逆时针顺序）：\n";    for (auto& p : hull) {        cout << "(" << p.x << ", " << p.y << ")\n";    }        return 0;}  

为什么选择Andrew算法？

相比传统的Graham扫描法，Andrew算法有以下优点：

• 无需计算极角，避免浮点运算和精度问题
• 代码逻辑更清晰，易于理解和调试
• 时间复杂度稳定为 O(n log n)，主要消耗在排序

总结

通过本文，你已经掌握了使用C++凸包算法来求解点集凸包的基本方法。无论是竞赛还是实际工程应用（如碰撞检测、图像处理等），凸包都是一个非常实用的工具。记住关键点：排序 + 叉积判断 + 单调栈维护。

希望这篇教程能帮助你入门计算几何！动手试试吧，修改点集看看凸包如何变化。如果你对Graham扫描法感兴趣，也可以在此基础上进一步探索。

SEO关键词提示：C++凸包算法、计算几何、Andrew算法、Graham扫描法