题目

给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。

要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。

示例 1：

输入：
line1 = {0, 0}, {1, 0}
line2 = {1, 1}, {0, -1}
输出： {0.5, 0}

示例 2：

输入：
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2}
输出： {1, 1}

示例 3：

输入：
line1 = {0, 0}, {1, 1}
line2 = {1, 0}, {2, 1}
输出： {}，两条线段没有交点

提示：

• 坐标绝对值不会超过 2^7
• 输入的坐标均是有效的二维坐标

题解

public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
    // 以方程式ax + by + c = 0表示一条直线
    BiFunction<int[], int[], int[]> lineProducer = (p1, p2) -> {
        int x1 = p1[0], y1 = p1[1], x2 = p2[0], y2 = p2[1];
        int x0 = x2 - x1, y0 = y2 - y1;
        if (x0 == 0) {
            // 与x轴平行
            // x + 0y - x1 = 0
            return new int[]{1, 0, -x1};
        } else if (y0 == 0) {
            // 与y轴平行
            // 0x + y0 - y1 = 0
            return new int[]{0, 1, -y1};
        } else {
            // 斜线
            // 两点直线方程式
            // (y-y1)/(x-x1) = (y2-y1)/(x2-x1) 令x0 = x2 - x1 y0 = y2 - y1
            // x0*(y-y1) = y0*(x-x1)
            // y0*x - x0*y + x0*y1 - y0*x1 = 0
            return new int[]{y0, -x0, x0 * y1 - y0 * x1};
        }
    };
    // 分别求的line1和line2的方程式
    int[] line1 = lineProducer.apply(start1, end1), line2 = lineProducer.apply(start2, end2);
    // 根据交点公式((b1*c2-b2*c1)/(a1*b2-a2*b1)，(a2*c1-a1*c2)/(a1*b2-a2*b1))
    // a1*b2-a2*b1 分母
    int denominator = line1[0] * line2[1] - line1[1] * line2[0];

    // 是否在区间内
    BiPredicate<double[], Double> inRange = (range, value) -> range[0] <= value && value <= range[1];
    double[] s1 = new double[]{start1[0], start1[1]}, e1 = new double[]{end1[0], end1[1]};
    double[] s2 = new double[]{start2[0], start2[1]}, e2 = new double[]{end2[0], end2[1]};
    // 线段1x坐标区间
    double[] rx1 = new double[]{Double.min(s1[0], e1[0]), Double.max(s1[0], e1[0])};
    double[] ry1 = new double[]{Double.min(s1[1], e1[1]), Double.max(s1[1], e1[1])};
    double[] rx2 = new double[]{Double.min(s2[0], e2[0]), Double.max(s2[0], e2[0])};
    double[] ry2 = new double[]{Double.min(s2[1], e2[1]), Double.max(s2[1], e2[1])};

    // 非平行线
    if (denominator != 0) {
        // 交点
        double[] cp = new double[]{
            (line1[1] * line2[2] - line2[1] * line1[2]) * 1.0D / denominator,
            (line2[0] * line1[2] - line1[0] * line2[2]) * 1.0D / denominator
        };

        // 若交点x坐标y坐标都在线段区间内 则存在交点 否则线段不相交
        return
            inRange.test(rx1, cp[0]) && inRange.test(rx2, cp[0])
                && inRange.test(ry1, cp[1]) && inRange.test(ry2, cp[1]) ? cp : new double[0];
    }

    // 重合线 a1*c2 - a2*c1 = 0 判断线段是否重叠
    // 若不重叠返回空 否则返回重叠最小坐标
    if (line1[0] * line2[2] - line2[0] * line1[2] == 0) {
        BiFunction<double[], double[], double[]> mp = (p1, p2) ->
            // 优先为x坐标值较小的 若x坐标相同 按照y坐标
            p1[0] != p2[0] ? (p1[0] < p2[0] ? p1 : p2) : (p1[1] < p2[1] ? p1 : p2);
        double[] mp1 = mp.apply(s1, e1), mp2 = mp.apply(s2, e2);
        if (inRange.test(rx2, mp1[0]) && inRange.test(ry2, mp1[1])) {
            return mp1;
        }

        if (inRange.test(rx1, mp2[0]) && inRange.test(ry1, mp2[1])) {
            return mp2;
        }
        // 否则 两条线段在同一直线 但是不重叠
    }

    // 平行线
    return new double[0];
}