LeetCode.程序员面试金典.1603.Intersection 交点

题目描述

《程序员面试金典（第 6 版）》面试题 16.03. 交点
https://leetcode-cn.com/problems/intersection-lcci/

给定两条线段（表示为起点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
输入的坐标均是有效的二维坐标

---

解题过程

不会做，直奔题解。
结果看完题解也发现写起来很费劲，直接copy了别人实现的官方题解一的java版。

不平行时

线段 (x1, y1) - (x2, y2) 的参数方程为

$$
\begin{cases}
x = x_1 + t_1(x_2 - x_1) \\
y = y_1 + t_1(y_2 - y_1)
\end{cases}
\quad t_1 \in [0,1]
$$

线段 (x3, y3) - (x4, y4) 的参数方程为

$$
\begin{cases}
x = x_3 + t_2(x_4 - x_3) \\
y = y_3 + t_2(y_4 - y_3)
\end{cases}
\quad t_2 \in [0,1]
$$

联立这两个方程组得

$$
\begin{cases}
x_1 + t_1(x_2 - x_1) = x_3 + t_2(x_4 - x_3) \\
y_1 + t_1(y_2 - y_1) = y_3 + t_2(y_4 - y_3)
\end{cases}
$$

进而可求出 $t_1$ 和 $t_2$

$$
\begin{cases}
t_1 = \frac{x_3(y_4-y_3) + y_1(x_4-x_3) - y_3(x_4-x_3) - x_1(y_4-y_3)}{(x_2-x_1)(y_4-y_3) - (x_4-x_3)(y_2-y_1)} \\
t_2 = \frac{x_1(y_2-y_1) + y_3(x_2-x_1) - y_1(x_2-x_1) - x_3(y_2-y_1)}{(x_4-x_3)(y_2-y_1) - (x_2-x_1)(y_4-y_3)}
\end{cases}
$$

$t_1$ 描述了交点在线段 (x1, y1) ∼ (x2,y2) 所在直线上的位置，t_2 描述了交点在线段 (x3, y3) ∼ (x4,y4) 所在直线上的位置。
只需要判断是否有 $0 \leq t_1 \leq 1$ 和 $0 \leq t_2 \leq 1$ 即可判断交点是否在线段上。

平行时

太复杂了，放弃，copy代码

代码

时间复杂度 O(1)，空间复杂度O(1)

private static class SolutionV2020 {
    public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
        int x1 = start1[0], y1 = start1[1];
        int x2 = end1[0], y2 = end1[1];
        int x3 = start2[0], y3 = start2[1];
        int x4 = end2[0], y4 = end2[1];

        double[] ans = new double[2];
        Arrays.fill(ans, Double.MAX_VALUE);
        // 判断两直线是否平行
        if ((y4-y3)*(x2-x1) == (y2-y1)*(x4-x3)) {
            // 判断两直线是否重叠
            if ((y2-y1)*(x3-x1) == (y3-y1)*(x2-x1)) {
                // 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上
                if (isInside(x1, y1, x2, y2, x3, y3)) {
                    updateRes(ans, x3, y3);
                }
                // 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上
                if (isInside(x1, y1, x2, y2, x4, y4)) {
                    updateRes(ans, (double)x4, (double)y4);
                }
                // 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上
                if (isInside(x3, y3, x4, y4, x1, y1)) {
                    updateRes(ans, (double)x1, (double)y1);
                }
                // 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上
                if (isInside(x3, y3, x4, y4, x2, y2)) {
                    updateRes(ans, (double)x2, (double)y2);
                }
            }
        } else {
            // 联立方程得到 t1 和 t2 的值
            double t1 = (double)(x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1));
            double t2 = (double)(x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3));
            // 判断 t1 和 t2 是否均在 [0, 1] 之间
            if (t1 >= 0.0 && t1 <= 1.0 && t2 >= 0.0 && t2 <= 1.0) {
                ans[0] = x1 + t1 * (x2 - x1);
                ans[1] = y1 + t1 * (y2 - y1);
            }
        }
        if (ans[0] == Double.MAX_VALUE) {
            return new double[0];
        }
        return ans;
    }

    // 判断 (x, y) 是否在「线段」(x1, y1)~(x2, y2) 上
    // 这里的前提是 (x, y) 一定在「直线」(x1, y1)~(x2, y2) 上
    private boolean isInside(int x1, int y1, int x2, int y2, int x, int y) {
        // 若与 x 轴平行，只需要判断 x 的部分
        // 若与 y 轴平行，只需要判断 y 的部分
        // 若为普通线段，则都要判断
        return (x1 == x2 || (Math.min(x1, x2) <= x && x <= Math.max(x1, x2)))
                && (y1 == y2 || (Math.min(y1, y2) <= y && y <= Math.max(y1, y2)));
    }

    private void updateRes(double[] ans, double x, double y) {
        if (x < ans[0] || (x == ans[0] && y < ans[1])) {
            ans[0] = x;
            ans[1] = y;
        }
    }
}

---

GitHub代码

algorithms/leetcode/crack/_1603_Intersection.java
https://github.com/masikkk/algorithms/blob/master/leetcode/crack/_1603_Intersection.java

---