convex_hull/convex_hull.c

#include <stdlib.h>

// 定义点结构
typedef struct {
    int x;
    int y;
} Point;

// 计算叉积
double crossProduct(Point p0, Point p1, Point p2) {
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

// 计算两点间距离的平方
double distanceSquare(Point p1, Point p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

// 比较函数
Point p0;
int comparePoints(const void* vp1, const void* vp2) {
    Point* p1 = (Point*)vp1;
    Point* p2 = (Point*)vp2;
    double cross = crossProduct(p0, *p1, *p2);
    if (cross == 0) {
        return (distanceSquare(p0, *p1) - distanceSquare(p0, *p2));
    }
    return (cross < 0) ? 1 : -1;
}

// 导出的凸包计算函数
void convexHull(Point* points, int n, Point* result, int* resultSize) {
    if (n < 3) {
        // 点数小于3，直接复制所有点
        for (int i = 0; i < n; i++) {
            result[i] = points[i];
        }
        *resultSize = n;
        return;
    }

    // 找到y坐标最小的点
    int min = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].y < points[min].y || 
           (points[i].y == points[min].y && points[i].x < points[min].x)) {
            min = i;
        }
    }

    // 将最下方的点交换到points[0]
    Point temp = points[0];
    points[0] = points[min];
    points[min] = temp;

    // 保存最下方的点用于排序
    p0 = points[0];

    // 按极角排序
    qsort(&points[1], n-1, sizeof(Point), comparePoints);

    // 构建凸包
    int m = 0;
    result[m++] = points[0];
    result[m++] = points[1];
    result[m++] = points[2];

    for (int i = 3; i < n; i++) {
        while (m > 1 && crossProduct(result[m-2], result[m-1], points[i]) <= 0) {
            m--;
        }
        result[m++] = points[i];
    }

    *resultSize = m;
}