the intersection point of two lines

概要

点\((x_0, y_0)\)と点\((x_1, y_1)\)を通る直線1と点\((x_2, y_2)\)と点\((x_3, y_3)\)を通る直線2の交点を求める。

具体的計算

\(a_0 = x_1 - x_0, b_0 = y_1 - y_0\)
\(a_2 = x_3 - x_2, b_2 = y_3 - y_2\)

とする。

2つの直線上の点 \((x, y)\) は

\(\displaystyle \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} x_0 \\ y_0 \end{array} \right) + s \left( \begin{array}{c} a_0 \\ b_0 \end{array} \right)\), \(\displaystyle \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} x_2 \\ y_2 \end{array} \right) + t \left( \begin{array}{c} a_2 \\ b_2 \end{array} \right)\)

と表すことができるため、この交点は

\(\displaystyle \left( \begin{array}{c} x_0 \\ y_0 \end{array} \right) + s \left( \begin{array}{c} a_0 \\ b_0 \end{array} \right) = \left( \begin{array}{c} x_2 \\ y_2 \end{array} \right) + t \left( \begin{array}{c} a_2 \\ b_2 \end{array} \right)\)

となる \(s, t\) を求めれば計算できる。

この \(s, t\) は、以下を計算することで求められる。

\(\displaystyle \left( \begin{array}{c} s \\ t \end{array} \right) = \frac{1}{a_0b_2 - a_2b_0} \left( \begin{array}{cc} b_2 & -a_2 \\ b_0 & -a_0 \end{array} \right) \left( \begin{array}{cc} x_2 - x_0 \\ y_2 - y_0 \end{array} \right)\)

2つの直線は平行の場合、 \(a_0b_2 - a_2b_0 = 0\) となる。 (解なし、もしくは無数に解が存在する)

また、 \(0 \le s \le 1\) や \(0 \le t \le 1\) に絞ることで線分上に点が存在するかを判定できる。

実装

def line_cross_point(P0, P1, Q0, Q1):
    x0, y0 = P0; x1, y1 = P1
    x2, y2 = Q0; x3, y3 = Q1
    a0 = x1 - x0; b0 = y1 - y0
    a2 = x3 - x2; b2 = y3 - y2

    d = a0*b2 - a2*b0
    if d == 0:
        # two lines are parallel
        return None

    # s = sn/d
    sn = b2 * (x2-x0) - a2 * (y2-y0)
    # t = tn/d
    #tn = b0 * (x2-x0) - a0 * (y2-y0)
    return x0 + a0*sn/d, y0 + b0*sn/d
print(line_cross_point((0, 0), (0, 3), (1, 10), (3, -1)))
# => (0.0, 15.5)

Verified

  • AOJ: "CGL_2_C: Segments/Lines - Cross Point": source (Python3, 0.03sec)