判斷 2 個(gè)線段相交有很多方法，最直接的方法就是直接計(jì)算兩條直線的交點(diǎn)，然后看看交點(diǎn)是否分別在這兩條線段上。這樣的方法很容易理解，但是代碼實(shí)現(xiàn)比較麻煩。

還有一種常用的方法是通過向量叉積來判斷的，這種方法不需要算出直線方程，在代碼實(shí)現(xiàn)上比較簡便。
用這種方法判別線段是否相交一般分為兩步：
1. 快速排斥實(shí)驗(yàn)
2. 跨立實(shí)驗(yàn)

快速排斥實(shí)驗(yàn)

我們首先判斷兩條線段在 x 以及 y 坐標(biāo)的投影是否有重合。
也就是判斷下一個(gè)線段中 x 較大的端點(diǎn)是否小于另一個(gè)線段中 x 較小的段點(diǎn)，若是，則說明兩個(gè)線段必然沒有交點(diǎn)，同理判斷下 y。

如上圖所示，代碼表示如下：

max(C.x,D.x)<min(A.x,B.x) || max(C.y,D.y)<min(A.y,B.y) ||max(A.x,B.x)<min(C.x,D.x) || max(A.y,B.y)<min(C.y,C.y)

如果上面的四條判斷有一個(gè)為真，則代表兩線段必不可交，否則應(yīng)該進(jìn)行第二步判斷。
顯然，上圖通不過快速排斥實(shí)驗(yàn)。

跨立實(shí)驗(yàn)

矢量叉積

計(jì)算矢量叉積是與直線和線段相關(guān)算法的核心部分。
設(shè)矢量 P = (x1, y1)，Q = ( x2, y2 )，則矢量叉積定義為：P × Q = x1*y2 - x2*y1，其結(jié)果是一個(gè)矢量，與為 P Q 向量所在平面的法向量。顯然有性質(zhì) P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。
叉積的一個(gè)非常重要性質(zhì)是可以通過它的符號(hào)判斷兩矢量相互之間的順逆時(shí)針關(guān)系：
　　若 P × Q > 0 , 則 P 在 Q 的順時(shí)針方向。
　　若 P × Q < 0 , 則 P 在 Q 的逆時(shí)針方向。
　　若 P × Q = 0 , 則 P 與 Q 共線，但可能同向也可能反向。

通過叉積來判斷線段相交

如果兩線段相交那么就意味著它們互相跨立，即如上圖點(diǎn) A 和 B 分別在線段 CD 兩側(cè)，點(diǎn) C 和 D 分別在線 AB 兩側(cè)。
判斷 A 點(diǎn)與 B 點(diǎn)是否在線段 DC 的兩側(cè)，即向量 A-D 與向量 B-D 分別在向量 C-D 的兩端，也就是其叉積是異號(hào)的，即 (A?D)×(C?D)?(B?D)×(C?D)<0 。
同時(shí)也要證明 C 點(diǎn)與 D 點(diǎn)在線段 AB 的兩端，兩個(gè)同時(shí)滿足，則表示線段相交。

然后我們來看看臨界情況，也就是上式恰好等于 0 的情況下：

當(dāng)出現(xiàn)如上圖所示的情況的時(shí)候， (A?D)×(C?D)?(B?D)×(C?D)=0 ，顯然，這種情況是相交的。只要將等號(hào)直接補(bǔ)上即可。

再接得想一想，如果沒有第一步的快速排斥實(shí)驗(yàn)，僅判斷第二步，會(huì)出現(xiàn)什么問題？

當(dāng)出現(xiàn)如上所示的情況的時(shí)候，叉積都為 0, 可以通過跨立實(shí)驗(yàn)，但是兩個(gè)線段并沒有交點(diǎn)。不過還好，這種情況在第一步快速排斥已經(jīng)被排除了。

代碼

struct Line {double x1;double y1;double x2;double y2; };bool intersection(const Line &l1, const Line &l2) {//快速排斥實(shí)驗(yàn)if ((l1.x1 > l1.x2 ? l1.x1 : l1.x2) < (l2.x1 < l2.x2 ? l2.x1 : l2.x2) ||(l1.y1 > l1.y2 ? l1.y1 : l1.y2) < (l2.y1 < l2.y2 ? l2.y1 : l2.y2) ||(l2.x1 > l2.x2 ? l2.x1 : l2.x2) < (l1.x1 < l1.x2 ? l1.x1 : l1.x2) ||(l2.y1 > l2.y2 ? l2.y1 : l2.y2) < (l1.y1 < l1.y2 ? l1.y1 : l1.y2)){return false;}//跨立實(shí)驗(yàn)if ((((l1.x1 - l2.x1)*(l2.y2 - l2.y1) - (l1.y1 - l2.y1)*(l2.x2 - l2.x1))*((l1.x2 - l2.x1)*(l2.y2 - l2.y1) - (l1.y2 - l2.y1)*(l2.x2 - l2.x1))) > 0 ||(((l2.x1 - l1.x1)*(l1.y2 - l1.y1) - (l2.y1 - l1.y1)*(l1.x2 - l1.x1))*((l2.x2 - l1.x1)*(l1.y2 - l1.y1) - (l2.y2 - l1.y1)*(l1.x2 - l1.x1))) > 0){return false;}return true; }

總結(jié)

以上是生活随笔為你收集整理的如何判断2个线段相交的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。