第2章 GIS算法的幾何基礎(chǔ)

第二章GIS算法的幾何基礎(chǔ)2.1維數(shù)擴(kuò)展的9交集模型2.2矢量的概念2.3折線段的拐向判斷2.4判斷點(diǎn)是否在線段上2.5判斷兩線段是否相交2.6判斷線段和直線是否相交2.7判斷矩形是否包含點(diǎn)2.8判斷線段、折線、多邊形是否在矩形中2.9判斷矩形是否在矩形中2.10判斷圓是否在矩形中2.11判斷點(diǎn)是否在多邊形內(nèi)2.12判斷線段是否在多邊形內(nèi)第二章GIS算法的幾何基礎(chǔ)2.13判斷折線是否在多邊形內(nèi)2.14判斷多邊形是否在多邊形內(nèi)2.15判斷矩形是否在多邊形內(nèi)2.16判斷圓是否在多邊形內(nèi)

2.17判斷點(diǎn)是否在圓內(nèi)

2.18判斷線段、折線、矩形、多邊形是否在圓內(nèi)2.19判斷圓是否在圓內(nèi)2.20計(jì)算兩條共線的線段的交點(diǎn)2.21計(jì)算線段或直線與線段的交點(diǎn)2.22求線段或直線與圓的交點(diǎn)關(guān)系運(yùn)算——檢驗(yàn)兩個(gè)幾何對(duì)象的特定的拓?fù)淇臻g關(guān)系的邏輯方法拓?fù)淇臻g關(guān)系基本的比較方法——成對(duì)比較兩個(gè)幾何對(duì)象的內(nèi)部、邊界和外部的交集。（空間關(guān)系分類）4交集模型9交集模型維數(shù)拓展的9交集模型2.1維數(shù)擴(kuò)展的9交集模型關(guān)系---拓?fù)淇臻g----交集——空間關(guān)系分類對(duì)“維數(shù)”的理解2.1維數(shù)擴(kuò)展的9交集模型9交集模型介紹

設(shè)有現(xiàn)實(shí)世界中的兩個(gè)簡(jiǎn)單實(shí)體A、B,B(A)、B(B)表示A、B的邊界,I(A)、I(B)表示A、B的內(nèi)部,E(A)、E(B)表示A、B外部。Egenhofer(1993)構(gòu)造出一個(gè)由邊界、內(nèi)部、外部的點(diǎn)集組成的9—交空間關(guān)系模型(9IM)如下:

（1）對(duì)于該矩陣中的每一元素，都有“空”與“非空”兩種取值，9個(gè)元素總共可產(chǎn)生29=512種情形9交模型形式化地描述了離散空間對(duì)象的拓?fù)潢P(guān)系，基于9交模型，可以定義空間數(shù)據(jù)庫(kù)的一致性原則，并應(yīng)用于數(shù)據(jù)庫(kù)更新、維護(hù)中。

維數(shù)擴(kuò)展的9交集模型9交模型一共可以表達(dá)512種可能的空間關(guān)系，但是在實(shí)際上，有些關(guān)系并不存在。拓?fù)潢P(guān)系數(shù)目要遠(yuǎn)遠(yuǎn)少于512個(gè)（面/面：6，面/線：19，面/點(diǎn)：3，線/線：16，線/點(diǎn)：3，點(diǎn)/點(diǎn)：2）從某種意義上講，9-交模型所描述的拓?fù)潢P(guān)系只是拓?fù)潢P(guān)系的類別，對(duì)于每一類別可以有多種可能的情形，例如兩條相交的線，一個(gè)交點(diǎn)的情形和多個(gè)交點(diǎn)的9-交模型表示是一致的，但是其拓?fù)潢P(guān)系并不同。相對(duì)于4交集模型，通過引進(jìn)點(diǎn)集的余（外部），9-交空間關(guān)系模型增強(qiáng)了面/線、線/線空間關(guān)系的唯一性。但它僅僅用“空”與“非空”來區(qū)分兩個(gè)目標(biāo)的邊界、內(nèi)部、余，對(duì)面/面、點(diǎn)/點(diǎn)、點(diǎn)/線、點(diǎn)/面的空間關(guān)系描述并無多大改進(jìn)。為此，該方法仍有一定的局限性。在地理信息系統(tǒng)中，數(shù)據(jù)可以劃分為幾何數(shù)據(jù)與屬性數(shù)據(jù)兩大類型。由于幾何數(shù)據(jù)具有可量測(cè)性，為此地理信息系統(tǒng)所涉及的客觀世界是一個(gè)度量空間，而且每個(gè)度量空間又是一個(gè)拓?fù)淇臻g。（關(guān)系確定，不能模糊表示）2.1維數(shù)擴(kuò)展的9交集模型

運(yùn)用維數(shù)擴(kuò)展法,將9IM進(jìn)行擴(kuò)展,利用點(diǎn)、線、面的邊界、內(nèi)部、外部之間的交集的維數(shù)來作為空間關(guān)系描述的框架。對(duì)于幾何實(shí)體的邊界,它是比其更低一維的幾何實(shí)體的集合。為此,點(diǎn)的邊界為空集;線的邊界為線的兩個(gè)端點(diǎn),當(dāng)線為閉曲線時(shí),線的邊界為空;面的邊界由構(gòu)成面的所有線構(gòu)成。若設(shè)P為一個(gè)集合,定義集合的求維函數(shù)DIM如下:2.1維數(shù)擴(kuò)展的9交集模型利用維數(shù)擴(kuò)展法,式(1)可擴(kuò)展為

（2）

2.1維數(shù)擴(kuò)展的9交集模型根據(jù)DE-9IM,對(duì)于集合拓?fù)淇臻gX,當(dāng)需要進(jìn)行關(guān)系判別時(shí),可對(duì)矩陣的9元取值進(jìn)行分析、比較。令C為各單元交的集合,其取值P可能為｛T,F,*,0,1,2｝。各個(gè)取值的具體含義為：

1)P=TDIM(C)∈｛0,1,2｝,即交集C包含有點(diǎn)、線、面;2)P=FDIM(C)=-1,即交集C為空;3)P=*DIM(C)∈｛-1,0,1,2｝,即兩目標(biāo)交集既有點(diǎn)、線、面,又含有某些部分的交為空的情形,該情況在關(guān)系判別時(shí),一般不予以考慮;4)P=0DIM(C)=0;5)P=1DIM(C)=1;6)P=2DIM(C)=2。

2.1維數(shù)擴(kuò)展的9交集模型式(2)中各元素通過取值｛T,F,*,0,1,2｝,可產(chǎn)生的情形為=10077696種,關(guān)系非常復(fù)雜,通過對(duì)大量的空間關(guān)系進(jìn)行歸納和分類,得出5種基本的空間關(guān)系:相離關(guān)系(Disjoint)、相接關(guān)系(Touch)、相交關(guān)系(Cross)、真包含關(guān)系(Within)、疊置關(guān)系(Overlap),并將這5種關(guān)系定義為空間關(guān)系的最小集,其特征為:1)相互之間不能進(jìn)行轉(zhuǎn)化;2)能覆蓋所有的空間關(guān)系模式;3)能應(yīng)用于同維與不同維的幾何目標(biāo);4)每一種關(guān)系對(duì)應(yīng)于唯一的DE-9IM矩陣;5)任何其它的DE-9IM關(guān)系可以通過用這5種基本關(guān)系進(jìn)行表達(dá)。

另外,為了用戶的使用方便,還定義幾個(gè)基本的空間關(guān)系即:

相等(Equal)、包含(Contain)、覆蓋(Cover)、和被覆蓋(CoverdBy)。

2.1維數(shù)擴(kuò)展的9交集模型在地理信息系統(tǒng)中,空間數(shù)據(jù)具有屬性特征、空間特征和時(shí)間特征,基本數(shù)據(jù)類型包括屬性數(shù)據(jù)、幾何數(shù)據(jù)和空間關(guān)系數(shù)據(jù)。作為基本數(shù)據(jù)類型的空間關(guān)系數(shù)據(jù)主要指點(diǎn)/點(diǎn)、點(diǎn)/線、點(diǎn)/面、線/線、線/面、面/面之間的相互關(guān)系。

利用DE-9IM方法,識(shí)別規(guī)則為:

（1）相離：A.Disjoint(B)A.Relate(B,“FF*FF****”)

（2）相接：A.Touch(B)A.Relate(B,“FT*******”)ORA.Relate(B,“F**T*****”)ORA.Relate(B,“F***T*****”)（如圖）

（3）相交：A.Cross(B)A.Relate(B,“P*T******”),CaseA,B∈L,P=0,ElseP=T（如圖）

2.1維數(shù)擴(kuò)展的9交集模型

(4)疊置：A.Overlap(B)A.Relate(B,“T*T***T**”),CaseA,B∈L,P=0,ElseP=T（如圖）

(5)真包含：A.Within(B)A.Relate(B,“TF*F**F***”)（如圖）

(6)包含：A.Contain(B)B.In(A)

(7)相等：A.Equal(B)A.Relate(B,“PF*FP****”),P=0,1,2

(8)覆蓋：A.Cover(B)(I(A)∩I(B)=I(A)And(E(A)∩E(B)≠Φ)

(9)被覆蓋：A.CoveredBy(B)B.Cover(A)

2.1維數(shù)擴(kuò)展的9交集模型(a)(b)多邊形/多邊形12(a)(b)12線/線。多邊形/點(diǎn)·線/點(diǎn)多邊形/線相接關(guān)系示例多邊形/線線/線相交關(guān)系示例2.1維數(shù)擴(kuò)展的9交集模型多邊形/多邊形多邊形/線線/線·多邊形/點(diǎn)真包含關(guān)系示意圖多邊形/多邊形s1s2e1e2線/線疊置關(guān)系示例空間分析幾何對(duì)象DE-9IM模版相離（Disjoint）AllFF*FF****相接（Touches）A/AFT*******或F**T*****或F***T****L/LL/AP/AP/L相交（Crosses）P/LT*T******P/AL/L0********L/AT*T******真包含（Within）AllT*F**F***疊置（Overlaps）A/AT*T***T**L/L1*T***T**P/PT*T***T**2.1維數(shù)擴(kuò)展的9交集模型DE-9IM模版分析2.2矢量的概念一、矢量的概念

如果一條線段的端點(diǎn)是有次序之分的，我們把這種線段稱為有向線段。如果有向線段P1P2的起點(diǎn)P1在坐標(biāo)原點(diǎn)，我們可以把它成為矢量P2(如圖)。P2OP1矢量的概念1）基于向量的表達(dá)2）基于數(shù)學(xué)方程的表達(dá)3）基于極坐標(biāo)的表達(dá)2.2矢量的概念二、矢量加減法設(shè)二維矢量P=（x1,y1），Q=(x2,y2),則：QPP+Q矢量加法QP-QP矢量減法P+Q=（x1+x2,y1+y2）P-Q=（x1-x2,y1-y2）2.2矢量的概念三、矢量叉積設(shè)二維矢量P=（x1,y1），Q=(x2,y2),則矢量叉積定義為：由(0,0)、P、Q和PQ所組成的平行四邊形的帶符號(hào)的面積，即：P×Q=x1·y2-x2·y1

其結(jié)果是一個(gè)標(biāo)量。顯然有性質(zhì)：

P×Q=-(Q×P)和P×（-Q）=-(P×Q)叉積的一個(gè)非常重要的性質(zhì)是可以通過它的符號(hào)判斷兩矢量相互之間的順逆時(shí)針關(guān)系：

(1)若P×Q>0，則P在Q的順時(shí)針方向；

(2)若P×Q<0，則P在Q的逆時(shí)針方向；

(3)若P×Q=0，則P與Q共線，但可能同向也可能反向。2.3折線段的拐向判斷折線段的拐向判斷方法可以直接由矢量叉積的性質(zhì)推出。對(duì)于有公共端點(diǎn)的線段p0p1和p1p2，通過計(jì)算(p2-p0)×(p1-p0)的符號(hào)便可以確定折線段的拐向：

(1)若(p2-p0)×(p1-p0)>0,則p0p1在p1點(diǎn)拐向右側(cè)后得到p1p2。

(2)若(p2-p0)×(p1-p0)<0,則p0p1在p1點(diǎn)拐向左側(cè)后得到p1p2。

(3)若(p2-p0)×(p1-p0)=0,則p0、p1、p2三點(diǎn)共線。具體情況可參考下圖：

p0p1p2p1p2p0·p0p1p2(2)(1)(3)2.4判斷點(diǎn)是否在線段上解題思路1流程圖首先確定P1、P2、Q三點(diǎn)是否共線（叉乘運(yùn)算）進(jìn)一步確定Q是否線段P1P2中（坐標(biāo)范圍）返回Ture返回False是否否2.4判斷點(diǎn)是否在線段上解題思路2流程圖首先確定P1、P2、Q三點(diǎn)是否共線（叉乘運(yùn)算）進(jìn)一步確定QP1、QP2是否背向（點(diǎn)乘運(yùn)算）返回Ture返回False是否否2.4判斷點(diǎn)是否在線段上設(shè)點(diǎn)為Q，線段為P1P2

，判斷點(diǎn)Q在該線段上的依據(jù)是：(

Q

-

P1

)

×

(

P2

-

P1

)

=

0

且

Q

在以

P1，P2為對(duì)角頂點(diǎn)的矩形內(nèi)。過程實(shí)現(xiàn)：ON-SEGMENT(pi,pj,pk)if

min(xi,xj)<=xk<=max(xi,xj)and

min(yi,yj)<=yk<=max(yi,yj)then

return

true;else

return

false;

由于需要考慮水平線段和垂直線段兩種特殊情況，min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)兩個(gè)條件必須同時(shí)滿足才能返回真值。C語(yǔ)言代碼如下：/*點(diǎn)是否在線段上:向量判斷*/int

PointIsOnSegment(PointP,PointA,PointB){ VectorAP=VectorConstruct(A,P); VectorAB=VectorConstruct(A,B);

//兩向量不平行

if(CrossProduct(AP,AB)==0&&

P.x>=Min(A.x,B.x)&&P.x<=Max(A.x,B.x)&&

P.y>=Min(A.y,B.y)&&P.y<=Max(A.y,B.y)) { return1; } else { return0; }}其中/**由兩個(gè)點(diǎn)構(gòu)造一個(gè)向量*/VectorVectorConstruct(PointA,PointB){ Vectorv;

v.x=B.x-A.x;

v.y=B.y-A.y; returnv;}//向量的叉積doubleCrossProduct(Vectora,Vectorb){ returna.x*b.y-a.y*b.x;}2.4判斷點(diǎn)是否在線段上思路2程序?qū)崿F(xiàn)輸入1）線段端點(diǎn)P1P2，2）單點(diǎn)Q輸出TureFalse主要運(yùn)算1）叉乘

2）點(diǎn)乘代碼實(shí)現(xiàn)：兩個(gè)向量叉乘：Doublecrossmulti(vpoint&p1,vpoint&p2){Return(p1xp2y-p2xp1y)}2.兩個(gè)向量點(diǎn)乘：Doublepointmulti(vpoint&p1,vpoint&p2){Return(p1xp2x+p1yp2y)}3.判斷點(diǎn)是否在線段上的代碼：Bool

isvpointonline(vpoint&p1,vpoint&p2,vpoint&Q){VpointQP1=subvput(P1,Q)VpointQP2=subvput(P2,Q)If(crossmulti(QP1,QP2)==0){if(pointmulti(QP1,QP2)

＜0)Returntrue}}returnfalse是否還有其他方法來判斷？2.5判斷兩線段是否相交我們分兩步確定兩條線段是否相交：(1)快速排斥試驗(yàn)設(shè)以線段

P1P2

為對(duì)角線的矩形為R，

設(shè)以線段

Q1Q2

為對(duì)角線的矩形為T，如果R和T不相交，顯然兩線段不會(huì)相交。(2)跨立試驗(yàn)如果兩線段相交，則兩線段必然相互跨立對(duì)方。若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。！2.5判斷兩線段是否相交當(dāng)(P1-Q1)×(Q2-Q1)=0時(shí)，說明(P1-Q1)和(Q2-Q1)共線，但是因?yàn)橐呀?jīng)通過快速排斥試驗(yàn)，所以P1一定在線段Q1Q2上；當(dāng)(Q2-Q1)×(P2-Q1)=0

時(shí)，說明P2一定在線段Q1Q2上。所以判斷P1P2跨立Q1Q2的依據(jù)是：

(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)>=0(3)同理判斷Q1Q2跨立P1P2的依據(jù)是：

(Q1-P1)×(P2-P1)*(P2-P1)×(Q2-P1)>=0。具體情況如下圖所示：2.5判斷兩線段是否相交通過跨立試驗(yàn)通過快速排斥試驗(yàn)未通過快速排斥試驗(yàn)未通過跨立試驗(yàn)RP1P2Q1Q2流程圖輸入線段A、B的頂點(diǎn)快速排斥矩形是否相交是否否A兩端點(diǎn)是否跨立BB兩端點(diǎn)是否跨立A返回Ture是是返回False否//判斷p在不在ps---pe的順時(shí)針或逆時(shí)針/**//*m=(pe-ps)X(p-ps)m>0逆時(shí)針m==03點(diǎn)在同一直線m<0順時(shí)針*/doublemulpti(Point

ps,Pointpe,Pointp){doublem;m=(pe.x-ps.x)*(p.y-ps.y)-(p.x-ps.x)*(pe.y-ps.y);returnm;}bool

inser(Pointp1,Pointp2,Pointp3,Pointp4){if(MAX(p1.x,p2.x)>=MIN(p3.x,p4.x)&&MAX(p3.x,p4.x)>=MIN(p1.x,p2.x)&&MAX(p1.y,p2.y)>=MIN(p3.y,p4.y)&&MAX(p3.y,p4.y)>=MIN(p1.y,p2.y)&&mulpti(p1,p2,p3)*mulpti(p1,p2,p4)<=0&&mulpti(p3,p4,p1)*mulpti(p3,p4,p2)<=0)returntrue;elsereturnfalse;}判斷兩線段是否相交（算法2）2.6判斷線段和直線是否相交

有了上面的基礎(chǔ)，這個(gè)算法就很容易了。如果線段P1P2和直線Q1Q2相交，則P1P2跨立Q1Q2，即：

(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)>=0。2.7

判斷矩形是否包含點(diǎn)

只要判斷該點(diǎn)的橫坐標(biāo)和縱坐標(biāo)是否夾在矩形的左右邊和上下邊之間。2.8

判斷線段、折線、多邊形是否在矩形中因?yàn)榫匦问莻€(gè)凸集，所以只要判斷所有端點(diǎn)是否都在矩形中就可以了。2.9判斷矩形是否在矩形中

只要比較左右邊界和上下邊界就可以了。2.10判斷圓是否在矩形中很容易證明，圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于等于圓心到矩形四邊的距離的最小值。2.11判斷點(diǎn)是否在多邊形內(nèi)射線法（奇偶測(cè)試法）交點(diǎn)個(gè)數(shù)奇內(nèi)部偶外部轉(zhuǎn)角法環(huán)繞數(shù)零外部非零內(nèi)部2.11判斷點(diǎn)是否在多邊形內(nèi)判斷點(diǎn)P是否在多邊形中是計(jì)算幾何中一個(gè)非?；镜鞘种匾乃惴?。以點(diǎn)P為端點(diǎn)，向左方作射線L，由于多邊形是有界的，……

所以很容易看出當(dāng)L和多邊形的交點(diǎn)數(shù)目C是奇數(shù)的時(shí)候，P在多邊形內(nèi)，是偶數(shù)的話P在多邊形外。

但是有些特殊情況要加以考慮。如圖下圖(a)(b)(c)(d)所示。在圖(a)中，L和多邊形的頂點(diǎn)相交，這時(shí)候交點(diǎn)只能計(jì)算一個(gè)；在圖(b)中，L和多邊形頂點(diǎn)的交點(diǎn)不應(yīng)被計(jì)算；在圖(c)和(d)

中，L和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計(jì)。如果L和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計(jì)。為了統(tǒng)一起見，我們?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屬于多邊形。2.11判斷點(diǎn)是否在多邊形內(nèi)P(a)(b)(c)(d)由此得出算法的偽代碼如下：

count

←

0;

以P為端點(diǎn)，作從右向左的射線L;

for

多邊形的每條邊s

do

if

P在邊s上

then

return

true;

if

s不是水平的

then

if

s的一個(gè)端點(diǎn)在L上

if

該端點(diǎn)是s兩端點(diǎn)中縱坐標(biāo)較大的端點(diǎn)

then

count

←

count+1

else

if

s和L相交

then

count

←

count+1;

if

count

mod

2

=

1

then

return

true;

else

return

false;

其中做射線L的方法是：設(shè)P‘的縱坐標(biāo)和P相同，橫坐標(biāo)為正無窮大（很大的一個(gè)正數(shù)），則P和P'就確定了射線L。

判斷點(diǎn)是否在多邊形中的這個(gè)算法的時(shí)間復(fù)雜度為O(n)。判斷點(diǎn)是否在多邊形內(nèi)轉(zhuǎn)角法利用帶符號(hào)的角度和

另外還有一種算法是用帶符號(hào)的三角形面積之和與多邊形面積進(jìn)行比較，這種算法由于使用浮點(diǎn)數(shù)運(yùn)算所以會(huì)帶來一定誤差，不推薦大家使用。

2.11判斷點(diǎn)是否在多邊形內(nèi)2.12判斷線段是否在多邊形內(nèi)

線段在多邊形內(nèi)的一個(gè)必要條件是線段的兩個(gè)端點(diǎn)都在多邊形內(nèi)，但由于多邊形可能為凹，所以這不能成為判斷的充分條件。如果線段和多邊形的某條邊內(nèi)交（兩線段內(nèi)交是指兩線段相交且交點(diǎn)不在兩線段的端點(diǎn)），因?yàn)槎噙呅蔚倪叺淖笥覂蓚?cè)分屬多邊形內(nèi)外不同部分，所以線段一定會(huì)有一部分在多邊形外(見圖a)。于是我們得到線段在多邊形內(nèi)的第二個(gè)必要條件：線段和多邊形的所有邊都不內(nèi)交。

線段和多邊形交于線段的兩端點(diǎn)并不會(huì)影響線段是否在多邊形內(nèi)；但是如果多邊形的某個(gè)頂點(diǎn)和線段相交，還必須判斷兩相鄰交點(diǎn)之間的線段是否包含于多邊形內(nèi)部（反例見圖b)。(a)(b)2.12判斷線段是否在多邊形內(nèi)因此我們可以先求出所有和線段相交的多邊形的頂點(diǎn)，然后按照X-Y坐標(biāo)排序(X坐標(biāo)小的排在前面，對(duì)于X坐標(biāo)相同的點(diǎn)，Y坐標(biāo)小的排在前面，這種排序準(zhǔn)則也是為了保證水平和垂直情況的判斷正確)，這樣相鄰的兩個(gè)點(diǎn)就是在線段上相鄰的兩交點(diǎn)，如果任意相鄰兩點(diǎn)的中點(diǎn)也在多邊形內(nèi)，則該線段一定在多邊形內(nèi)。

2.12判斷線段是否在多邊形內(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)矛盾，故命題成立。證畢。

2.12判斷線段是否在多邊形內(nèi)由命題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í)際編程中，沒有必要計(jì)算所有的交點(diǎn)，首先應(yīng)判斷線段和多邊形的邊是否內(nèi)交，倘若線段和多邊形的某條邊內(nèi)交則線段一定在多邊形外；如果線段和多邊形的每一條邊都不內(nèi)交，則線段和多邊形的交點(diǎn)一定是線段的端點(diǎn)或者多邊形的頂點(diǎn)，只要判斷點(diǎn)是否在線段上就可以了。至此我們得出算法如下：if

線端PQ的端點(diǎn)不都在多邊形內(nèi)

then

return

false;else

點(diǎn)集pointSet初始化為空;

for

多邊形的每條邊s

do

if

線段的某個(gè)端點(diǎn)在s上

then

將該端點(diǎn)加入pointSet;

else

if

s的某個(gè)端點(diǎn)在線段PQ上

then

將該端點(diǎn)加入pointSet;

else

if

s和線段PQ相交

/*這時(shí)候已經(jīng)可以肯定是內(nèi)交了*/

then

return

false;else

將pointSet中的點(diǎn)按照X-Y坐標(biāo)排序;

for

pointSet中每?jī)蓚€(gè)相鄰點(diǎn)pointSet[i],pointSet[i+1]

doif

pointSet[i]

,

pointSet[

i+1]

的中點(diǎn)不在多邊形中

then

return

false;

elsereturn

true

這個(gè)過程中的排序因?yàn)榻稽c(diǎn)數(shù)目肯定遠(yuǎn)小于多邊形的頂點(diǎn)數(shù)目n，所以最多是常數(shù)級(jí)的復(fù)雜度，幾乎可以忽略不計(jì)。因此算法的時(shí)間復(fù)雜度也是O(n)。2.13判斷折線是否在多邊形內(nèi)

只要判斷折線的每條線段是否都在多邊形內(nèi)即可。設(shè)折線有m條線段，多邊形有n個(gè)頂點(diǎn)，則該算法的時(shí)間復(fù)雜度為O(m×n)。2.14

判斷多邊形是否在多邊形內(nèi)

只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可。判斷一個(gè)有m個(gè)頂點(diǎn)的多邊形是否在一個(gè)有n個(gè)頂點(diǎn)的多邊形內(nèi)復(fù)雜度為O(m×n)。

2.15判斷矩形是否在多邊形內(nèi)

將矩形轉(zhuǎn)化為多邊形，然后再判斷是否在多邊形內(nèi)。

2.16判斷圓是否在多邊形內(nèi)

只要計(jì)算圓心到多邊形的每條邊的最短距離，如果該距離大于等于圓半徑則該圓在多邊形內(nèi)。計(jì)算圓心到多邊形每條邊最短距離的算法在后文闡述。

2.17判斷點(diǎn)是否在圓內(nèi)

計(jì)算圓心到該點(diǎn)的距離，如果小于等于半徑則該點(diǎn)在圓內(nèi)。

2.18判斷線段、折線、矩形、多邊形是否在圓內(nèi)

因?yàn)閳A是凸集，所以只要判斷是否每個(gè)頂點(diǎn)都在圓內(nèi)即可。

2.19判斷圓是否在圓內(nèi)

設(shè)兩圓為O1,O2，半徑分別為r1,

r2，要判斷O2是否在O1內(nèi)。先比較r1，r2的大小，如果r1<r2則O2不可能在O1內(nèi)；否則如果兩圓心的距離大于r1

-

r2

，則O2不在O1內(nèi)；否則O2在O1內(nèi)。

2.20計(jì)算兩條共線的線段的交點(diǎn)對(duì)于兩條共線的線段，它們之間的位置關(guān)系有下圖所示的幾種情況。圖(a)中兩條線段沒有交點(diǎn)；圖(b)和(d)中兩條線段有無窮焦點(diǎn)；圖(c)中兩條線段有一個(gè)交點(diǎn)。設(shè)line1是兩條線段中較長(zhǎng)的一條，line2是較短的一條.(1)如果line1包含了line2的兩個(gè)端點(diǎn)，則是圖(d)的情況，兩線段有無窮交點(diǎn)；(2)如果line1只包含line2的一個(gè)端點(diǎn)，那么如果line1的某個(gè)端點(diǎn)等于被line1包含的line2的那個(gè)端點(diǎn)，則是圖(c)的情況，這時(shí)兩線段只有一個(gè)交點(diǎn)，否則就是圖(b)的情況，兩線段也是有無窮的交點(diǎn);(3)如果line1不包含line2的任何端點(diǎn)，則是圖(a)的情況，這時(shí)兩線段沒有交點(diǎn)。

2.20計(jì)算兩條共線的線段的交點(diǎn)L2L1(a)L1L2(b)L2L1(c)L1L2(d)共線線段的位置關(guān)系2.21計(jì)算線段或直線與線段的交點(diǎn)

設(shè)一條線段為L(zhǎng)0=P1P2，另一條線段或直線為L(zhǎng)1=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)，假如L是線段的話可用“計(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)；

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

3.