GIS算法原理知識點總結(jié)

GIS算法原理學(xué)問點總結(jié)算法設(shè)計和分析：1、算法設(shè)計的原則：正確性：假設(shè)一個算法本身有缺陷，那么它將不會解決問題；清楚性：一個良好的算法，必需思路清楚，構(gòu)造合理。2、算法的簡單性包括：時間簡單性和空間簡單性。3、時間簡單性：用一個與問題相關(guān)的整數(shù)量來衡量問題的大小，該整數(shù)量n的輸入所需要的時間，稱為該算法的時間簡單性。4、算法的概念：算法是完成特定任務(wù)的有限指令集。全部的算法必需滿足下面的標(biāo)準(zhǔn)：輸入輸出明確性有限性有效性GIS算法的計算幾何根底1、理解矢量的概念：假設(shè)一條線段的端點是有次序之分的,我們把這種線段稱為有向線段(directedsegmentp1p2P1P2。p2p1p2p15.矢量叉積：計算矢量叉積是直線和線段相關(guān)算法的核心局部。P=〔x1,y1Q〔x2,y2,則矢量叉積定義為0,0p1P×〔×P〕〔Q。6：折線段的拐向推斷方法，可以直接由矢量叉積的性質(zhì)推號便可以給出折線段的拐向。p2 p2 p2p1 p1p1p0基〔p2p0〕×(P1p0)<0，P0P1P1點拐向左側(cè)后得到P1P2

p0基〔p2p0〕×(P1p0)=0，P0P1P2三點共線

p0基〔p2p0〕×(P1P1點拐向右側(cè)后得到P1P2理解矢量的概念通過矢量差積的方法就可以推斷的拐向了。7.推斷點是否在線段上QP1P2：(Q-P1)X(P2-P1)=0Q保證點不在線段延長線或反向延長線上。8、推斷兩線段是否相交〔算法一：快速排斥試驗：P1P2為對角線的矩形為RQ1Q2為對角TRT不相交，明顯兩線段不會相交跨立試驗：p1p2Q1Q2，和〔P2-Q2〕位于矢量〔Q2-Q1〕的兩側(cè)，則〔P1-〕×〕〕〔〈0。當(dāng)〕×P1Q1Q2上；同理〔Q2-Q1〕P2Q1Q2上。Q1Q2的依據(jù)是：〔P1-Q1〕×〔Q2-Q1〕〔Q2-Q1〕〔P2-Q1≥0。P1P2的依據(jù)是〔Q1-P1〕×〔P2-P1〕〔P2-P1〕×〔Q2-P1〕≥0。留意在進(jìn)展“跨立推斷”的時候是進(jìn)展兩次跨立推斷推斷矩形內(nèi)是否包含點：只要推斷該店的橫坐標(biāo)和縱坐標(biāo)是否都夾在矩形的左右邊和上下邊之間。推斷線段、折線、多邊形是否在矩形中：由于矩形是個凸集，所以只了。推斷矩形是否在矩形中：只要比較左右邊界和上下邊界就行了。：圓心在矩形中且圓的半徑小于或等于圓心到矩形四邊的距離的最小值。推斷點是否在多邊形內(nèi)：P開頭，穿過多邊形的邊界的次數(shù)稱為交點數(shù)目。邊形內(nèi)部。射線法要考慮幾種特別的狀況，并且射線法適用于凸多邊形0P在多邊形外部，否則在多邊形內(nèi)部?！舱劬€是推斷它的每條線段〕條件一：線段的兩個端點都在多邊形內(nèi)條件二：線段和多邊形的全部邊都不內(nèi)交。推斷多邊形否在多邊形內(nèi)：m個頂點的多邊形是O(mXn)推斷矩形是否在多邊形內(nèi)：將矩形轉(zhuǎn)化為多邊形，然后再推斷是否在多邊形內(nèi)。推斷圓是否在多邊形內(nèi)：計算圓心到多邊形每條變邊的最短距離，假設(shè)該距離大于或等于圓半徑，則該圓在多邊形內(nèi)。推斷點是否在圓內(nèi)：計算圓心到該點的距離，假設(shè)小于或等于半徑，則該點在圓內(nèi)。由于圓是凸集，所以只要推斷是否每個頂點都在圓內(nèi)即可。推斷圓是否在圓內(nèi)：r1,r2r1<r2,O2不行能r1-r2O2O1內(nèi)；反之，O2O1內(nèi)。距離交會:是以兩個掌握點為中心，分別以目標(biāo)點與兩掌握點的距離為半徑劃圓，交會點即為要求目標(biāo)點〔留意方向二選其中一個。距離量算算法的實現(xiàn)：空間數(shù)據(jù)的變換算法了解平面坐標(biāo)變換的幾種形式:仿射變換：它是使用最多的一種幾何訂正方式。在保存線條平行條件下，原點旋轉(zhuǎn)x和y軸；平移是指把源點移動到的位置；傾斜是指以一個傾xy方向同時或單獨增XYXY大和縮小比例尺。xx 0(myyA1mxcos,AmB1mysin,B2m2xsiny0XYAAxAy0 1 2BBxBy0 1 2平移變換實例代碼：比例變換實現(xiàn)代碼：旋轉(zhuǎn)變換實現(xiàn)代碼：相像變換：圖形的相像變換是指由一個圖形到另一個圖形，在轉(zhuǎn)變的過程中保持形狀不變〔大小方向和位置可變〕的圖形。圖形相像變換的性質(zhì)：圖形的相像變換不轉(zhuǎn)變圖形中每一個角的大??；圖形相像變換后對應(yīng)線段都擴(kuò)〔或縮小相像比。相像變換面積：經(jīng)相像變換的像與原圖的面積等于相像比的平方。XYm(xcosXYm(xcosysin)A0m(xsinycos)BB1msin0XYAAxBy0 1 1BBxAy0 1 1點：簡潔的坐標(biāo)變換線：線的柵格化點：簡潔的坐標(biāo)變換線：線的柵格化面：線的柵格化+的填充方法1、內(nèi)部點集中法〔種子集中法〕2、掃描法3、射線法4、復(fù)數(shù)積分法5、邊界代數(shù)算法柵格表示法的精度與區(qū)分率有關(guān)。在圖(a)、(b)、(c)中，柵格的區(qū)分率分別為7*5，15*11，24*13。區(qū)分率的大小與下面兩個問題有關(guān)：柵格矢量化：從柵格單元轉(zhuǎn)換為幾何圖形的過程為矢量化；〔一〕要求〔矢量化過程應(yīng)保持：柵->矢轉(zhuǎn)換為拓?fù)滢D(zhuǎn)換，即保持實體原有的連通性、鄰接性等；轉(zhuǎn)換實體保持正確的外形?！捕撤椒℅IS數(shù)據(jù)輸入、更的瓶頸問題之一。方法二，程序轉(zhuǎn)化轉(zhuǎn)換〔全自動或半自動〕12、二值化34、細(xì)化:[1〕剝皮法2)骨架法]5跟蹤 撲化”矢量點”轉(zhuǎn)柵格實例：矢量數(shù)據(jù)的壓縮：矢量數(shù)據(jù)的壓縮包括兩個方面的內(nèi)容，一是在不擾亂拓?fù)潢P(guān)系的編碼，以削減所需要的存儲空間。1〕間隔取點法：每隔K個點取一點，或舍去那些比規(guī)定距離更近的點，首末點肯定要保存。臨界值隔點法臨界值法2〕垂距法：臨界值隔點法臨界值法2〕垂距法：原始曲線 4312 對點2測試距離大于規(guī)定的限差4312保存24312 3測試距離小于規(guī)定的限差432限差41 432限差412光柵法：c1a1 d/2P2p1a2

P4Pnb1d/2P3c2b2(上圖)：定義一個扇形區(qū)域，通過推斷曲線上的點在扇形外還是在扇形內(nèi)，確定保存還是舍去。設(shè)曲線上的點列為｛i，＝1，2，…，d，可依據(jù)壓縮量的大小自己定義，則光欄法的實施步驟可描述為：p2p2p1p2a1a2，使a1a2為“光欄”邊界點，p1a1、p1a2的連線為以p1為頂點的扇形的兩條邊，這就定義了一個扇形(這個扇形的口朝向曲線的前進(jìn)方向，邊長是任p1p2上各點到這些直線的垂距都d/2。點在扇形內(nèi)，則舍去p2點。然后連接p1和p3，過p3作p1p1的垂線，該垂線扇形邊交于c1和c2。在垂線上找到b1和b2點，使p3b1＝p3b2＝d／2，假設(shè)圖443 外面，則用c1或c2取代(圖443 中由c2取p1b1和p1c2定義一個的扇形，這固然是口徑(b1c2)縮小了的“光欄。、檢查下一節(jié)點，假設(shè)該點在扇形內(nèi)，則重復(fù)第(2)步；直到覺察有一個節(jié)點在最定義的扇形外為止。、當(dāng)覺察在扇形外的節(jié)點，如圖443 中的p4，此時保存p3點，以p3作為起點，重個點列檢測完為止。全部被保存的節(jié)點(含首、末點)，挨次地構(gòu)成了簡化后的點列。道格拉斯—普克法：差臨界值，以獲得最好的結(jié)果。即道格拉斯—普克〔Douglaspeuker〕算法。splitpointPsplitpointPNP1ResultP1

PN弦第一輪垂距其次輪垂距閾值柵格數(shù)據(jù)的壓縮：鏈?zhǔn)骄幋a：游程編碼：所謂游程是指按行的挨次連續(xù)且屬性值一樣的假設(shè)干柵格。游程長度的記錄方式有兩種①記錄每個游程起〔迄〕列號②記錄每個游程像元數(shù)塊式編碼的數(shù)據(jù)構(gòu)造由初始位置〔行列號、半徑和屬性代碼組成。3〕四叉樹編碼四叉樹又稱四元樹或四分樹，是最有效的柵格數(shù)據(jù)壓縮編碼方法之一。四分樹將整個圖像區(qū)域逐步分解為一系列方形區(qū)域，且每一個方形區(qū)域具有單一的屬性。最小區(qū)域為一個象元。隔點取樣法實例：4.雙線性插值算法：4.雙線性插值算法：是一種數(shù)字圖像處理、DEM數(shù)據(jù)處理等方面使用較多的局部插值算法。8.5所示，設(shè)f(0，0)=Z1，f(1，0)=Z3，f(1，1)Z4f(x,y)點的值，其中f(0，0)、f(1，0)、f(0，1)、f(1，1)代入雙線性內(nèi)插方程：f(x,y)=ax+by+cxy+da、b、c、dx,y代入，解得f(x,y)。1.空間數(shù)據(jù)內(nèi)插的定義：依據(jù)的空間數(shù)據(jù)估量(推測)未知空間的數(shù)據(jù)值?？臻g數(shù)據(jù)內(nèi)插目標(biāo)：空間數(shù)據(jù)內(nèi)插目標(biāo)：①缺值估量：估量某一點缺失的觀測數(shù)據(jù)，以提高數(shù)據(jù)密度。②內(nèi)插等值線：以等值線的形式直觀地顯示數(shù)據(jù)的空間分布。如規(guī)章矩形格網(wǎng)、三角網(wǎng)等?？臻g內(nèi)插法的種類：幾何方法、統(tǒng)計方法、空間統(tǒng)計方法、函數(shù)方法、隨機(jī)模擬方法、物理模型模擬方法和綜合方法。優(yōu)缺點比較：每一種方法均有其適用范圍、算法和優(yōu)缺點，因此，沒有確定最優(yōu)的空間內(nèi)插方法。5.如何選擇：對數(shù)據(jù)進(jìn)展空間探究分析，依據(jù)數(shù)據(jù)的特點，選擇最優(yōu)方法；同時，應(yīng)對內(nèi)插結(jié)果進(jìn)展嚴(yán)格的檢驗。6空間數(shù)據(jù)內(nèi)插的分類依據(jù)：①確定或隨機(jī)；②點與面；③全局或局部等標(biāo)準(zhǔn)分類；式中，z式中，z00的估量值；zii的zs為在估算中用到的掌握點的數(shù)目；K為指定的冪。3.3.反距離權(quán)重插值算法：是一種局部插值算法，它假設(shè)未知值的點受較近掌握反距離權(quán)重方法的通用方程是：55反距離權(quán)重插值實例：TIN、DEM、DAT數(shù)字高程模型概念與理解：高程常常用來描述地形外表的起伏形態(tài)，傳統(tǒng)的高程模型用計算機(jī)來表達(dá)時，稱為數(shù)字高程模型。是通過有限的地形高程數(shù)據(jù)實現(xiàn)對地形曲面的數(shù)字化模擬或者ElevationModelDEM。3.DEMDTM：〔即從大地水準(zhǔn)面起算的高度M也常常稱為對“Terrain”的理解也不一樣，DTMDEM更為廣泛的內(nèi)容，詳見后文的分析。TINDEM的區(qū)分：不規(guī)章三角網(wǎng)數(shù)字高程模型由連續(xù)的三角面組成，三角形的格就越大；反之地形變化比較簡單，數(shù)據(jù)點分布比較密集，格網(wǎng)單元就越小。TINDEMTIN模型不需要維護(hù)模型的構(gòu)造規(guī)章性，不但形特征點線如山脊點、山谷線、地形變化線等表示地形特征。DEM數(shù)據(jù)構(gòu)造：規(guī)章格網(wǎng)DEM數(shù)據(jù)構(gòu)造不規(guī)章三角形DEM數(shù)據(jù)構(gòu)造6.6.規(guī)章格網(wǎng)數(shù)據(jù)：由于DEM的邊界范圍一般是規(guī)章矩形，而實際地形范圍卻是不規(guī)章的還應(yīng)考慮不在爭論區(qū)域內(nèi)的M高程值的表示方〔無效區(qū)域數(shù)據(jù)一般是給出一個特別的常數(shù)值，如9999 規(guī)章格網(wǎng)DEM的數(shù)據(jù)文件一般包數(shù)據(jù)進(jìn)展說明的數(shù)據(jù)頭和DEM數(shù)據(jù)體兩局部。數(shù)據(jù)頭：一般包括定義DEM西南角起點坐標(biāo)、坐標(biāo)類型、格網(wǎng)間距、行列數(shù)、最低高程以及高程放大系數(shù)等內(nèi)容；2〕數(shù)據(jù)體：按行或列分布記錄的高程數(shù)字陣列。TIN：TIN模型中，根本的構(gòu)造元素有三角形頂點、邊和面。它們之間存在系(以下圖)通常用點在坐標(biāo)文件中的序號表示〕文件。這種構(gòu)造雖然簡潔，三角形構(gòu)造元素的拓?fù)潢P(guān)系卻是隱含的，不利于TINTIN的數(shù)據(jù)構(gòu)造。TIN模型的面構(gòu)造最大特點是：由于存儲了三角形之間的鄰接關(guān)系，TIN內(nèi)插、檢TIN的編輯中要隨時維護(hù)這種關(guān)系。DEM數(shù)據(jù)獵?。航EM的第一步是獵取地形數(shù)據(jù)。DEM的數(shù)據(jù)源和數(shù)據(jù)獵取DEM數(shù)據(jù)采集的方法和策略。DEM數(shù)據(jù)等。*/坡度：坡度是地表形態(tài)最為重要的因子，通過坡度可以完整地形成地形曲面〔Evans,1972；；坡度是地形曲面函數(shù)一階微分的函數(shù)，表達(dá)了高程隨距離變化的比率〔坡面的二階微分，進(jìn)一步刻畫了坡度的變化，從而反映地形的簡單程度；大量的爭論說明，區(qū)域DEM高程精度與平均坡度值之間存在強(qiáng)相關(guān)，通過M的精度〔；坡度通過相互垂直的兩個坐標(biāo)軸方向的高程變化表達(dá)地形曲面局部單元的的陡峭方向和大小。TIN基于不規(guī)章三角網(wǎng)的數(shù)字高程模型〔BasedonTriangulatedTINDEM的又一個主要數(shù)據(jù)模型，TIN的特點在其字面意思中表露無遺。TIN的三角剖分準(zhǔn)則：TINTIN中三角形的形成法則，它打算TINGIS、計算幾何和計算機(jī)圖形學(xué)鄰域常用的三角剖分準(zhǔn)則有以下幾種空外接圓準(zhǔn)則：在TIN中，過每個三角形的外接圓均不包含點集的其余任A所示；最大最小角準(zhǔn)則：在兩相鄰三角形形成的凸四邊形中，這兩三角形中的最小內(nèi)角肯定大于交換凸四邊形對角線后所形成的兩三角形的最小內(nèi)角,如圖B所示；最短距離和準(zhǔn)則：圖C，最短距離和就是指一點到基邊兩端的距離和為最??；張角最大準(zhǔn)則：圖D，一點到基邊的張角為最大；圖E，三角形內(nèi)切圓面積與三角形面積或三角形面積與周長平方之比最??；對角線準(zhǔn)則：圖F定限定值時對三角形進(jìn)展優(yōu)化。理論上可以證明：張角最大準(zhǔn)則、空外接圓準(zhǔn)則及最大最小角準(zhǔn)則是等價的，其余的則不然。三角形剖分準(zhǔn)則是建立三角形網(wǎng)絡(luò)的根本原則因素，現(xiàn)今使用已不多。LOP局部優(yōu)化過程DelaunayDelaunay三角網(wǎng)的兩個根本性質(zhì)。DT三角剖分是目前應(yīng)用最為廣泛的三角剖分方法，其特性是可最大限度避開狹長三角形的消滅以及不管從何處開頭構(gòu)網(wǎng)都能保持三角形網(wǎng)絡(luò)的唯TIN，LOP法則〔局部優(yōu)化過程，localoptimalprocedure，LOP〕對其進(jìn)展優(yōu)化LOPLawson1977年提出的，其DT三角網(wǎng)的空外接圓性質(zhì)對由兩個有公共邊的三角形組成的四LOP局部優(yōu)化過程無約束散點域的三角剖分算法與實現(xiàn)：*分割合并算法*三角法生長算法*逐點插入算法@1*分割合并算法：分割合并算法〔divideandconquerdelaunaytriangulationDTDT三角網(wǎng)中相鄰三角形邊垂直平分線交點的連線所形成的多邊形，有關(guān)V-圖的定義、性質(zhì)〕。LewisRobinson1978年將該方法DTLeeSchachter、DwyerLewis和LeeSchachter1980年的算法適合于無約束數(shù)據(jù)域的三角剖分，而Dwyer1987年的算法則考慮了帶約束條件LOP優(yōu)化策略，因而能處理帶約束條件的數(shù)據(jù)。DT三角網(wǎng)。當(dāng)每個子集剖分完成可有不同的點集劃分方法、子三角網(wǎng)生成方法及合并方法等。分割合并算法的根本步驟為：第一步，把數(shù)據(jù)集以橫坐標(biāo)為主、縱坐標(biāo)為輔按升序進(jìn)展排序；以凸殼為數(shù)據(jù)邊界，對每一數(shù)據(jù)子集進(jìn)展三角剖分，并用LOP進(jìn)展優(yōu)化，使之成為DT三角剖分；③找出連接左右子集兩個凸殼的底線和頂線；④由底線到頂線，合并兩個子三角網(wǎng)；第三步：假設(shè)數(shù)據(jù)集中的數(shù)據(jù)個數(shù)小于給定的閾值，則直接輸出三角剖分結(jié)果；〔凸殼，并以此作為源頭，逐步縮小以形成整個三角網(wǎng)。收縮生長算法與數(shù)據(jù)點的會分解成假設(shè)干個相互獨立的子區(qū)域，這就增加了三角剖分的簡單性擴(kuò)張生長算法與收縮算法過程剛好相反展，最終形成掩蓋整個區(qū)域的三角網(wǎng)，其主要步驟為：第一步，生成初始三角形。在數(shù)據(jù)點中任取一點A〔該點一般是位于數(shù)據(jù)點的幾何中心四周〔空外接圓準(zhǔn)則或張角最大準(zhǔn)則C，ABC。DBACDelaunayD、E、F點。DBAC D BFACEFACE〔1ABCAB，第三邊的C同側(cè)，推斷方法為：2〕為避開三角形的穿插和重復(fù)，通過上述異側(cè)點判別所選的第三點還要進(jìn)展進(jìn)形共用過兩次，假設(shè)是，則三角形無效，否則為有效三角形。@逐點插入算法逐點插入算法的過程格外簡潔，根本步驟為：〔PLOP算法對初始三角剖分進(jìn)展優(yōu)化處理。第三步，處理外圍三角形。12.DEM讀取實例：13緩沖區(qū)分析算法：(buffer)概念：是依據(jù)空間數(shù)據(jù)庫中的點、線、面地理實體或規(guī)劃目標(biāo)，自動建立其四周肯定寬度范圍的多邊形。分類：點緩沖區(qū)、線緩沖區(qū)、面緩沖區(qū)和簡單實體緩沖區(qū)。步進(jìn)擬合的思想圓弧彌合〔雙側(cè)平行線法〕大，誤差越大。凸角圓弧法，根本思想：在軸線的兩端用半徑為緩沖距的圓弧彌合；為對應(yīng)頂點?！?〕自相交多邊形的兩種狀況：島嶼，多邊形干島嶼。緩沖區(qū)邊線只繪制外圍邊線和島嶼輪廓。形。網(wǎng)絡(luò)分析11網(wǎng)絡(luò)中根本組成局部：接關(guān)系由弧段-結(jié)點拓?fù)鋽?shù)據(jù)構(gòu)造來表達(dá)。屬性如資源流淌的時間、速度等中心(Center)：網(wǎng)絡(luò)中位于結(jié)點處，具有沿著鏈?zhǔn)占桶l(fā)放資源力量的設(shè)施，如郵局、電站、水庫等郵件投放點、公共汽車站，屬性如資源需求量邊/邊集圖：是一個非空的有限結(jié)點和有限邊的集合。網(wǎng)絡(luò)流：指網(wǎng)絡(luò)中任意一條弧的物流量。2.給定單源點的最短路徑的求解〔三步〕:1〕選一頂點v為源點，并視從源點v動身的全部邊為到各頂點的最短路徑dist[],開頭時，distvi的distv行。②設(shè)一個用來記