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)