-
YAML 元数据 已设置 tags: [KACTL, 几何, 核心实体]。
-
核心概述 给定两条由点对 (s1,e1)、(s2,e2) 定义的直线，判断是否存在唯一交点、平行无交或重合，并在唯一交点时返回交点坐标。
-
原文引述
If a unique intersection point of the lines going through s1,e1 and s2,e2 exists {1, point} is returned. If no intersection point exists {0, (0,0)} is returned and if infinitely many exists {-1, (0,0)} is returned.
- 展开阐述
-
定义与背景
- 直线由两个不同点确定；本函数在“无限直线”意义下判定其关系，并给出状态码与交点。
- 典型用途：作为更复杂几何运算（多边形布尔、半平面交、外接圆构造）的基础原语。
-
接口/字段说明（据实现）
- 函数签名：template
pair<int,P> lineInter(P s1, P e1, P s2, P e2) - 返回：
- {1, p}：唯一交点 p
- {0, (0,0)}：平行无交
- {-1, (0,0)}：重合（无穷多交点）
- 类型注意：若 P=Point
且交点坐标为非整数，则除法截断会导致返回点不精确。
- 函数签名：template
-
核心流程/要点（向量与叉积）
- 令 d = (e1−s1) × (e2−s2)
- 若 d == 0：两直线平行或重合
- 若 s1.cross(e1, s2) == 0：重合 ⇒ 返回 {-1, (0,0)}
- 否则平行 ⇒ 返回 {0, (0,0)}
- 若 d == 0：两直线平行或重合
- 若 d ≠ 0（唯一交）：
- 令 p = s2.cross(e1, e2)，q = s2.cross(e2, s1)
- 交点 r = (s1·p + e1·q) / d
- 返回 {1, r}
- 令 d = (e1−s1) × (e2−s2)
-
复杂度与边界条件
- 时间：O(1)
- 边界与数值：
- 平行判定依赖叉积符号；建议结合 eps 处理浮点近似平行
- 整型中间会出现“三坐标乘积”，需防溢出（可用内置 128 位或长浮点）
- 对 P=Point
：非整交点会被截断，不适合需要精确坐标的小数场景
-
变体与扩展
- 线段相交：在唯一交点时再检查参数是否落入 [0,1]，参见 048-几何-线段相交
- 射线相交：参数区间改为 t≥0 判定
- 多线并发：可先做方向分组与哈希归类减少比较次数
-
正确性要点与不变式
- d 为两方向向量叉积，其为 0 当且仅当平行（含重合）；非零则存在唯一交
- 交点线性组合式来源于解二元一次方程组（参数方程）并以叉积避免显式解矩阵
-
与相邻技术的对比和取舍
- 032-几何-点线距离：提供量化的“离线远近”，而本函数给拓扑关系与交点
- 048-几何-线段相交：在本函数之上加区间裁剪，处理有限长度对象
- 039-几何-点：统一使用向量运算（dot/cross/dist）以保持实现一致
-
工程实践注意
- 输入去重：若 s1e1 或 s2e2 则“直线”退化，应在调用前规避
- eps 策略：浮点场景下统一使用阈值避免误判平行/重合
- 输出精度：对 double 返回保留足够小数位；对 ll 避免用于需小数的下游
- 关联节点