第45讲 计算几何基础：向量运算与凸包问题

各位同学，今天我们来聊聊计算几何。说实话，很多搞C语言开发的朋友，一听到“几何”两个字就头疼。我当年刚接触这部分内容时，也觉得这玩意儿离实际开发太远。直到有一次做地图导航项目，需要判断车辆行驶轨迹是否偏离路线——嗯，那时候我才发现，向量运算简直就是救命稻草。

这一讲，我会带着大家从最基础的向量运算开始，一步步走到凸包问题。你想想看，从点积叉积到多边形面积，再到Graham扫描法和Andrew算法，其实是一条很清晰的逻辑链。咱们不搞花架子，直接上干货。

1. 向量的点积与叉积

先说说向量。在C语言里，我们通常用一个结构体来表示二维向量：

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

点积（Dot Product）的计算公式很简单：a·b = a.x * b.x + a.y * b.y。它有什么用？我个人最常用的场景是判断两个向量的方向关系。如果点积大于0，说明夹角小于90度；等于0就是垂直；小于0就是钝角。

叉积（Cross Product）稍微复杂一点。在二维空间中，叉积的结果是一个标量：a × b = a.x * b.y - a.y * b.x。这个值的正负号，直接告诉你b在a的左侧还是右侧。我习惯用这个来判断多边形的顶点顺序——顺时针还是逆时针。

// 点积
static inline double dot(Vector2D a, Vector2D b) {
    return a.x * b.x + a.y * b.y;
}

// 叉积
static inline double cross(Vector2D a, Vector2D b) {
    return a.x * b.y - a.y * b.x;
}

2. 判断线段相交

这个功能，我在做路径规划项目时几乎天天用。判断两条线段是否相交，最经典的方法就是“跨立实验”。说白了，就是看一条线段的两个端点，是否分别位于另一条线段的两侧。

具体做法：对线段AB和CD，计算叉积 (B-A) × (C-A) 和 (B-A) × (D-A)。如果这两个叉积异号，说明C和D在AB的两侧。同理再检查A和B相对于CD的位置。如果两组都异号，那就相交了。

// 判断线段AB和CD是否相交
int segments_intersect(Vector2D A, Vector2D B, Vector2D C, Vector2D D) {
    Vector2D AB = {B.x - A.x, B.y - A.y};
    Vector2D AC = {C.x - A.x, C.y - A.y};
    Vector2D AD = {D.x - A.x, D.y - A.y};
    
    double cross1 = cross(AB, AC);
    double cross2 = cross(AB, AD);
    
    // 如果C和D在AB两侧
    if (cross1 * cross2 < 0) {
        Vector2D CD = {D.x - C.x, D.y - C.y};
        Vector2D CA = {A.x - C.x, A.y - C.y};
        Vector2D CB = {B.x - C.x, B.y - C.y};
        double cross3 = cross(CD, CA);
        double cross4 = cross(CD, CB);
        if (cross3 * cross4 < 0) return 1;
    }
    
    // 处理共线情况（略）
    return 0;
}

3. 多边形面积

计算多边形面积，我推荐用“鞋带公式”（Shoelace Formula）。名字挺有意思，其实就是把顶点坐标按顺序排好，交叉相乘再求和。公式如下：

Area = 0.5 * |Σ(x_i * y_{i+1} - x_{i+1} * y_i)|

注意顶点要按顺序给出（顺时针或逆时针都行），最后一个顶点要连回第一个。这个公式的好处是，不需要把多边形分割成三角形，直接一次遍历就能算出来。

double polygon_area(Vector2D *points, int n) {
    double area = 0.0;
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        area += points[i].x * points[j].y;
        area -= points[j].x * points[i].y;
    }
    return fabs(area) / 2.0;
}

4. 凸包问题

凸包，说白了就是用一个最小的凸多边形，把一堆点全部包在里面。想象一下用橡皮筋圈住一堆钉子，橡皮筋的形状就是凸包。

4.1 Graham扫描法

Graham扫描法的思路很直观：先找到最左下角的点作为起点，然后按极角排序，最后用一个栈来维护凸包。我当年学这个算法时，觉得“极角排序”这一步最绕。其实用叉积就能比较角度，不用真的去算角度值。

// 比较极角（用叉积）
int cmp_angle(const void *a, const void *b) {
    Vector2D *p1 = (Vector2D *)a;
    Vector2D *p2 = (Vector2D *)b;
    double c = cross(*p1, *p2);
    if (c != 0) return c > 0 ? -1 : 1;
    // 如果共线，距离近的优先
    double d1 = p1->x * p1->x + p1->y * p1->y;
    double d2 = p2->x * p2->x + p2->y * p2->y;
    return d1 < d2 ? -1 : 1;
}

排序之后，依次把点压入栈。每次压入前，检查栈顶两个点和新点是否构成“左转”。如果是左转就压入，否则弹出栈顶。最终栈里的点就是凸包。

4.2 Andrew算法

Andrew算法是Graham的改进版。它不需要计算极角，直接按x坐标排序。然后分别构造上凸包和下凸包。我个人更喜欢Andrew算法，因为实现起来更简洁，而且数值稳定性更好。

// Andrew算法求凸包
int convex_hull(Vector2D *points, int n, Vector2D *hull) {
    // 先按x排序，x相同按y排序
    qsort(points, n, sizeof(Vector2D), cmp_x);
    
    int m = 0;
    // 构造下凸包
    for (int i = 0; i < n; i++) {
        while (m >= 2 && cross(hull[m-1] - hull[m-2], points[i] - hull[m-2]) <= 0)
            m--;
        hull[m++] = points[i];
    }
    
    // 构造上凸包
    int t = m + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (m >= t && cross(hull[m-1] - hull[m-2], points[i] - hull[m-2]) <= 0)
            m--;
        hull[m++] = points[i];
    }
    
    return m - 1;  // 最后一个点重复了起点，去掉
}

总结

这一讲的内容，从向量运算到凸包算法，其实是一条很清晰的脉络。点积和叉积是基础中的基础，线段相交是实际应用最多的功能，多边形面积计算是很多几何问题的起点，而凸包则是这些知识的综合运用。

我个人建议，初学者先把点积和叉积的代码写熟练，然后试着实现线段相交判断。等这些基础打牢了，再挑战凸包算法。别一上来就啃凸包，容易消化不良。

最后说一句，计算几何的代码，调试起来确实有点麻烦。因为很多错误是数值精度导致的，不是逻辑问题。我的习惯是，所有比较都用eps（比如1e-9）来做容差，不要直接用==。这个小习惯，能帮你省下不少调试时间。

---