C 语言中的多边形凸性检查：算法与实现

C语言凸多边形判断：从理论到稳健实现

判断多边形是否为凸形是计算几何中的核心任务，在游戏引擎、导航系统和计算机图形学中不可或缺。凸形处理速度更快，此检查是关键优化步骤。

算法的几何基础

多边形的凸性取决于遍历顶点时转弯的方向。如果所有转弯方向一致（均为左转或右转），则为凸多边形。方向改变则为凹多边形。

转弯方向通过每三个连续点 A、B、C 的叉积符号计算：

cross = (B.x - A.x)(C.y - A.y) - (B.y - A.y)(C.x - A.x)

• cross > 0 — 左转
• cross < 0 — 右转
• cross = 0 — 三点共线

此公式给出向量 AB 和 AC 形成的平行四边形的有符号面积。符号表示点 C 相对于 A 到 B 方向的“上方”或“下方”。

基础数据结构

我们使用结构体定义点和多边形。顶点采用动态分配，因为顶点数仅在运行时确定。

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

typedef struct {
    Point *vertices;
    int n;
} Polygon;

创建和销毁函数管理内存：

Polygon* CreatePolygon(int n) {
    Polygon *p = malloc(sizeof(Polygon));
    if (!p) return NULL;
    p->n = n;
    p->vertices = malloc(n * sizeof(Point));
    if (!p->vertices) {
        free(p);
        return NULL;
    }
    return p;
}

void DestroyPolygon(Polygon *p) {
    if (!p) return;
    free(p->vertices);
    free(p);
}

方向函数与溢出问题

核心 Orient 函数计算叉积。使用 long long 防止坐标乘法溢出，但 64 位类型也有极限。

long long Orient(Point a, Point b, Point c) {
    return (long long)(b.x - a.x) * (c.y - a.y) -
           (long long)(b.y - a.y) * (c.x - a.x);
}

对于关键应用，需添加溢出保护：

#include <limits.h>

int SafeMul(long long a, long long b, long long *res) {
    if (a > 0 && b > 0 && a > LLONG_MAX / b) return 0;
    if (a > 0 && b < 0 && b < LLONG_MIN / a) return 0;
    if (a < 0 && b > 0 && a < LLONG_MIN / b) return 0;
    if (a < 0 && b < 0 && a < LLONG_MAX / b) return 0;
    *res = a * b;
    return 1;
}

long long OrientSafe(Point a, Point b, Point c) {
    long long p1, p2;
    if (!SafeMul((long long)b.x - a.x, (long long)c.y - a.y, &p1) ||
        !SafeMul((long long)b.y - a.y, (long long)c.x - a.x, &p2)) {
        // 溢出处理：返回 0 会与共线冲突
        // 实际中设置错误标志或使用 __int128
        printf("OVERFLOW\n");
        exit(1);
    }
    return p1 - p2;
}

重要提示： 溢出时返回 0 是错误的，因为它也表示共线。在严格代码中，使用错误标志或更宽类型。

凸性检查算法

主函数 IsConvex 检查所有顶点三元组的叉积符号。sign 记录首个非零转弯方向。

int IsConvex(const Polygon *p) {
    int sign = 0;
    for (int i = 0; i < p->n; i++) {
        Point a = p->vertices[i];
        Point b = p->vertices[(i + 1) % p->n];
        Point c = p->vertices[(i + 2) % p->n];
        long long cross = Orient(a, b, c);
        if (cross == 0) continue; // 跳过共线点
        if (sign == 0) {
            sign = (cross > 0) ? 1 : -1; // 锁定首方向
        } else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) {
            return 0; // 方向改变 — 非凸
        }
    }
    return 1; // 所有转弯方向一致
}

关键实现特性：

• % p->n 实现循环遍历。
• 共线点（cross == 0）被跳过，适用于有直边段的多边形。
• O(n) 时间复杂度，常量额外空间。

完整程序示例

此代码展示从标准输入读取多边形并分析的完整应用。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 结构体和方向函数（如上）
// ...

int ReadPolygon(Polygon *p) {
    for (int i = 0; i < p->n; i++) {
        if (scanf("%d %d", &p->vertices[i].x, &p->vertices[i].y) != 2) return 0;
    }
    return 1;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n < 3) {
        printf("INPUT ERROR: need at least 3 vertices\n");
        return 1;
    }
    Polygon *p = CreatePolygon(n);
    if (!p) {
        printf("MEMORY ERROR\n");
        return 1;
    }
    if (!ReadPolygon(p)) {
        printf("INPUT ERROR: invalid coordinates\n");
        DestroyPolygon(p);
        return 1;
    }
    printf(IsConvex(p) ? "CONVEX\n" : "NOT CONVEX\n");
    DestroyPolygon(p);
    return 0;
}

实际考虑与限制

算法假设顶点按遍历顺序（顺时针或逆时针）排列，且多边形简单（无自相交）。

关键要点：

• 共线处理： 跳过 cross == 0 适用于有直边的凸多边形，但可能掩盖输入错误。
• 溢出保护： 生产代码需安全乘法或 __int128，尤其大坐标时。
• 性能： 基础算法 O(n) 最优，但 OrientSafe 检查会降低速度。根据输入范围选择。
• 适用性： 仅限 2D 多边形。3D 需面检查或体积符号分析。
• 替代方案： 复杂情况用 CGAL 或 Boost.Geometry 库，或 GPU 加速。

— Editorial Team