# 推導兩條線相交的算法

$$
line\_a\ 由\ (u_a, u_a + v_a)\ 構成，而\ p_a = u_a + sv_a \\
line\_b\ 由\ (u_b, u_b + v_b)\ 構成，而\ p_b = u_b + tv_b \\
其中\ u, v, p\ 都是\ 2d\ vector，且\ s, t \in [0, 1] \\
如果\ line\_a\ 與\ line\_b\ 相交的話，則 \\
p_a = p_b \\
\Rightarrow u_a + sv_a = u_b + tv_b \\
\Rightarrow u_a - u_b = -sv_a + tv_b \\
\Rightarrow
\begin{vmatrix}
u_{ax} - u_{bx} \\
u_{ay} - u_{by}
\end{vmatrix}
= -s
\begin{vmatrix}
v_{ax} \\
v_{ay}
\end{vmatrix}
+ t
\begin{vmatrix}
v_{bx} \\
v_{by}
\end{vmatrix} \\
\Rightarrow
\begin{vmatrix}
\Delta u_x \\
\Delta u_y
\end{vmatrix}
=
\begin{vmatrix}
v_{ax} & v_{bx} \\
v_{ay} & v_{by}
\end{vmatrix}
\begin{vmatrix}
-s \\
t
\end{vmatrix}
= \mathbf{M}
\begin{vmatrix}
-s \\
t
\end{vmatrix} \\
如果矩陣\ \mathbf{M}\ 是可逆的，則\ s, t\ 有解，即 \\
\begin{vmatrix}
-s \\
t
\end{vmatrix} = \mathbf{M}^{-1}
\begin{vmatrix}
\Delta u_x \\
\Delta u_y
\end{vmatrix} \\
令\ d = \det(\mathbf{M}) = v_{ax}v_{by} - v_{bx}v_{ay} \\
則\ \mathbf{M}^{-1} = \frac{1}{d}
\begin{vmatrix}
v_{by} & -v_{bx} \\
-v_{ay} & v_{ax}
\end{vmatrix} \\
所以\ \begin{vmatrix}
-s \\
t
\end{vmatrix} =
\frac{1}{d}
\begin{vmatrix}
v_{by} & -v_{bx} \\
-v_{ay} & v_{ax}
\end{vmatrix}
\begin{vmatrix}
\Delta u_x \\
\Delta u_y
\end{vmatrix} \\
於是可以得到\ s, t\ 的算式 \\
s = \frac{1}{d}(-v_{by}\Delta u_x + v_{bx}\Delta u_y) \\
t = \frac{1}{d}(-v_{ay}\Delta u_x + v_{ax}\Delta u_y) \\
如果\ d\ 為\ 0\ 代表這兩條線平行，\\
如果\ d\ 不為\ 0\ 且\ s, t \in [0, 1]\ 則兩條線相交，\\
其中\ s, t\ 可以代回對應的算式求交點座標。
$$