C语言计算几何算法详解（从零开始掌握点、线、面关系判断）

基础数据结构定义

在开始算法前，我们先定义点和线段的基本结构：

// 定义二维点结构typedef struct {    double x;    double y;} Point;// 定义线段结构（由两个端点组成）typedef struct {    Point p1;    Point p2;} Segment;

1. 判断点是否在线段上

这是最基础的问题之一。判断方法分两步：

• 点必须在由线段两端点确定的直线上（共线）
• 点的坐标必须在线段两个端点的包围盒内

我们使用向量叉积来判断共线性。若向量AB与向量AP的叉积为0，则三点共线。

#include <math.h>// 计算叉积：(B - A) × (C - A)double cross(const Point* A, const Point* B, const Point* C) {    return (B->x - A->x) * (C->y - A->y) -            (B->y - A->y) * (C->x - A->x);}// 判断点P是否在线段S上int isPointOnSegment(Point P, Segment S) {    // 叉积为0表示共线    if (fabs(cross(&S.p1, &S.p2, &P)) > 1e-9) {        return 0; // 不共线    }        // 检查P是否在S的包围盒内    double minX = fmin(S.p1.x, S.p2.x);    double maxX = fmax(S.p1.x, S.p2.x);    double minY = fmin(S.p1.y, S.p2.y);    double maxY = fmax(S.p1.y, S.p2.y);        return (P.x >= minX && P.x <= maxX &&             P.y >= minY && P.y <= maxY);}

2. 判断两条线段是否相交

这是几何算法入门中的经典问题。我们使用“快速排斥”+“跨立实验”两步法：

1. 快速排斥：两个线段的包围矩形必须相交
2. 跨立实验：每条线段的两个端点必须位于另一条线段的两侧（或在其上）

// 判断两个区间 [a1, a2] 和 [b1, b2] 是否重叠int overlap(double a1, double a2, double b1, double b2) {    if (a1 > a2) { double t = a1; a1 = a2; a2 = t; }    if (b1 > b2) { double t = b1; b1 = b2; b2 = t; }    return !(a2 < b1 || b2 < a1);}// 判断线段S1和S2是否相交int segmentsIntersect(Segment S1, Segment S2) {    // 快速排斥：包围盒不相交则线段不相交    if (!overlap(S1.p1.x, S1.p2.x, S2.p1.x, S2.p2.x) ||        !overlap(S1.p1.y, S1.p2.y, S2.p1.y, S2.p2.y)) {        return 0;    }        // 跨立实验    double d1 = cross(&S2.p1, &S2.p2, &S1.p1);    double d2 = cross(&S2.p1, &S2.p2, &S1.p2);    double d3 = cross(&S1.p1, &S1.p2, &S2.p1);    double d4 = cross(&S1.p1, &S1.p2, &S2.p2);        // 一般情况：两端点分别在两侧    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {        return 1;    }        // 特殊情况：端点在线段上    if (fabs(d1) < 1e-9 && isPointOnSegment(S1.p1, S2)) return 1;    if (fabs(d2) < 1e-9 && isPointOnSegment(S1.p2, S2)) return 1;    if (fabs(d3) < 1e-9 && isPointOnSegment(S2.p1, S1)) return 1;    if (fabs(d4) < 1e-9 && isPointOnSegment(S2.p2, S1)) return 1;        return 0;}

3. 计算多边形面积

对于简单多边形（无自交），我们可以使用鞋带公式（Shoelace Formula）快速计算面积。这也是点线面关系判断的重要应用之一。

// 使用鞋带公式计算多边形面积// points: 多边形顶点数组（按顺时针或逆时针顺序）// n: 顶点数量double polygonArea(Point points[], int n) {    if (n < 3) return 0.0;        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;    }    area = fabs(area) / 2.0;    return area;}

为什么学习C语言图形编程？

掌握C语言图形编程不仅能加深你对内存管理和算法效率的理解，还能为你进入游戏引擎开发、嵌入式图形界面、科学可视化等领域打下坚实基础。计算几何算法虽然数学性强，但通过模块化实现，完全可以被初学者掌握。

总结

本文介绍了三个核心的C语言计算几何算法：点在线段上判断、线段相交检测、多边形面积计算。这些是构建更复杂系统（如碰撞检测、路径规划）的基础。建议你动手编写并测试这些函数，修改参数观察结果，从而真正掌握几何算法入门的关键思想。

希望这篇教程能帮助你在C语言计算几何的道路上迈出坚实的第一步！