GIS算法原理知識(shí)點(diǎn)總結(jié)

GIS算法原理知識(shí)點(diǎn)總結(jié)算法設(shè)計(jì)和分析：1、算法設(shè)計(jì)的原則：正確性：若一個(gè)算法本身有缺陷，那么它將不會(huì)解決問題；確定性：指每個(gè)步驟必須含義明確，對每種可能性都有確定的操作。清晰性：一個(gè)良好的算法，必須思路清晰，結(jié)構(gòu)合理。2、算法的復(fù)雜性包括：時(shí)間復(fù)雜性和空間復(fù)雜性。3、時(shí)間復(fù)雜性：用一個(gè)與問題相關(guān)的整數(shù)量來衡量問題的大小，該整數(shù)量表示輸入數(shù)據(jù)量的度，稱為問題的規(guī)模。利用某算法處理一個(gè)問題規(guī)模為n 的輸入所需要的時(shí)間，稱為該算法的時(shí)間復(fù)雜性。4、算，去的概念：算法是完成特定任務(wù)的有限指令集。所有的算法必須滿足下面的標(biāo)準(zhǔn)：明確性有限性有效性? ?5.矢量叉積：計(jì)算矢量叉積是直線和線段相關(guān)算法的核心部分。GIS1把這種線段稱為有向線段(directedsegment)?plp2Pl在坐標(biāo)原點(diǎn)，我們P25.矢量叉積：計(jì)算矢量叉積是直線和線段相關(guān)算法的核心部分。P=(xl,yl),Q=(x2,y2)，則矢量叉積定義為(0,0)、plp2plp2所組成的平PXQxby2-X2.yl,其結(jié)果是個(gè)標(biāo)量。顯然有性質(zhì)PXQ=-(QXP)Px-Q=-(PxQ)oPXQ〉0,則P在Q的順時(shí)針方向；voidCpntToDemDlg::RecToDemO3(//TODO:在此添加控件通知處理程序代碼CDC*pDC-GetDC()；FILE*OUt；out=fopen("d:Wraster.txt","w");Invalidate();UpdateWindow();UpdateData(true);returnRecO;intdy?(ymax-ymin)/(row-);intdx?(xmax-xmin)/(col-);booljudge-false;fprintf(out,"'did\n",row,col);for(inti=l;i<row+;i++)(for(intj?;j<col+;j++){for(intn=;n<cnt+;n++)<if(arr[n].x>(xmin+(j-)*dx)&&arr[n].x<(xmin+j*dx)&&arr[n].y>(ymin+(i-)*dy)arr(nJ.y<(ymin+i*dy))(judge-true;break;if(judge){pDC->Rectangle(xmin+(j-：)*dx,ymin+(i?)*dy,xmin+j*dxzymin+i*dy);CRectrt(xmin+(j-)*dx,ymin+(i-)*dy,xmin+j*dx,ymin+i*dy);pDC->FinSolidRect(&rt,RGB(255,,0));fprintf(outz"%d",1);judge=false;}else{pDC->Rectangle(xmin+(j-)*dxrymin+(i-)*dy,xmin+j*dxzymin+i*dy);fprintf(out,"%d",0);judge=false;}} voidCpntToDemDlg::returnRec(void)fprintf(out,"Xn");xmax=arr[1].xzymax=arr[1].y;xmin=arr[1].xzymin=arr[1].y;i=l;i<cnt+l;i++){

for(intxmin=arr[i].x;ymin=arr[i].y;xmax=arr[i].x;ymax=arr[i].y;Col:if(xmin>arr[i].x) if(ymin>arr[i].y)if(xmax<arr[i].x)if(ymax<arr[i].y)Col:io 確定 取消矢量數(shù)據(jù)的壓縮：矢量數(shù)據(jù)的壓縮包括兩個(gè)方面的內(nèi)容，一是在不擾亂拓?fù)潢P(guān)系的前提下，對采樣點(diǎn)數(shù)據(jù)進(jìn)行合理的抽稀。二是對矢量坐標(biāo)數(shù)據(jù)重新進(jìn)行編碼，以減少所需要的存儲(chǔ)空間。間隔取點(diǎn)法：每隔K個(gè)點(diǎn)取一點(diǎn)，或舍去那些比規(guī)定距離更近的點(diǎn)，首末點(diǎn)一定要保留。垂距法:。原始曲。線"線.Q-一3II，，1-3，1-，，，．，，，，．，，3 ，夕3 ，夕｀r,20，1

對點(diǎn)2測試距離大于規(guī)定的限差4,Q4限差|限差|21-，2r，，321-，2r，，3)＇

對點(diǎn)3測試距離小于規(guī)定的限差||，aPnao1--.-.c2

一三．一光欄法的基本思想是（上圖）：還是舍去。設(shè)曲線上的點(diǎn)列為{pi},i1,2,d,可根據(jù)壓縮量的大小自己定義，則光欄法的實(shí)施步驟可描述為：1p1p2點(diǎn)，過p2點(diǎn)作一條垂直于p1p2的直線，在該垂線上取兩點(diǎn)a1a2,a1p2=a2p2=d/2,a1a2為“光欄”邊界點(diǎn)，p1a1、p1a2的連線為以p1）p1并在扇形內(nèi)的所有直線都具有這種性質(zhì)，即p1p2±d您。2p3點(diǎn)在扇形內(nèi)，則舍去p2點(diǎn)。然后連接p1和p3,過p3p1p1c1C2。在垂線上找到b1和b2p3b1=p3b2=d/2,b1b2點(diǎn)（（圖4-4-3b2點(diǎn)）落在原扇形c1c2取代（圖4-4-3c2b2）p1b1p1c2定義一個(gè)新的扇形，這當(dāng)然是口徑（b1c2）縮小了的“光欄”。3。、檢查下一節(jié)點(diǎn)，若該點(diǎn)在新扇形內(nèi)，則重復(fù)第（2）步；直到發(fā)現(xiàn)有一個(gè)節(jié)點(diǎn)在最新定義的扇形外為止。44-4-3中的p4,此時(shí)保留p3點(diǎn)，以p31。?3。。如此繼續(xù)下去，直到整個(gè)點(diǎn)列檢測完為止。所有被保留的節(jié)點(diǎn)（含首、末點(diǎn)），順序地構(gòu)成了簡化后的新點(diǎn)列。4）道格拉斯一普克法：首先將一條曲線首、末點(diǎn)連一直線，求出各點(diǎn)到該直線的距離，選其最大者與規(guī)定的臨界值相比較若大于臨界值，則離該直線距離最大的點(diǎn)保留，否則，將直線兩端間各點(diǎn)全部舍去，并將原線條分成兩部分，對每部分線條再實(shí)施該抽稀過程，直到結(jié)束。抽稀結(jié)果點(diǎn)數(shù)隨選取限差臨界值的增大而減少，應(yīng)用時(shí)應(yīng)根據(jù)精度要求來確定抽稀限差臨界值，以獲得最好的結(jié)果。即道格拉斯一普克（Douglas-peuker）算法。PResultP】弦第一輪垂距第二輪垂距I|閾值柵格數(shù)據(jù)的壓縮:1）鏈?zhǔn)骄幋a：3,1,7,0,1,2,3,4,5,64,1,6,7,0,1,2,3,4,5（Freeman）2）游程編碼：所謂游程是指按行的順序連續(xù)且屬性值相同的若干柵格。游程長度的記錄方式有兩種記錄每個(gè)游程起（迄）列號(hào)①記錄每個(gè)游程像元數(shù)②記錄每個(gè)游程像元數(shù)5,5A A B BA C C C

2, AB1,A3,C1,AD1, C2,A劃分成若干具性的方形后對各個(gè)正方形進(jìn)行編碼。塊式編碼的數(shù)據(jù)結(jié)構(gòu)由初始DDDDCAADDAAA1,2,M；1,3,1,R；1,1,M； 1,5,1,M；M 1 7,2,M1,6,3,2,R；2,5,1,M；2,1,R1,1,M；3,2,1,R；3,3,R；3, 8,1,M1,1,M；4,2,3,R;8,1,M1,1,M：5,8,1, M法之一。四分樹將整個(gè)圖像區(qū)域逐步分解為一系列方形區(qū)域，且每一個(gè)方形區(qū)域具有單一的屬性。最小區(qū)域?yàn)橐粋€(gè)象元。2345678MM R MM M MMMM R R MR MMM R RR RR RMM R RR RR RMM R RR RR RMM R RR RR RMMM R R R R RMMM MR R MMM四叉樹編碼方法記錄每個(gè)葉子結(jié)點(diǎn)的地址和屬性NW(0)NE(1)SW SE(3)(2)200201202203230231232233隔點(diǎn)取樣法實(shí)例:ttdefineMax100-typedefstructEi{intx;inty;}Pnt;Pntarr[Max];Pntarr2[Max];intnum=0;intnum2=0;//定義倆數(shù)組intn;voidCcompress2Dlg::OnBnClickedCompress(){|//TODO:在此添加控件通知處理程序代碼CDC*pDC=GetDC();//Invalidate();//UpdateWindow();UpdateData(TRUE);for(inti=l;i<=num;i++)(if(i%n—1)(num2++；arr2[num2].x=arr[i].x;arr2[num2].v=arr[i]?v;})y+5);

if(num%n!=l)(num2++;arr2[num2].x=arr[num].x;arr2[num2].y=arr[num],y;}for(intj=2;j<=num2;j++)(CDC*pDC=GetDC();pDC->El1ipse(arr2[j].x-5,arr2[j].y-5,arr2[j].x+5,arr2[j].pDC->MoveTo(arr2j-1x,arr2[j-1].y);pDC->LineTo(arr2[j].x,?y);}voidCcompress2Dlg::OnLButtonDown(UINTnFlags,CPointpoint)//TODO:在此添加消息處理程序代碼和/或調(diào)用默認(rèn)值CDC*pDC=GetDC():pDC->Rectangle(point,x-2,point,y-2,point,x+2,point,y+2);num++;arr[num].x=point.x;arr[num].y=point.y;if(num>l)(pDC->MoveTo(arr[num-1].x,arr[num-1],y);pDC->LineTo(arr[num].x,arr[num],y);}CDialogEx::OnLButtonDown(nFlags,point);空間數(shù)據(jù)內(nèi)插算法1.空間數(shù)據(jù)內(nèi)插的定義：根據(jù)已知的空間數(shù)據(jù)估計(jì)(預(yù)測)未知空間的數(shù)據(jù)值?？臻g數(shù)據(jù)內(nèi)插目標(biāo)：① 缺值估計(jì)：估計(jì)某一點(diǎn)缺失的觀測數(shù)據(jù)，以提高數(shù)據(jù)密度。② 內(nèi)插等值線：以等值線的形式直觀地顯示數(shù)據(jù)的空間分布。③ 三角網(wǎng)等。模型模擬方法和綜合方法。方法。果進(jìn)行嚴(yán)格的檢驗(yàn)。6空間數(shù)據(jù)內(nèi)插的分類依據(jù)：①確定或隨機(jī)；點(diǎn)與面；②全局或局部等標(biāo)準(zhǔn)分類；內(nèi)插方法的基本假設(shè)和數(shù)學(xué)本質(zhì)。較近控制點(diǎn)的影響比較遠(yuǎn)控制點(diǎn)的影響更大。反距離權(quán)重方法的通用方程是：式中，Z00的估計(jì)值；Z,zi與點(diǎn)0間的趾離；sK為指定的慕。20雙線性插值算法：是一種數(shù)字圖像處理、DEM部插值算法。原理：如圖8.5所示，設(shè)犬0,0)=Z|,/(I,0)=Z2,/(0,1)=Z3,/(I,1)Z4,f(x,y)點(diǎn)的值,其中知，e[0,l]of(0,0)、/(I,0)、f(0,1)、/(1,1)J(x,y)=or+by+cxy+d求出各參數(shù)小b、c、d的值，再將代入，解得TUy)。5反距離權(quán)重插值實(shí)例:PXQ<(),則P在Q的順逆針方向；PXQ>0,則PQ共線，但可能同向也可能反向。6、判斷線段的拐向：折線段的拐向判斷方法，可以直接由矢量叉積的性質(zhì)推出，對于有公共端點(diǎn)的線段pOpl和P1P2,通過計(jì)算(p2-p0)X(Pl-pO)的符號(hào)便可以給出折線段的拐向?；?p2?p0)X(P1.pO)vO,POP1

基(p2-p0)X(P1-p0)=0,po則P0P1P2三點(diǎn)共線

pO基(p2?p0)X(P1-p0)>0,則P0P1在P1點(diǎn)拐向右側(cè)后得到在P1點(diǎn)拐向左側(cè)后得到P1P2 P1P2理解矢量的概念通過矢量差積的方法就可以判斷的拐向了。7.判斷點(diǎn)是否在線段上：設(shè)點(diǎn)為Q,線段為PlP2：(Q-Pl)X(P2-Pl)=O且Q在以Pl,P2為對角頂點(diǎn)的矩形內(nèi)。前者抱走點(diǎn)在直線上，后者保證點(diǎn)不在線段延長線或反向延長線上。8、判斷兩線段是否相交(算法一)：快速排斥實(shí)驗(yàn)：設(shè)以線段P1P2為對角線的矩形為R,設(shè)以線段Q1Q2為對角的矩形為T,如果R和T不相交，顯然兩線段不會(huì)相交#include<math.h>#defineMAX100etypedefstructs{intx,y,z;}Pnt;Pntarr[MAX];intnum=0;-voidCinterpolationDlg::OnLButtonDown(UINTnFlags,CPointpoint){//TODO:在此添加消息處理程序代碼和/或調(diào)用默認(rèn)值CDC*pDC=GetDC();pDC->El1ipse(point,x-3,point,y-3,point,x+3,point,y+3);num++;arr[num].x=point.arr[num],y=point,UpdateData(TRUE);arr[num].z=IDWy；//IDWy就是IDWz,純屬手誤CStringstr;str.Formatarr[num],z);pDC->TextOutA(arr[num].x-30,arr[num],y-30,str);J-vil:tolnlg,inckedButtonIDW()(//TODO:doublenAtor=0,dAtor=0;doubledis=0,Z;CStringstr;for(inti=l;i<=num;i++)(dis=sqrtf((arr[i].x-X)*(arr[i].x-X)+(arr[i].y-Y)*(arr[i].y-Y));str.Formatdis);nAtor+=(arr[i].z/dis);I} dAtor+=(1.0/dis);Z=nAtor/dAtor;str.FormatZ);CDC*pDCGetDCOTIN、DEM、DAT1.1.2.數(shù)字高程模型：是通過有限的地形高程數(shù)據(jù)實(shí)現(xiàn)對地形曲面的數(shù)字化模擬或者說是地形表面形態(tài)的數(shù)字化表示，英文為DigitalElevationModel,簡稱DEM。2.DEMDTM（，DEM也常常稱為DTMo要說明的是由于“Terrain”一詞的含義比較廣泛，不同專業(yè)背景對“Terrain”的理解也不一樣，DTM趨向于表達(dá)比DEM更為廣泛的內(nèi)容，詳見后文的分析。表2數(shù)字地面模型有關(guān)術(shù)語術(shù)語全稱 特點(diǎn)與含義DigitalElevationDEM ModelDHM DigitalHeightModelDigitalGroundModelDGMDigitalGeomorphologyModelDTM DigitalTerrainDTEDDigitalTerrain

以絕對高程或海拔表示的地形模型以任意高程表示的地形模型，包括絕對高程和相對高程，為德國所使用具有連續(xù)變化特征的地表實(shí)體模型，為英國所使用除高程外的其他地貌形態(tài)模型，如坡度、坡向等泛指地形表面自然、人文、社會(huì)景觀模型,為美國國防制圖局所使用的地形模型，強(qiáng) 調(diào)模型的I取決于aidl

c大TINDEMTIN如山脊點(diǎn)、山谷線、地形變化線等表示地形特征。規(guī)則格網(wǎng)DEM優(yōu)點(diǎn)?簡單的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)；；好的表面分析功能缺點(diǎn)?i+W缺點(diǎn)效率較低；?數(shù)據(jù)冗余；?格網(wǎng)結(jié)構(gòu)規(guī)則

不規(guī)則三角網(wǎng)TIN優(yōu)點(diǎn)?較少的點(diǎn)可獲取較高的精度??可雋分辨率；?良好的拓?fù)浣Y(jié)構(gòu)缺點(diǎn)?i?缺點(diǎn)分析能力較差；?構(gòu)建比較費(fèi)時(shí)；?算法設(shè)計(jì)比較復(fù)雜DEM

格網(wǎng)DEM數(shù)據(jù)結(jié)構(gòu)不規(guī)則三角形DEM數(shù)據(jù)結(jié)構(gòu)DEM的邊界范圍一般是規(guī)則矩形，而實(shí)際地形范圍卻是不規(guī)則的,DEM高程值的表示方法（無效區(qū)域數(shù)據(jù)）,一般是給出一個(gè)特殊的常數(shù)值，如-9999等。規(guī)則格網(wǎng)DEMDEM數(shù)據(jù)進(jìn)行說明的數(shù)據(jù)頭和DEM數(shù)據(jù)體兩部分。1）數(shù)據(jù)頭：一般包括定義DEM及高程放大系數(shù)等內(nèi)容；2）數(shù)據(jù)體：按行或列分布記錄的高程數(shù)字陣列。例 困術(shù)我15敏酮角格咐利蠕網(wǎng)B酗角格怫無冷蠕處'、格網(wǎng)幄里融幅靴

2512345.054321.010*999912,14,15,￡n蚌傾的DEM 蹴件 咖觀?"3I

繞T與序?qū)偬?hào)性XyZ123456坐標(biāo)表三角形表XyZ號(hào)性1點(diǎn)2點(diǎn)XyZ號(hào)性1點(diǎn)2點(diǎn)3111622226333364444655 5 5 6 16基本鋌表結(jié)構(gòu)圖TIN模型的基本鏈表結(jié)構(gòu)TIN模型的面結(jié)構(gòu)最大特點(diǎn)是：由于存儲(chǔ)了三角形之間的鄰接關(guān)系，TIN內(nèi)插、檢索、等高線提取、顯示以及局部結(jié)構(gòu)分析都比較方便，不足之處是：存儲(chǔ)量較大，而且在TIN的編輯中要隨時(shí)維護(hù)這種關(guān)系。DEMDEM的第一步是獲取地形數(shù)據(jù)。DEM的數(shù)據(jù)源和數(shù)據(jù)獲取方式對于DEM的最終質(zhì)量至關(guān)重要。DEMDEM應(yīng)用目的、數(shù)據(jù)采集效率和成本、技術(shù)熟DEM/*目前DEM的數(shù)據(jù)主要來源于地形圖、攝影測量與遙感影像數(shù)據(jù)、地面測量、既有DEM數(shù)據(jù)等。*/坡度：坡度是地表形態(tài)最為重要的因子，通過坡度可以完整地形成地形曲面(Evans,1972；Strahler,1956)；坡度是地形曲面函數(shù)一階微分的函數(shù)，表達(dá)了高程隨距離變化的比率(坡度定義為地面一點(diǎn)的切平面與水平面之間的夾角)，而坡度的變率是地形曲面的二階微分，進(jìn)一步刻畫了坡度的變化，從而反映地形的復(fù)雜程度；DEM高程精度與平均坡度值之間存在強(qiáng)相關(guān)，通過模型的平均坡度可DEM的精度(Ackermann,1979;Ley,坡度通過相互垂直的兩個(gè)坐標(biāo)軸方向的高程變化表達(dá)地形曲面局部單元的傾斜程度，也就是通過地形表面的凸面和凹面來描述地形表面特性，即地表的陡峭方向和大小。TIN數(shù)據(jù)的建立：基于不規(guī)則三角網(wǎng)的數(shù)字高程模型(BasedonTriangulatedIrregularNetwork

DEM,簡寫為 Based on

DEM,俗稱 TIN)就是用一系列11.互不交叉、互不重疊的連接在一起的三角形來表示地形表面。TIN是DEM11.N幾TINA所示；最大最凸四邊形對角線后所形成的兩三角形的最小內(nèi)角，如圖B所示；最短距離和準(zhǔn)則：圖C,最短距離和就是指一點(diǎn)到基邊兩端的距離和為最小；D,E,三角形內(nèi)切圓面積與三角形面積或三角形面積與周長平方之比最?。籉,兩三角形組成的凸四邊形的兩條對角線之比。超過給定限定值時(shí)對三角形進(jìn)理論上可以證明：張角最大準(zhǔn)則、空外接圓準(zhǔn)則及最大最小角準(zhǔn)則是等價(jià)的，其余的則不然。行優(yōu)化。理論上可以證明：張角最大準(zhǔn)則、空外接圓準(zhǔn)則及最大最小角準(zhǔn)則是等價(jià)的，其余的則不然。三角形剖分準(zhǔn)則是建立三角形網(wǎng)絡(luò)的基本原則，應(yīng)用不同的準(zhǔn)則將會(huì)得到不 同的三角形網(wǎng)絡(luò)。一般而言，應(yīng)盡量保持三角網(wǎng)的唯一性，即在同一準(zhǔn)則下由不 同的位置開始建立三角形網(wǎng)絡(luò)，其最終的形狀和結(jié)構(gòu)應(yīng)是相同的，在這-點(diǎn)上,張伯最大準(zhǔn)則、空外接圓準(zhǔn)則及最大最小們準(zhǔn)則可以做到對角線準(zhǔn)則含有主觀因素，現(xiàn)今使用已不多。通常將在空外接圓準(zhǔn)則、最大最小角準(zhǔn)則下進(jìn)行三角剖分稱為DelaunayDT,Delaunay三角網(wǎng)的兩個(gè)基本性質(zhì)。DT三角剖分是目前應(yīng)用最為廣泛的三角剖分方法，其特性是可最大限度避免狹長三角形的出現(xiàn)以及不管從何處開始構(gòu)網(wǎng)都能保持三角形網(wǎng)絡(luò)的唯一性，這一點(diǎn)在實(shí)際應(yīng)用中相當(dāng)重要。實(shí)際上，在任何三角剖分準(zhǔn)則下得到TIN,LOP法則（localoptimalprocedureDT三角網(wǎng)絡(luò)。LOPLawson1977DT三角網(wǎng)的空外接圓性質(zhì)對由兩個(gè)有公共邊的三角形組成的四邊形進(jìn)行判斷。如果其中一個(gè)三角形的外接圓中含有第四個(gè)頂點(diǎn)，則交換四邊形的對角線。無約束散點(diǎn)域的三角剖分算法與實(shí)現(xiàn)：?分割合并算法*三角法生長算法無約束散點(diǎn)域的三角剖分算法與實(shí)現(xiàn)：★逐點(diǎn)插入算法@1*分割合并算法：分割合并算法(divideandconquerdelaunaytriangulationalgorithm)ShamosHoey1975年提出V-圖的構(gòu)成(V-VorinoiDT三角網(wǎng)的對偶圖，DTV-義、性質(zhì)和分割算法參見計(jì)算幾何方面的書籍)。LewisRobinson1978DTLeeSchachler、DwyerLewisRobinsonLeeSchachter1980Dwyer1987優(yōu)化策略，因而能處理帶約束條件的數(shù)據(jù)。LOP算法保證三角DT三角網(wǎng)。當(dāng)每個(gè)子集剖分完成后，對每個(gè)子集的三角剖分進(jìn)行合并，形成最終的整體三角網(wǎng)。不同的實(shí)現(xiàn)方法可有不同的點(diǎn)集劃分方法、子三角網(wǎng)生成方法及合并方法等。分割合并算法的基本步驟為：'｀．'｀．對每一個(gè)子集進(jìn)行三角剖分對每一個(gè)子集進(jìn)行三角剖分LOP絆法進(jìn)行優(yōu)化線（租實(shí)線），底線開始自下而^｀，第一步，把數(shù)據(jù)集以橫坐標(biāo)為主、縱坐標(biāo)為輔按升序進(jìn)行排序;第二步，如果數(shù)據(jù)集中的數(shù)據(jù)個(gè)數(shù)大于給定的閾值，則把數(shù)據(jù)域劃分為個(gè)數(shù)近似相等的左右兩個(gè)子集，并對每一子集做如下的工作，①計(jì)算每一子集的凸殼；②以凸殼為數(shù)據(jù)邊界，對每一數(shù)據(jù)子集LOPDT三角剖分；③找出連接左右子集兩個(gè)凸殼的底線和頂線；④由底線到頂線，合并兩個(gè)子三角網(wǎng)；第三步：如果數(shù)據(jù)集中的數(shù)據(jù)個(gè)數(shù)小于給定的閾值，則直接輸出三角剖分結(jié)果；Z和夫，NZ和夫上的點(diǎn)，A.8下條件：AzAX=max{X[}底線查找：從N8有向線段開始，對于夫中點(diǎn)，如果沿逆時(shí)針且與8相鄰的匕點(diǎn)位于43的右側(cè)，則J5=F； 在新的方向上，如順時(shí)針且與N相鄰的X點(diǎn)位于48的右側(cè)，則A=X.直到，和人中沒有位于43線段右側(cè)的點(diǎn)為止，4月為連接/和&的底線。A= B=

頂線查找：從義8有向線段開始，對于夫中點(diǎn)，如果順時(shí)針且與&相鄰的匕點(diǎn)位于幽的左側(cè)，則8=1;在新的方向上，如果逆時(shí)針且與義相鄰的X點(diǎn)位于48的左側(cè)，則A=X,直到￡和夫中沒有位于43線段左側(cè)的點(diǎn)為止，48為連接E和&的上線。子三角網(wǎng)合并：合并的方式是同層優(yōu)先，從下至上的遞歸方式進(jìn)（這是分割合并算法“合并一詞的由來）。合并時(shí)先找出兩個(gè)鄰子三角網(wǎng)凸殼在上下（或左右）的公共切線，這些公共切 線將是最終三角網(wǎng)的一部分。上下公切線查找完后，即可從連接兩三角網(wǎng)的底線開始，在兩子 三角網(wǎng)中尋找與Delaunay三角形的第三點(diǎn)，中外接圓半徑小的一個(gè)插入到最終的三角網(wǎng)中。新生成的連接左右兩個(gè)子三角網(wǎng)的邊成為新的底線，逐步上推到頂線結(jié)束，如圖所示。在第一步中，主要工作是對數(shù)據(jù)點(diǎn)進(jìn)行排序，目的是使 子三網(wǎng)不相互重疊和交叉。一般是以橫坐標(biāo)為主、縱坐標(biāo)為輔按升序進(jìn)行排序，即數(shù)據(jù)點(diǎn)之間滿足如下的條件：（也況）＜不等式成立的條件是t +1 x<x. <zt +1 且排序的方法采用以遞歸方式進(jìn)行的分割快速排序方法,詳見數(shù)據(jù)結(jié)構(gòu)書籍的介瓦第二步是該算法的主體，包括數(shù)據(jù)集的連續(xù)分割、凸殼生成、凸殼三角剖分、子網(wǎng)合并 計(jì)算R和其余數(shù)據(jù)點(diǎn)/的連線與水等內(nèi)容，集中體現(xiàn)了該算法的基本思想，即分割（數(shù)據(jù)點(diǎn)的分割），合并（子三角網(wǎng)的合并）。@2*三角網(wǎng)生長算法：顧名思義，三角網(wǎng)生長算法就是從一個(gè)“源”開始，

水平線

平線的夾角.并按夾伯進(jìn)行排序（央角相同.按距離排序）將排序后的定點(diǎn)順次連接成一個(gè)多邊形R.PiPio循環(huán)刪除非凸頂點(diǎn)％PTPg，得到凸光頂點(diǎn)R?Pv逐步形成覆蓋整個(gè)數(shù)據(jù)區(qū)域的三角網(wǎng)。從生長過程角度，三角網(wǎng)生長算法分為收縮生長算法和擴(kuò)張生長算法兩種。收縮生長算法是先形成整個(gè)數(shù)據(jù)域的數(shù)據(jù)邊界（凸殼），并以此作為源頭，逐步縮小以形成整個(gè)三角網(wǎng)。收縮生長算法與數(shù)據(jù)點(diǎn)的分布密度有關(guān)，實(shí)際情況往往比較復(fù)雜，例如當(dāng)邊界收縮后一個(gè)完整的區(qū)域可能會(huì)分解成若干個(gè)相互獨(dú)立的子區(qū)域，這就增加了三角剖分的復(fù)雜性擴(kuò)張生長算法與收縮算法過程剛好相反，該算法是從一個(gè)三角形開始向外層層擴(kuò) 展，最終形成覆蓋整區(qū)域的三角網(wǎng)，其主要步驟為：第一步，生成初始三角形。在數(shù)據(jù)點(diǎn)中任取一點(diǎn)A（該點(diǎn)一般是位于數(shù)據(jù)點(diǎn)的幾何中心附近），并8,AB,（空外接圓準(zhǔn)則或張角最大準(zhǔn)則），C,DelaunayA8C。第二步，擴(kuò)展形成三角網(wǎng)。以初始三角形的三條邊為初始基線，利用空外接圓準(zhǔn) 則或張角最大準(zhǔn)則尋找能與該三條初始基線形成Delaunay三角形的。、￡、F點(diǎn)。AACC注意：（1）ABC,AB.C，ABCD,C同側(cè)，判斷方法為：設(shè)直線兩端點(diǎn)的坐標(biāo)為』

,3（喝力），另兩點(diǎn)分別為C（x

y）,y'可通過下式判斷點(diǎn)。刀在他的同異側(cè)關(guān)系,

Cfc f DDx）=y-ax-3。次_小人）/（十位）.在式中代入D坐標(biāo)，則有若F（Dc）與F（知,&）符號(hào)相同，則C、D位于AF的同一側(cè)IF（xc，〉c）與尸（勺＞，&）D若映，沁=?；蛳Γㄉ祝?＞攝=0,CD與朋共線?跨立實(shí)驗(yàn)：如果兩線段相交，則兩線段必然相互跨立對方。若plp2跨立Q1Q2,則矢量(P1-Q1)和(P2-Q2)位于矢量(Q2-Q1)的兩側(cè)，則(P1-Q1)X(Q2-Q1)X(P2-QI)X(Q2.Q1)〈O°當(dāng)(P1-Q1)X(Q2-Q1)二0時(shí)，說明(Pl-Ql)X(Q2-Q1)共線，但是因?yàn)橐呀?jīng)通過快速排斥實(shí)驗(yàn)，所以PI一定在線段Q1Q2上；同理(Q2-Q1)X(P2-Q1)=0說明P2Q1Q2上。所以判斷P1P2跨立Q1Q2的依據(jù)是：(Pl-Ql)X(Q2-Q1)X(Q2-Q1)X(P2-Q1。同理判斷Q1Q2跨立P1P2的依據(jù)是(Ql-Pl)X(P2-P1X(P2-P1)X(Q2-P1)30。注意在進(jìn)行“跨立判斷”的時(shí)候是進(jìn)行兩次跨立判斷判斷矩形內(nèi)是否包含點(diǎn)：只要判斷該店的橫坐標(biāo)和縱坐標(biāo)是否都夾在矩形的左右邊和上下邊之間。判斷線段、折線、多邊形是否在矩形中：因?yàn)榫匦问莻€(gè)凸集，所以只要判斷所有端點(diǎn)都在矩形就行了。判斷矩形是否在矩形中：只要比較左右邊界和上下邊界就行了。判斷圓是否在矩形中：圓心在矩形中且圓的半徑小于或等于圓心到矩形四邊的距離的最小值。1)

判斷點(diǎn)是否在多邊形內(nèi):射線法：一條射線從點(diǎn)P開始，穿過多邊形的邊界的次數(shù)稱為交點(diǎn)數(shù)目。當(dāng)交點(diǎn)數(shù)目是偶數(shù)時(shí)，點(diǎn)P在多邊形外部；否則，為奇數(shù)時(shí)，在多邊形內(nèi)部。點(diǎn)

(c)位于濱點(diǎn)上下兩點(diǎn)下倒 側(cè)(方向向下〉B?Rz:多邊形的頂點(diǎn);①?⑤,判斷

(方向向上)

點(diǎn)三@逐點(diǎn)插入算法逐點(diǎn)插入算法的過程非常簡單，基本步驟為：第一步，定義包含所有數(shù)據(jù)點(diǎn)的初始包容盒，并對該包容盒進(jìn)行初始三角剖分；第二步，對所有數(shù)據(jù)點(diǎn)進(jìn)行循環(huán)，做如下工作(設(shè)當(dāng)前處理的數(shù)據(jù)點(diǎn)為P),在已存在的三角網(wǎng)中，查找包含p的三角形t；②pttLOP算法對初始三角剖分進(jìn)行優(yōu)化處理。第三步，處理外圍三角形。DEM讀取實(shí)例：-voidCDemView::OnDemDem()(//TODO:在此添加命令處理程序代碼CDC*PDC=GetDC();introw=10,col=10;CStringstr;intsize=50;//定義二維數(shù)組intdemtlOO][100];charstrrflOO]:char*p;FILE*in;in=fopenCD:\\Upan\\GIS算法原理\\dem2.txt”,"r”);fscanf(in,"%d%d\n",&row,&col);for(inti=l;i〈=row；i++)fgets(strr,100,in);p=strtok(strr,"")：dem[i][l]=atoi(p);for(intj=l;j<=col-l：j++)(p=strtok(NULL,"");dem[i][j+l]=atoi(p);}//str.FormatC%d*,dem[3][4]);MessageBox(str);)fclose(in);for(inti=l;i<=col;i++)(for(int(pDC->Rectangle((i-1)*size,(j-l)*size,i*size,j*size);3//CRectrt((i-l)*size,(j-l)*size,i*size,j*size);//pDC->Fi1ISolidRect(&rt,RGB(dem[j+l][i+l]*5,0,0));pDC->TextOut((i-1)*size,(j-l)*size,itoa(dem[j][i],strr,10));}13緩沖區(qū)分析算法：緩沖區(qū)（buffer）立其周圍一定寬度范圍的多邊形。分類：點(diǎn)緩沖區(qū)、線緩沖區(qū)、面緩沖區(qū)和復(fù)雜實(shí)體緩沖區(qū)。步進(jìn)擬合的思想，即圓弧彌合的方法：（雙側(cè)平行線法）將圓心角等分，用等長的弦代替圓弧，即用均勻步長的直線段逼近圓弧段。等分的圓心角越小，步長越小，誤差越小；等分的圓心角越大，步長越大，誤差越大。凸角圓弧法，基本思想：在軸線的兩端用半徑為緩沖距的圓弧彌合；在軸線的各轉(zhuǎn)折點(diǎn)，判斷該點(diǎn)的凸凹性，在凸側(cè)用半徑為緩沖距的圓弧彌合，在凹 側(cè)用與該點(diǎn)關(guān)聯(lián)的前后兩相鄰線段偏移量為緩沖距的兩平行線的交點(diǎn)作為對應(yīng)頂點(diǎn)。關(guān)于緩沖區(qū)自相交處理：（P194）自相交多邊形的兩種情況：島嶼，多邊形緩沖區(qū)邊線只繪制外圍邊線和島嶼輪廓。緩沖區(qū)檢索時(shí)，在外邊線所形成的多邊形檢索后，再扣除所有島嶼多邊形。網(wǎng)絡(luò)分析1網(wǎng)絡(luò)中基本組成部分：結(jié)點(diǎn)（Node）：網(wǎng)絡(luò)中任意兩條線段的交點(diǎn)，屬性如資源數(shù)量等鏈（Link）：連接兩個(gè)結(jié)點(diǎn)的弧段。供物體運(yùn)營的通道，鏈間的連 接關(guān)系由孤段■結(jié)點(diǎn)拓?fù)鋽?shù)據(jù)結(jié)構(gòu)來表達(dá)。屬性如資源流動(dòng)的時(shí)間、速度等中心（Center）：網(wǎng)絡(luò)中位于結(jié)點(diǎn)處，具有沿著鏈?zhǔn)占桶l(fā)放資源 能力的設(shè)施，如郵局、電站、水座等站點(diǎn)（Stop）：資源沿著網(wǎng)絡(luò)路徑流動(dòng)時(shí)被分配或收集的位置，如 郵件投放點(diǎn)、公共汽車站，屬性如資源需求量轉(zhuǎn)向點(diǎn)（拐點(diǎn)，Turn）：鏈路相交處，資源流向發(fā)生改變的點(diǎn)邊/邊集圖：是一個(gè)非空的有限結(jié)點(diǎn)和有限邊的集合。網(wǎng)絡(luò)流：指網(wǎng)絡(luò)中任意一條弧的物流量。2.給定單源點(diǎn)的最短路徑的求解（三步）：1）vv出發(fā)的所有邊為到各頂點(diǎn)的最短路徑（確定數(shù)據(jù)結(jié)構(gòu)：vdist[],開始時(shí),diStVidiStV行。②設(shè)一個(gè)用pathn,pathi個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)）。2）dist[]中選一條最短的，并將其終點(diǎn)（即＜v,k＞）ks3）TvksvT中剩余的jkjvUj原來的最短的還要dist[k]+g[k,j]dist|j]，取其中的較小者。4)再選出一個(gè)到源點(diǎn)v路徑長度最小的頂點(diǎn)k,從T中刪去后加入S中，再回去到第三步，如此重復(fù)，直到集合S中的包含圖G的所有頂點(diǎn)。3(要求掌握基本概念和步驟，他們的區(qū)別)帶權(quán)圖分為有向和無向，無向圖的最短路徑又叫做最小生成樹，有prime算法和kruskal算法；有向圖的最短路徑算法有dijkstra算法和tloyd算法。(-)Floyd算法(P209)：Floyd算法又稱為弗洛伊德算法，插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法。AB21AB,2AXBDis(AB)AB的最短路X,Dis(AX)Dis(XB)Dis(AB)是否成立，如果成立AXBABDis(AB)Dis(AX)Dis(XB),X,Dis(AB)AB步驟：1)從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無窮大。2)uv,wuwvGViVj有路可達(dá)，G[i,j]=d,dG[ij]=DViVjD[i,j]=jmin(G[iJ],G[i,k]+G[kj]),G[i,j]D[ij]=ko在G中包含有兩點(diǎn)之間最短道路的信息，而在D中則包含了最短通路徑的信息。比如,要尋找從V5到VI的路徑。根據(jù)D,假如D(5,l)=3則說明從V5到VI經(jīng)過V3,路徑為｛V5,V3,V1｝，如果D(5,3)=3,說明V5與V3直接相連，如果D(3,l)=l,說明V3與VI直接相連。實(shí)驗(yàn)作業(yè)1：1空間數(shù)據(jù)(矢量)的采集作業(yè)2：實(shí)驗(yàn)2空間數(shù)據(jù)的保存作業(yè)3：實(shí)驗(yàn)三計(jì)算幾何基礎(chǔ)(1)折線拐向判斷作業(yè)4：實(shí)驗(yàn)三計(jì)算幾何基礎(chǔ)(2)地圖量算作業(yè)5：實(shí)驗(yàn)三計(jì)算兒何基礎(chǔ)(3)三角形面積量算作業(yè)6：實(shí)驗(yàn)四(一)坐標(biāo)變換作業(yè)7：實(shí)驗(yàn)四(二)格式轉(zhuǎn)換作業(yè)8：實(shí)驗(yàn)四(三)矢量數(shù)據(jù)壓縮作業(yè)9：實(shí)驗(yàn)四(四)柵格數(shù)據(jù)壓縮作業(yè)10：實(shí)驗(yàn)五空間數(shù)據(jù)的內(nèi)插射線法要考慮幾種特殊的情況，并且射線法適用于凸多邊形2）轉(zhuǎn)角法：多邊形環(huán)繞點(diǎn)P的次數(shù)稱為環(huán)繞數(shù)，環(huán)繞數(shù)為0時(shí)，點(diǎn)P在多邊形外部，否則在多邊形內(nèi)部。判斷線段是否在多邊形內(nèi)：（折線是判斷它的每條線段條件一：線段的兩個(gè)端點(diǎn)都在多邊形內(nèi)條件二：線段和多邊形的所有邊都不內(nèi)交。判斷多邊形否在多邊形內(nèi)：mn個(gè)頂點(diǎn)O（mXn）判斷矩形是否在多邊形內(nèi)：將矩形轉(zhuǎn)化為多邊形，然后再判斷是否在多邊形內(nèi)。徑，則該圓在多邊形內(nèi)。判斷點(diǎn)是否在圓內(nèi)：計(jì)算圓心到該點(diǎn)的距離，若小于或等于半徑，則該點(diǎn)在圓內(nèi)。要判斷是否每個(gè)頂點(diǎn)都在圓內(nèi)即可。判斷圓是否在圓內(nèi)：01,02,半徑為rl,r2rl,r2rl<r2,0201內(nèi)；若兩圓rl-r2,0201內(nèi)；反之，0201內(nèi)。會(huì)點(diǎn)即為要求目標(biāo)點(diǎn)（注意方向二選其中一個(gè)）。距離量算算法的實(shí)現(xiàn)：ftdefineMAX100ftypedefstruct{intx;inty;}Pnt;〔Pntarr[MAX];intnum;floatDis;CStringstr;CStringpvoidCDistanceAddView::OnLButtonDown(CINTnFlags,CPointpoint)//TODO:在此添加消息處理程序代碼和/或調(diào)用默認(rèn)值CDC*pDOGetDC();pDC->Rectangle(point.x~2,point,y-2,point,x+2,point.y+2);num++;arrtnum].x=point.x;arr[num].y=point.y;if(num>l){pDC->MoveTo(arr[num].x,arrtnum].y);pDC->LineTo(arr[num-1].x,arr[num-1],y);Dis=Dis+sqrtf((arr[num].x-arr[num-1],x)*(arr[num],x-arr[num-1],x)+(arr[num],y-arr[num-1],y)*(arr[num],y-arr[num-1],y));str.FormatDis);MessageBox(str);}CView::OnLButtonDown(nFlags,point);}空間數(shù)據(jù)的變換算法1.了解平面坐標(biāo)變換的兒種形式：x=x0cosex—sinexy=x0sina+%cosax=x04-D、y=Dyx=Sxx0y=Sy2.仿射?變換：它是使用最多的一種幾何糾正方式。在保留線條平行條件下，仿射變換允許對長方xy軸；平移是指把源點(diǎn)移動(dòng)xy方向同時(shí)或單獨(dú)增大和縮小比例尺。X=(zwvcosa)x-(zwvsina)y+An=(mysina)x+(〃八cosa)y+B。xKvrAl=mxKvr

cosa,A,=

sinaBl=

sina,B2=

cosa、4=4+4*_=+Bx+By、2平移變換實(shí)例代碼：ttdefineMaxNum100typedefstruct(intx;inty;}Pnt;PntarrPnt[MaxNum];intnumPnt:avoidCmoveDlg::OnLButtonDown(UINTnFlags,CPointpoint){//TODO:在此添加消息處理程序代碼和/或調(diào)用默認(rèn)值CDC pDC->Rectangle(point,x-5,point,y-5,point,x+5,point,y+5);numPnt++;arrPnt[numPnt]. x=point. x; arrPnt [numPnt]. y=point.CDialogEx::OnLButtonDown(nFlags,point);J「voidCpanDlg::OnBnClickedButtonUP()(CDC*pDC=GetDC():Invalidate0:UpdateWindow()；for(inti=l;i<=numPnt;i++)(arrPnt[i].y-=10;|pDC->Rectangle(arrPnt[i].x-5,arrPnt[i].arrPnt[