如何修复JS线段相交检测函数共享端点时返回false positive误报问题

• 基于Google Maps SDK开发地图项目，绘制新线段前需要校验新线段与已有线段的相交关系
• 当前存在检测误报：实际不相交的线段会被判定为相交，所有误判线段对都存在共享公共端点的特征
• 项目共约150条线段，其中10-15条与待检测线段共享端点的线段会被误判；调换两个线段传入检测函数的顺序时，检测结果会发生变化
• 原检测函数实现如下，测试用例中两条线段仅共享端点，函数会错误返回true：

let crosses = intersects(
        39.018223, -76.75899, 39.018387, -76.758773,
        39.018387, -76.758773, 39.019813, -76.757388,
);
      
console.log('Intersects:', crosses);

// returns true if the line from (a,b)->(c,d) intersects with (p,q)->(r,s)
function intersects(a,b,c,d,p,q,r,s) {
        var det, gamma, lambda;
        det = (c - a) * (s - q) - (r - p) * (d - b);
        if (det === 0) {
                console.log('det is zero');
                return false;
        } else {
                lambda = ((s - q) * (r - a) + (p - r) * (s - b)) / det;
                gamma = ((b - d) * (r - a) + (c - a) * (s - b)) / det;
                return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);
        }
};

该问题和地理坐标适配无关，核心原因有两点：

1. 原函数存在变量书写错误：计算lambda参数时误用了线段端点坐标，导致参数计算结果偏移，调换线段传入顺序时计算结果不一致
2. 浮点数计算存在精度误差：共享端点场景下，本应等于0或1的lambda、gamma参数会出现微小偏移，恰好落在原函数设定的(0,1)开区间判断范围内，触发误判

引入极小容差值抵消浮点数计算误差，同时修正原函数的变量计算错误，调整判断逻辑适配「共享端点不算相交」的业务需求，修复后代码如下：

// 浮点精度容差，可根据业务使用的坐标精度调整
const EPSILON = 1e-10;

/**
 * 检测两条线段是否相交（仅判定线段真正交叉的场景，共享端点、端点落在线段上不算相交）
 * 线段1坐标范围：(a,b) -> (c,d)
 * 线段2坐标范围：(p,q) -> (r,s)
 */
function intersects(a,b,c,d,p,q,r,s) {
  const det = (c - a) * (s - q) - (r - p) * (d - b);
  // 两线平行/共线时直接判定不相交，如需识别共线重叠场景可在此处追加逻辑
  if (Math.abs(det) < EPSILON) {
    return false;
  }
  // 修正原函数变量错误，正确计算两线段的交点位置参数
  const lambda = ((s - q) * (p - a) - (r - p) * (q - b)) / det;
  const gamma = ((b - d) * (p - a) + (c - a) * (q - b)) / det;
  // 加入容差判断，排除端点接触场景，抵消浮点误差影响
  return (lambda > EPSILON && lambda < 1 - EPSILON) && (gamma > EPSILON && gamma < 1 - EPSILON);
}

使用上述修复后的函数测试原有误判用例，会正确返回false，调换线段传入顺序结果保持一致。

补充说明 #

• 如果后续业务需要将「共享端点、线段端点落在另一条线段上」的场景也判定为相交，只需要将判断条件调整为(lambda >= -EPSILON && lambda <= 1 + EPSILON) && (gamma >= -EPSILON && gamma <= 1 + EPSILON)即可
• 该平面几何计算方案在小范围（线段长度10公里以内）的经纬度坐标场景下误差可以忽略，性能远高于球面相交算法；如果业务涉及跨度几十公里以上的长线段检测，再考虑替换为球面线段相交算法即可。

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