计算平面上两条线段的交点

在一个平面上，给出两条线段，判断它们是否有交点。如果有交点，求出这个交点；如果没有，返回null。

我们分析一下，什么情况下两线段才会相交。

首先我们要求出两线段对应的直线的交点。在一个平面上，两条不平行的线段，就必定有且只有一个交点。这个交点，如果在线段上，那就说明这两条线段是相交的。

另外，如果包围线段的两个矩形范围不相交，它们就不可能有交点：

/**
 * @param {Object{x: number, y:number}} p1 线段1的起点
 * @param {Object} p2 线段1的终点
 * @param {Object} p3 线段2的起点
 * @param {Object} p4 线段2的终点
 * @return {Object{type: number, x?:number, y?:number} | null}
 */
const getIntersectionFrom2Line = (p1, p2, p3, p4) => {
    
    // console.log(p1, p2, p2, p3)
    // 1. 求出两条线段的box，判断是否相交。
    let box1 = {},
        box2 = {};

    box1.x = Math.min(p1.x, p2.x)
    box1.y = Math.min(p1.y, p2.y)
    box1.x2 = Math.max(p1.x, p2.x),
    box1.y2 = Math.max(p1.y, p2.y),
        
    box2.x = Math.min(p3.x, p4.x),
    box2.y =  Math.min(p3.y, p4.y),
    box2.x2 = Math.max(p3.x, p4.x),
    box2.y2 = Math.max(p3.y, p4.y);

    // 判断box是否有相交区域。若没有，则返回null
    if(!(box1.x <= box2.x2 &&
        box1.x2 >= box2.x &&
        box1.y <= box2.y2 &&
        box1.y2 >= box2.y)
    ) return null; 


    // 2. 求出斜率。如果相同，说明平行，返回null
    const k1 = (p2.x - p1.x) / (p2.y - p1.y),
          k2 = (p4.x - p3.x) / (p4.y - p3.y);
    console.log(k1)
    console.log(k2)
    if (Math.abs(k1 - k2) < 0.000001) {  // 给一个误差值
        // 两线段平行
        return null;
    }
    
    // 3. 求出对应 “直线” 交点 （斜截式，二元一次方程组求解）
    // 这里暂未考虑垂直 x 轴 和 垂直 y 轴的情况
    const y = (-k2 * p3.y + p3.x + k1 * p1.y - p1.x) / (k1 - k2),
          x = k1 * (y - p1.y) + p1.x;
         
    // 4. 检查交点是否在任意一个 box 内。 
    if (x >= box1.x && x <= box1.x2){
        return {x, y};
    } else {
        return null;
    }
}