两条二维线段的相交判定与交点返回：唯一交点给单点，无交为空，共线重叠返回端点对；覆盖端点/共线重叠/数值容差均需稳健处理。
If a unique intersection point between the line segments going from s1 to e1 and from s2 to e2 exists then it is returned. If no intersection point exists an empty vector is returned. If infinitely many exist a vector with 2 elements is returned, containing the endpoints of the common line segment.
展开阐述
-
定义与背景
- 目标：给定线段 a–b 与 c–d（二维），判断其是否相交，并按语义返回交集合：
- 空：不相交；单点：唯一交点；两点：共线且有重叠的线段端点（按参数顺序）。
- 典型场景：多边形布尔运算与裁剪、路径/障碍碰撞检测、图形渲染中的边相交过滤。
- 目标：给定线段 a–b 与 c–d（二维），判断其是否相交，并按语义返回交集合：
-
接口/数据结构（据实现）
- 函数签名：template
vector segInter(P a, P b, P c, P d)
- P 通常为 Point
（见 039-几何-点），T 可为 double 或 long long - 返回值：交集合（0/1/2 个点）
- P 通常为 Point
- 数值注意（据原文引述）：
- 若 P=Point
且交点坐标非整数，将返回错误位置（除法截断） - 中间将使用“三坐标乘积”，int/long long 可能溢出
- 若 P=Point
- 函数签名：template
-
核心流程/要点（定向面积/跨立实验 + 参数求交）
- 方向测试（有向面积）
- 记 oa = cross(c,d,a)，ob = cross(c,d,b)，oc = cross(a,b,c)，od = cross(a,b,d)
- 唯一交点充要条件：oa 与 ob 异号且 oc 与 od 异号（允许端点在对方线上则进入“端点集合”逻辑）
- 唯一交点的参数式
- 当存在唯一交点时，按比例求交：
- p = (a·ob − b·oa) / (ob − oa)（向量线性组合的标量系数形式，避免显式解线性方程）
- 当存在唯一交点时，按比例求交：
- 共线与端点处理
- 若两段共线（四个有向面积均为 0），收集所有“在线段上的端点”并去重/排序后返回首末两点（可能相同）
- onSegment 判定可复用 038-几何-点在线段上 或以投影参数 + 范围判定实现
- 容差与稳健
- 浮点：统一 eps 处理“≈0 的 cross”与端点相等；以 sgn(cross) 的三态比较避免抖动
- 整型：注意乘积溢出，必要时使用内建 128 位中间量
- 返回语义一致性
- 空向量：无交；单点：唯一交点；两点：共线重叠段的两个端点（按参数从 a→b 的顺序）
- 方向测试（有向面积）
-
复杂度与边界条件
- 时间复杂度：O(1)
- 边界/退化：
- 端点接触：视为“唯一交点”，返回端点
- 平行不共线：无交
- 共线但仅在端点处相接：可按唯一交点返回或落入“端点集合”后去重为单点
- 零长度段（ab 或 cd）：退化为点与线段交，一并由 onSegment 覆盖
- 数值与溢出：
- 整数几何：乘法和叉积可溢出 64 位；用 128 位或长浮点承载中间值
- 浮点几何：使用 eps 统一阈值；比较/排序时先按坐标，再用 eps 合并近等点
-
变体/扩展
- 射线-线段/射线-射线：在参数 t 的区间上将 [0,1] 替换为 [0,∞) 或同时替换
- 直线-直线唯一交点：参见 034-几何-直线相交，然后对参数落入区间进行裁剪
- 线段-多边形交：对每条边应用 segInter 并收集结果，或使用裁剪框架（见 044-几何-多边形切割）
-
正确性要点与不变式
- 方向（cross）符号一致性：以差向量构造并固定 ccw 正向；“异号即跨立”的充分必要性来自平面有向面积的连续性
- 去重与顺序：共线重叠返回“端点区间”；按参数有序可避免输出自相矛盾
- 端点优先：先判端点落段上可稳定处理“触碰”而不依赖精细阈值
-
与相邻技术的对比与取舍
- 034-几何-直线相交：无限直线层面的关系判定；本节点在此基础上做区间裁剪
- 038-几何-点在线段上：边界与共线分支依赖该判定以确保稳健
- 047-几何-线段间距离：当 segInter 为空时，最近距离由端点到对段的最小值给出