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

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

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

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

5、 × （Q2-Q1）0。當（P1-Q1）×（Q2-Q1）=0時，說明 （P1-Q1）×（Q2-Q1）共線，但是因為已經通過快速排斥實驗，所以P1一定在線段Q1Q2上；同理 （Q2-Q1） × （P2-Q1） =0說明P2一定在線段Q1Q2上。所以判斷P1P2跨立Q1Q2的依據是：（P1-Q1）×（Q2-Q1） × （Q2-Q1） ×（P2-Q1 0。同理判斷Q1Q2跨立P1P2的依據是（Q1-P1）×（P2-P1） × （P2-P1） ×（Q2-P1）0。注意在進行“跨立判斷”的時候是進行兩次跨

6、立判斷9.判斷矩形內是否包含點：只要判斷該店的橫坐標和縱坐標是否都夾在矩形的左右邊和上下邊之間。10.判斷線段、折線、多邊形是否在矩形中：因為矩形是個凸集，所以只要判斷所有端點都在矩形就行了。11.判斷矩形是否在矩形中：只要比較左右邊界和上下邊界就行了。12.判斷圓是否在矩形中：圓心在矩形中且圓的半徑小于或等于圓心到矩形四邊的距離的最小值。13.判斷點是否在多邊形內： 1)射線法：一條射線從點P開始，穿過多邊形的邊界的次數稱為交點數目。當交點數目是偶數時，點P在多邊形外部；否則，為奇數時，在多邊形內部。射線法要考慮幾種特殊的情況，并且射線法適用于凸多邊形2)轉角法：多邊形環繞點P的次數稱為環繞

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

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

9、傾斜和不均勻縮放。旋轉指在原點旋轉x和y軸；平移是指把源點移動到新的位置；傾斜是指以一個傾向將形狀改變為平行四邊形；不均勻縮放是指在x或y方向同時或單獨增大和縮小比例尺。平移變換實例代碼：比例變換實現代碼：旋轉變換實現代碼：3.相似變換：圖形的相似變換是指由一個圖形到另一個圖形，在改變的過程中保持形狀不變（大小方向和位置可變）的圖形。圖形相似變換的性質：圖形的相似變換不改變圖形中每一個角的大小；圖形相似變換后對應線段都擴大（或縮小）相同的倍數，這個數叫相似比。相似變換面積：經相似變換的像與原圖的面積等于相似比的平方。相似變換的分解：任何相似變換可以分解為放縮，平移，旋轉和翻轉變換的復合。相似變

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

11、體保持正確的外形。（二）方法方法一，實際應用中大多數采用人工矢量化法，如掃描矢量化，該法工作量大，成為GIS數據輸入、更新的瓶頸問題之一。方法二，程序轉化轉換（全自動或半自動）過程為：1、邊界提取2、二值化 3、二值圖像的預處理4、細化:1）剝皮法 2)骨架法5、跟蹤 6、拓撲化 6.”矢量點”轉柵格實例：6.矢量數據的壓縮：矢量數據的壓縮包括兩個方面的內容，一是在不擾亂拓撲關系的前提下，對采樣點數據進行合理的抽稀。二是對矢量坐標數據重新進行編碼，以減少所需要的存儲空間。1）間隔取點法：每隔K個點取一點，或舍去那些比規定距離更近的點，首末點一定要保留。臨界值 隔點法臨界值法2）垂距法：原始曲線

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

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

14、#160;3°、檢查下一節點，若該點在新扇形內，則重復第(2)步；直到發現有一個節點在最新定義的扇形外為止。 4°、當發現在扇形外的節點，如圖4-4-3中的p4，此時保留p3點，以p3作為新起點，重復1°3°。如此繼續下去，直到整個點列檢測完為止。所有被保留的節點(含首、末點)，順序地構成了簡化后的新點列。首先將一條曲線首、末點連一直線，求出各點到該直線的距離，選其最大者與規定的臨界值相比較若大于臨界值，則離該直線距離最大的點保留，否則，將直線兩端間各點全部舍去，并將原線條分成兩部分，對每部分線條再實施該抽稀過程，直到結束。抽稀結果點數隨選取限

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

16、又稱四元樹或四分樹，是最有效的柵格數據壓縮編碼方法之一。 四分樹將整個圖像區域逐步分解為一系列方形區域，且每一個方形區域具有單一的屬性。最小區域為一個象元。8.隔點取樣法實例：空間數據內插算法1.空間數據內插的定義：根據已知的空間數據估計(預測)未知空間的數據值。2. 空間數據內插目標：缺值估計：估計某一點缺失的觀測數據，以提高數據密度。內插等值線：以等值線的形式直觀地顯示數據的空間分布。數據網格化。把無規則分布的空間數據內插為規則分布的空間數據集，如規則矩形格網、三角網等。3.空間內插法的種類：幾何方法、統計方法、空間統計方法、函數方法、隨機模擬方法、物理模型模擬方法和綜合方法。 4.優缺點

17、比較：每一種方法均有其適用范圍、算法和優缺點，因此，沒有絕對最優的空間內插方法。5.如何選擇：對數據進行空間探索分析，根據數據的特點，選擇最優方法；同時，應對內插結果進行嚴格的檢驗。6空間數據內插的分類依據：確定或隨機；點與面；全局或局部等標準分類；內插方法的基本假設和數學本質。3.反距離權重插值算法：是一種局部插值算法，它假設未知值的點受較近控制點的影響比較遠控制點的影響更大。反距離權重方法的通用方程是：式中，z0為點0的估計值；zi為控制點i的z值；dj為控制點i與點0間的趾離；s為在估算中用到的控制點的數目；K為指定的冪。4.雙線性插值算法：是一種數字圖像處理、DEM數據處理等方面使用較

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

19、為數字高程模型。2.數字高程模型：是通過有限的地形高程數據實現對地形曲面的數字化模擬或者說是地形表面形態的數字化表示，英文為Digital Elevation Model，簡稱DEM。3.理解DEM和DTM：由于高程數據常常采用絕對高程或海拔（即從大地水準面起算的高度），DEM也常常稱為DTM。要說明的是由于“Terrain”一詞的含義比較廣泛，不同專業背景對“Terrain”的理解也不一樣，DTM趨向于表達比DEM更為廣泛的內容，詳見后文的分析。4. TIN和規則DEM的區別：不規則三角網數字高程模型由連續的三角面組成，三角形的形狀、大小取決于不規則分布的點的位置和密度。地形變化越簡單，采樣

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

21、M數據進行說明的數據頭和DEM數據體兩部分。 1）數據頭：一般包括定義DEM西南角起點坐標、坐標類型、格網間距、行列數、最低高程以及高程放大系數等內容；2）數據體：按行或列分布記錄的高程數字陣列。 7.TIN：在TIN模型中，基本的結構元素有三角形頂點、邊和面。它們之間存在著點與線、點與面、線與面、面與面等拓撲關系。理論上，通過組成三角形的三頂點可完整地表達三角形的構成以及三角形頂點、三角形邊、三角形之間的拓撲關系(下圖)，這種結構只需要兩個文件，即三角形頂點坐標文件和組成三角形三頂點（通常用點在坐標文件中的序號表示）文件。這種結構雖然簡單，三角形結構元素的拓撲關系卻是隱含的，不利于TIN模型

22、的檢索與應用。因此，圍繞三角形的拓撲關系描述而產生了多種TIN的數據結構。 8.TIN模型的面結構最大特點是：由于存儲了三角形之間的鄰接關系，TIN內插、檢索、等高線提取、顯示以及局部結構分析都比較方便，不足之處是：存儲量較大，而且在TIN的編輯中要隨時維護這種關系。9.DEM數據獲取：建立DEM的第一步是獲取地形數據。DEM的數據源和數據獲取方式對于DEM的最終質量至關重要。DEM原始數據主要是高程和平面位置數據，在可能條件下還應包括各種地形結構線如山脊線、山谷線、斷裂線等。另外，DEM應用目的、數據采集效率和成本、技術熟練程度也影響著DEM數據采集的方法和策略。/*目前DEM的數據主要來源

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

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

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

26、最大準則、空外接圓準則及最大最小角準則是等價的，其余的則不然。三角形剖分準則是建立三角形網絡的基本原則，應用不同的準則將會得到不同的三角形網絡。一般而言，應盡量保持三角網的唯一性，即在同一準則下由不同的位置開始建立三角形網絡，其最終的形狀和結構應是相同的，在這一點上，張角最大準則、空外接圓準則及最大最小角準則可以做到。對角線準則含有主觀因素，現今使用已不多。 通常將在空外接圓準則、最大最小角準則下進行三角剖分稱為Delaunay三角剖分，簡稱為DT，同時空外接圓和最大最小角也是Delaunay三角網的兩個基本性質。DT三角剖分是目前應用最為廣泛的三角剖分方法，其特性是可最大限度避免狹長三角形的

27、出現以及不管從何處開始構網都能保持三角形網絡的唯一性，這一點在實際應用中相當重要。實際上，在任何三角剖分準則下得到的TIN，只要用LOP法則（局部優化過程，local optimal procedure ，LOP）對其進行優化處理，就能得到唯一的DT三角網絡。LOP法則是Lawson在1977年提出的，其基本思想是運用DT三角網的空外接圓性質對由兩個有公共邊的三角形組成的四邊形進行判斷。如果其中一個三角形的外接圓中含有第四個頂點，則交換四邊形的對角線。 LOP局部優化過程12.無約束散點域的三角剖分算法與實現 ：*分割合并算法 *三角法生長算法*逐點插入算法 1*分割合并算法：分割合并算法（d

28、ivide and conquer delaunay triangulation algorithm）的思想最早是由Shamos和Hoey在1975年提出的，并將其應用于V-圖的構成（V-圖是Vorinoi圖的簡稱，是DT三角網的對偶圖，為DT三角網中相鄰三角形邊垂直平分線交點的連線所形成的多邊形，有關V-圖的定義、性質和分割算法參見計算幾何方面的書籍）。Lewis和Robinson于1978年將該方法用來進行DT三角網的剖分，隨后Lee和Schachter、Dwyer等相繼對Lewis和Robinson的算法進行了優化和改進，其中Lee和Schachter于1980年的算法適合于無約束數據域

29、的三角剖分，而Dwyer于1987年的算法則考慮了帶約束條件的LOP優化策略，因而能處理帶約束條件的數據。分割合并算法的思想很簡單，就是將復雜問題簡單化，首先將數據點分割成易于進行三角剖分的子集，如一個子集中包括三個、四個點，然后對每個子集進行三角剖分，并用LOP算法保證三角剖分為DT三角網。當每個子集剖分完成后，對每個子集的三角剖分進行合并，形成最終的整體三角網。不同的實現方法可有不同的點集劃分方法、 子三角網生成方法及合并方法等。分割合并算法的基本步驟為： 第一步，把數據集以橫坐標為主、 縱坐標為輔按升序進行排序；第二步，如果數據集中的數據個數大于給定的閾值，則把數據域劃分為個數近似相等的

30、左右兩個子集，并對每一子集做如下的工作，計算每一子集的凸殼；以凸殼為數據邊界，對每一數據子集進行三角剖分，并用LOP進行優化，使之成為DT三角剖分；找出連接左右子集兩個凸殼的底線和頂線；由底線到頂線，合并兩個子三角網；第三步：如果數據集中的數據個數小于給定的閾值，則直接輸出三角剖分結果；2*三角網生長算法：顧名思義，三角網生長算法就是從一個“源”開始，逐步形成覆蓋整個數據區域的三角網。從生長過程角度，三角網生長算法分為收縮生長算法和擴張生長算法兩種。收縮生長算法是先形成整個數據域的數據邊界（凸殼），并以此作為源頭，逐步縮小以形成整個三角網。收縮生長算法與數據點的分布密度有關，實際情況往往比較復

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

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

33、程非常簡單，基本步驟為：第一步，定義包含所有數據點的初始包容盒，并對該包容盒進行初始三角剖分；第二步，對所有數據點進行循環，做如下工作（設當前處理的數據點為P），在已存在的三角網中，查找包含p的三角形t；p與t的三個頂點相連，形成t的三個初始三角剖分；用LOP算法對初始三角剖分進行優化處理。第三步，處理外圍三角形。12.規則格網DEM讀取實例： 13緩沖區分析算法：56. 緩沖區(buffer)概念：是根據空間數據庫中的點、線、面地理實體或規劃目標，自動建立其周圍一定寬度范圍的多邊形。分類：點緩沖區、線緩沖區、面緩沖區和復雜實體緩沖區。57. 步進擬合的思想，即圓弧彌合的方法：（雙側平行線法）

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

35、多邊形。網絡分析1網絡中基本組成部分：1）結點(Node)：網絡中任意兩條線段的交點，屬性如資源數量等n 鏈(Link)：連接兩個結點的弧段。供物體運營的通道，鏈間的連接關系由弧段-結點拓撲數據結構來表達。屬性如資源流動的時間、速度等n 中心(Center)：網絡中位于結點處，具有沿著鏈收集和發放資源能力的設施，如郵局、電站、水庫等 n 站點(Stop)：資源沿著網絡路徑流動時被分配或收集的位置，如郵件投放點、公共汽車站，屬性如資源需求量n 轉向點(拐點，Turn)：鏈路相交處，資源流向發生改變的點 2）邊/邊集 3）圖：是一個非空的有限結點和有限邊的集合。 4）網絡 5）流：指網絡中任意一條弧的物流量。2.給定單源點的最短路徑的求解（三步）: 1）選一頂點v為源點，并視從源點v出發的所有邊為到各頂點的最短路徑（確定數據結構：因為求的是最短路徑，所以就要用一個記錄從源點v到其它各頂點的路徑長度數組dist,開始時，dist是源點v到頂點i的直接邊長度，即dist中記錄的是鄰接陣的第v行。設一個用來記錄從源點到其它頂點的路徑數組path,path中存放路徑上第i個頂點的前驅頂點）。2）在上述的最短路徑dist中選一條最短的，并將其終點（即<v,k>）k加入到集合s中。3）