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

1、GIS算法原理知識(shí)點(diǎn)總結(jié)算法設(shè)計(jì)和分析：1、算法設(shè)計(jì)的原則：正確性：若一個(gè)算法本身有缺陷，那么它將不會(huì)解決問(wèn)題；確定性：指每個(gè)步驟必須含義明確，對(duì)每種可能性都有確定的操作。清晰性：一個(gè)良好的算法，必須思路清晰，結(jié)構(gòu)合理。2、算法的復(fù)雜性包括：時(shí)間復(fù)雜性和空間復(fù)雜性。3、時(shí)間復(fù)雜性：用一個(gè)與問(wèn)題相關(guān)的整數(shù)量來(lái)衡量問(wèn)題的大小，該整數(shù)量表示輸入數(shù)據(jù)量的尺度，稱(chēng)為問(wèn)題的規(guī)模。利用某算法處理一個(gè)問(wèn)題規(guī)模為n的輸入所需要的時(shí)間，稱(chēng)為該算法的時(shí)間復(fù)雜性。4、算法的概念：算法是完成特定任務(wù)的有限指令集。所有的算法必須滿(mǎn)足下面的標(biāo)準(zhǔn)：u 輸入u 輸出u 明確性u(píng) 有限性u(píng) 有效性GIS算法的計(jì)算幾何基礎(chǔ)O1、理

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

3、順時(shí)針?lè)较?；P X Q<0,則P在Q的順逆針?lè)较颍籔 X Q>0,則P Q共線(xiàn)，但可能同向也可能反向。6、判斷線(xiàn)段的拐向：折線(xiàn)段的拐向判斷方法，可以直接由矢量叉積的性質(zhì)推出，對(duì)于有公共端點(diǎn)的線(xiàn)段p0p1和P1P2，通過(guò)計(jì)算（p2-p0）×(P1-p0)的符號(hào)便可以給出折線(xiàn)段的拐向。p2p2p2p1p1p1p0p0p0基（p2-p0）×(P1-p0)>0，則P0P1在P1點(diǎn)拐向右側(cè)后得到P1P2基（p2-p0）×(P1-p0)=0，則P0P1P2三點(diǎn)共線(xiàn)基（p2-p0）×(P1-p0)<0，則P0P1在P1點(diǎn)拐向左側(cè)后得到P1P2理

4、解矢量的概念通過(guò)矢量差積的方法就可以判斷的拐向了。7.判斷點(diǎn)是否在線(xiàn)段上：設(shè)點(diǎn)為Q，線(xiàn)段為P1 P2：(Q-P1)X(P2-P1)=0且Q在以P1，P2為對(duì)角頂點(diǎn)的矩形內(nèi)。前者抱走點(diǎn)在直線(xiàn)上，后者保證點(diǎn)不在線(xiàn)段延長(zhǎng)線(xiàn)或反向延長(zhǎng)線(xiàn)上。8、判斷兩線(xiàn)段是否相交（算法一）：快速排斥實(shí)驗(yàn)：設(shè)以線(xiàn)段P1P2為對(duì)角線(xiàn)的矩形為R，設(shè)以線(xiàn)段Q1Q2為對(duì)角的矩形為T(mén)，如果R和T不相交，顯然兩線(xiàn)段不會(huì)相交跨立實(shí)驗(yàn)： 如果兩線(xiàn)段相交，則兩線(xiàn)段必然相互跨立對(duì)方。若p1p2跨立Q1Q2，則矢量（P1-Q1）和（P2-Q2）位于矢量（Q2-Q1）的兩側(cè)，則（P1-Q1）×（Q2-Q1） ×（P2-Q1）

5、 × （Q2-Q1）0。當(dāng)（P1-Q1）×（Q2-Q1）=0時(shí)，說(shuō)明 （P1-Q1）×（Q2-Q1）共線(xiàn)，但是因?yàn)橐呀?jīng)通過(guò)快速排斥實(shí)驗(yàn)，所以P1一定在線(xiàn)段Q1Q2上；同理 （Q2-Q1） × （P2-Q1） =0說(shuō)明P2一定在線(xiàn)段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ìn)行“跨立判斷”的時(shí)候是進(jìn)行兩次跨

6、立判斷9.判斷矩形內(nèi)是否包含點(diǎn)：只要判斷該店的橫坐標(biāo)和縱坐標(biāo)是否都夾在矩形的左右邊和上下邊之間。10.判斷線(xiàn)段、折線(xiàn)、多邊形是否在矩形中：因?yàn)榫匦问莻€(gè)凸集，所以只要判斷所有端點(diǎn)都在矩形就行了。11.判斷矩形是否在矩形中：只要比較左右邊界和上下邊界就行了。12.判斷圓是否在矩形中：圓心在矩形中且圓的半徑小于或等于圓心到矩形四邊的距離的最小值。13.判斷點(diǎn)是否在多邊形內(nèi)： 1)射線(xiàn)法：一條射線(xiàn)從點(diǎn)P開(kāi)始，穿過(guò)多邊形的邊界的次數(shù)稱(chēng)為交點(diǎn)數(shù)目。當(dāng)交點(diǎn)數(shù)目是偶數(shù)時(shí)，點(diǎn)P在多邊形外部；否則，為奇數(shù)時(shí)，在多邊形內(nèi)部。射線(xiàn)法要考慮幾種特殊的情況，并且射線(xiàn)法適用于凸多邊形2)轉(zhuǎn)角法：多邊形環(huán)繞點(diǎn)P的次數(shù)稱(chēng)為環(huán)繞

7、數(shù)，環(huán)繞數(shù)為0時(shí)，點(diǎn)P在多邊形外部，否則在多邊形內(nèi)部。14.判斷線(xiàn)段是否在多邊形內(nèi)：（折線(xiàn)是判斷它的每條線(xiàn)段）條件一：線(xiàn)段的兩個(gè)端點(diǎn)都在多邊形內(nèi)條件二：線(xiàn)段和多邊形的所有邊都不內(nèi)交。15.判斷多邊形否在多邊形內(nèi)：只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可。判斷有m個(gè)頂點(diǎn)的多邊形是否在一個(gè)有n個(gè)頂點(diǎn)的多邊形內(nèi)的復(fù)雜度為O(mXn)16.判斷矩形是否在多邊形內(nèi)：將矩形轉(zhuǎn)化為多邊形，然后再判斷是否在多邊形內(nèi)。17.判斷圓是否在多邊形內(nèi)：計(jì)算圓心到多邊形每條變邊的最短距離，若該距離大于或等于圓半徑，則該圓在多邊形內(nèi)。18.判斷點(diǎn)是否在圓內(nèi)：計(jì)算圓心到該點(diǎn)的距離，若小于或等于半徑，則該點(diǎn)在圓內(nèi)。19.判

8、斷線(xiàn)段、折線(xiàn)、矩形、多邊形是否在圓內(nèi)：因?yàn)閳A是凸集，所以只要判斷是否每個(gè)頂點(diǎn)都在圓內(nèi)即可。20.判斷圓是否在圓內(nèi)：設(shè)兩圓為O1,O2,半徑為r1,r2。先比較r1,r2的大小，若r1<r2,則O2不可能在O1內(nèi)；若兩圓心距離大魚(yú)r1-r2，則O2不在O1內(nèi)；反之，O2在O1內(nèi)。21.距離交會(huì): 是以?xún)蓚€(gè)已知控制點(diǎn)為中心，分別以目標(biāo)點(diǎn)與兩已知控制點(diǎn)的距離為半徑劃圓，交會(huì)點(diǎn)即為要求目標(biāo)點(diǎn)（注意方向二選其中一個(gè)）。22.距離量算算法的實(shí)現(xiàn)：空間數(shù)據(jù)的變換算法1.了解平面坐標(biāo)變換的幾種形式:2.仿射變換：它是使用最多的一種幾何糾正方式。在保留線(xiàn)條平行條件下，仿射變換允許對(duì)長(zhǎng)方形目標(biāo)做旋轉(zhuǎn)、平移、

9、傾斜和不均勻縮放。旋轉(zhuǎn)指在原點(diǎn)旋轉(zhuǎn)x和y軸；平移是指把源點(diǎn)移動(dòng)到新的位置；傾斜是指以一個(gè)傾向?qū)⑿螤罡淖優(yōu)槠叫兴倪呅?；不均勻縮放是指在x或y方向同時(shí)或單獨(dú)增大和縮小比例尺。平移變換實(shí)例代碼：比例變換實(shí)現(xiàn)代碼：旋轉(zhuǎn)變換實(shí)現(xiàn)代碼：3.相似變換：圖形的相似變換是指由一個(gè)圖形到另一個(gè)圖形，在改變的過(guò)程中保持形狀不變（大小方向和位置可變）的圖形。圖形相似變換的性質(zhì)：圖形的相似變換不改變圖形中每一個(gè)角的大?。粓D形相似變換后對(duì)應(yīng)線(xiàn)段都擴(kuò)大（或縮?。┫嗤谋稊?shù)，這個(gè)數(shù)叫相似比。相似變換面積：經(jīng)相似變換的像與原圖的面積等于相似比的平方。相似變換的分解：任何相似變換可以分解為放縮，平移，旋轉(zhuǎn)和翻轉(zhuǎn)變換的復(fù)合。相似變

10、換是仿射變換的一種特殊情況，也就是在仿射變換中去除錯(cuò)位變換這個(gè)因子后的結(jié)果。4.矢量轉(zhuǎn)柵格：點(diǎn)：簡(jiǎn)單的坐標(biāo)變換 線(xiàn)：線(xiàn)的柵格化 面：線(xiàn)的柵格化 +面填充 面(多邊形)的填充方法 1、內(nèi)部點(diǎn)擴(kuò)散法（種子擴(kuò)散法）2、掃描法3、射線(xiàn)法4、復(fù)數(shù)積分法 5、邊界代數(shù)算法 柵格表示法的精度與分辨率有關(guān)。在圖(a)、(b)、(c)中，柵格的分辨率分別為7*5，15*11，24*13。分辨率的大小與下面兩個(gè)問(wèn)題有關(guān)： 5.柵格矢量化：從柵格單元轉(zhuǎn)換為幾何圖形的過(guò)程為矢量化；（一）要求（矢量化過(guò)程應(yīng)保持）：1）  柵->矢轉(zhuǎn)換為拓?fù)滢D(zhuǎn)換，即保持實(shí)體原有的連通性、鄰接性等；2）  轉(zhuǎn)換實(shí)

11、體保持正確的外形。（二）方法方法一，實(shí)際應(yīng)用中大多數(shù)采用人工矢量化法，如掃描矢量化，該法工作量大，成為GIS數(shù)據(jù)輸入、更新的瓶頸問(wèn)題之一。方法二，程序轉(zhuǎn)化轉(zhuǎn)換（全自動(dòng)或半自動(dòng)）過(guò)程為：1、邊界提取2、二值化 3、二值圖像的預(yù)處理4、細(xì)化:1）剝皮法 2)骨架法5、跟蹤 6、拓?fù)浠?6.”矢量點(diǎn)”轉(zhuǎn)柵格實(shí)例：6.矢量數(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)一定要保留。臨界值 隔點(diǎn)法臨界值法2）垂距法：原始曲線(xiàn)

12、對(duì)點(diǎn)2測(cè)試距離大于規(guī)定的限差點(diǎn)2保留對(duì)點(diǎn)3測(cè)試距離小于規(guī)定的限差234234234234141113點(diǎn)舍去，化簡(jiǎn)結(jié)果14限差23）光柵法：d/2c1c2b2b1p1P4P3P2a1a2d/2Pn光欄法的基本思想是(上圖)：定義一個(gè)扇形區(qū)域，通過(guò)判斷曲線(xiàn)上的點(diǎn)在扇形外還是在扇形內(nèi)，確定保留還是舍去。設(shè)曲線(xiàn)上的點(diǎn)列為pi，i1，2，n，光欄口經(jīng)為d，可根據(jù)壓縮量的大小自己定義，則光欄法的實(shí)施步驟可描述為：1°、連接p1和p2點(diǎn)，過(guò)p2點(diǎn)作一條垂直于p1p2的直線(xiàn)，在該垂線(xiàn)上取兩點(diǎn)a1和a2，使a1p2a2p2d2，此時(shí)a1和a2為“光欄”邊界點(diǎn)，p1與a1、p1與a2的連線(xiàn)為以p1為頂點(diǎn)

13、的扇形的兩條邊，這就定義了一個(gè)扇形(這個(gè)扇形的口朝向曲線(xiàn)的前進(jìn)方向，邊長(zhǎng)是任意的)。通過(guò)p1并在扇形內(nèi)的所有直線(xiàn)都具有這種性質(zhì)，即p1p2上各點(diǎn)到這些直線(xiàn)的垂距都不大于d/2。    2°、若p3點(diǎn)在扇形內(nèi)，則舍去p2點(diǎn)。然后連接p1和p3，過(guò)p3作p1p1的垂線(xiàn)，該垂線(xiàn)與前面定義的扇形邊交于c1和c2。在垂線(xiàn)上找到b1和b2點(diǎn)，使p3b1p3b2d2，若b1或b2點(diǎn)(圖4-4-3中為b2點(diǎn))落在原扇形外面，則用c1或c2取代(圖4-4-3中由c2取代b2)。此時(shí)用p1b1和p1c2定義一個(gè)新的扇形，這當(dāng)然是口徑(b1c2)縮小了的“光欄”。&

14、#160;3°、檢查下一節(jié)點(diǎn)，若該點(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í)保留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)列。首先將一條曲線(xiàn)首、末點(diǎn)連一直線(xiàn)，求出各點(diǎn)到該直線(xiàn)的距離，選其最大者與規(guī)定的臨界值相比較若大于臨界值，則離該直線(xiàn)距離最大的點(diǎn)保留，否則，將直線(xiàn)兩端間各點(diǎn)全部舍去，并將原線(xiàn)條分成兩部分，對(duì)每部分線(xiàn)條再實(shí)施該抽稀過(guò)程，直到結(jié)束。抽稀結(jié)果點(diǎn)數(shù)隨選取限

15、差臨界值的增大而減少，應(yīng)用時(shí)應(yīng)根據(jù)精度要求來(lái)確定抽稀限差臨界值，以獲得最好的結(jié)果。即道格拉斯普克（Douglas-peuker）算法。4）道格拉斯普克法：P1PN splitpointP1PN Result 第一輪垂距第二輪垂距弦閾值7柵格數(shù)據(jù)的壓縮：1）鏈?zhǔn)骄幋a：2）游程編碼：所謂游程是指按行的順序連續(xù)且屬性值相同的若干柵格。 游程長(zhǎng)度的記錄方式有兩種 記錄每個(gè)游程起（迄）列號(hào) 記錄每個(gè)游程像元數(shù)3）塊式編碼：塊式編碼是將游程擴(kuò)大到兩維情況，把多邊形范圍劃分成若干具有同一屬性的正方形，然后對(duì)各個(gè)正方形進(jìn)行編碼。塊式編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置（行列號(hào)）、半徑和屬性代碼組成。3）四叉樹(shù)編碼：四叉樹(shù)

16、又稱(chēng)四元樹(shù)或四分樹(shù)，是最有效的柵格數(shù)據(jù)壓縮編碼方法之一。 四分樹(shù)將整個(gè)圖像區(qū)域逐步分解為一系列方形區(qū)域，且每一個(gè)方形區(qū)域具有單一的屬性。最小區(qū)域?yàn)橐粋€(gè)象元。8.隔點(diǎn)取樣法實(shí)例：空間數(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)插等值線(xiàn)：以等值線(xiàn)的形式直觀地顯示數(shù)據(jù)的空間分布。數(shù)據(jù)網(wǎng)格化。把無(wú)規(guī)則分布的空間數(shù)據(jù)內(nèi)插為規(guī)則分布的空間數(shù)據(jù)集，如規(guī)則矩形格網(wǎng)、三角網(wǎng)等。3.空間內(nèi)插法的種類(lèi)：幾何方法、統(tǒng)計(jì)方法、空間統(tǒng)計(jì)方法、函數(shù)方法、隨機(jī)模擬方法、物理模型模擬方法和綜合方法。 4.優(yōu)缺點(diǎn)

17、比較：每一種方法均有其適用范圍、算法和優(yōu)缺點(diǎn)，因此，沒(méi)有絕對(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)插的分類(lèi)依據(jù)：確定或隨機(jī)；點(diǎn)與面；全局或局部等標(biāo)準(zhǔn)分類(lèi)；內(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ì)值；zi為控制點(diǎn)i的z值；dj為控制點(diǎn)i與點(diǎn)0間的趾離；s為在估算中用到的控制點(diǎn)的數(shù)目；K為指定的冪。4.雙線(xiàn)性插值算法：是一種數(shù)字圖像處理、DEM數(shù)據(jù)處理等方面使用較

18、多的局部插值算法。原理：如圖8.5所示，設(shè)f(0，0) = Z1，f (1，0)= Z2，f (0，1) = Z3，f (1，1) = Z4，求f (x,y)點(diǎn)的值，其中x,y 0，1。將f (0，0)、f (1，0)、f (0，1)、f (1，1)代入雙線(xiàn)性?xún)?nèi)插方程：f(x,y) = ax + by + cxy + d求出各參數(shù)a、b、c、d的值，再將x, y代入，解得f(x,y)。5反距離權(quán)重插值實(shí)例：TIN、DEM、DAT1.數(shù)字高程模型概念與理解：高程常常用來(lái)描述地形表面的起伏形態(tài)，傳統(tǒng)的高程模型是等高線(xiàn)，其數(shù)學(xué)意義是定義在二維地理空間上的連續(xù)曲面函數(shù)，當(dāng)此高程模型用計(jì)算機(jī)來(lái)表達(dá)時(shí)，稱(chēng)

19、為數(shù)字高程模型。2.數(shù)字高程模型：是通過(guò)有限的地形高程數(shù)據(jù)實(shí)現(xiàn)對(duì)地形曲面的數(shù)字化模擬或者說(shuō)是地形表面形態(tài)的數(shù)字化表示，英文為Digital Elevation Model，簡(jiǎn)稱(chēng)DEM。3.理解DEM和DTM：由于高程數(shù)據(jù)常常采用絕對(duì)高程或海拔（即從大地水準(zhǔn)面起算的高度），DEM也常常稱(chēng)為DTM。要說(shuō)明的是由于“Terrain”一詞的含義比較廣泛，不同專(zhuān)業(yè)背景對(duì)“Terrain”的理解也不一樣，DTM趨向于表達(dá)比DEM更為廣泛的內(nèi)容，詳見(jiàn)后文的分析。4. TIN和規(guī)則DEM的區(qū)別：不規(guī)則三角網(wǎng)數(shù)字高程模型由連續(xù)的三角面組成，三角形的形狀、大小取決于不規(guī)則分布的點(diǎn)的位置和密度。地形變化越簡(jiǎn)單，采樣

20、點(diǎn)就越少，則單元格就越大；反之地形變化比較復(fù)雜，數(shù)據(jù)點(diǎn)分布比較密集，格網(wǎng)單元就越小。因此TIN與規(guī)則格網(wǎng)DEM顯著不同之處在于TIN模型不需要維護(hù)模型的結(jié)構(gòu)規(guī)則性，不但能靈活地隨地形的復(fù)雜程度而改變格網(wǎng)單元大小，避免平坦地形的數(shù)據(jù)冗余，而且又能按地形特征點(diǎn)線(xiàn)如山脊點(diǎn)、山谷線(xiàn)、地形變化線(xiàn)等表示地形特征。5.DEM數(shù)據(jù)結(jié)構(gòu)：規(guī)則格網(wǎng)DEM數(shù)據(jù)結(jié)構(gòu)不規(guī)則三角形DEM數(shù)據(jù)結(jié)構(gòu)6.規(guī)則格網(wǎng)數(shù)據(jù)：由于DEM的邊界范圍一般是規(guī)則矩形，而實(shí)際地形范圍卻是不規(guī)則的，還應(yīng)考慮不在研究區(qū)域內(nèi)的DEM高程值的表示方法（無(wú)效區(qū)域數(shù)據(jù)），一般是給出一個(gè)特殊的常數(shù)值，如-9999等。規(guī)則格網(wǎng)DEM的數(shù)據(jù)文件一般包含用對(duì)DE

21、M數(shù)據(jù)進(jìn)行說(shuō)明的數(shù)據(jù)頭和DEM數(shù)據(jù)體兩部分。 1）數(shù)據(jù)頭：一般包括定義DEM西南角起點(diǎn)坐標(biāo)、坐標(biāo)類(lèi)型、格網(wǎng)間距、行列數(shù)、最低高程以及高程放大系數(shù)等內(nèi)容；2）數(shù)據(jù)體：按行或列分布記錄的高程數(shù)字陣列。 7.TIN：在TIN模型中，基本的結(jié)構(gòu)元素有三角形頂點(diǎn)、邊和面。它們之間存在著點(diǎn)與線(xiàn)、點(diǎn)與面、線(xiàn)與面、面與面等拓?fù)潢P(guān)系。理論上，通過(guò)組成三角形的三頂點(diǎn)可完整地表達(dá)三角形的構(gòu)成以及三角形頂點(diǎn)、三角形邊、三角形之間的拓?fù)潢P(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模型

22、的檢索與應(yīng)用。因此，圍繞三角形的拓?fù)潢P(guān)系描述而產(chǎn)生了多種TIN的數(shù)據(jù)結(jié)構(gòu)。 8.TIN模型的面結(jié)構(gòu)最大特點(diǎn)是：由于存儲(chǔ)了三角形之間的鄰接關(guān)系，TIN內(nèi)插、檢索、等高線(xiàn)提取、顯示以及局部結(jié)構(gòu)分析都比較方便，不足之處是：存儲(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)線(xiàn)如山脊線(xiàn)、山谷線(xiàn)、斷裂線(xiàn)等。另外，DEM應(yīng)用目的、數(shù)據(jù)采集效率和成本、技術(shù)熟練程度也影響著DEM數(shù)據(jù)采集的方法和策略。/*目前DEM的數(shù)據(jù)主要來(lái)源

23、于地形圖、攝影測(cè)量與遙感影像數(shù)據(jù)、地面測(cè)量、既有DEM數(shù)據(jù)等。*/ 10.坡度：（1）坡度是地表形態(tài)最為重要的因子，通過(guò)坡度可以完整地形成地形曲面（Evans,1972；Strahler,1956）；（2）坡度是地形曲面函數(shù)一階微分的函數(shù)，表達(dá)了高程隨距離變化的比率（坡度定義為地面一點(diǎn)的切平面與水平面之間的夾角），而坡度的變率是地形曲面的二階微分，進(jìn)一步刻畫(huà)了坡度的變化，從而反映地形的復(fù)雜程度；（3）大量的研究表明，區(qū)域DEM高程精度與平均坡度值之間存在強(qiáng)相關(guān)，通過(guò)模型的平均坡度可預(yù)測(cè)DEM的精度（Ackermann,1979; Ley, 1986）；（4）坡度通過(guò)相互垂直的兩個(gè)坐標(biāo)軸方向的高

24、程變化表達(dá)地形曲面局部單元的傾斜程度，也就是通過(guò)地形表面的凸面和凹面來(lái)描述地形表面特性，即地表的陡峭方向和大小。11.TIN數(shù)據(jù)的建立：基于不規(guī)則三角網(wǎng)的數(shù)字高程模型（Based on Triangulated Irregular Network DEM，簡(jiǎn)寫(xiě)為 Based on TIN DEM，俗稱(chēng)TIN）就是用一系列互不交叉、互不重疊的連接在一起的三角形來(lái)表示地形表面。TIN是DEM的又一個(gè)主要數(shù)據(jù)模型，TIN的特點(diǎn)在其字面意思中表露無(wú)遺。 11. TIN的三角剖分準(zhǔn)則：TIN的三角剖分準(zhǔn)則是指TIN中三角形的形成法則，它決定著三角形的幾何形狀和TIN的質(zhì)量。目前在GIS、計(jì)算幾何和計(jì)算機(jī)

25、圖形學(xué)鄰域常用的三角剖分準(zhǔn)則有以下幾種（1）空外接圓準(zhǔn)則：在TIN中，過(guò)每個(gè)三角形的外接圓均不包含點(diǎn)集的其余任何點(diǎn)，如圖A所示；（2）最大最小角準(zhǔn)則：在兩相鄰三角形形成的凸四邊形中，這兩三角形中的最小內(nèi)角一定大于交換凸四邊形對(duì)角線(xiàn)后所形成的兩三角形的最小內(nèi)角,如圖B所示；（3）最短距離和準(zhǔn)則： 圖C，最短距離和就是指一點(diǎn)到基邊兩端的距離和為最?。唬?）張角最大準(zhǔn)則：圖D，一點(diǎn)到基邊的張角為最大；（5）面積比準(zhǔn)則：圖E，三角形內(nèi)切圓面積與三角形面積或三角形面積與周長(zhǎng)平方之比最小；（6）對(duì)角線(xiàn)準(zhǔn)則：圖F，兩三角形組成的凸四邊形的兩條對(duì)角線(xiàn)之比。超過(guò)給定限定值時(shí)對(duì)三角形進(jìn)行優(yōu)化。理論上可以證明：張角

26、最大準(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)則下由不同的位置開(kāi)始建立三角形網(wǎng)絡(luò)，其最終的形狀和結(jié)構(gòu)應(yīng)是相同的，在這一點(diǎn)上，張角最大準(zhǔn)則、空外接圓準(zhǔn)則及最大最小角準(zhǔn)則可以做到。對(duì)角線(xiàn)準(zhǔn)則含有主觀因素，現(xiàn)今使用已不多。 通常將在空外接圓準(zhǔn)則、最大最小角準(zhǔn)則下進(jìn)行三角剖分稱(chēng)為Delaunay三角剖分，簡(jiǎn)稱(chēng)為DT，同時(shí)空外接圓和最大最小角也是Delaunay三角網(wǎng)的兩個(gè)基本性質(zhì)。DT三角剖分是目前應(yīng)用最為廣泛的三角剖分方法，其特性是可最大限度避免狹長(zhǎng)三角形的

27、出現(xiàn)以及不管從何處開(kāi)始構(gòu)網(wǎng)都能保持三角形網(wǎng)絡(luò)的唯一性，這一點(diǎn)在實(shí)際應(yīng)用中相當(dāng)重要。實(shí)際上，在任何三角剖分準(zhǔn)則下得到的TIN，只要用LOP法則（局部?jī)?yōu)化過(guò)程，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ì)角線(xiàn)。 LOP局部?jī)?yōu)化過(guò)程12.無(wú)約束散點(diǎn)域的三角剖分算法與實(shí)現(xiàn) ：*分割合并算法 *三角法生長(zhǎng)算法*逐點(diǎn)插入算法 1*分割合并算法：分割合并算法（d

28、ivide and conquer delaunay triangulation algorithm）的思想最早是由Shamos和Hoey在1975年提出的，并將其應(yīng)用于V-圖的構(gòu)成（V-圖是Vorinoi圖的簡(jiǎn)稱(chēng)，是DT三角網(wǎng)的對(duì)偶圖，為DT三角網(wǎng)中相鄰三角形邊垂直平分線(xiàn)交點(diǎn)的連線(xiàn)所形成的多邊形，有關(guān)V-圖的定義、性質(zhì)和分割算法參見(jiàn)計(jì)算幾何方面的書(shū)籍）。Lewis和Robinson于1978年將該方法用來(lái)進(jìn)行DT三角網(wǎng)的剖分，隨后Lee和Schachter、Dwyer等相繼對(duì)Lewis和Robinson的算法進(jìn)行了優(yōu)化和改進(jìn)，其中Lee和Schachter于1980年的算法適合于無(wú)約束數(shù)據(jù)域

29、的三角剖分，而Dwyer于1987年的算法則考慮了帶約束條件的LOP優(yōu)化策略，因而能處理帶約束條件的數(shù)據(jù)。分割合并算法的思想很簡(jiǎn)單，就是將復(fù)雜問(wèn)題簡(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)生成方法及合并方法等。分割合并算法的基本步驟為： 第一步，把數(shù)據(jù)集以橫坐標(biāo)為主、 縱坐標(biāo)為輔按升序進(jìn)行排序；第二步，如果數(shù)據(jù)集中的數(shù)據(jù)個(gè)數(shù)大于給定的閾值，則把數(shù)據(jù)域劃分為個(gè)數(shù)近似相等的

30、左右兩個(gè)子集，并對(duì)每一子集做如下的工作，計(jì)算每一子集的凸殼；以凸殼為數(shù)據(jù)邊界，對(duì)每一數(shù)據(jù)子集進(jìn)行三角剖分，并用LOP進(jìn)行優(yōu)化，使之成為DT三角剖分；找出連接左右子集兩個(gè)凸殼的底線(xiàn)和頂線(xiàn)；由底線(xiàn)到頂線(xiàn)，合并兩個(gè)子三角網(wǎng)；第三步：如果數(shù)據(jù)集中的數(shù)據(jù)個(gè)數(shù)小于給定的閾值，則直接輸出三角剖分結(jié)果；2*三角網(wǎng)生長(zhǎng)算法：顧名思義，三角網(wǎng)生長(zhǎng)算法就是從一個(gè)“源”開(kāi)始，逐步形成覆蓋整個(gè)數(shù)據(jù)區(qū)域的三角網(wǎng)。從生長(zhǎng)過(guò)程角度，三角網(wǎng)生長(zhǎng)算法分為收縮生長(zhǎng)算法和擴(kuò)張生長(zhǎng)算法兩種。收縮生長(zhǎng)算法是先形成整個(gè)數(shù)據(jù)域的數(shù)據(jù)邊界（凸殼），并以此作為源頭，逐步縮小以形成整個(gè)三角網(wǎng)。收縮生長(zhǎng)算法與數(shù)據(jù)點(diǎn)的分布密度有關(guān)，實(shí)際情況往往比較復(fù)

31、雜，例如當(dāng)邊界收縮后一個(gè)完整的區(qū)域可能會(huì)分解成若干個(gè)相互獨(dú)立的子區(qū)域，這就增加了三角剖分的復(fù)雜性擴(kuò)張生長(zhǎng)算法與收縮算法過(guò)程剛好相反，該算法是從一個(gè)三角形開(kāi)始向外層層擴(kuò)展，最終形成覆蓋整個(gè)區(qū)域的三角網(wǎng)，其主要步驟為：第一步，生成初始三角形。在數(shù)據(jù)點(diǎn)中任取一點(diǎn)A（該點(diǎn)一般是位于數(shù)據(jù)點(diǎn)的幾何中心附近），并尋找距離此點(diǎn)最近的點(diǎn)B，兩者相連形成初始基線(xiàn)AB，如圖。利用三角剖分準(zhǔn)則（空外接圓準(zhǔn)則或張角最大準(zhǔn)則），在數(shù)據(jù)域中尋找第三點(diǎn)C，從而形成第一個(gè)Delaunay三角形ABC。第二步，擴(kuò)展形成三角網(wǎng)。以初始三角形的三條邊為初始基線(xiàn)，利用空外接圓準(zhǔn)則或張角最大準(zhǔn)則，尋找能與該三條初始基線(xiàn)形成Delauna

32、y三角形的D、E、F點(diǎn)。 BCADEFBCAD注意：（1）初始邊界將整個(gè)數(shù)據(jù)域分成兩個(gè)部分，搜尋第三點(diǎn)一般是在初始三角形另一頂點(diǎn)的異側(cè)范圍進(jìn)行。例如若初始三角形為ABC，初始邊界為AB，第三個(gè)頂點(diǎn)為C，能與三角形ABC共用AB邊的另一三角形ABD，D點(diǎn)要位于AB邊的另一側(cè)，而不能與C同側(cè)，判斷方法為： 2）為避免三角形的交叉和重復(fù)，通過(guò)上述異側(cè)點(diǎn)判別所選的第三點(diǎn)還要進(jìn)行進(jìn)一步的認(rèn)定。其方法是根據(jù)三角形任一條邊最多只能與兩個(gè)三角形所共用這個(gè)條件，進(jìn)行三角形的全等比較，即判斷新三角形的三條邊是否被前面所形成的三角形共用過(guò)兩次，如果是，則新三角形無(wú)效，否則為有效三角形。逐點(diǎn)插入算法 逐點(diǎn)插入算法的過(guò)

33、程非常簡(jiǎn)單，基本步驟為：第一步，定義包含所有數(shù)據(jù)點(diǎn)的初始包容盒，并對(duì)該包容盒進(jìn)行初始三角剖分；第二步，對(duì)所有數(shù)據(jù)點(diǎn)進(jìn)行循環(huán)，做如下工作（設(shè)當(dāng)前處理的數(shù)據(jù)點(diǎn)為P），在已存在的三角網(wǎng)中，查找包含p的三角形t；p與t的三個(gè)頂點(diǎn)相連，形成t的三個(gè)初始三角剖分；用LOP算法對(duì)初始三角剖分進(jìn)行優(yōu)化處理。第三步，處理外圍三角形。12.規(guī)則格網(wǎng)DEM讀取實(shí)例： 13緩沖區(qū)分析算法：56. 緩沖區(qū)(buffer)概念：是根據(jù)空間數(shù)據(jù)庫(kù)中的點(diǎn)、線(xiàn)、面地理實(shí)體或規(guī)劃目標(biāo)，自動(dòng)建立其周?chē)欢▽挾确秶亩噙呅巍７诸?lèi)：點(diǎn)緩沖區(qū)、線(xiàn)緩沖區(qū)、面緩沖區(qū)和復(fù)雜實(shí)體緩沖區(qū)。57. 步進(jìn)擬合的思想，即圓弧彌合的方法：（雙側(cè)平行線(xiàn)法）

34、將圓心角等分，用等長(zhǎng)的弦代替圓弧，即用均勻步長(zhǎng)的直線(xiàn)段逼近圓弧段。等分的圓心角越小，步長(zhǎng)越小，誤差越小；等分的圓心角越大，步長(zhǎng)越大，誤差越大。58. 凸角圓弧法，基本思想：在軸線(xiàn)的兩端用半徑為緩沖距的圓弧彌合；在軸線(xiàn)的各轉(zhuǎn)折點(diǎn)，判斷該點(diǎn)的凸凹性，在凸側(cè)用半徑為緩沖距的圓弧彌合，在凹側(cè)用與該點(diǎn)關(guān)聯(lián)的前后兩相鄰線(xiàn)段的偏移量為緩沖距的兩平行線(xiàn)的交點(diǎn)作為對(duì)應(yīng)頂點(diǎn)。59.關(guān)于緩沖區(qū)自相交處理：（P194）自相交多邊形的兩種情況：島嶼，多邊形當(dāng)存在島嶼和重疊自相交多邊形時(shí)，最終計(jì)算的邊線(xiàn)被分為外部邊線(xiàn)和若干島嶼。緩沖區(qū)邊線(xiàn)只繪制外圍邊線(xiàn)和島嶼輪廓。緩沖區(qū)檢索時(shí)，在外邊線(xiàn)所形成的多邊形檢索后，再扣除所有島嶼

35、多邊形。網(wǎng)絡(luò)分析1網(wǎng)絡(luò)中基本組成部分：1）結(jié)點(diǎn)(Node)：網(wǎng)絡(luò)中任意兩條線(xiàn)段的交點(diǎn)，屬性如資源數(shù)量等n 鏈(Link)：連接兩個(gè)結(jié)點(diǎn)的弧段。供物體運(yùn)營(yíng)的通道，鏈間的連接關(guān)系由弧段-結(jié)點(diǎn)拓?fù)鋽?shù)據(jù)結(jié)構(gòu)來(lái)表達(dá)。屬性如資源流動(dòng)的時(shí)間、速度等n 中心(Center)：網(wǎng)絡(luò)中位于結(jié)點(diǎn)處，具有沿著鏈?zhǔn)占桶l(fā)放資源能力的設(shè)施，如郵局、電站、水庫(kù)等 n 站點(diǎn)(Stop)：資源沿著網(wǎng)絡(luò)路徑流動(dòng)時(shí)被分配或收集的位置，如郵件投放點(diǎn)、公共汽車(chē)站，屬性如資源需求量n 轉(zhuǎn)向點(diǎn)(拐點(diǎn)，Turn)：鏈路相交處，資源流向發(fā)生改變的點(diǎn) 2）邊/邊集 3）圖：是一個(gè)非空的有限結(jié)點(diǎn)和有限邊的集合。 4）網(wǎng)絡(luò) 5）流：指網(wǎng)絡(luò)中任意一條弧的物流量。2.給定單源點(diǎn)的最短路徑的求解（三步）: 1）選一頂點(diǎn)v為源點(diǎn)，并視從源點(diǎn)v出發(fā)的所有邊為到各頂點(diǎn)的最短路徑（確定數(shù)據(jù)結(jié)構(gòu)：因?yàn)榍蟮氖亲疃搪窂剑跃鸵靡粋€(gè)記錄從源點(diǎn)v到其它各頂點(diǎn)的路徑長(zhǎng)度數(shù)組dist,開(kāi)始時(shí)，dist是源點(diǎn)v到頂點(diǎn)i的直接邊長(zhǎng)度，即dist中記錄的是鄰接陣的第v行。設(shè)一個(gè)用來(lái)記錄從源點(diǎn)到其它頂點(diǎn)的路徑數(shù)組path,path中存放路徑上第i個(gè)頂點(diǎn)的前驅(qū)頂點(diǎn)）。2）在上述的最短路徑dist中選一條最短的，并將其終點(diǎn)（即<v,k>）k加入到集合s中。3）