平面内两条线段的位置关系(相交)判定与交点求解
http://www.cnblogs.com/devymex/archive/2010/08/19/1803885.html
概念
平面內兩條線段位置關系的判定在很多領域都有著廣泛的應用，比如游戲、CAD、圖形處理等，而兩線段交點的求解又是該算法中重要的一環(huán)。本文將盡可能用通俗的語言詳細的描述一種主流且性能較高的判定算法。
外積，又稱叉積，是向量代數(shù)（解析幾何）中的一個概念。兩個二維向量v1(x1, y1)和v2(x2, y2)的外積v1×v2=x1y2-y1x2。如果由v1到v2是順時針轉動，外積為負，反之為正，為0表示二者方向相同（平行）。此外，文中涉及行例式和方程組的概念，請參閱線性代數(shù)的相關內容。
為方便計算，對坐標點的大小比較作如下定義：x坐標較大的點為大，x坐標相等但y坐標較大的為大，x與y都相等的點相等。一條線段中較小的一端為起點，較大的一端為終點。
?
問題
給定兩條線段的端點坐標，求其位置關系，并求出交點（如果存在）。
?
分析
兩條線段的位置關系大體上可以分為三類：有重合部分、無重合部分但有交點（相交）、無交點。為避免精度問題，首先要將所有存在重合的情況排除。
重合可分為：完全重合、一端重合、部分重合三種情況。顯然，兩條線段的起止點都相同即為完全重合；只有起點相同或只有終點相同的為一端重合（注意：坐標較小的一條線段的終點與坐標較大的一條線段的起點相同時應判定為相交）。要判斷是否部分重合，必須先判斷是否平行。設線段L1(p1->p2)和L2(p3->p4)，其中p1(x1, y1)為第一條線段的起點，p2(x2, y2)為第一條線段的終點，p3(x3, y3)為第二條線段的起點，p4(x4, y4)為第二段線段的終點，由此可構造兩個向量：
- v1(x2-x1, y2-y1)，v2(x4-x3, y4-y3)
若v1與v2的外積v1×v2為0，則兩條線段平行，有可能存在部分重合。再判斷兩條平行線段是否共線，方法是用L1的一端和L2的一端構成向量vs并與v2作外積，如果vs與v2也平行則兩線段共線（三點共線）。在共線的前提下，若起點較小的線段終點大于起點較大的線段起點，則判定為部分重合。
沒有重合，就要判定兩條線是否相交，主要的算法還是依靠外積。然而外積的計算開銷比較大，如果不相交的情況比較多，可先做快速排斥實驗：將兩條線段視為兩個矩形的對角線，并構造出這兩個矩形。如果這兩個矩形沒有重疊部分（x坐標相離或y坐標相離）即可判定為不相交。
然后執(zhí)行跨立試驗。兩條相交的線段必然相互跨立，簡單的講就是p1和p2兩點位于L2的兩側且p3和p4兩點位于L1的兩側，這樣就可利用外積做出判斷了。分別構造向量s1(p3, p1), s2(p3, p2)，如果s1×v2與s2×v2異號(s1->v2與s2->v2轉動的方向相反），則說明p1和p2位于L2的兩側。同理可判定p3和p4是否跨立L1。如果上述四個叉積中任何一個等于0，則說明一條線段的端點在另一條線上。
當判定兩條線段相交后，就可以進行交點的求解了。當然，求交點可以用平面幾何方法，列點斜式方程來完成。但這樣作會難以處理斜率為0的特殊情況，且運算中會出現(xiàn)多次除法，很難保證精度。這里將使用向量法求解。
設交點為(x0, y0)，則下列方程組必然成立：
其中k1和k2為任意不為0的常數(shù)（若為0，則說明有重合的端點，這種情況在上面已經(jīng)被排除了）。1式與2式聯(lián)系，3式與4式聯(lián)立，消去k1和k2可得：
將含有未知數(shù)x0和y0的項移到左邊，常數(shù)項移動到右邊，得：
設兩個常數(shù)項分別為b1和b2：
- b1=(y2-y1)x1+(x1-x2)y1
- b2=(y4-y3)x3+(x3-x4)y3
系數(shù)行列式為D，用b1和b2替換x0的系數(shù)所得系數(shù)行列式為D1，替換y0的系數(shù)所得系數(shù)行列式為D2，則有：
- |D|=(x2-x1)(y4-y3)-(x4-x3)(y2-y1)
- |D1|=b2(x2-x1)-b1(x4-x3)
- |D2|=b2(y2-y1)-b1(y4-y3)
由此，可求得交點坐標為：
- x0=|D1|/|D|, y0=|D2|/|D|
解畢。
判斷兩線段相交
經(jīng)典方法，就是跨立試驗了，即如果一條線段跨過另一條線段，則線段的兩個端點分別在另一條線段的兩側。但是，還需要檢測邊界情況，即兩條線段中可能某條線段的某個端點正好落在另一條線段上。這也是算法導論中介紹的算法。
程序模擬如下：
總結
以上是生活随笔為你收集整理的平面内两条线段的位置关系(相交)判定与交点求解的全部內容，希望文章能夠幫你解決所遇到的問題。
