1. 概述

可以通過線段的跨立實(shí)驗(yàn)[1]判斷兩條線段是否相交，但是想要進(jìn)一步求它們的交點(diǎn)還是比較麻煩。[2]給出的方法更加簡(jiǎn)單，其原理來自求三維空間兩條線段的交點(diǎn)[3]。為了更好的理解，本文將詳細(xì)介紹二維空間兩條線段的交點(diǎn)求解過程。

(資料圖)

2. 兩條線段交點(diǎn)求解過程

給定兩條線段\(\overline{P_1 P_2}\)和\(\overline{P_3 P_4}\)，端點(diǎn)表示為\(P_1(x_1,y_1)\)、\(P_2(x_2,y_2)\)、\(P_3(x_3,y_3)\)和\(P_4(x_4,y_4)\)，兩條線段對(duì)應(yīng)的向量表示為\(\overrightarrow{P_1 P_2}\)和\(\overrightarrow{P_3 P_4}\)。假設(shè)兩條線段的交點(diǎn)為\(P_0(x_0,y_0)\)，且\(t=\frac{|\overline{P_1 P_0}|}{|\overline{P_1 P_2}|}\) 、\(s=\frac{|\overline{P_3 P_0}|}{|\overline{P_3 P_4}|}\)，那么 \(P_0\) 可以表示為：

\[\begin{cases}P_0=P_1 + t * \overrightarrow{P_1 P_2} , 0\leq t \leq 1 \\P_0=P_3 + s * \overrightarrow{P_3 P_4} , 0\leq s \leq 1\end{cases}\]

\(t\)和\(s\)在等于\(0\)或\(1\)時(shí)表示兩條線段相交在端點(diǎn)，如果為其他值，表示兩條線段不相交。將點(diǎn)坐標(biāo)代入公式得：

\[\begin{cases}x_1 + t * (x_2 - x_1) = x_3 + s * (x_4 - x_3) \\y_1 + t * (y_2 - y_1) = y_3 + s * (y_4 - y_3)\end{cases}\]

利用公式消元法求得\(t\)和\(s\)：

\[t = \frac{ (x_3 - x_1)(y_4 - y_3) - (y_3 - y_1)(x_4 - x_3) }{ (x_2 - x_1)(y_4 - y_3) - (y_2 - y_1)(x_4 - x_3) } \\ s = \frac{ (x_3 - x_1)(y_2 - y_1) - (y_3 - y_1)(x_2 - x_1) }{ (x_2 - x_1)(y_4 - y_3) - (y_2 - y_1)(x_4 - x_3)} \]

\(t\)和\(s\)方程的分子和分母都是向量的叉乘：

\[t = \frac{ \overrightarrow{P_3 P_1} * \overrightarrow{P_4 P_3} } { \overrightarrow{P_2 P_1} * \overrightarrow{P_4 P_3} } \\ s = \frac{ \overrightarrow{P_3 P_1} * \overrightarrow{P_2 P_1} }{ \overrightarrow{P_2 P_1} * \overrightarrow{P_4 P_3} } \]

如果\(\overrightarrow{P_2 P_1} * \overrightarrow{P_4 P_3} = 0\)，表示兩條線段平行，如果端點(diǎn)在另一條線段上，則該端點(diǎn)為交點(diǎn)，否則不是。如果\(t\)和\(s\)有一個(gè)沒有落在區(qū)間\([0,1]\)內(nèi)，則兩條線段不相交。那么交點(diǎn)\(P_0\)的坐標(biāo)為：

\[\begin{cases}x_0 = x_1 + t*(x_2 - x_1) \\y_0 = y_1 + t*(y_2 - y_1)\end{cases}\]

或

\[\begin{cases}x_0 = x_3 + s*(x_4 - x_3) \\y_0 = y_3 + s*(y_4 - y_3)\end{cases}\]

至此，整個(gè)求解過程介紹完成，再去看[2]的代碼就非常容易理解了。

參考文獻(xiàn)

1. How to check if two given line segments intersect?

2. Find the Intersection Point of Two Line Segments

3. Intersections of Lines In Three-Space - Jon Garvin