题解 | #两直线交点#

题目链接

两直线交点

题目描述

给定两条直线，每条直线由两个不同的点确定。你需要计算这两条直线的交点坐标。

题目以核心代码模式提供，你需要实现 findMeetingPoint 函数。
直线 A 由点 $P_1, P_2$ 定义。
直线 B 由点 $P_3, P_4$ 定义。
如果两直线平行或重合（没有唯一交点），则返回点 (-1, -1)。
数据保证每条直线上的两个定义点不重合。

示例: 输入:

Line 1: (0, 0), (1, 1)
Line 2: (0, 2), (2, 0) 输出: 1.000000 1.000000

解题思路

这是一个典型的计算几何问题，可以通过解线性方程组来解决。最稳健的方法是使用直线的参数方程和向量叉积。

参数方程表示法

一条经过点 $P_1$ 和 $P_2$ 的直线可以表示为： $L_1(t) = P_1 + t \cdot (P_2 - P_1)$ 其中 $t$ 是一个任意实数参数。

同样，经过点 $P_3$ 和 $P_4$ 的第二条直线可以表示为： $L_2(u) = P_3 + u \cdot (P_4 - P_3)$ 其中 $u$ 是另一个任意实数参数。

求解交点

如果两直线相交，那么在交点处，存在特定的 $t$ 和 $u$ 使得 $L_1(t) = L_2(u)$ 。 $P_1 + t \cdot (P_2 - P_1) = P_3 + u \cdot (P_4 - P_3)$

为了求解 $t$ （或 $u$ ），我们可以利用二维向量的叉积。将上式两边同时与向量 $(P_4 - P_3)$ 进行叉积运算： $(P_1 - P_3) \times (P_4 - P_3) = t \cdot (P_2 - P_1) \times (P_4 - P_3)$

这里的叉积 $A \times B$ 定义为 $A_x B_y - A_y B_x$ 。由此，我们可以解出参数 $t$ ： $t = \frac{(P_1 - P_3) \times (P_4 - P_3)}{(P_2 - P_1) \times (P_4 - P_3)}$

关键步骤:

计算分母 (Denominator): den = (P_2 - P_1) × (P_4 - P_3) den = (x_2 - x_1)(y_4 - y_3) - (y_2 - y_1)(x_4 - x_3) 如果 den 等于 0（或由于浮点数精度问题，其绝对值非常小），则说明两直线平行或重合，没有唯一交点。此时返回 (-1, -1)。
计算分子 (Numerator) 并求出 t: num = (P_1 - P_3) × (P_4 - P_3) num = (x_1 - x_3)(y_4 - y_3) - (y_1 - y_3)(x_4 - x_3) $t = \text{num} / \text{den}$
计算交点坐标: 将求得的 $t$ 值代入第一条直线的参数方程，即可得到交点的坐标： $x_{intersect} = x_1 + t \cdot (x_2 - x_1)$ $y_{intersect} = y_1 + t \cdot (y_2 - y_1)$
返回交点。

代码

cpp
java
python

const double EPS = 1e-9;

point findMeetingPoint(line line_A, line line_B){
    double x1 = line_A.point_A.x, y1 = line_A.point_A.y;
    double x2 = line_A.point_B.x, y2 = line_A.point_B.y;
    double x3 = line_B.point_A.x, y3 = line_B.point_A.y;
    double x4 = line_B.point_B.x, y4 = line_B.point_B.y;

    double den = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3);

    // 如果分母接近0，则直线平行或重合
    if (std::abs(den) < EPS) {
        return point(-1, -1);
    }
    
    // 使用 t 的公式分子部分不同，这里直接展开求解
    // t = ((x3-x1)*(y4-y3) - (y3-y1)*(x4-x3)) / den
    double t_num = (x3 - x1) * (y4 - y3) - (y3 - y1) * (x4 - x3);
    double t = t_num / den;

    double intersect_x = x1 + t * (x2 - x1);
    double intersect_y = y1 + t * (y2 - y1);

    return point(intersect_x, intersect_y);
}

private static final double EPS = 1e-9;

public static Point findMeetingPoint(Line lineA, Line lineB) {
    double x1 = lineA.point_A.x, y1 = lineA.point_A.y;
    double x2 = lineA.point_B.x, y2 = lineA.point_B.y;
    double x3 = lineB.point_A.x, y3 = lineB.point_A.y;
    double x4 = lineB.point_B.x, y4 = lineB.point_B.y;

    double den = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3);

    // 如果分母接近0，则直线平行或重合
    if (Math.abs(den) < EPS) {
        return new Point(-1, -1);
    }

    double t_num = (x3 - x1) * (y4 - y3) - (y3 - y1) * (x4 - x3);
    double t = t_num / den;

    double intersectX = x1 + t * (x2 - x1);
    double intersectY = y1 + t * (y2 - y1);

    return new Point(intersectX, intersectY);
}

EPS = 1e-9

def find_meeting_point(line_A: Line, line_B: Line) -> Point:
    x1, y1 = line_A.point_A.x, line_A.point_A.y
    x2, y2 = line_A.point_B.x, line_A.point_B.y
    x3, y3 = line_B.point_A.x, line_B.point_A.y
    x4, y4 = line_B.point_B.x, line_B.point_B.y

    den = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3)

    # 如果分母接近0，则直线平行或重合
    if abs(den) < EPS:
        return Point(-1, -1)

    t_num = (x3 - x1) * (y4 - y3) - (y3 - y1) * (x4 - x3)
    t = t_num / den

    intersect_x = x1 + t * (x2 - x1)
    intersect_y = y1 + t * (y2 - y1)

    return Point(intersect_x, intersect_y)

算法及复杂度

算法: 向量参数方程与叉积
时间复杂度: $\mathcal{O}(1)$ 。该计算涉及固定数量的算术运算。
空间复杂度: $\mathcal{O}(1)$ 。没有使用与输入规模相关的额外空间。