推導兩條線相交的算法

l i n e_a 由 (u_{a}, u_{a} + v_{a}) 構 成 ， 而 p_{a} = u_{a} + s v_{a} l i n e_b 由 (u_{b}, u_{b} + v_{b}) 構 成 ， 而 p_{b} = u_{b} + t v_{b} 其 中 u, v, p 都 是 2 d v e c t o r ， 且 s, t \in [0, 1] 如 果 l i n e_a 與 l i n e_b 相 交 的 話 ， 則 p_{a} = p_{b} \Rightarrow u_{a} + s v_{a} = u_{b} + t v_{b} \Rightarrow u_{a} - u_{b} = - s v_{a} + t v_{b} \Rightarrow | \begin{matrix} u_{a x} - u_{b x} \\ u_{a y} - u_{b y} \end{matrix} | = - s | \begin{matrix} v_{a x} \\ v_{a y} \end{matrix} | + t | \begin{matrix} v_{b x} \\ v_{b y} \end{matrix} | \Rightarrow | \begin{matrix} Δ u_{x} \\ Δ u_{y} \end{matrix} | = | \begin{matrix} v_{a x} & v_{b x} \\ v_{a y} & v_{b y} \end{matrix} | | \begin{matrix} - s \\ t \end{matrix} | = M | \begin{matrix} - s \\ t \end{matrix} | 如 果 矩 陣 M 是 可 逆 的 ， 則 s, t 有 解 ， 即 | \begin{matrix} - s \\ t \end{matrix} | = M^{- 1} | \begin{matrix} Δ u_{x} \\ Δ u_{y} \end{matrix} | 令 d = det (M) = v_{a x} v_{b y} - v_{b x} v_{a y} 則 M^{- 1} = \frac{1}{d} | \begin{matrix} v_{b y} & - v_{b x} \\ - v_{a y} & v_{a x} \end{matrix} | 所 以 | \begin{matrix} - s \\ t \end{matrix} | = \frac{1}{d} | \begin{matrix} v_{b y} & - v_{b x} \\ - v_{a y} & v_{a x} \end{matrix} | | \begin{matrix} Δ u_{x} \\ Δ u_{y} \end{matrix} | 於 是 可 以 得 到 s, t 的 算 式 s = \frac{1}{d} (- v_{b y} Δ u_{x} + v_{b x} Δ u_{y}) t = \frac{1}{d} (- v_{a y} Δ u_{x} + v_{a x} Δ u_{y}) 如 果 d 為 0 代 表 這 兩 條 線 平 行 ， 如 果 d 不 為 0 且 s, t \in [0, 1] 則 兩 條 線 相 交 ， 其 中 s, t 可 以 代 回 對 應 的 算 式 求 交 點 座 標 。