C语言线段相交算法（小白也能看懂的线段交叉检测教程）

核心思想：方向与跨立

判断线段是否相交，常用的方法是跨立实验（Cross Product Method）。其基本原理是：

• 如果线段 AB 和 CD 相交，那么点 C 和 D 必须分别位于 AB 的两侧；
• 同时，点 A 和 B 也必须分别位于 CD 的两侧。

这可以通过向量叉积（cross product）来判断方向。

步骤详解

1. 定义点结构体：用 (x, y) 表示一个点。
2. 编写叉积函数：计算向量 OA × OB 的值。
3. 判断方向：通过叉积符号判断点在直线的哪一侧。
4. 跨立判断：检查两线段是否互相跨立。
5. 处理特殊情况：如共线、端点重合等（本教程先实现基础版本）。

完整 C 语言代码实现

下面是一个清晰、可运行的 C 语言程序，用于判断两条线段是否相交：

#include <stdio.h>// 定义点结构体typedef struct {    double x, y;} Point;// 计算向量 (p1 - p0) × (p2 - p0) 的叉积double cross(const Point* p0, const Point* p1, const Point* p2) {    return (p1->x - p0->x) * (p2->y - p0->y) -            (p2->x - p0->x) * (p1->y - p0->y);}// 判断点 p 是否在线段 ab 上（用于处理共线情况）int onSegment(Point a, Point b, Point p) {    return p.x >= (a.x < b.x ? a.x : b.x) &&           p.x <= (a.x > b.x ? a.x : b.x) &&           p.y >= (a.y < b.y ? a.y : b.y) &&           p.y <= (a.y > b.y ? a.y : b.y);}// 判断线段 ab 和 cd 是否相交int doIntersect(Point a, Point b, Point c, Point d) {    double d1 = cross(&a, &b, &c);    double d2 = cross(&a, &b, &d);    double d3 = cross(&c, &d, &a);    double d4 = cross(&c, &d, &b);    // 一般情况：互相跨立    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))        return 1;    // 特殊情况：某点在线段上（共线）    if (d1 == 0 && onSegment(a, b, c)) return 1;    if (d2 == 0 && onSegment(a, b, d)) return 1;    if (d3 == 0 && onSegment(c, d, a)) return 1;    if (d4 == 0 && onSegment(c, d, b)) return 1;    return 0;}int main() {    Point a = {0, 0};    Point b = {4, 4};    Point c = {0, 4};    Point d = {4, 0};    if (doIntersect(a, b, c, d)) {        printf("线段相交！\n");    } else {        printf("线段不相交。\n");    }    return 0;}

代码说明

- cross() 函数计算叉积，结果正负表示方向；

- onSegment() 处理三点共线时，判断点是否在线段上；

- doIntersect() 是主判断函数，结合了跨立和共线两种情况。

应用场景

掌握 C语言判断线段是否相交 的技能后，你可以在以下领域大展身手：

• 2D 游戏中的碰撞检测；
• 地图路径规划（如判断道路是否交叉）；
• 计算机辅助设计（CAD）软件；
• 机器人避障算法。

总结

本文详细讲解了 线段交叉检测 的原理与 C 语言实现。通过叉积判断方向，再结合跨立实验，我们就能高效准确地判断两条线段是否相交。这是 计算几何 中的基础算法，建议你动手敲一遍代码，加深理解！

关键词：C语言线段相交算法、计算几何、C语言判断线段是否相交、线段交叉检测