1. 矢量減法
設(shè)二維矢量 P = （x1,y1） ，Q = (x2,y2)
則矢量減法定義為：P - Q = ( x1 - x2 , y1 - y2 )
顯然有性質(zhì) P - Q = - ( Q - P )
如不加說(shuō)明，下面所有的點(diǎn)都看作矢量，兩點(diǎn)的減法就是矢量相減；
2.矢量叉積
設(shè)矢量P = （x1,y1） ，Q = (x2,y2)
則矢量叉積定義為：P × Q = x1*y2 - x2*y1 得到的是一個(gè)標(biāo)量
顯然有性質(zhì) P × Q = - ( Q × P ) P × ( - Q ) = - ( P × Q )
如不加說(shuō)明，下面所有的點(diǎn)都看作矢量，點(diǎn)的乘法看作矢量叉積；
叉乘的重要性質(zhì)：
> 若 P × Q > 0 , 則P 在Q的順時(shí)針?lè)较?br style="line-height: normal;"> > 若 P × Q < 0 , 則P 在Q的逆時(shí)針?lè)较?br style="line-height: normal;"> > 若 P × Q = 0 , 則P 與Q共線，但可能同向也可能反向
3.判斷點(diǎn)在線段上
設(shè)點(diǎn)為Q，線段為P1P2 ，判斷點(diǎn)Q在該線段上的依據(jù)是：
( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1，P2為對(duì)角頂點(diǎn)的矩形內(nèi)
4.判斷兩線段是否相交
我們分兩步確定兩條線段是否相交：
(1)． 快速排斥試驗(yàn)
設(shè)以線段 P1P2 為對(duì)角線的矩形為R， 設(shè)以線段 Q1Q2 為對(duì)角線的矩形為T(mén)，如果R和T不相
交，顯然兩線段不會(huì)相交；
(2)． 跨立試驗(yàn)
如果兩線段相交，則兩線段必然相互跨立對(duì)方，如圖1所示。在圖1中，P1P2跨立Q1Q2 ，則
矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的兩側(cè)，即
( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0
上式可改寫(xiě)成
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
當(dāng) ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 時(shí)，說(shuō)明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共線，
但是因?yàn)橐呀?jīng)通過(guò)快速排斥試驗(yàn)，所以 P1 一定在線段 Q1Q2上；同理，( Q2 - Q1 ) ×(
P2 - Q1 ) = 0 說(shuō)明 P2 一定在線段 Q1Q2上。
所以判斷P1P2跨立Q1Q2的依據(jù)是：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0
同理判斷Q1Q2跨立P1P2的依據(jù)是：
( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) ≥ 0
至此已經(jīng)完全解決判斷線段是否相交的問(wèn)題。
5.判斷線段和直線是否相交
如果線段 P1P2和直線Q1Q2相交，則P1P2跨立Q1Q2，即：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0
6.判斷矩形是否包含點(diǎn)
只要判斷該點(diǎn)的橫坐標(biāo)和縱坐標(biāo)是否夾在矩形的左右邊和上下邊之間。
判斷線段、折線、多邊形是否在矩形中
因?yàn)榫匦问莻€(gè)凸集，所以只要判斷所有端點(diǎn)是否都在矩形中就可以了。
6.判斷矩形是否在矩形中
只要比較左右邊界和上下邊界就可以了。
7.判斷圓是否在矩形中
圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于等于圓心到矩形四邊的距離的最
小值。
8.判斷點(diǎn)是否在多邊形中
以點(diǎn)P為端點(diǎn)，向左方作射線L，由于多邊形是有界的，所以射線L的左端一定在多邊形外，
考慮沿著L從無(wú)窮遠(yuǎn)處開(kāi)始自左向右移動(dòng)，遇到和多邊形的第一個(gè)交點(diǎn)的時(shí)候，進(jìn)入到了多
邊形的內(nèi)部，遇到第二個(gè)交點(diǎn)的時(shí)候，離開(kāi)了多邊形，……所以很容易看出當(dāng)L和多邊形的
交點(diǎn)數(shù)目C是奇數(shù)的時(shí)候，P在多邊形內(nèi)，是偶數(shù)的話P在多邊形外。
但是有些特殊情況要加以考慮。如果L和多邊形的頂點(diǎn)相交，有些情況下交點(diǎn)只能計(jì)算一個(gè)
，有些情況下交點(diǎn)不應(yīng)被計(jì)算（你自己畫(huà)個(gè)圖就明白了）；如果L和多邊形的一條邊重合，
這條邊應(yīng)該被忽略不計(jì)。為了統(tǒng)一起見(jiàn)，我們?cè)谟?jì)算射線L和多邊形的交點(diǎn)的時(shí)候，1。對(duì)
于多邊形的水平邊不作考慮；2。對(duì)于多邊形的頂點(diǎn)和L相交的情況，如果該頂點(diǎn)是其所屬
的邊上縱坐標(biāo)較大的頂點(diǎn)，則計(jì)數(shù)，否則忽略；3。對(duì)于P在多邊形邊上的情形，直接可判
斷P屬于多邊行。由此得出算法的偽代碼如下：
1. count ← 0;
2. 以P為端點(diǎn)，作從右向左的射線L;
3, for 多邊形的每條邊s
4. do if P在邊s上
5. then return true;
6. if s不是水平的
7. then if s的一個(gè)端點(diǎn)在L上且該端點(diǎn)是s兩端點(diǎn)中縱坐標(biāo)較大的端點(diǎn)
9. then count ← count+1
10. else if s和L相交
11. then count ← count+1;
12. if count mod 2 = 1
13. then return true
14. else return false;
其中做射線L的方法是：設(shè)P'的縱坐標(biāo)和P相同，橫坐標(biāo)為正無(wú)窮大（很大的一個(gè)正數(shù)），
則P和P'就確定了射線L。這個(gè)算法的復(fù)雜度為O(n)。
9.判斷線段是否在多邊形內(nèi)
線段在多邊形內(nèi)的一個(gè)必要條件是線段的兩個(gè)端點(diǎn)都在多邊形內(nèi)；
如果線段和多邊形的某條邊內(nèi)交（兩線段內(nèi)交是指兩線段相交且交點(diǎn)不在兩線段的端點(diǎn)）
，因?yàn)槎噙呅蔚倪叺淖笥覂蓚?cè)分屬多邊形內(nèi)外不同部分，所以線段一定會(huì)有一部分在多邊
形外。于是我們得到線段在多邊形內(nèi)的第二個(gè)必要條件：線段和多邊形的所有邊都不內(nèi)交
；
線段和多邊形交于線段的兩端點(diǎn)并不會(huì)影響線段是否在多邊形內(nèi)；但是如果多邊形的某個(gè)
頂點(diǎn)和線段相交，還必須判斷兩相鄰交點(diǎn)之間的線段是否包含與多邊形內(nèi)部。因此我們可
以先求出所有和線段相交的多邊形的頂點(diǎn)，然后按照X-Y坐標(biāo)排序，這樣相鄰的兩個(gè)點(diǎn)就是
在線段上相鄰的兩交點(diǎn)，如果任意相鄰兩點(diǎn)的中點(diǎn)也在多邊形內(nèi)，則該線段一定在多邊形
內(nèi)。證明如下：
命題1：
如果線段和多邊形的兩相鄰交點(diǎn)P1 ，P2的中點(diǎn)P' 也在多邊形內(nèi)，則P1, P2之間的所有點(diǎn)
都在多邊形內(nèi)。
證明：
假設(shè)P1,P2之間含有不在多邊形內(nèi)的點(diǎn)，不妨設(shè)該點(diǎn)為Q，在P1, P'之間，因?yàn)槎噙呅问情]
合曲線，所以其內(nèi)外部之間有界，而P1屬于多邊行內(nèi)部，Q屬于多邊性外部，P'屬于多邊性
內(nèi)部，P1-Q-P'完全連續(xù)，所以P1Q和QP'一定跨越多邊形的邊界，因此在P1,P'之間至少還
有兩個(gè)該線段和多邊形的交點(diǎn)，這和P1P2是相鄰兩交點(diǎn)矛盾，故命題成立。證畢
由命題1直接可得出推論：
推論2：
設(shè)多邊形和線段PQ的交點(diǎn)依次為P1,P2,……Pn，其中Pi和Pi+1是相鄰兩交點(diǎn)，線段PQ在多
邊形內(nèi)的充要條件是：P，Q在多邊形內(nèi)且對(duì)于i =1, 2,……, n-1，Pi ,Pi+1的中點(diǎn)也在多
邊形內(nèi)。
在實(shí)際編程中，沒(méi)有必要計(jì)算所有的交點(diǎn)，首先應(yīng)判斷線段和多邊形的邊是否內(nèi)交，倘若
線段和多邊形的某條邊內(nèi)交則線段一定在多邊形外；如果線段和多邊形的每一條邊都不內(nèi)
交，則線段和多邊形的交點(diǎn)一定是線段的端點(diǎn)或者多邊形的頂點(diǎn)，只要判斷點(diǎn)是否在線段
上就可以了。
至此我們得出算法如下：
1. if 線端PQ的端點(diǎn)不都在多邊形內(nèi)
2. then return false;
3. 點(diǎn)集pointSet初始化為空;
4. for 多邊形的每條邊s
5. do if 線段的某個(gè)端點(diǎn)在s上
6. then 將該端點(diǎn)加入pointSet;
7. else if s的某個(gè)端點(diǎn)在線段PQ上
8. then 將該端點(diǎn)加入pointSet;
9. else if s和線段PQ相交 // 這時(shí)候可以肯定是內(nèi)交
10. then return false;
11. 將pointSet中的點(diǎn)按照X-Y坐標(biāo)排序，X坐標(biāo)小的排在前面，對(duì)于X坐標(biāo)相同的點(diǎn)，Y坐
標(biāo)小的排在前面；
12. for pointSet中每?jī)蓚€(gè)相鄰點(diǎn) pointSet[i] , pointSet[ i+1]
13. do if pointSet[i] , pointSet[ i+1] 的中點(diǎn)不在多邊形中
14. then return false;
15. return true;
這個(gè)算法的復(fù)雜度也是O(n)。其中的排序因?yàn)榻稽c(diǎn)數(shù)目肯定遠(yuǎn)小于多邊形的頂點(diǎn)數(shù)目n，所
以最多是常數(shù)級(jí)的復(fù)雜度，幾乎可以忽略不計(jì)。
10.判斷折線在多邊形內(nèi)
只要判斷折線的每條線段是否都在多邊形內(nèi)即可。設(shè)折線有m條線段，多邊形有n個(gè)頂點(diǎn)，
則復(fù)雜度為O(m*n)。
11.判斷多邊形是否在多邊形內(nèi)
只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可。判斷一個(gè)有m個(gè)頂點(diǎn)的多邊形是否在一個(gè)
有n個(gè)頂點(diǎn)的多邊形內(nèi)復(fù)雜度為O(m*n)。
12.判斷矩形是否在多邊形內(nèi)
將矩形轉(zhuǎn)化為多邊形，然后再判斷是否在多邊形內(nèi)。
13.判斷圓是否在多邊形內(nèi)
只要計(jì)算圓心到多邊形的每條邊的最短距離，如果該距離大于等于圓半徑則該圓在多邊形
內(nèi)。計(jì)算圓心到多邊形每條邊最短距離的算法在后文闡述。
14.判斷點(diǎn)是否在圓內(nèi)
計(jì)算圓心到該點(diǎn)的距離，如果小于等于半徑則該點(diǎn)在圓內(nèi)。
15.判斷線段、折線、矩形、多邊形是否在圓內(nèi)
因?yàn)閳A是凸集，所以只要判斷是否每個(gè)頂點(diǎn)都在圓內(nèi)即可。
16.判斷圓是否在圓內(nèi)
設(shè)兩圓為O1,O2，半徑分別為r1, r2，要判斷O2是否在O1內(nèi)。先比較r1，r2的大小，如果r
1<r2則O2不可能在O1內(nèi)；否則如果兩圓心的距離大于r1 - r2 ，則O2不在O1內(nèi)；否則O2在
O1內(nèi)。
17.計(jì)算點(diǎn)到線段的最近點(diǎn)
如果該線段平行于X軸（Y軸），則過(guò)點(diǎn)point作該線段所在直線的垂線，垂足很容易求得，
然后計(jì)算出垂足，如果垂足在線段上則返回垂足，否則返回離垂足近的端點(diǎn)；
如果該線段不平行于X軸也不平行于Y軸，則斜率存在且不為0。設(shè)線段的兩端點(diǎn)為pt1和pt
2，斜率為：
k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );
該直線方程為：
y = k* ( x - pt1.x) + pt1.y
其垂線的斜率為 - 1 / k，
垂線方程為：
y = (-1/k) * (x - point.x) + point.y
聯(lián)立兩直線方程解得：
x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1)
y = k * ( x - pt1.x) + pt1.y;
然后再判斷垂足是否在線段上，如果在線段上則返回垂足；如果不在則計(jì)算兩端點(diǎn)到垂足
的距離，選擇距離垂足較近的端點(diǎn)返回。
18.計(jì)算點(diǎn)到折線、矩形、多邊形的最近點(diǎn)
只要分別計(jì)算點(diǎn)到每條線段的最近點(diǎn)，記錄最近距離，取其中最近距離最小的點(diǎn)即可。
19.計(jì)算點(diǎn)到圓的最近距離
如果該點(diǎn)在圓心，則返回UNDEFINED
連接點(diǎn)P和圓心O，如果PO平行于X軸，則根據(jù)P在O的左邊還是右邊計(jì)算出最近點(diǎn)的橫坐標(biāo)為
centerPoint.x - radius 或 centerPoint.x + radius， 如圖4 (a)所示；如果如果PO平
行于Y軸，則根據(jù)P在O的上邊還是下邊計(jì)算出最近點(diǎn)的縱坐標(biāo)為 centerPoint.y -+radius
或 centerPoint.y - radius， 如圖4 (b)所示。
如果PO不平行于X軸和Y軸，則PO的斜率存在且不為0，如圖4(c)所示。這時(shí)直線PO斜率為
k = （ P.y - O.y ）/ ( P.x - O.x )
直線PO的方程為：
y = k * ( x - P.x) + P.y
設(shè)圓方程為:
(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，
聯(lián)立兩方程組可以解出直線PO和圓的交點(diǎn)，取其中離P點(diǎn)較近的交點(diǎn)即可。
20.計(jì)算兩條共線的線段的交點(diǎn)
對(duì)于兩條共線的線段，它們之間的位置關(guān)系有圖5所示的幾種情況。
圖5(a)中兩條線段沒(méi)有交點(diǎn)；圖5 (b) 和 (d) 中兩條線段有無(wú)窮焦點(diǎn)；圖5 (c) 中兩條線
段有一個(gè)交點(diǎn)。設(shè)line1是兩條線段中較長(zhǎng)的一條，line2是較短的一條，如果line1包含了
line2的兩個(gè)端點(diǎn)，則是圖5(d)的情況，兩線段有無(wú)窮交點(diǎn)；如果line1只包含line2的一個(gè)
端點(diǎn)，那么如果line1的某個(gè)端點(diǎn)等于被line1包含的line2的那個(gè)端點(diǎn)，則是圖5(c)的情況
，這時(shí)兩線段只有一個(gè)交點(diǎn)，否則就是圖5(c)的情況，兩線段也是有無(wú)窮的交點(diǎn)；如果li
ne1不包含line2的任何端點(diǎn)，則是圖5(a)的情況，這時(shí)兩線段沒(méi)有交點(diǎn)。
21.計(jì)算線段或直線與線段的交點(diǎn)
設(shè)一條線段為L(zhǎng)0 = P1P2，另一條線段或直線為L(zhǎng)1 = Q1Q2 ，要計(jì)算的就是L0和L1的交點(diǎn)。
1． 首先判斷L0和L1是否相交（方法已在前文討論過(guò)），如果不相交則沒(méi)有交點(diǎn)，否則說(shuō)
明L0和L1一定有交點(diǎn)，下面就將L0和L1都看作直線來(lái)考慮。
2． 如果P1和P2橫坐標(biāo)相同，即L0平行于Y軸
a) 若L1也平行于Y軸，
i. 若P1的縱坐標(biāo)和Q1的縱坐標(biāo)相同，說(shuō)明L0和L1共線，假如L1是直線的話他們有無(wú)窮的交
點(diǎn)，假如L1是線段的話可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前
文已討論過(guò)）；
ii. 否則說(shuō)明L0和L1平行，他們沒(méi)有交點(diǎn)；
b) 若L1不平行于Y軸，則交點(diǎn)橫坐標(biāo)為P1的橫坐標(biāo)，代入到L1的直線方程中可以計(jì)算出交
點(diǎn)縱坐標(biāo)；
3． 如果P1和P2橫坐標(biāo)不同，但是Q1和Q2橫坐標(biāo)相同，即L1平行于Y軸，則交點(diǎn)橫坐標(biāo)為Q
1的橫坐標(biāo)，代入到L0的直線方程中可以計(jì)算出交點(diǎn)縱坐標(biāo)；
4． 如果P1和P2縱坐標(biāo)相同，即L0平行于X軸
a) 若L1也平行于X軸，
i. 若P1的橫坐標(biāo)和Q1的橫坐標(biāo)相同，說(shuō)明L0和L1共線，假如L1是直線的話他們有無(wú)窮的交
點(diǎn)，假如L1是線段的話可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前
文已討論過(guò)）；
ii. 否則說(shuō)明L0和L1平行，他們沒(méi)有交點(diǎn)；
b) 若L1不平行于X軸，則交點(diǎn)縱坐標(biāo)為P1的縱坐標(biāo)，代入到L1的直線方程中可以計(jì)算出交
點(diǎn)橫坐標(biāo)；
5． 如果P1和P2縱坐標(biāo)不同，但是Q1和Q2縱坐標(biāo)相同，即L1平行于X軸，則交點(diǎn)縱坐標(biāo)為Q
1的縱坐標(biāo)，代入到L0的直線方程中可以計(jì)算出交點(diǎn)橫坐標(biāo)；
6． 剩下的情況就是L1和L0的斜率均存在且不為0的情況
a) 計(jì)算出L0的斜率K0，L1的斜率K1 ；
b) 如果K1 = K2
i. 如果Q1在L0上，則說(shuō)明L0和L1共線，假如L1是直線的話有無(wú)窮交點(diǎn)，假如L1是線段的話
可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前文已討論過(guò)）；
ii. 如果Q1不在L0上，則說(shuō)明L0和L1平行，他們沒(méi)有交點(diǎn)。
c) 聯(lián)立兩直線的方程組可以解出交點(diǎn)來(lái)
說(shuō)明：這個(gè)算法并不復(fù)雜，但是要分情況討論清楚，尤其是當(dāng)兩條線段共線的情況需要單
獨(dú)考慮，所以在前文將求兩條共線線段的算法單獨(dú)寫(xiě)出來(lái)。另外，一開(kāi)始就先利用矢量叉
乘判斷線段與線段（或直線）是否相交，如果結(jié)果是相交，那么在后面就可以將線段全部
看作直線來(lái)考慮。
22.求線段或直線與折線、矩形、多邊形的交點(diǎn)
分別求與每條邊的交點(diǎn)即可。
23.求線段或直線與圓的交點(diǎn)
設(shè)圓心為O，圓半徑為r，直線（或線段）L上的兩點(diǎn)為P1,P2。
1. 如果L是線段且P1，P2都包含在圓O內(nèi)，則沒(méi)有交點(diǎn)；否則進(jìn)行下一步
2. 如果L平行于Y軸，
a) 計(jì)算圓心到L的距離dis
b) 如果dis > r 則L和圓沒(méi)有交點(diǎn)；
c) 利用勾股定理，可以求出兩交點(diǎn)坐標(biāo)，如圖6(a)所示；但要注意考慮L和圓的相切情況
3. 如果L平行于X軸，做法與L平行于Y軸的情況類似；
4. 如果L既不平行X軸也不平行Y軸，可以求出L的斜率K，然后列出L的點(diǎn)斜式方程，和圓方
程聯(lián)立即可求解出L和圓的兩個(gè)交點(diǎn)；
5. 如果L是線段，對(duì)于2，3，4中求出的交點(diǎn)還要分別判斷是否屬于該線段的范圍內(nèi)。 |
下載APP