快速排斥试验通过判断两线段轴对齐包围矩形是否重叠来预筛不相交情况，需同时满足：min(a.x,b.x)≤max(c.x,d.x)、min(c.x,d.x)≤max(a.x,b.x)、min(a.y,b.y)≤max(c.y,d.y)、min(c.y,d.y)≤max(a.y,b.y)。
快速排斥试验：先筛掉明显不相交的情况
两条线段不相交，最常见原因是它们在 x 或 y 方向上完全错开。比如 AB 全在 CD 左边，或 AB 全在 CD 下方——这种情况下根本不用算叉积，直接返回 false。
判断依据是：以每条线段为对角线构造矩形，看两个矩形是否重叠。四个条件必须**同时满足**，矩形才可能重叠：
min(a.x, b.x)min(c.x, d.x)min(a.y, b.y)min(c.y, d.y)
任意一个不成立，就说明矩形无重叠，线段必然不相交。注意这里用的是 ，允许端点对齐（共线但不重叠也算不相交，后续跨立会处理端点落在另一线段上的情况）。
跨立试验：用叉积判断“是否分居两侧”
快速排斥通过后，还需确认：一条线段的两个端点是否分别落在另一线段所在直线的两侧（或至少一个端点在线段上）。这正是叉积的强项——它能通过符号判断相对方向。
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
设向量 u = c - a，v = d - a，w = b - a，则：
-
Cross(u, w)和Cross(v, w)同号 →c、d在ab同侧 → 不跨立 - 异号 →
c、d在ab两侧 → 跨立成功 - 其中一者为 0 → 对应点在线段
ab所在直线上，需结合快速排斥判断是否真在线段上
因此，AB 跨立 CD 的判定是：Cross(c - a, b - a) * Cross(d - a, b - a) ；同理，<code>CD 跨立 AB 是：Cross(a - c, d - c) * Cross(b - c, d - c) 。两者都成立才算相交。
Cross 函数怎么写才不出错
叉积计算本身很简单，但容易因坐标类型、精度、顺序出错：
- 务必用
double或带足够精度的整数类型，避免int溢出（如坐标范围 ±1e5 时，乘积可达 1e10） - 函数签名推荐：
double Cross(const Point& a, const Point& b, const Point& c)，表示向量ab × ac，即(b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) - 不要省略括号，尤其当参数是表达式时，如
Cross(a, c, d)表示(c-a) × (d-a)，不是c × d - 浮点比较慎用
== 0，但跨立中用是安全的——因为 0 值只出现在共线情形，而快速排斥已保证该共线点在线段投影范围内
端点重合、共线重叠这些边界怎么处理
标准快速排斥 + 双跨立能覆盖绝大多数情况，但以下边界需特别注意：
- 一个端点恰好落在另一线段内部（如
c在ab上）：此时Cross(c - a, b - a) == 0，且快速排斥已确保c的坐标在[min(a.x,b.x), max(a.x,b.x)]和[min(a.y,b.y), max(a.y,b.y)]内 → 跨立条件中乘积为 0，判定为相交 ✔ - 两线段共线且部分重叠（如
ab = [(0,0),(2,0)]，cd = [(1,0),(3,0)]）：快速排斥通过，且两个跨立乘积均为 0 → 判定为相交 ✔ - 两线段共线但不重叠（如
ab = [(0,0),(1,0)]，cd = [(2,0),(3,0)]）：快速排斥失败（max(a.x,b.x) ）→ 直接返回 <code>false✔
真正容易漏的是浮点误差导致的“本该为 0 却是极小负数”，建议加 eps = 1e-9 容差，把判断改成 ，但不要对叉积结果做 abs 或 round——那会破坏符号语义。
