C语言凸包算法详解（从零开始掌握Graham扫描法实现）

什么是凸包？

凸包具有以下性质：

• 所有原始点都在凸包内部或边界上；
• 凸包是一个凸多边形（任意两点连线都在多边形内）；
• 凸包的顶点一定是原始点集中的某些点。

在实际应用中，C语言凸包算法广泛用于计算机图形学、碰撞检测、地理信息系统（GIS）、机器人路径规划等领域。

常用凸包算法简介

常见的凸包算法包括：

• Jarvis步进法（Gift Wrapping）：时间复杂度 O(nh)，h 为凸包顶点数；
• Graham扫描法：时间复杂度 O(n log n)，效率高，适合大多数场景；
• Andrew单调链算法：也是 O(n log n)，实现简洁。

本教程将重点讲解 凸包Graham扫描法 的 C 语言实现，这是学习 C语言计算几何 的经典入门算法。

Graham扫描法原理

Graham 扫描法的核心思想是：

1. 找到最下方（y 最小，若相同则 x 最小）的点 P₀，作为起始点；
2. 将其他点按相对于 P₀ 的极角从小到大排序（若极角相同，则按距离近到远）；
3. 用一个栈维护当前凸包的点，依次检查每个点是否“向左转”，如果不是，则弹出栈顶，直到满足凸性。

判断三点是否“向左转”可通过叉积（cross product）实现。

C语言实现步骤

1. 定义点结构体

typedef struct {    double x;    double y;} Point;

2. 计算叉积

给定三点 O、A、B，叉积 = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)

• 叉积 > 0：O→A→B 是左转（逆时针）；
• 叉积 < 0：右转（顺时针）；
• 叉积 = 0：三点共线。

double cross(const Point *O, const Point *A, const Point *B) {    return (A->x - O->x) * (B->y - O->y) -            (A->y - O->y) * (B->x - O->x);}

3. 比较函数（用于 qsort）

// 全局变量，存储基准点 P0Point P0;int compare(const void *a, const void *b) {    Point *p1 = (Point *)a;    Point *p2 = (Point *)b;        double c = cross(&P0, p1, p2);    if (c == 0) {        // 极角相同，按距离排序        double d1 = (p1->x - P0.x)*(p1->x - P0.x) + (p1->y - P0.y)*(p1->y - P0.y);        double d2 = (p2->x - P0.x)*(p2->x - P0.x) + (p2->y - P0.y)*(p2->y - P0.y);        return (d1 > d2) ? 1 : -1;    }    return (c > 0) ? -1 : 1; // 极角小的排前面}

4. Graham 扫描主函数

int convexHull(Point points[], int n, Point hull[]) {    if (n < 3) return 0; // 凸包至少需要3个点    // 1. 找到最下最左的点    int idx = 0;    for (int i = 1; i < n; i++) {        if (points[i].y < points[idx].y ||            (points[i].y == points[idx].y && points[i].x < points[idx].x))            idx = i;    }    // 2. 将 P0 放到第一个位置    Point temp = points[0];    points[0] = points[idx];    points[idx] = temp;    P0 = points[0];    // 3. 按极角排序    qsort(points + 1, n - 1, sizeof(Point), compare);    // 4. 处理共线点（保留最远的）    int m = 1;    for (int i = 1; i < n; i++) {        while (i < n - 1 && cross(&P0, &points[i], &points[i+1]) == 0)            i++;        points[m++] = points[i];    }    if (m < 3) return 0; // 无法构成凸包    // 5. Graham 扫描    int k = 2;    for (int i = 2; i < m; i++) {        while (k >= 2 && cross(&hull[k-2], &hull[k-1], &points[i]) <= 0)            k--;        hull[k++] = points[i];    }    // 复制前两个点到末尾（可选，用于闭合多边形）    // hull[k] = hull[0]; hull[k+1] = hull[1];    return k; // 返回凸包顶点数}

完整示例与测试

下面是一个完整的 凸包实现教程 示例程序：

#include <stdio.h>#include <stdlib.h>// 上述所有函数定义...int main() {    Point points[] = {        {0, 0}, {1, -4}, {-1, -5}, {-5, -3},        {-3, -1}, {-1, -3}, {-2, -2}, {-4, -2}    };    int n = sizeof(points) / sizeof(points[0]);    Point hull[100];    int h = convexHull(points, n, hull);    printf("凸包顶点（共 %d 个）:\n", h);    for (int i = 0; i < h; i++) {        printf("(%.1f, %.1f)\n", hull[i].x, hull[i].y);    }    return 0;}

总结

通过本教程，你已经掌握了使用 C 语言实现 凸包Graham扫描法 的完整流程。该算法高效、稳定，是学习 C语言计算几何 的重要基石。无论你是学生、算法爱好者，还是从事图形开发的工程师，理解并实现凸包算法都将为你打下坚实的基础。

记住：多动手写代码、调试、可视化结果，是掌握 C语言凸包算法 的最佳方式。祝你编程愉快！