等高線的自動追蹤

1、等高線自動追蹤等高線自動追蹤1. DEM的表示的表示2. 格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤3. TIN等高線追蹤等高線追蹤4. TIN和格網(wǎng)模型的應(yīng)用比較和格網(wǎng)模型的應(yīng)用比較數(shù)字地形表達(dá)20世紀(jì)中葉后，隨著計算機科學(xué)、現(xiàn)代數(shù)學(xué)和計算機圖形學(xué)的發(fā)展，各種數(shù)字地形表達(dá)方式得到迅猛的發(fā)展。計算機和計算機技術(shù)在測繪方面的應(yīng)用使得測繪學(xué)科逐步向數(shù)字化與自動化、實時處理與多用途的方向發(fā)展。計算機技術(shù)在很大程度上改變了地圖制圖的生產(chǎn)方式，同時也改變著地圖產(chǎn)品的樣式和用圖概念。數(shù)字地形表達(dá)的方式可以分為兩大類，即數(shù)學(xué)描述和圖像描述。使用傅立葉級數(shù)和多項式來描述地形是常用的數(shù)學(xué)描述方法。規(guī)則格網(wǎng)、不規(guī)則格網(wǎng)、等

2、高線則是圖像描述的常用方式。2.1 2.1 DEM的表示的表示2.1 2.1 DEM的表示的表示數(shù)字地形表達(dá)1.測繪學(xué)中數(shù)字地形數(shù)字地形(地面地面)模型模型（DTM：Digital Terrain Model）是地形數(shù)字化的表達(dá)方式。2.數(shù)字地形模型是新一代的地形圖，地貌和地物不再用直觀的等高線和圖例符號在紙上表達(dá)，而是通過計算機儲存介質(zhì)中的大量密集的地面點的空間坐標(biāo)和地形屬性編碼，以數(shù)字的形式描述。3.通常根據(jù)不同的具體需要，將某些地面的特性信息與地形信息結(jié)合在一起，構(gòu)成有特殊用途的數(shù)字地面模型。 數(shù)字地面模型中所包含的地面特性信息類型一般可分為下列四組： 1地貌信息：高程、坡度、坡向、坡面

3、形態(tài)及描述地表起伏情況的更為復(fù)雜的地貌因子； 2基本地物信息：水系、交通網(wǎng)、居民點和工礦企業(yè)及境界線； 3主要的自然資源和環(huán)境信息：土壤、植被、地質(zhì)、氣候； 4主要的社會經(jīng)濟(jì)信息：人口、工農(nóng)業(yè)產(chǎn)值、經(jīng)濟(jì)活動等。2.1 2.1 DEM的表示的表示數(shù)字高程模型-DEM傳統(tǒng)地形測圖中，地物用地物符號表達(dá)，地貌用高程點或等高線表達(dá)。從地形測繪的角度出發(fā)，一般僅把基本地形圖中的地形要素、特別是高程信息高程信息，作為數(shù)字地形模型數(shù)字地形模型（ DTM ）的內(nèi)容。即通常DTM的主要內(nèi)容是數(shù)字高程模型（DEM: Digital Elevation Model ）。從測繪學(xué)的角度，地面高程模型是高程Z關(guān)于平面坐

4、標(biāo)X，Y兩個自變量的連續(xù)函數(shù)，DEM只是地面高程模型的一個有限的離散表示。2.1 2.1 DEM的表示的表示數(shù)字高程模型-DEM表示法1.數(shù)學(xué)方法：用數(shù)學(xué)方法來表達(dá)，可以采用整體擬合方法，即根據(jù)區(qū)域所有的高程點數(shù)據(jù)，用傅立葉級數(shù)和高次多項式擬合統(tǒng)一的地面高程曲面。也可用局部擬合方法，將地表復(fù)雜表面分成正方形規(guī)則區(qū)域或面積大致相等的不規(guī)則區(qū)域進(jìn)行分塊搜索，根據(jù)有限個點進(jìn)行擬合形成高程曲面。 2.1 2.1 DEM的表示的表示數(shù)字高程模型-DEM表示法2.圖形方法：線模式線模式等高線是表示地形最常見的形式。其它的地形特征線也是表達(dá)地面高程的重要信息源，如山 脊 線 、 谷 底 線 、 海 岸 線

5、及 坡 度 變 換 線 等 。 點模式點模式用離散采樣數(shù)據(jù)點建立DEM是DEM建立常用的方法之一。數(shù)據(jù)采樣可以按規(guī)則格網(wǎng)采樣，可以是密度一致的或不一致的；可以是不規(guī)則采樣，如不規(guī)則三角網(wǎng)、鄰近網(wǎng)模型等；也可以有選擇性地采樣，采集山峰、洼坑、隘口、邊界等重要特征點。在地理信息系統(tǒng)中，DEM最主要的三種表示模型是：規(guī)則格網(wǎng)模型，等高線模型和不規(guī)則三角網(wǎng)模型。2.1 2.1 DEM的表示的表示DEM表示法2.1 2.1 DEM的表示的表示點模式DEM的幾種表示模型1.規(guī)則格網(wǎng)模型2.不規(guī)則三角網(wǎng)模型(TIN: Triangulated Irregular Network)3.等高線模型4.層次模型

6、(Layer of Details,LOD):表達(dá)多種不同精度水平的數(shù)字高程模型。*規(guī)則格網(wǎng)模型和TIN模型是最常用的模型2.1 2.1 DEM的表示的表示點模式DEM的幾種表示模型規(guī)則格網(wǎng)模型規(guī)則網(wǎng)格將區(qū)域空間切分為規(guī)則的格網(wǎng)單元，每個格網(wǎng)單元對應(yīng)一個高程值。數(shù)學(xué)上表示為一個矩陣，計算機實現(xiàn)中則是一個二維數(shù)組。 每個格網(wǎng)的高程值有兩種不同的解釋。格網(wǎng)柵格觀點認(rèn)為格網(wǎng)單元對應(yīng)的地面面積內(nèi)高程是均一的高度，這種DEM是一個不連續(xù)的函數(shù)。點柵格觀點認(rèn)為該網(wǎng)格單元的高程值是網(wǎng)格中心點的高程，這樣就需要用距離加權(quán)平均方法來計算每個點的高程。點柵格觀點比較常用。矩陣結(jié)構(gòu)的2.1 2.1 DEM的表示的表

7、示點模式DEM的幾種表示模型TIN模型TIN模型根據(jù)區(qū)域有限個點集將區(qū)域劃分為相連的三角面網(wǎng)絡(luò)，區(qū)域中任意點落在三角面的頂點、邊上或三角形內(nèi)。如果點不在頂點上，該點的高程值通常通過線性插值的方法得到。TIN是一個三維空間的分段線性模型，在整個區(qū)域內(nèi)連續(xù)但不可微。TIN的數(shù)據(jù)存儲方式不僅要存儲每個點的高程，還要存儲其平面坐標(biāo)、節(jié)點連接的拓?fù)潢P(guān)系，三角形及鄰接三角形等關(guān)系。頻繁使用指針。2.1 2.1 DEM的表示的表示點模式DEM的幾種表示模型等高線模型等高線模型表示高程，每一條等高線對應(yīng)一個已知的高程值，這樣一系列等高線集合和它們的高程值一起就構(gòu)成了一種地面高程模型 。等高線通常用二維的鏈表來

8、存儲，其被存成一個有序的坐標(biāo)點對序列，可以認(rèn)為是一條帶有高程值屬性的簡單多邊形或多邊形弧段。由于等高線模型只表達(dá)了區(qū)域的部分（位于等高線上的點）高程值，需要用插值方法來計算落在等高線外的其它點的高程。通常只使用外包最鄰近的兩條等高線的高程進(jìn)行插值。2.1 2.1 DEM的表示的表示點模式DEM的幾種表示模型層次模型層次模型是一種表達(dá)多種不同精度水平的數(shù)字高程模型。大多數(shù)層次模型是基于TIN模型的，通常TIN的數(shù)據(jù)點越多精度越高，數(shù)據(jù)點越少精度越低，但數(shù)據(jù)點多則要求更多的計算資源。所以如果在精度滿足要求的情況下，最好使用盡可能少的數(shù)據(jù)點。層次模型允許根據(jù)不同的任務(wù)要求選擇不同精度的TIN地形模型

9、。2.1 2.1 DEM的表示的表示點模式DEM的幾種表示模型間的相互轉(zhuǎn)換 格網(wǎng)TIN 格網(wǎng)等高線 TIN等高線 TIN的形成：Delaunay三角剖分方法2.1 2.1 DEM的表示的表示 DEM的建立與質(zhì)量2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤 DEM規(guī)則格網(wǎng)模型的生成 等高線點的追蹤2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤規(guī)則格網(wǎng)模型的生成 對于不規(guī)則分布的高程點，可以通過距離加權(quán)平均法或其它方法求格網(wǎng)點高程，從而生成格網(wǎng)模型。a.距離加權(quán)平均法 距離加權(quán)平均法基于一種假設(shè)：在一定區(qū)域內(nèi)的某點高程受周圍點高程的影響，其影響的大小與它們之間的距離成反比。 通常需要選擇410個點來

10、確定待定點的高程。2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤規(guī)則格網(wǎng)模型的生成a.距離加權(quán)平均法1.以待定高程的格網(wǎng)點為中心（圓心），在預(yù)先設(shè)定的搜索圓半徑范圍內(nèi)，從小到大進(jìn)行高程點的搜索。2.當(dāng)搜索圓內(nèi)的高程點數(shù)目介于預(yù)先設(shè)定的數(shù)目（通常為410）時，搜索成功，將搜索到的高程點用以格網(wǎng)點高程的距離加權(quán)平均計算。否則，搜索失敗，初始高程點數(shù)據(jù)有缺陷。2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤規(guī)則格網(wǎng)模型的生成a.距離加權(quán)平均法22)0()0(yyixxiDi設(shè)格網(wǎng)點坐標(biāo)為(x0,y0)，搜索到的高程點坐標(biāo)為(xi, yi, zi) (4i10, z為高程)，高程點到格網(wǎng)點的距離為Di則格網(wǎng)

11、點高程為：)/1()/(DiDiziz2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤規(guī)則格網(wǎng)模型的生成b.其它求格網(wǎng)點高程的方法 改進(jìn)的距離加權(quán)方法 普通的距離加權(quán)平均法在原始高程數(shù)據(jù)點均勻分布的情況下是合理的。但是，有時原始數(shù)據(jù)的分布并不理想，搜索到的原始高程點可能集中在某一個方向，甚至是在一個十分狹小的方向內(nèi)，而在其它方向則沒有點。在這種情況下，需要擴(kuò)大搜索半徑，并分象限（扇面）去確定和選擇搜索點。2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤規(guī)則格網(wǎng)模型的生成b.其它求格網(wǎng)點高程的方法多項式內(nèi)插線性：搜索最近3個高程點，插值函數(shù)雙線性：搜索最近4個高程點，插值函數(shù)其它多項式（已知高程點數(shù)目必

12、須等于待定系數(shù)個數(shù)） *對格網(wǎng)點鄰近點的搜索，有時并不唯一地以距離的遠(yuǎn)近作為取舍的依據(jù)。適當(dāng)考慮高程點的方位分布，使搜索點環(huán)布格網(wǎng)點四周為好。012zaaxay0123zaaxayaxy2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤等高線點的追蹤A.等高線點位置的確定1.確定高程為z0的等高線點是否在格網(wǎng)邊上僅當(dāng)z0值介于邊的2個端點高程值之間時，等高線z0才通過該邊。等高線z0通過某邊的判別式L=(z0-z1)(z0-z2)L0時，等高線不過該邊。2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤等高線點的追蹤A.等高線點位置的確定2.確定高程為z0的等高線點在格網(wǎng)邊上的平面位置如果確認(rèn)等高線z0通

13、過格網(wǎng)邊，則按等高線線性內(nèi)插線性內(nèi)插原則確定等高線點的平面位置。關(guān)于格網(wǎng)邊界直線的參數(shù)方程是：x=x1+(x2-x1)t; y=y1+(y2-y1)t; z=z1+(z2-z1)t; 令z=z0，解得t0；將t0回代入?yún)?shù)方程解得(x0, y0)，其就是等高線點的平面位置。21210110112121();()xxyyxxzzyyzzzzzz2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤等高線點的追蹤B.等高線點位置的追蹤二義性問題當(dāng)一個格網(wǎng)的4條邊上都有等高線點時，這時會產(chǎn)生等高線追蹤的二義性問題（如僅12條邊有等高線點，則無此問題。不可不可能能3 3條邊有等高線點條邊有等高線點）。如圖(a)

14、 ,(b)所示(z=50)，2種等高線追蹤都是可能合理，但真正正確的方式應(yīng)該只有一種。一條等高線完全包含在一個矩形單元內(nèi)非常少見。2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤等高線點的追蹤B.等高線點位置的追蹤二義性問題1.通過在格網(wǎng)的中心位置補測一個高程點，構(gòu)成4個三角形來解決二義性問題。2.可以認(rèn)為距離近的連線方式是正確的追蹤方向；3.參考地性線的走向來決定。4.縮小格網(wǎng)尺寸，重建格網(wǎng)模型。（1）（2）（3）2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤等高線點的追蹤B.等高線點位置的追蹤微量調(diào)整格網(wǎng)點高程問題如果一個網(wǎng)格點的高程數(shù)值恰好等于要提取的等高線的高程數(shù)值（整數(shù)），會使等高線追蹤的

15、判斷過程變得復(fù)雜，并且會生成不閉合的等高線，一般的解決辦法是將部分（高程為整數(shù)）或全部的網(wǎng)格點的數(shù)值增加一個小的偏移量偏移量 （ = =最小高程度量值的1/10或1/100）。2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤等高線點的追蹤B.等高線點位置的追蹤追蹤算法1）設(shè)立格網(wǎng)標(biāo)志數(shù)組，其初始值為0。其元素與格網(wǎng)對應(yīng)，凡搜索處理過的格網(wǎng)將標(biāo)志置為1，以后不再被搜索。當(dāng)?shù)雀呔€的高程數(shù)值改變，格網(wǎng)標(biāo)志數(shù)組應(yīng)該清零。DEM的格網(wǎng)尺寸一般保證相應(yīng)等高距的等高線不會在一個格網(wǎng)內(nèi)閉合。2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤等高線點的追蹤B.等高線點位置的追蹤追蹤算法2）按格網(wǎng)點在計算機中的順序，依次判

16、斷格網(wǎng)邊中是否有等高線穿過。直至搜索到等高線與格網(wǎng)邊的第一個交點（該點為搜索起點）。線性內(nèi)插該點的平面坐標(biāo)，同時標(biāo)記該格網(wǎng)邊所在的一個格網(wǎng)作為起始格網(wǎng)（起始格網(wǎng)的選擇也是對搜索方向的選擇），另一個格網(wǎng)為二次搜索格網(wǎng)。在搜索過程中，如果格網(wǎng)點高程為等高距的整數(shù)倍，則對其作高程值微量調(diào)整。2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤等高線點的追蹤B.等高線點位置的追蹤追蹤算法3）依次對該格網(wǎng)的另外三條邊進(jìn)行搜索，尋找等高線在該格網(wǎng)的離去邊，也就是相鄰格網(wǎng)的進(jìn)入邊，并內(nèi)插等高線點的平面坐標(biāo)。在搜索過程中，一定要對另外三條邊全部進(jìn)行搜索判斷。如果一個格網(wǎng)的四條邊都有等高線穿過，則要按照預(yù)設(shè)的方式來解決

17、二義性問題。2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤等高線點的追蹤B.等高線點位置的追蹤追蹤算法4）進(jìn)入相鄰格網(wǎng)，重復(fù)第（3）步，直至該格網(wǎng)不存在等高線的離去邊（此時等高線為開曲線）或該格網(wǎng)為起始格網(wǎng)（此時等高線為閉曲線）為止。5）對于開曲線，將已搜索到的等高線點順序倒過來；并回到搜索起點，由二次搜索格網(wǎng)開始進(jìn)行搜索，直至到達(dá)搜索邊界。6）當(dāng)一條等高線的等高線點全部跟蹤完，將其光滑輸出。然后繼續(xù)格網(wǎng)的搜索，直至全部格網(wǎng)處理完，再改變等高線高程，重復(fù)以上過程，直到完成全部等高線的繪制為止。2.22.2格網(wǎng)法等高線追蹤格網(wǎng)法等高線追蹤等高線點的追蹤等高線點的插值、光滑 由于DEM格網(wǎng)模型尺寸的

18、原因，一些DEM的分辨率受到限制。追蹤到的等高線點在平滑輸出時可能視覺效果較差，或者和實際地形相差較大。因此有必要在追蹤到的等高線點間進(jìn)行一些高程點的增補，然后再作曲線光滑。 高程點的增補和光滑有如下要求：l曲線要通過等高線追蹤點l曲線在等高線追蹤點處的一階（或二階）導(dǎo)數(shù)連續(xù)l相鄰的等高線追蹤點間的曲線沒有多余擺動l同一等高線自身不能相交2.3 2.3 TIN等高線追蹤等高線追蹤 TIN模型的生成 等高線點的追蹤2.3 2.3 TIN等高線追蹤等高線追蹤TIN模型的生成對于TIN模型的建構(gòu)，有如下基本要求a.生成的TIN必須具有唯一性b.力求最佳的三角形形狀，三角形形狀以等邊為最優(yōu)，避免小的銳

19、角和大的鈍角c.保證最鄰近的點構(gòu)成三角形，即三角形的3邊之和最小Delaunay三角網(wǎng)生成法就是大致滿足上述要求的一種常用方法。其在地形擬合方面十分出色。2.3 2.3 TIN等高線追蹤等高線追蹤TIN模型的生成Voronoi(沃羅努瓦)圖由一組連續(xù)多邊形(又稱泰森多邊形)組成，多邊形的邊界是由連接兩鄰點線段的垂直平分線組成。圖中紅點為原始高程數(shù)據(jù)點，虛黑線為Voronoi多邊形的邊界 線 。 具 有 公 共 邊 線 的Voronoi多邊形為鄰接多邊形。點與其所在多邊形為包含關(guān)系。2.3 2.3 TIN等高線追蹤等高線追蹤TIN模型的生成Delaunay三角形是由每每3 3個兩兩相鄰的個兩兩相

20、鄰的VoronoiVoronoi多邊形多邊形所包含的點連接而成的。三角形的外接圓圓心是多邊形的公共頂點。 2.3 2.3 TIN等高線追蹤等高線追蹤TIN模型的生成對于給定的初始點集P，Delaunay三角網(wǎng)有以下特性：只要不超過4個鄰域點共圓，Delaunay三角網(wǎng)是唯一的三角網(wǎng)的外邊界構(gòu)成了點集P的凸多邊形“外殼”；沒有任何點在三角形的外接圓內(nèi)部。反之，如果一個三角網(wǎng)滿足此條件，它就是Delaunay三角網(wǎng)。Delaunay三角網(wǎng)并不能理想地滿足構(gòu)建TIN三角網(wǎng)的3點要求，但總體上它趨于最佳，為構(gòu)建TIN三角網(wǎng)的合適選擇。為了進(jìn)一步優(yōu)化三角網(wǎng)的生成，可以采用改進(jìn)的Delaunay三角網(wǎng)生成

21、方法。2.3 2.3 TIN等高線追蹤等高線追蹤TIN模型的生成改進(jìn)的Delaunay三角網(wǎng)生成方法最大化最小角原則每兩個相鄰的三角形所構(gòu)成的凸四邊形中，在對角線互換后，6個內(nèi)角中的最小角不再增大，則原三角網(wǎng)較優(yōu)。2.3 2.3 TIN等高線追蹤等高線追蹤TIN模型的生成將一系列高程點組成的點集P轉(zhuǎn)成TIN，最常用的方法是用Delaunay三角剖分方法。生成過程分兩步完成：1.利用P中點集的平面坐標(biāo)產(chǎn)生Delaunay三角網(wǎng)；具體算法參見文獻(xiàn)2D-Delaunay 三角網(wǎng)格的數(shù)據(jù)結(jié)構(gòu)與遍歷2.給Delaunay三角形中的節(jié)點賦予高程值。（需要內(nèi)插嗎？）TIN模型生成方法 間接構(gòu)網(wǎng)：先生成泰森多

22、邊形，再構(gòu)建三角網(wǎng) 直接構(gòu)網(wǎng)：離散點直接參與構(gòu)建三角網(wǎng)，如三角形生長法2.3 2.3 TIN等高線追蹤等高線追蹤等高線點位置的確定設(shè)高程為z的等高線點，通過三角形邊的兩個端點的三維坐標(biāo)分別為(x1,y1,z1)和(x2,y2,z2)，則等高線點的平面坐標(biāo)為：211121211121()()zzxxxxzzzzyyyyzzzz2.3 2.3 TIN等高線追蹤等高線追蹤等高線點的追蹤按記錄的三角形順序搜索，其過程如下：1.對給定的等高線高程h，將其與所有三角網(wǎng)的網(wǎng)點高程zi (i=1, 2, , n)，進(jìn)行比較，若zi=h，則將zi加上（或減）一個微小正數(shù)。(微量調(diào)整)2.設(shè)立三角形標(biāo)志數(shù)組，其初

23、始值為0，每一元素與一個三角形對應(yīng)，凡處理過的三角形將標(biāo)志置為1，以后不再處理。等高線高程改變后，三角形標(biāo)志數(shù)組應(yīng)清零。3.按順序判斷每一個三角形的三邊中的兩條邊是否有等高線穿過。直至搜索到等高線與網(wǎng)邊的第一個交點，稱該點為搜索起點。2.3 2.3 TIN等高線追蹤等高線追蹤等高線點的追蹤4.在三角形的另兩邊上搜索等高線在該三角形的離去邊（相鄰三角形的進(jìn)入邊），并內(nèi)插其平面坐標(biāo)。5.進(jìn)入相鄰三角形，重復(fù)第4步，直至沒有離去邊（此時等高線為開曲線）或相鄰三角形即搜索起點所在的三角形（此時等高線為閉曲線）時為止。6.對于開曲線，將已搜索到的等高線點順序倒過來，并回到搜索起點向另一方向搜索，直至到達(dá)邊界。7.當(dāng)一條等高線全部跟蹤完后，將其光滑輸出，方法與矩形格網(wǎng)等高線的繪制相同。然后繼續(xù)三角形的搜索，直至全部三角形處理完，再改變等高線高程，重復(fù)以上過程，直到完成全部等高線的繪制為止。2.4 2.4 TINTIN和格網(wǎng)模型的應(yīng)用比較和格網(wǎng)模型的應(yīng)用比較格網(wǎng)模型和TIN是應(yīng)用最廣的兩種數(shù)字地形表示方法。從數(shù)據(jù)存儲結(jié)構(gòu)、地形分辨率表達(dá)以及計算機運算處理上，它