旋转卡壳算法详解（C语言实现凸包直径与最小外接矩形）

前置知识：凸包

旋转卡壳的前提是已经有一个凸包（Convex Hull）。凸包可以理解为包裹所有点的最小凸多边形。我们可以使用 Graham 扫描法或 Andrew 算法先求出凸包。

下面是一个简单的 Andrew 算法实现（按 x 坐标排序，再构建上下凸壳）：

// 点结构体typedef struct {    double x, y;} Point;// 叉积：判断转向int 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);}// 比较函数：先按x，再按yint cmp(const void *a, const void *b) {    Point *p1 = (Point *)a, *p2 = (Point *)b;    if (p1->x == p2->x) return p1->y < p2->y ? -1 : 1;    return p1->x < p2->x ? -1 : 1;}// 构建凸包int convex_hull(Point P[], int n, Point H[]) {    if (n <= 1) return n;    qsort(P, n, sizeof(Point), cmp);        int k = 0;    // 下凸壳    for (int i = 0; i < n; ++i) {        while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;        H[k++] = P[i];    }        // 上凸壳    for (int i = n-2, t = k+1; i >= 0; --i) {        while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;        H[k++] = P[i];    }        return k - 1; // 最后一点与第一点重复}

旋转卡壳求凸包直径

凸包直径是指凸包上任意两点之间的最大距离。暴力方法是 O(n²)，而旋转卡壳可以在 O(n) 时间内完成。

核心思想：对于凸包上的每一条边，找到离它最远的点（对踵点）。随着边顺时针旋转，对踵点也单调移动，无需回溯。

#include <math.h>double dist(Point a, Point b) {    double dx = a.x - b.x;    double dy = a.y - b.y;    return sqrt(dx*dx + dy*dy);}// 旋转卡壳求直径double rotating_calipers_diameter(Point H[], int m) {    if (m == 1) return 0;    if (m == 2) return dist(H[0], H[1]);        double max_dist = 0;    int j = 1; // 对踵点索引        for (int i = 0; i < m; i++) {        // 找到使三角形面积最大的 j        while (cross(H[i], H[(i+1)%m], H[(j+1)%m]) > cross(H[i], H[(i+1)%m], H[j])) {            j = (j + 1) % m;        }                // 更新最大距离        max_dist = fmax(max_dist, dist(H[i], H[j]));        max_dist = fmax(max_dist, dist(H[(i+1)%m], H[j]));    }        return max_dist;}

为什么叫“旋转卡壳”？

这个名字来源于其几何直观：就像用两把平行的卡尺夹住凸多边形，一边旋转一边保持接触。在 C 语言实现中，我们通过叉积判断“高度”变化，从而模拟这一旋转过程。

应用场景

• 求点集的最远点对（旋转卡壳算法的核心应用）
• 计算凸多边形的最小面积/周长外接矩形（最小外接矩形）
• 碰撞检测、模式识别等计算几何领域
• 优化路径规划中的包围盒计算

完整流程总结

1. 输入点集
2. 用 Andrew 或 Graham 算法求C语言凸包
3. 对凸包应用旋转卡壳算法
4. 输出直径、宽度或外接矩形信息

通过本教程，你应该已经掌握了旋转卡壳的基本原理和 C 语言实现。记住，关键在于理解叉积如何帮助我们判断“最远点”，以及为什么对踵点可以单调移动。

继续练习吧！尝试用这个算法解决实际问题，比如在地图上找两个最远的城市，或者为机器人路径生成最小包围区域。