实现类扫线算法时，如何精确计算两条几乎平行线段的交点？

问题本质 #

近乎平行的线段交点计算易受端点微小误差干扰，核心原因是线性方程组的病态性——两条直线方向向量近乎共线，导致系数矩阵条件数极大，普通求解方法会放大误差。

最优求解思路 #

1. 基于垂直投影的鲁棒插值法 #

这是处理此类场景最实用的方法，避开病态方程组求解：

• 选取其中一条线段（如AB）作为基准，计算另一条线段（CD）两端点到AB的带符号垂直距离
• 由于线段相交，两端点的距离符号必然相反（或其中一个为0），通过线性插值找到CD上距离AB为0的点，即为交点
  • 具体步骤：
    1. 计算向量 AB = B - A，AC = C - A，AD = D - A
    2. 生成AB的单位法向量 n（垂直于AB的单位向量）
    3. 计算C、D到AB的带符号距离：d_C = dot(AC, n)，d_D = dot(AD, n)
    4. 插值参数 t = d_C / (d_C - d_D)（因相交，d_C*d_D ≤ 0，分母不会趋近于0）
    5. 交点 P = C + t*(D - C)
  • 优势：误差被限制在垂直于基准线段的方向，对平行度敏感度远低于传统方法

2. 精确有理数运算（整数坐标场景） #

若线段端点为整数坐标，可通过精确有理数运算完全避免浮点误差：

• 用参数方程表示两条线段：
  • 线段1：P1(s) = A + s*(B - A)，s ∈ [0,1]
  • 线段2：P2(t) = C + t*(D - C)，t ∈ [0,1]
• 联立方程得到线性方程组，全程用分数运算求解s和t，再验证参数是否在[0,1]区间内
• 即使线段近乎平行，只要确实相交，就能得到精确的分数形式交点坐标

3. 最小二乘拟合（端点带误差场景） #

如果端点本身存在测量误差，最优方案是拟合两条直线的最小二乘交点：

• 对四个端点分别拟合直线 L1: a1x + b1y + c1 = 0 和 L2: a2x + b2y + c2 = 0
• 求解使 (a1x + b1y + c1)^2 + (a2x + b2y + c2)^2 最小的点，即两条直线的最小二乘交点
• 该方法能给出统计意义上最优的交点，适合端点含随机误差的场景

避坑提醒 #

• 不要直接用克莱姆法则等传统公式处理近乎平行线段，分母趋近于0会导致数值爆炸
• 先做平行性预判：计算两条线段方向向量的叉积，若绝对值小于设定的极小阈值（如1e-8，按需调整），立即切换到鲁棒求解逻辑

内容的提问来源于stack exchange，提问作者Nekomiya Kasane