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

1、實(shí)用文檔GIS算法原理知識(shí)點(diǎn)總結(jié)算法設(shè)計(jì)和分析：1、算法設(shè)計(jì)的原那么：正確性：假設(shè)一個(gè)算法本身有缺陷,那么它將不會(huì)解決問題；確定性：指每個(gè)步驟必須含義明確,對(duì)每種可能性都有確定的操作. 清楚性：一個(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)：輸入 輸出 明確性 有限性 有效性GIS算法的計(jì)算幾何根底1、理

2、解矢量的概念：如果一條線段的端點(diǎn)是有次序之分的,我們把這種線段稱為有向線段(directed segment).如果有向線段p1p2的起點(diǎn)P1在坐 標(biāo)原點(diǎn),我們可以把它稱為矢量 P2.5.矢量叉積：計(jì)算矢量叉積是直線和線段相關(guān)算法的核心局部.設(shè)矢量P = (x1,y1),Q= (x2,y2),那么矢量叉積定義為(0,0 )、p1、 p2和p1p2所組成的平行四邊形的帶符號(hào)的面積,即PX Q = x1 y2-x2 y1,其結(jié)果是個(gè)標(biāo)量.顯然有性質(zhì)PX Q= - (QX P)和PX -Q= -( PX Q).P X Q>0,那么P在Q的順時(shí)針方向；P X Q<0,那么P在Q的順逆針方向

3、；P X Q>0,那么P Q共線,但可能同向也可能反向.6、判斷線段的拐向：折線段的拐向判斷方法,可以直接由矢量叉積的性質(zhì)推出,對(duì)于有公共端點(diǎn)的線段 p0p1和P1P2通過計(jì)算(p2-p0 )x (P1-p0)的 符號(hào)便可以給出折線段的拐向.p2基( p2-p0 )x (P1-p0)<0,那么P0P1在P1點(diǎn)拐向左側(cè)后得到P1P2plp0基(p2-p0 )x (P1-p0)>0, 那么 P0P1在P1點(diǎn)拐向右側(cè)后得到P1P2基(p2-p0 )x (P1-p0)=0,貝U P0P1P2三點(diǎn)共線理解矢量的概念通過矢量差積的方法就可以判斷的拐向了7.判斷點(diǎn)是否在線段上：設(shè)點(diǎn)為Q,線

4、段為P1 P2: (Q-P1)X(P2-P1)=0且Q在以P1, P2為對(duì)角頂點(diǎn)的矩形內(nèi).前者抱走點(diǎn)在直線上,后者保 證點(diǎn)不在線段延長(zhǎng)線或反向延長(zhǎng)線上.8判斷兩線段是否相交(算法一)：快速排斥實(shí)驗(yàn)：設(shè)以線段P1P2為對(duì)角線的矩形為R,設(shè)以線段Q1Q2為對(duì)角的矩形為T,如果R和T不相交,顯然兩線段不會(huì)相交跨立實(shí)驗(yàn)：如果兩線段相交,那么兩線段必然相互跨立對(duì)方.假設(shè)p1p2跨立Q1Q2 那么矢量P1-Q1和P2-Q2位于矢量Q2-Q1的兩側(cè),那么J P1-Q1X Q2-Q1 X P2-Q1 X Q2-Q1 0.當(dāng)P1-Q1 X Q2-Q1 =0時(shí),說明P1-Q1X Q2-Q1共線,但是由于已經(jīng)通過快

5、速排 斥實(shí)驗(yàn),所以P1 一定在線段Q1Q2±同理Q2-Q1 X P2-Q1 =0說明P2一定在線段Q1Q2±0所以判斷P1P2跨立Q1Q2的依據(jù)是:X( P2-Q1 >0oX( Q2-P1 ) > 0o(P1-Q1) X( Q2-Q1 X (Q2-Q1) 同理判斷Q1Q2跨立P1P2的依據(jù)是(Q1-P1) X( P2-P1 ) X (P2-P1)注意在進(jìn)行“跨立判斷的時(shí)候是進(jìn)行兩次跨立判斷9.判斷矩形內(nèi)是否包含點(diǎn)：只要判斷該店的橫坐標(biāo)和縱坐標(biāo)是否都夾在矩形的左右邊和上下邊之間10.判斷線段、折線、多邊形是否在矩形中：由于矩形是個(gè)凸集,所以只要判斷所有端點(diǎn)都在矩形

6、就行 了.11. 判斷矩形是否在矩形中：只要比擬左右邊界和上下邊界就行了.12. 判斷圓是否在矩形中：圓心在矩形中且圓的半徑小于或等于圓心到矩形四邊的距離的最小值.13. 判斷點(diǎn)是否在多邊形內(nèi)：1射線法：一條射線從點(diǎn)P開始,穿過多邊形的邊界的次數(shù)稱為交點(diǎn)數(shù)目. 當(dāng) 交點(diǎn)數(shù)目是偶數(shù)時(shí),點(diǎn)P在多邊形外部；否那么,為奇數(shù)時(shí),在多邊 形內(nèi)部.紹-H:;:多迷形的山點(diǎn)?-:肖騎空；曲：由判斷點(diǎn)引Hitfrit找Wf5干氏古門俺于構(gòu)和皿上下萍*1點(diǎn)的兩的扁妁閆彌O閘常上 只.富世W帀點(diǎn)中旬刪輛宜灼®點(diǎn)1 Pi FS *1融射線法要考慮幾種特殊的情況,2轉(zhuǎn)角法：多邊形環(huán)繞點(diǎn)P的次數(shù)稱為環(huán)繞數(shù),部,

7、否那么在多邊形內(nèi)部.并且射線法適用于凸多邊形環(huán)繞數(shù)為0時(shí),點(diǎn)P在多邊形外14.判斷線段是否在多邊形內(nèi):折線是判斷它的每條線段條件一：線段的兩個(gè)端點(diǎn)都在多邊形內(nèi) 條件二：線段和多邊形的所有邊都不內(nèi)交15. 判斷多邊形否在多邊形內(nèi):只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可.判斷有m個(gè)頂點(diǎn)的多邊形是否在一個(gè)有n個(gè)頂點(diǎn)的多邊形內(nèi)的復(fù)雜度為 OmXn16. 判斷矩形是否在多邊形內(nèi):將矩形轉(zhuǎn)化為多邊形,然后再判斷是否在多邊形內(nèi).17. 判斷圓是否在多邊形內(nèi)：計(jì)算圓心到多邊形每條變邊的最短距離,假設(shè)該距離大于或等于圓半徑,那么該圓在多邊形內(nèi).18. 判斷點(diǎn)是否在圓內(nèi)：計(jì)算圓心到該點(diǎn)的距離,假設(shè)小于或等于半

8、徑,那么該點(diǎn)在圓內(nèi).19. 判斷線段、折線、矩形、多邊形是否在圓內(nèi)：由于圓是凸集,所以只 要判斷是否每個(gè)頂點(diǎn)都在圓內(nèi)即可.20. 判斷圓是否在圓內(nèi)：設(shè)兩圓為01,02,半徑為r1,r2.先比擬r1,r2的大小,假設(shè)r1<r2,那么O2不可 能在01內(nèi)；假設(shè)兩圓心距離大魚r1-r2,貝U 02不在01內(nèi)；反之,02在01內(nèi).21.距離交會(huì)：是以兩個(gè)限制點(diǎn)為中央,分別以目標(biāo)點(diǎn)與兩限制點(diǎn)的距離為半徑劃圓,交會(huì)點(diǎn)即為要求目標(biāo)點(diǎn)注意方向二選其中一個(gè)22.距離量算算法的實(shí)現(xiàn):ttdefine MAX 100itypedef struct 印int x;int y;：Pnt;Pnt ar譏MAX;in

9、t num;float Dis;CString str;CString cDis;I void CDi st anc eAddV i ew：OnLBut t onDown(UINT nFIags, CPoint point)/ TODO:在此添加消息處理程序代碼和/或調(diào)用默認(rèn)值CDC *pDC=GetDC();pDC->Rectangle(point, x-2, point, y 2, point, x+2, point, v+2):num十十；aij num_. x-point. x:srrnum'* ypoi nt. v；if(num>l)pDC>MoveTo(a

10、rrCnum. x, arrInum y):pDC->LineTo(arrnum-l» x, arrnum-1+ y);D1 s-Dis+strtf (arr num. x arr tiuhi 1. x) *(arr num. x-arr num- 1 . x) + (arrnum, varrnjm'1 . y)*(arrnum* y-arrnum-1, y);str. FormatD1 s);MessageBox(Etr):CView:OnLButtonDown(nFlags point);空間數(shù)據(jù)的變換算法1. 了解平面坐標(biāo)變換的幾種形式：2. 仿射變換：它是使用最

11、多的一種幾何糾正方式.在保存線條平行條件下,仿 射變換允許對(duì)長(zhǎng)方形目標(biāo)做旋轉(zhuǎn)、平移、傾斜和不均勻縮放.旋轉(zhuǎn)指在原點(diǎn) 旋轉(zhuǎn)x和y軸；平移是指把源點(diǎn)移動(dòng)到新的位置；傾斜是指以一個(gè)傾向?qū)⑿?狀改變?yōu)槠叫兴倪呅危徊痪鶆蚩s放是指在x或y方向同時(shí)或單獨(dú)增大和縮小 比例尺.X = (mi cos :)x -(mx sin :)y AY =(my sin ： )x (my cos : )yBqA1 = mx cos : , A = mi sin := m) sin : , B2 = my cos :X 二 A Ax - AyY 二 Bq B-ix 5y平移變換實(shí)例代碼：Sdefine MaxNum 100ty

12、pedef struct int x;int y;Pnt;Pnt arrPntMaxNum;int numPnt;Ivoid QnoveDlg: :0nLButtonDown(UINT nFlags, CPoint point)/ TODO:在此添加消息處理程序代碼和/或調(diào)用默認(rèn)值CDC 切DOGetDCO; pX->Rectangle (point x-5, point, y-5, point. x+5t point, y+5); numPnt+;arrPntnumPnt. x二point x;arrPnt numPnt. y=point. y；|CDialogEx:OnLBu11on

13、Down(nFlags, point);-void CpatiDlg:OflBnCllckedButtontP0(CDC *pX=CetDC():Invalidate 0;lpdateKlndow();far(int i=l; i<=nuinPnt; i-H-) arrPnt ily -=10;|pDC->Rectangle(arrPnti, x-6, arrPnti. y-6, arrPnt1*x+5jarrPnti. y+5);A TODO:在此添加控件通鈕處理程序代碼比例變換實(shí)現(xiàn)代碼：int xl-150, yl-150, x2-300, y2-250;/比例因子float

14、s;|-void CscalcChangeDLg:OnBnC1ickedBu11onSca1e() / TODO:在此添加控件通知處理稈序代碼CDC 軽DC =GetDC()；Inval idate ();Updateffindow();/更新巳dit值IpdateData (TRUE);xl=xls；yl=yl*s;x2=x2*s;y2=y2S；pDC->MoveTo(xl1 yl);pDC->LineTo(x21 y2):旋轉(zhuǎn)變換實(shí)現(xiàn)代碼：float x=200, y=200, x2二400 y2=200, x3=200, v3=300, x4二400, y4=300; flo

15、at PI=3,1415926;void CspinDlg:OnBriC 1 ickedButtonSpin0/ roix)：在此添加控件通知處理程序代碼CDC *pDC-GetDCO :T nval t dat e ();UpdateWindow 0:UpdateData (TRUE)；x=x*cos(P1/180)*10)-v*sin(Pl 180)*10); y=y*cos(PI/180)*10)+x*sin(PI/180)*10): x2=x2*cos(PI/180)*10)-v2*sin(PI/180)*10); y2=y2*cos (PI/180) *10)+x2*sin(PI/l

16、80*10); x3=x3*cos(1/180)*10) -y3*sin(PI/180)*10): y3=y3*cos (PI/180)*10)+x3*sin(PI/180) *10): x4=x4*cos(PI/180)*10)-y4*sin(PI/180)*10)； y4=y4*cos(PI/180)*10)+x4*s i n(PI/180)*10): pDC->MoveTo (x y);pDC ->UneTo(x2, y2); pDC->LineTo(x4, y4); pDC_>LineTo (x3, y3)； pDC->LineTo(x, y);3.相似變

17、換：圖形的相似變換是指由一個(gè)圖形到另一個(gè)圖形,在改變的過程中保持形狀不變大小方向和位置可變的圖形.圖形相似變換的性質(zhì)：圖形的相似變換不改變圖形中每一個(gè)角的大小；圖形相似變換后對(duì)應(yīng)線段都擴(kuò)大或縮小相同的倍數(shù),這個(gè)數(shù)叫相似比.相似變換面積：經(jīng)相似變換的像與原圖的面積等于相似比的平方.相似變換的分解：任何相似變換可以分解為放縮,平移,旋轉(zhuǎn)和翻轉(zhuǎn)變換的復(fù)合.相似變換是仿射變換的一種特殊情況,也就是在仿射變換中去除錯(cuò)位變換這個(gè)因子后的結(jié)果.X = nx cos二-y sin : AY = mx sin 二心 y cos : B0= mcos := msin :X = A A,x - BiyY = B0

18、B1xA4.矢量轉(zhuǎn)柵格:點(diǎn)：簡(jiǎn)單的坐標(biāo)變換線：線的柵格化|面：線的柵格化+面填充面多邊形的填充方法1、內(nèi)部點(diǎn)擴(kuò)散法種子擴(kuò)散法2、掃描法3、射線法4、5、邊界代數(shù)算法柵格表示法的精度與分辨率有關(guān).在圖a、b、c中,柵格的分辨率分別為7*5,15*11,24*13.分辨率的大小與下面兩個(gè)問題有關(guān)：(b)5. 柵格矢量化：從柵格單元轉(zhuǎn)換為幾何圖形的過程為矢量化；一要求矢量化過程應(yīng)保持：1柵-> 矢轉(zhuǎn)換為拓?fù)滢D(zhuǎn)換,即保持實(shí)體原有的連通性、鄰接性等；2轉(zhuǎn)換實(shí)體保持正確的外形.二方法方法一,實(shí)際應(yīng)用中大多數(shù)采用人工矢量化法,如掃描矢量化,該法工 作量大,成為GIS數(shù)據(jù)輸入、更新的瓶頸問題之一.方法二

19、,程序轉(zhuǎn)化轉(zhuǎn)換全自動(dòng)或半自動(dòng)過程為：1、邊界提取2、二值化3、二值圖像的預(yù)處理4、細(xì)化:1 剝皮法2骨架法5、跟蹤6、 拓?fù)浠?. 矢量點(diǎn)轉(zhuǎn)柵格實(shí)例：ir* MAX 100struct PNT_<i ciL x ;int y：struct PNT jrrMAX;int ent-;string str:intKHkizl* yniirLi you工；vc iri CpntTaDeniDlg : :RerToDMi()JH ttdc:在此添加挫件ifi知力理轄序代訊GDC *pC»CM3etX：():FILE *out;out=foper. (". r',hInv

20、alidate t);UpdateWindowt);UpdMtuOald ftru«);returnRc ():'nl d/* (iTidN-yinin) / (cow ；inb dx" (yjiLax'Kmin) / (ccl -or uqQ=ialse;fprintf (cut f" : - : t "f row,col);fQT<int i« r Krow* ; i +>for ( . nt j= ;；_+>for( nt n；rKnt* ;n*+)tif (arrn. K>txmin4 )*dv)

21、 4 u rr nJ. :< (i<n in+j *d)rr n. y> yr ir + (i-)*dy) £ £ arr InJ r Y<yrnin+i*d/)(juda=true;brak tif ( iudge)pDC->Rec) *dx, ymln+(i- ) *Jy rxmiii+j "dx, yjnin+i*uly; 亡Rect rt xmin+ (j- *dx,ymin+(i- *dyf?onin+j*dx,ymin+idy: pDC->FillSolidRect(4rt,RGB(2 f , ) J;fprintf

22、(outr"-： ",)；j udg=fal9e:elsepDC*>RectangLe txniin+ (j - ) *dx, ymin+ (i- ),xmin+j*(1x71010+1*17);fprintf(out," J "t ):j udg-fAlAe;fprintf tout/' i；'H);void CpntToDemDlg;:returnRec(void) xmax=arrI.xfymax=arrL.y; xmin=arr.x,ymin=arr .y; for (int i=l;i<cnt+l;i+)xmin=a

23、rri.x; yinin=arr i .y; xmax=arri.x; ymax=arri.y;if(xmin>arri*x) if(ymin>arri .y) if(xmax<arri.x) if(ymax<arri.y)斗 pntTQDemRow: |106.矢量數(shù)據(jù)的壓縮：矢量數(shù)據(jù)的壓縮包括兩個(gè)方面的內(nèi)容,一是在不擾亂拓?fù)潢P(guān)系的前提下,對(duì)采樣點(diǎn)數(shù)據(jù)進(jìn)行合理的抽稀.二是對(duì)矢量坐標(biāo)數(shù)據(jù)重新進(jìn) 行編碼,以減少所需要的存儲(chǔ)空間.1間隔取點(diǎn)法：每隔K個(gè)點(diǎn)取一點(diǎn),或舍去那些比規(guī)定距離更近的點(diǎn),首末點(diǎn) 一定要保存.臨界值法2垂距法:4對(duì)點(diǎn)2測(cè)試距離大于規(guī)定的限差3232點(diǎn)2保存

24、對(duì)點(diǎn)3測(cè)試距離小于規(guī)定的限差限差b光欄法的根本思想是上圖：定義一個(gè)扇形區(qū)域,通過判斷曲線上的點(diǎn)在扇形外還是在扇 形內(nèi),確定保存還是舍去.設(shè)曲線上的點(diǎn)列為 pi, i二1, 2,n,光欄口經(jīng)為d,可根據(jù) 壓縮量的大小自己定義,那么光欄法的實(shí)施步驟可描述為：1 °連接pl和p2點(diǎn),過p2點(diǎn)作一條垂直于p1p2的直線,在該垂線上取兩點(diǎn)al和a2,使 a1p2 = a2p2 = d/2,此時(shí)al和a2為“光欄邊界點(diǎn),pl與al、pl與a2的連線為以pl為 頂點(diǎn)的扇形的兩條邊,這就定義了一個(gè)扇形這個(gè)扇形的口朝向曲線的前進(jìn)方向,邊長(zhǎng)是任意 的.通過pl并在扇形內(nèi)的所有直線都具有這種性質(zhì),即p1p

25、2上各點(diǎn)到這些直線的垂距都不大于d/2.2°假設(shè)p3點(diǎn)在扇形內(nèi),那么舍去p2點(diǎn).然后連接pl和p3,過p3作plpl的垂線,該垂線與 前面定義的扇形邊交于cl和c2.在垂線上找到bl和b2點(diǎn),使p3b1 = p3b2 = d/2,假設(shè)bl 或b2點(diǎn)圖4-4-3中為b2點(diǎn)落在原扇形外面,那么用cl或c2取代圖4-4-3中由c2取代b2. 此時(shí)用plbl和p1c2定義一個(gè)新的扇形,這當(dāng)然是口徑b1c2縮小了的“光欄.3°檢查下一節(jié)點(diǎn),假設(shè)該點(diǎn)在新扇形內(nèi),那么重復(fù)第 2步；直到發(fā)現(xiàn)有一個(gè)節(jié)點(diǎn)在最新定義的 扇形外為止.4°當(dāng)發(fā)現(xiàn)在扇形外的節(jié)點(diǎn),如圖4-4-3中的p4,此時(shí)

26、保存p3點(diǎn),以p3作為新起點(diǎn),重復(fù) 1°3°如此繼續(xù)下去,直到整個(gè)點(diǎn)列檢測(cè)完為止.所有被保存的節(jié)點(diǎn) 含首、末點(diǎn),順序地 構(gòu)成了簡(jiǎn)化后的新點(diǎn)列.4道格拉斯一普克法：首先將一條曲線首、末點(diǎn)連一直線,求出各點(diǎn)到該直線的距離,選其最大者與規(guī)定的臨 界值相比擬假設(shè)大于臨界值,那么離該直線距離最大的點(diǎn)保存,否那么,將直線兩端間各點(diǎn)全 部舍去,并將原線條分成兩局部,對(duì)每局部線條再實(shí)施該抽稀過程,直到結(jié)束.抽稀結(jié) 果點(diǎn)數(shù)隨選取限差臨界值的增大而減少,應(yīng)用時(shí)應(yīng)根據(jù)精度要求來確定抽稀限差臨界 值,以獲得最好的結(jié)果.即道格拉斯 一普克Douglas-peuker 算法.P1弦第一輪垂距 第二輪垂

27、距閾值7. 柵格數(shù)據(jù)的壓縮:1鏈?zhǔn)骄幋a:3,1,7,0,1,2?3A5,64,1,6,7,0,12,3,4,5費(fèi)里曼鏈碼Freeman2游程編碼：所謂游程是指按行的順序連續(xù)且屬性值相同的假設(shè)干柵格.一丄TFr游程長(zhǎng)度的記錄方式有兩種 記錄每個(gè)游程起迄列號(hào) 記錄每個(gè)游程像元數(shù)記錄每個(gè)游程像元數(shù)5, 5A,2.B,3A,1,C,3,A,1D,1,C,2,A,2D,2,C,1,A,2D,2,A,3記錄每個(gè)游程像元數(shù)5, 5A, 2,B,3A, hC,3,A,1D, bC,2,2D, 2,C,1,A,2D, 2,A,3記錄每個(gè)游程像元數(shù)5, 52, A3, B3,L2, C2, A3塊式編碼：塊式編碼

28、是將游程擴(kuò)大到兩維情況,把多邊形范圍劃分成假設(shè)干具有同一屬性的正方形,然后對(duì)各個(gè)正方形進(jìn)行編碼.塊式編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置行列號(hào)、半徑和屬性代碼組成.- j -MMMM2MMRM3MRRRMRRRRR5MRRRRMRRRRR6MMRRRMRMMRRTRRImR1 -12M3M4"XK2345678L4,1,2,6,3,5,4,4,5,h 2, M； 1, 3, I, R： 1JL M； 1, 5t 1, M： h 6 M； 1, 7, 2f M3, 2, R； 2, 5, b M； 2J h R1, 1, M： 3, 2, h R： 3, 3, R： 3, 8, 1, Mh U M

29、； 4, 2, 3, R;8f b Mi, i, M； 5, 8, I, M3四叉樹編碼：四叉樹又稱四元樹或四分樹,是最有效的柵格數(shù)據(jù)壓縮編碼方23法之一.四分樹將整個(gè)圖像區(qū)域逐步分解為一系列方形區(qū)域,且每一個(gè)方形區(qū)域具 有單一的屬性.最小區(qū)域?yàn)橐粋€(gè)象元.2 34 5 6 7 84Bp4RMMFmM MMMRRMKM MMr!RRRRR MMRRRRRR MMRRl<RRR MMRRRRRR MMMRRRRR MMMMRRMM M563478四叉樹編碼方法記錄每個(gè)葉子結(jié)點(diǎn)的地址和屬性NW (0)NE (1)20232122SW (2)SE3E-200 201 202 203 230 23

30、1 232 2338隔點(diǎn)取樣法實(shí)例:define Max 100Etypedef struct hint x;int y;Pnt;Pnt arrMax:Pnt arr2Max:int num=0;int num2=0;/定義倆數(shù)組 int n;voi '.I Ccornpre5s2Dlg: : OnBnCl ickedCompress ()|/ IODO:在此添加控件通知處理程序代碼CDC *pDC=GetDC0 , /Inval idateO;/UpdateWindow();VpdateData(TRUE);for (int i=l, i<-jmniT i+ >if (i

31、%n=l)num2+：arr2num2 x-arrIi , x； arr2 Lnum2« y=arril* y;if(num%n!=l)! num2+;arr2Tii】m2. x=arr num+ x;arr2num2. y=arrnuiii. y：for(int j=2；j<=mnn2； j+) CDC 軽DOG航DC 0 : pDC->El 1 ipse(arr2j. x-5(arr2j. rlarr2jL x+5, arr2j-f y+5);pDC->MoveTo (ar：'2【jT arr2 j-J I. y); pDC->LineTo (ar

32、r2 jh 斗 arr2jl. y) ;void Ccompress2D18：:OnLButtonDoffn(lINT nFlags, CPoint point)/ TODO:在此添加消息處理程序代碼和/或調(diào)用默認(rèn)值CDC W=GetDC0;pDC->Rectangle(point.葢-2,point, y-2, point, x+2, point, y+2): num+: arrnum I xpoint. x: aiLtnuun y二 y: if (nutnM)pDC- MoveTo(airnum-1 x, arrnum-l y):pDC>Li neTo (.arr num.l.

33、 x, arr _ruini |. y) ;CDialogEx:OnLButtonDown(nflagst point);空間數(shù)據(jù)內(nèi)插算法1. 空間數(shù)據(jù)內(nèi)插的定義：根據(jù)的空間數(shù)據(jù)估計(jì)預(yù)測(cè)未知空間的數(shù)據(jù)值.2. 空間數(shù)據(jù)內(nèi)插目標(biāo)： 缺值估計(jì)：估計(jì)某一點(diǎn)缺失的觀測(cè)數(shù)據(jù),以提升數(shù)據(jù)密度. 內(nèi)插等值線：以等值線的形式直觀地顯示數(shù)據(jù)的空間分布. 數(shù)據(jù)網(wǎng)格化.把無規(guī)那么分布的空間數(shù)據(jù)內(nèi)插為規(guī)那么分布的空間數(shù)據(jù)集,如規(guī)那么矩形格網(wǎng)、三角網(wǎng)等.3. 空間內(nèi)插法的種類：幾何方法、統(tǒng)計(jì)方法、空間統(tǒng)計(jì)方法、函數(shù)方法、隨機(jī)模擬方法、物理模型模擬方法和綜合方法.4. 優(yōu)缺點(diǎn)比擬：每一種方法均有其適用范圍、算法和優(yōu)缺點(diǎn),

34、因此,沒有絕對(duì)最優(yōu)的空間內(nèi)插方法.5. 如何選擇：對(duì)數(shù)據(jù)進(jìn)行空間探索分析,根據(jù)數(shù)據(jù)的特點(diǎn),選擇最優(yōu)方法；同時(shí),應(yīng)對(duì)內(nèi)插結(jié)果進(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ì).3. 反距離權(quán)重插值算法：是一種局部插值算法,它假設(shè)未知值的點(diǎn)受較近限制點(diǎn) 的影響比擬遠(yuǎn)限制點(diǎn)的影響更大.反距離權(quán)重方法的通用方程是：式中,Z0為點(diǎn)0的估計(jì)值；乙為限制點(diǎn)i的z 值；d為限制點(diǎn)i與點(diǎn)0間的趾離；s為在估算中 用到的限制點(diǎn)的數(shù)目；K為指定的幕.4.雙線性插值算法：是一種數(shù)字圖像處理、DEM據(jù)處理等方面使用較多的局部插值算法原理：如圖8.5所

35、示,設(shè)f0, 0=乙,f 1,0= Z2,f 0,1 = Z3,f 1,1=乙,求 f x,y 點(diǎn)的值, 其中 x,y 0,1.將 f 0,0、f 1,0 > f 0,1、 f 1,1代入雙線性內(nèi)插方程：f x,y = ax + by + cxy + d求出各參數(shù)a、b、c、d的值,再將x, y代入,解 得 f x,y .5反距離權(quán)重插值實(shí)例:Hinclude<math. h>itdefine MAX 100Htypedef struct 早int x? y, z; Pnt;Pnt arrMAX;int num=0;-vol d Cinterpolat ionDlg: lOr

36、iLButtonDownfriM nFJags, CPoint point) / TODO:在此添加消息處理程庫(kù)代碼和/或調(diào)用默認(rèn)值CDC *pDC<etDC()；pDC Llipsetpoint* x31 point, y-3, point兀片3, point, y+3),num+:arrnum* xpoint. x;arrnum,尸point, y:UpdateData (TRUE):| arrtnumLzIDWy： /IDWv就是ID粒,純屬手誤CStnng str:str. Format C%arrnuiii, z);pDC->TextOLitA (arrTnum., x_

37、30, arr.num* y-30* str);CDialogEx' :OnLButtonDowii UiFlags, point):I J void Cinterpolat ionDl g: : OnBnCl i c kedBut t onl DA' (J/ TODO'：在此添加控件通知處理程序代碼double nAtor=0t dAtor=0;double dis=0p Z；CString str:fori int i=1；i<=num;i+)dis=sqrtf (arriT x-X)*(arriL x-X + (arr iL y-Y)*(arrri, y-Y

38、): str. Formatdis):nAtor +=(arr i* z/dis):dAtor +=(L. 0/dls);2-nAtor/dAtor；str. Format (*11 f*, Z)；CDC 也DOGtDCO:pDC->T ext Out A (Xj Y, str):TIN、DEM DAT1. 數(shù)字高程模型概念與理解：高程常常用來描述地形外表的起伏形態(tài), 傳統(tǒng)的高 程模型是等高線,其數(shù)學(xué)意義是定義在二維地理空間上的連續(xù)曲面函數(shù), 當(dāng)此高 程模型用計(jì)算機(jī)來表達(dá)時(shí),稱為數(shù)字高程模型.2. 數(shù)字高程模型：是通過有限的地形高程數(shù)據(jù)實(shí)現(xiàn)對(duì)地形曲面的數(shù)字化模擬或者 說是地形外表形態(tài)的數(shù)

39、字化表示, 英文為Digital Elevation Model,簡(jiǎn)稱DEM3. 理解 DEM和DTM由于高程數(shù)據(jù)常常采用絕對(duì)高程或海拔即從大地水準(zhǔn)面起算的高 度,DEM也常常稱為DTM要說明的是由于“ Terrain 一詞的含義比擬廣泛,不同專業(yè)背 景對(duì)“ Terrain 的理解也不一樣, DTM趨向于表達(dá)比 DEM更為廣泛的內(nèi)容,詳見后文的分 析表2數(shù)字地面模型有關(guān)術(shù)語術(shù)IS全稱特點(diǎn)與含義DEMDigital ElevationModel以絕對(duì)高程或梅拔衣示的地形模塑DlfMDigital Height Model以仃適爲(wèi)程走示的地形模型,包期絕對(duì)疝 程和相對(duì)高畀“為徳國(guó)所使川DGUDig

40、ital Ground Model具冇連續(xù)變化特征的地衣實(shí)體模型.為英 國(guó)所使用Digital Geomorphology Model除話程外的耳他地貌形態(tài)模型.如坡度r 坡向等DTMDigital Terrain Model泛指地形外表人文、社會(huì)最觀模劃,DTEDDigital Terrain Elevation Model為美H國(guó)防制圖局所使川的地形模塑,強(qiáng) 調(diào)模型的格網(wǎng)結(jié)構(gòu)特征4. TIN和規(guī)那么DEM的區(qū)別：不規(guī)那么三角網(wǎng)數(shù)字高程模型由連續(xù)的三角面組成,三角形的 形狀、大小取決于不規(guī)那么分布的點(diǎn)的位置和密度.地形變化越簡(jiǎn)單,采樣點(diǎn)就越少,那么單元格就越大；反之地形變化比擬復(fù)雜,數(shù)據(jù)點(diǎn)分

41、布比擬密集,格網(wǎng)單元就越小.因此TIN與規(guī)那么格網(wǎng)DEM顯著不同之處在于 TIN模型不需要維護(hù)模型的結(jié)構(gòu)規(guī)那么性, 不但能 靈活地隨地形的復(fù)雜程度而改變格網(wǎng)單元大小,防止平坦地形的數(shù)據(jù)冗余,而且又能按地形特征點(diǎn)線如山脊點(diǎn)、山谷線、地形變化線等表示地形特征.規(guī)那么格網(wǎng)DEM不規(guī)那么三角網(wǎng)TIN孔點(diǎn):優(yōu)點(diǎn)簡(jiǎn)單的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：較少的點(diǎn)可獲取較高的與遙感影像數(shù)據(jù)的復(fù)合精度：性：可辨分辨率：良好的外表分析功能良好的拓?fù)浣Y(jié)構(gòu)缺點(diǎn)缺點(diǎn)計(jì)算效率較低；外表分析水平較差；數(shù)據(jù)兀余豪構(gòu)建比擬費(fèi)時(shí)*格網(wǎng)結(jié)構(gòu)規(guī)那么算法設(shè)計(jì)比擬復(fù)雜5.DEM數(shù)據(jù)結(jié)構(gòu)：規(guī)那么格網(wǎng)不規(guī)那么三角形DEM數(shù)據(jù)結(jié)構(gòu)6. 規(guī)那么格網(wǎng)數(shù)據(jù)：由于DEM

42、勺邊界范圍一般是規(guī)那么矩形,而實(shí)際地形范圍卻是不 規(guī)那么的,還應(yīng)考慮不在研究區(qū)域內(nèi)的 DEM高程值的表示方法無效區(qū)域數(shù)據(jù), 一般是給出一個(gè)特殊的常數(shù)值,如-9999等.規(guī)那么格網(wǎng)DEM勺數(shù)據(jù)文件一般包含 用對(duì)DEM數(shù)據(jù)進(jìn)行說明的數(shù)據(jù)頭和DEM數(shù)據(jù)體兩局部.1數(shù)據(jù)頭：一般包括定義DEMS南角起點(diǎn)坐標(biāo)、坐標(biāo)類型、格網(wǎng)間距、行列數(shù)、 最低高程以及高程放大系數(shù)等內(nèi)容；2數(shù)據(jù)體：按行或列分布記錄的高程數(shù)字陣列.mi«StL5a25西砒朋單馴端型12UJ.9頭西南脫枷刑t赭MLQ11呻沖?R ILBft時(shí)的啲D踰帙榕7. TIN :在TIN模型中,根本的結(jié)構(gòu)元素有三角形頂點(diǎn)、邊和面.它們之間存在

43、 著點(diǎn)與線、點(diǎn)與面、線與面、面與面等拓?fù)潢P(guān)系.理論上,通過組成三角形的三 頂點(diǎn)可完整地表達(dá)三角形的構(gòu)成以及三角形頂點(diǎn)、三角形邊、三角形之間的拓?fù)?關(guān)系下列圖,這種結(jié)構(gòu)只需要兩個(gè)文件,即三角形頂點(diǎn)坐標(biāo)文件和組成三角形三 頂點(diǎn)通常用點(diǎn)在坐標(biāo)文件中的序號(hào)表示文件.這種結(jié)構(gòu)雖然簡(jiǎn)單,三角形結(jié) 構(gòu)元素的拓?fù)潢P(guān)系卻是隱含的,不利于TIN模型的檢索與應(yīng)用.因此,圍繞三角 形的拓?fù)潢P(guān)系描述而產(chǎn)生了多種 TIN的數(shù)據(jù)結(jié)構(gòu).序性XY£12345d圖的基蘋璉突結(jié)彼8. TIN模型的面結(jié)構(gòu)最大特點(diǎn)是：由于存儲(chǔ)了三角形之間的鄰接關(guān)系,TIN內(nèi)插、檢 索、等高線提取、顯示以及局部結(jié)構(gòu)分析都比擬方便,缺乏之處是：

44、存儲(chǔ)量較大, 而且在TIN的編輯中要隨時(shí)維護(hù)這種關(guān)系.9. DEM數(shù)據(jù)獲?。航EM勺第一步是獲取地形數(shù)據(jù).DEM勺數(shù)據(jù)源和數(shù)據(jù)獲取 方式對(duì)于DEM的最終質(zhì)量至關(guān)重要.DEM原始數(shù)據(jù)主要是高程和平面位置數(shù)據(jù),在可能條件下還應(yīng)包括各種地形結(jié)構(gòu)線如山脊線、山谷線、斷裂線等.另外,DEM 應(yīng)用目的、數(shù)據(jù)采集效率和本錢、技術(shù)熟練程度也影響著DE贓據(jù)采集的方法和 策略./*目前DEM勺數(shù)據(jù)主要來源于地形圖、攝影測(cè)量與遙感影像數(shù)據(jù)、地面測(cè)量、既 有DEM數(shù)據(jù)等.*/10. 坡度：(1) 坡度是地表形態(tài)最為重要的因子,通過坡度可以完整地形成地形曲面(Evans,1972 ; Strahler,1956 )

45、;(2) 坡度是地形曲面函數(shù)一階微分的函數(shù),表達(dá)了高程隨距離變化的比率(坡度定義為地面一點(diǎn)的切平面與水平面之間的夾角),而坡度的變率是地形曲 面的二階微分,進(jìn)一步刻畫了坡度的變化,從而反映地形的復(fù)雜程度；(3) 大量的研究說明,區(qū)域 DEM高程精度與平均坡度值之間存在強(qiáng)相關(guān),通過 模型的平均坡度可預(yù)測(cè) DEM勺精度(Ackermann,1979; Ley, 1986 );(4) 坡度通過相互垂直的兩個(gè)坐標(biāo)軸方向的高程變化表達(dá)地形曲面局部單元的 傾斜程度,也就是通過地形外表的凸面和凹面來描述地形外表特性,即地表 的陡峭方向和大小.11. TIN數(shù)據(jù)的建立：基于不規(guī)那么三角網(wǎng)的數(shù)字高程模型 (Ba

46、sedon TriangulatedIrregular Network DEM ,簡(jiǎn)寫為 Based on TIN DEM,俗稱 TIN)就是用一 系列互不交叉、互不重疊的連接在一起的三角形來表示地形外表.TIN是DEM 的又一個(gè)主要數(shù)據(jù)模型,TIN的特點(diǎn)在其字面意思中表露無遺.11. TIN的三角剖分準(zhǔn)那么：TIN的三角剖分準(zhǔn)那么是指 TIN中三角形的形成法那么,它 決定著三角形的幾何形狀和 TIN的質(zhì)量.目前在GIS、計(jì)算幾何和計(jì)算機(jī)圖形學(xué)鄰域常 用的三角剖分準(zhǔn)那么有以下幾種(1) 空外接圓準(zhǔn)那么：在TIN中,過每個(gè)三角形的外接圓均不包含點(diǎn)集的其余任 何點(diǎn),如圖A所示；(2) 最大最小角準(zhǔn)

47、那么：在兩相鄰三角形形成的凸四邊形中,這兩三角形中的最小內(nèi)角一定大于交換凸四邊形對(duì)角線后所形成的兩三角形的最小內(nèi)角,如圖B所示；(3)最短距離和準(zhǔn)那么：圖C,最短距離和就是指一點(diǎn)到基邊兩端的距離和為最小;(4) 張角最大準(zhǔn)那么：圖D, 點(diǎn)到基邊的張角為最大；(5) 面積比準(zhǔn)那么：圖E,三角形內(nèi)切圓面積與三角形面積或三角形面積與周長(zhǎng) 平方之比最??；(6) 對(duì)角線準(zhǔn)那么：圖F,兩三角形組成的凸四邊形的兩條對(duì)角線之比.超過給 定限定值時(shí)對(duì)三角形進(jìn)行優(yōu)化.(A)空外接圜準(zhǔn)那么(D)張角最大準(zhǔn)那么(E)面積比準(zhǔn)那么(F)時(shí)角線準(zhǔn)那么XIX(B)最大最小市淮那么(C)最短距離 WRJ理論上可以證實(shí)：張角最

48、大準(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)那么可以做到.對(duì)角線準(zhǔn)那么含有主觀 因素,現(xiàn)今使用已不多.通常將在空外接圓準(zhǔn)那么、最大最小角準(zhǔn)那么下進(jìn)行三角剖分稱為 Delaunay三角剖分,簡(jiǎn)稱為DT,同時(shí)空外接圓和最大最小角也是 Delaunay三角 網(wǎng)的兩個(gè)根本性質(zhì).DT三角剖分是目前應(yīng)用最為廣泛的三角剖分

49、方法,其特性 是可最大限度防止狹長(zhǎng)三角形的出現(xiàn)以及不管從何處開始構(gòu)網(wǎng)都能保持三角形 網(wǎng)絡(luò)的唯一性,這一點(diǎn)在實(shí)際應(yīng)用中相當(dāng)重要.實(shí)際上,在任何三角剖分準(zhǔn)那么下 得到的TIN,只要用LOP法那么(局部?jī)?yōu)化過程,local optimal procedure , LOP 對(duì)其進(jìn)行優(yōu)化處理,就能得到唯一的DT三角網(wǎng)絡(luò).LOP法那么是Lawson在1977年提出的,其根本思想是運(yùn)用 DT三角網(wǎng)的空外接圓性質(zhì)對(duì)由兩個(gè)有公共邊的三 角形組成的四邊形進(jìn)行判斷.如果其中一個(gè)三角形的外接圓中含有第四個(gè)頂點(diǎn), 那么交換四邊形的對(duì)角線.12.無約束散點(diǎn)域的三角剖分算法與實(shí)現(xiàn)：*分割合并算法*三角法生長(zhǎng)算法*逐點(diǎn)插入算

50、法1分害U合并算法： 分害U合并算法 divide and conquer delaunay triangulation algorithm 的思想最早是由 Shamos和Hoey在1975年提出的,并將其應(yīng)用于 V-圖的構(gòu)成V-圖是Vorinoi圖的簡(jiǎn)稱,是DT三角網(wǎng)的對(duì)偶圖,為DT三角網(wǎng)中 相鄰三角形邊垂直平分線交點(diǎn)的連線所形成的多邊形,有關(guān)V-圖的定義、性質(zhì)和分割算法參見計(jì)算幾何方面的書籍.Lewis和Rob in son于1978年將該方法用來進(jìn)行DT三角網(wǎng)的剖分,隨后 Lee和Schachter、Dwyer等相繼對(duì)Lewis和 Robinson的算法進(jìn)行了優(yōu)化和改良, 其中Lee和S

51、chachter于1980年的算法適 合于無約束數(shù)據(jù)域的三角剖分,而 Dwyer于1987年的算法那么考慮了帶約束條件 的LOP優(yōu)化策略,因而能處理帶約束條件的數(shù)據(jù).分割合并算法的思想很簡(jiǎn)單,就是將復(fù)雜問題簡(jiǎn)單化,首先將數(shù)據(jù)點(diǎn)分割成 易于進(jìn)行三角剖分的子集,如一個(gè)子集中包括三個(gè)、四個(gè)點(diǎn),然后對(duì)每個(gè)子集進(jìn) 行三角剖分,并用LOP算法保證三角剖分為DT三角網(wǎng).當(dāng)每個(gè)子集剖分完成后, 對(duì)每個(gè)子集的三角剖分進(jìn)行合并,形成最終的整體三角網(wǎng).不同的實(shí)現(xiàn)方法可有 不同的點(diǎn)集劃分方法、子三角網(wǎng)生成方法及合并方法等.分割合并算法的根本步驟為：對(duì)每一個(gè)子集進(jìn)行三 角剖分.并用LOP算 法進(jìn)行優(yōu)化尋找了集凸殼的底線

52、 和頂線粗實(shí)線,并從底線開始自下而 上進(jìn)行合并遞歸的對(duì)原始數(shù)據(jù)進(jìn) 行分割.將原始數(shù)據(jù) 域分成大致相等的左 右兩個(gè)局部利用凸殼算法上成每 子塊的邊界合并三角網(wǎng)*形成最 終的三角形網(wǎng)絡(luò)第一步,把數(shù)據(jù)集以橫坐標(biāo)為主、縱坐標(biāo)為輔按升序進(jìn)行排序;第二步,如果數(shù)據(jù)集中的數(shù)據(jù)個(gè)數(shù)大于給定的閾值, 那么把數(shù)據(jù)域劃分為個(gè)數(shù)近似 相等的左右兩個(gè)子集,并對(duì)每一子集做如下的工作,計(jì)算每一子集的凸殼； 以凸殼為數(shù)據(jù)邊界,對(duì)每一數(shù)據(jù)子集進(jìn)行三角剖分,并用LOP進(jìn)行優(yōu)化,使之成 為DT三角剖分；找出連接左右子集兩個(gè)凸殼的底線和頂線；由底線到頂線, 合并兩個(gè)子三角網(wǎng)；第三步：如果數(shù)據(jù)集中的數(shù)據(jù)個(gè)數(shù)小于給定的閾值,那么直接輸出三角剖分結(jié)果;設(shè)左右凸殼分別為Z和瓦/和B分 別是Z和R上的點(diǎn),A.喪滿足如下 條件：A JVAk=max XLB: Y=ra.inXR底線査找；從48有向線段開始, 對(duì)于人中點(diǎn)#如果沿逆時(shí)針且與B 相鄰的V點(diǎn)位于曲的右側(cè),那么B=Y； 在新的力君方向上,如果順吋