1. 矢量減法

設(shè)二維矢量 P = （x1,y1） 戒傻，Q = (x2,y2)

則矢量減法定義為： P - Q = ( x1 - x2 , y1 - y2 )

顯然有性質(zhì) P - Q = - ( Q - P )

如不加說明坊夫，下面所有的點(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 )

如不加說明斩启，下面所有的點(diǎn)都看作矢量商架，點(diǎn)的乘法看作矢量叉積；

叉乘的重要性質(zhì)：

??? > 若 P × Q > 0 , 則P 在Q的順時(shí)針方向

??? > 若 P × Q < 0 , 則P 在Q的逆時(shí)針方向

??? > 若 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為對角頂點(diǎn)的矩形內(nèi)

4.判斷兩線段是否相交

我們分兩步確定兩條線段是否相交：

(1)．?? 快速排斥試驗(yàn)

設(shè)以線段 P1P2 為對角線的矩形為R蹦肴， 設(shè)以線段 Q1Q2 為對角線的矩形為T，如果R和T不相

交猴娩，顯然兩線段不會(huì)相交阴幌；

(2)．?? 跨立試驗(yàn)

如果兩線段相交勺阐，則兩線段必然相互跨立對方，如圖1所示矛双。在圖1中渊抽，P1P2跨立Q1Q2 ，則

矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的兩側(cè)议忽，即

( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0

上式可改寫成

??? ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0

當(dāng) ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 時(shí)懒闷，說明?? ( P1 - Q1 ) 和 ( Q2 - Q1 )共線，

但是因?yàn)橐呀?jīng)通過快速排斥試驗(yàn)栈幸，所以 P1 一定在線段 Q1Q2上愤估；同理，( Q2 - Q1 ) ×(

P2 - Q1 ) = 0 說明 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)完全解決判斷線段是否相交的問題灵疮。

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從無窮遠(yuǎn)處開始自左向右移動(dòng)养篓，遇到和多邊形的第一個(gè)交點(diǎn)的時(shí)候秃流，進(jìn)入到了多

邊形的內(nèi)部，遇到第二個(gè)交點(diǎn)的時(shí)候柳弄，離開了多邊形舶胀，……所以很容易看出當(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ì)算（你自己畫個(gè)圖就明白了）；如果L和多邊形的一條邊重合逝变，

這條邊應(yīng)該被忽略不計(jì)基茵。為了統(tǒng)一起見刻撒，我們在計(jì)算射線L和多邊形的交點(diǎn)的時(shí)候，1耿导。對

于多邊形的水平邊不作考慮声怔；2。對于多邊形的頂點(diǎn)和L相交的情況舱呻，如果該頂點(diǎn)是其所屬

的邊上縱坐標(biāo)較大的頂點(diǎn)醋火，則計(jì)數(shù)，否則忽略箱吕；3芥驳。對于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)為正無窮大（很大的一個(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)且對于i =1, 2,……, n-1，Pi ,Pi+1的中點(diǎn)也在多

邊形內(nèi)晕窑。

在實(shí)際編程中抑片，沒有必要計(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)小的排在前面说敏，對于X坐標(biāo)相同的點(diǎn)鸥跟，Y坐

標(biāo)小的排在前面；

12. for pointSet中每兩個(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ù)級的復(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

O1內(nèi)。

17.計(jì)算點(diǎn)到線段的最近點(diǎn)

如果該線段平行于X軸（Y軸）碘举，則過點(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)

對于兩條共線的線段妹蔽，它們之間的位置關(guān)系有圖5所示的幾種情況椎眯。

圖5(a)中兩條線段沒有交點(diǎn)；圖5 (b) 和 (d) 中兩條線段有無窮焦點(diǎn)胳岂；圖5 (c) 中兩條線

段有一個(gè)交點(diǎn)编整。設(shè)line1是兩條線段中較長的一條，line2是較短的一條乳丰，如果line1包含了

line2的兩個(gè)端點(diǎn)掌测，則是圖5(d)的情況，兩線段有無窮交點(diǎn)产园；如果line1只包含line2的一個(gè)

端點(diǎn)汞斧，那么如果line1的某個(gè)端點(diǎn)等于被line1包含的line2的那個(gè)端點(diǎn)，則是圖5(c)的情況

什燕，這時(shí)兩線段只有一個(gè)交點(diǎn)粘勒，否則就是圖5(c)的情況，兩線段也是有無窮的交點(diǎn)屎即；如果li

ne1不包含line2的任何端點(diǎn)庙睡，則是圖5(a)的情況，這時(shí)兩線段沒有交點(diǎn)技俐。

21.計(jì)算線段或直線與線段的交點(diǎn)

設(shè)一條線段為L0 = P1P2埃撵，另一條線段或直線為L1 = Q1Q2 ，要計(jì)算的就是L0和L1的交點(diǎn)虽另。

1． 首先判斷L0和L1是否相交（方法已在前文討論過）翎猛，如果不相交則沒有交點(diǎn)，否則說

明L0和L1一定有交點(diǎn)早抠，下面就將L0和L1都看作直線來考慮囚痴。

2． 如果P1和P2橫坐標(biāo)相同，即L0平行于Y軸

a) 若L1也平行于Y軸族展，

i. 若P1的縱坐標(biāo)和Q1的縱坐標(biāo)相同森缠，說明L0和L1共線，假如L1是直線的話他們有無窮的交

點(diǎn)仪缸，假如L1是線段的話可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前

文已討論過）贵涵；

ii. 否則說明L0和L1平行，他們沒有交點(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)相同蒋伦，說明L0和L1共線，假如L1是直線的話他們有無窮的交

點(diǎn)焚鹊，假如L1是線段的話可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前

文已討論過）痕届；

ii. 否則說明L0和L1平行，他們沒有交點(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上，則說明L0和L1共線私植，假如L1是直線的話有無窮交點(diǎn)忌栅，假如L1是線段的話

可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前文已討論過）；

ii. 如果Q1不在L0上曲稼，則說明L0和L1平行索绪，他們沒有交點(diǎn)。

c) 聯(lián)立兩直線的方程組可以解出交點(diǎn)來

說明：這個(gè)算法并不復(fù)雜贫悄，但是要分情況討論清楚瑞驱，尤其是當(dāng)兩條線段共線的情況需要單

獨(dú)考慮，所以在前文將求兩條共線線段的算法單獨(dú)寫出來窄坦。另外唤反，一開始就先利用矢量叉

乘判斷線段與線段（或直線）是否相交凳寺，如果結(jié)果是相交，那么在后面就可以將線段全部

看作直線來考慮彤侍。

22.求線段或直線與折線肠缨、矩形、多邊形的交點(diǎn)

分別求與每條邊的交點(diǎn)即可拥刻。

23.求線段或直線與圓的交點(diǎn)

設(shè)圓心為O怜瞒，圓半徑為r父泳，直線（或線段）L上的兩點(diǎn)為P1,P2般哼。

1. 如果L是線段且P1，P2都包含在圓O內(nèi)惠窄，則沒有交點(diǎn)蒸眠；否則進(jìn)行下一步

2. 如果L平行于Y軸，

a) 計(jì)算圓心到L的距離dis

b) 如果dis > r 則L和圓沒有交點(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是線段作彤，對于2，3乌逐，4中求出的交點(diǎn)還要分別判斷是否屬于該線段的范圍內(nèi)竭讳。