C++线段相交算法详解（从零开始掌握计算几何中的线段交叉检测）

核心思想：方向向量与叉积

判断线段是否相交的关键在于使用向量叉积（Cross Product）来判断点的相对位置。叉积可以告诉我们一个点在另一条线段的“左侧”还是“右侧”。

定义向量 PQ = (x2 - x1, y2 - y1)，向量 PR = (x3 - x1, y3 - y1)，则叉积为：

// 叉积公式：// cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)  

叉积结果的符号决定了点 R 相对于线段 PQ 的方向：

• cross > 0：R 在 PQ 的左侧
• cross < 0：R 在 PQ 的右侧
• cross = 0：三点共线

快速排斥实验 + 跨立实验

完整的线段相交判断通常分为两步：

1. 快速排斥实验：先判断两条线段的包围矩形是否相交。如果不相交，线段肯定不相交。
2. 跨立实验：利用叉积判断每条线段的两个端点是否分别位于另一条线段的两侧。

C++ 实现代码

下面是一个完整、可运行的 C++ 线段相交判断函数：

#include <iostream>#include <algorithm>struct Point {    double x, y;};// 计算叉积：(p2 - p1) × (p3 - p1)double cross(const Point& p1, const Point& p2, const Point& p3) {    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);}// 判断点 p 是否在线段 ab 上（用于处理共线情况）bool onSegment(const Point& a, const Point& b, const Point& p) {    return std::min(a.x, b.x) <= p.x && p.x <= std::max(a.x, b.x) &&           std::min(a.y, b.y) <= p.y && p.y <= std::max(a.y, b.y);}// 判断线段 ab 和 cd 是否相交bool segmentsIntersect(const Point& a, const Point& b,                       const Point& c, const 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 true;    }    // 处理共线情况    if (d1 == 0 && onSegment(a, b, c)) return true;    if (d2 == 0 && onSegment(a, b, d)) return true;    if (d3 == 0 && onSegment(c, d, a)) return true;    if (d4 == 0 && onSegment(c, d, b)) return true;    return false;}int main() {    Point a = {0, 0}, b = {2, 2};    Point c = {0, 2}, d = {2, 0};    if (segmentsIntersect(a, b, c, d)) {        std::cout << "线段相交！\n";    } else {        std::cout << "线段不相交。\n";    }    return 0;}  

代码解析

1. cross 函数计算三个点构成的两个向量的叉积。
2. onSegment 用于判断共线时点是否真的在线段上。
3. segmentsIntersect 先通过叉积符号判断是否“跨立”，再处理边界共线情况。

这个算法的时间复杂度是 O(1)，非常高效，适用于实时系统如游戏引擎或机器人路径规划。

总结

通过本教程，你已经掌握了 C++判断线段是否相交 的核心方法。无论是做 计算几何 练习，还是开发需要 线段交叉检测 的应用，这套算法都能为你提供坚实基础。

建议你动手敲一遍代码，修改点的坐标测试不同情况（如平行、共线、端点相交等），加深理解。祝你在编程之路上越走越远！