基于標(biāo)準(zhǔn)差的地形三維表面模型建立方法

摘要：針對(duì)二維數(shù)據(jù)域的Delaunay三角剖分推廣到空間時(shí)存在的關(guān)鍵問(wèn)題，提出一種基于標(biāo)準(zhǔn)差的地形三維表面模型建立算法。與空外接圓準(zhǔn)則相比，該算法在計(jì)算時(shí)考慮了附加高程信息，引入標(biāo)準(zhǔn)差作為構(gòu)網(wǎng)判斷準(zhǔn)則。剖析了標(biāo)準(zhǔn)差的含義，為什么使用標(biāo)準(zhǔn)差以及基于標(biāo)準(zhǔn)差的剖分準(zhǔn)則，最后給出基于標(biāo)準(zhǔn)差的地形三維表面模型建立算法的具體步驟，并通過(guò)一個(gè)具體實(shí)例對(duì)算法進(jìn)行了驗(yàn)證。

關(guān)鍵詞：標(biāo)準(zhǔn)差；算法；表面模型；三角剖分；地形

中圖分類(lèi)號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)11-0295-03

TIN（triangulated irregular network，不規(guī)則三角網(wǎng)）就是用一系列互不交叉、互不重疊的連接在一起的三角形來(lái)表示地形表面。TIN作為地表的數(shù)字化表現(xiàn)手段和分析工具，在諸多領(lǐng)域，如公（鐵）路勘測(cè)設(shè)計(jì)一體化、地理信息系統(tǒng)等得到了廣泛的應(yīng)用[1]。其核心技術(shù)就是散點(diǎn)的三角剖分算法。三角剖分過(guò)程也就是TIN的建立過(guò)程，TIN的三角剖分就是按照三角剖分準(zhǔn)則，將地形采樣點(diǎn)用互不相交的直線段連接起來(lái)，并按一定的結(jié)構(gòu)進(jìn)行存儲(chǔ)[2]。目前的三角剖分均是在二維平面上進(jìn)行的，然后在三角形的頂點(diǎn)上疊加所對(duì)應(yīng)的高程值，從而形成空間三角形平面。三角剖分中使用最廣泛的算法是Delaunay直接三角剖分算法。Tsai在1993年根據(jù)其實(shí)現(xiàn)過(guò)程將DT三角剖分分成分割合并算法、三角網(wǎng)增長(zhǎng)算法和逐點(diǎn)插入算法三類(lèi)。其中，分割合并算法和三角網(wǎng)增長(zhǎng)算法是靜態(tài)過(guò)程，已形成的三角網(wǎng)不會(huì)因?yàn)樾曼c(diǎn)的插入而破壞。而逐點(diǎn)插入算法是動(dòng)態(tài)構(gòu)網(wǎng)過(guò)程，新點(diǎn)的插入會(huì)導(dǎo)致已有三角網(wǎng)的改變，而且過(guò)程簡(jiǎn)單、容易編程及實(shí)現(xiàn)[3]。

然而這些傳統(tǒng)的算法是在進(jìn)行散點(diǎn)域的三角剖分時(shí)，依據(jù)散點(diǎn)的平面分布先確定一個(gè)三角形網(wǎng)絡(luò)，然后將第三維數(shù)據(jù)如高程附加于平面三角網(wǎng)絡(luò)上，從而形成包含連續(xù)的三角形面元的地表模型，因此它是一種面向曲面（三角形面元）的表面重構(gòu)技術(shù)。面向曲面的建模方法僅考慮了曲面元素（三角形面元）的平面幾何形狀，而沒(méi)有考慮其在空間的分布情況，故對(duì)一些特殊的約束條件如陡坎、虎口、懸崖等特殊地形需進(jìn)行特殊處理[4]。這些基于二維平面上的三角剖分由于忽略了點(diǎn)的高程值，只考慮了x，y坐標(biāo)，就會(huì)導(dǎo)致出現(xiàn)如下投影變形，形成的表面與實(shí)際地形表面相差甚遠(yuǎn)，如圖1、2所示。具體來(lái)說(shuō)，就是：a）有可能將正三角形投影成狹長(zhǎng)三角形；b）有可能將狹長(zhǎng)三角形投影成正三角形。

要解決上述問(wèn)題，可以通過(guò)直接在空間上對(duì)采樣點(diǎn)進(jìn)行剖分，就是通常所說(shuō)的體剖分。體剖分的關(guān)鍵是確定剖分原則、數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)。本文在逐點(diǎn)插入算法的基礎(chǔ)上，研究了一種基于標(biāo)準(zhǔn)差的地形三維表面模型建立方法，理論和實(shí)驗(yàn)均證實(shí)了該算法簡(jiǎn)單有效，并且能解決平面三角剖分由于投影導(dǎo)致的剖分結(jié)果不準(zhǔn)確的問(wèn)題。該方法利用標(biāo)準(zhǔn)差的特性，在確定剖分準(zhǔn)則時(shí)考慮了附加高程信息，即計(jì)算標(biāo)準(zhǔn)差時(shí)用到了空間點(diǎn)的x、y、z坐標(biāo)。將標(biāo)準(zhǔn)差作為一種剖分準(zhǔn)則，生成的表面模型更符合自然地形表面。

1三角剖分準(zhǔn)則分析

三角剖分準(zhǔn)則是指三角形網(wǎng)絡(luò)的形成法則，它決定著三角形的幾何形狀和生成的TIN質(zhì)量。應(yīng)用不同的準(zhǔn)則將會(huì)得到不同的三角形網(wǎng)絡(luò)。目前常見(jiàn)的三角剖分準(zhǔn)則有六種，分別是空外接圓準(zhǔn)則、最大最小角準(zhǔn)則、最短距離和準(zhǔn)則、張角最大準(zhǔn)則、面積比準(zhǔn)則、對(duì)角線準(zhǔn)則。其中，空外接圓準(zhǔn)則、張角最大準(zhǔn)則和最大最小角準(zhǔn)則能做到三角網(wǎng)的惟一性，而這也正是Delaunay三角網(wǎng)所要求的[2]。

實(shí)際上，Lawson在1977年提出的LOP法則能優(yōu)化任何三角剖分準(zhǔn)則下得到的TIN，從而得到惟一的DT三角網(wǎng)絡(luò)[5]。其基本思想是利用Delaunay三角形的空外接圓特性[1]，即一個(gè)三角形為 Delaunay三角形，該三角形外接圓中不含有其余任何數(shù)據(jù)點(diǎn) (圖3)。方法為：對(duì)具有公共邊的兩個(gè)三角形組成的四邊形進(jìn)行判斷，如果其中一個(gè)三角形的外接圓中包含有另一三角形除公頂點(diǎn)外的第三頂點(diǎn)，則交換公共邊，圖4表示了該過(guò)程。

容易看出，現(xiàn)有的LOP法則考慮的是二維平面上的三角剖分，在LOP過(guò)程中，每個(gè)三角形都要經(jīng)過(guò)空外接圓檢測(cè)，而空外接圓檢測(cè)公式中只涉及空間點(diǎn)的x，y坐標(biāo)，忽略了空間點(diǎn)的高程信息，也就是在運(yùn)算過(guò)程中沒(méi)有考慮空間點(diǎn)的z坐標(biāo)。這導(dǎo)致的后果是剖分是平面上的剖分，其剖分結(jié)果不能準(zhǔn)確地反映空間真實(shí)地形。比如考慮空間四個(gè)點(diǎn)，其三維坐標(biāo)分別為A(-2，0，0)，B(0，-23，42)，C(2，0，0)，D(0， 23，42)。經(jīng)分析可以得出，在空間上，三角形ABD和BCD都是等邊三角形，其邊長(zhǎng)為43（可通過(guò)空間兩點(diǎn)的距離公式求各邊邊長(zhǎng)）；而三角形ABC和ACD都是等腰三角形。下面用空外接圓準(zhǔn)則對(duì)其進(jìn)行三角剖分。

首先，將這四個(gè)點(diǎn)忽略z坐標(biāo)投影到平面上，投影后各點(diǎn)的坐標(biāo)分別為A(-2，0)，B(0，-23)，C(2，0)，D(0， 23)，如圖5所示。在平面上，三角形ABC和ACD是邊長(zhǎng)為4的等邊三角形（可通過(guò)平面兩點(diǎn)的距離公式求各邊邊長(zhǎng)）；三角形ABD和BCD是等腰三角形，三角形ABD的三邊長(zhǎng)分別為AB=AD=4，BD=43，三角形BCD的三邊長(zhǎng)分別為BC=CD=4，BD=43。顯然，空外接圓準(zhǔn)則會(huì)選擇三角形形狀好的，所以選擇的結(jié)果是三角形ABC和ACD。仔細(xì)分析后可以發(fā)現(xiàn)，在空間上三角形ABC和ACD的形狀就不如三角形ABD和BCD。在空間上，三角形ABD和BCD都是等邊三角形，其邊長(zhǎng)為43，而三角形ABC和ACD都是等腰三角形。三角形ABC的三邊長(zhǎng)分別為AB=BC=43，AC=2；三角形ACD的三邊長(zhǎng)分別為AD=CD=43， AC=2。

也就是說(shuō)，空外接圓準(zhǔn)則選擇了平面上是等邊三角形而空間上是等腰三角形的那組三角形，這顯然與真實(shí)地形是不符合的。正確的選擇應(yīng)該是空間上形狀較好的三角形而不是平面上形狀較好的三角形。對(duì)于這個(gè)問(wèn)題用下面的標(biāo)準(zhǔn)差準(zhǔn)則就可以作出正確的選擇。

4算法驗(yàn)證

為了驗(yàn)證標(biāo)準(zhǔn)差算法，在Visual C++ 6.0下編程實(shí)現(xiàn)該算法，并用大數(shù)據(jù)量的數(shù)據(jù)進(jìn)行測(cè)試，將實(shí)驗(yàn)結(jié)果與空外接圓算法進(jìn)行比較。圖9是利用空外接圓準(zhǔn)則構(gòu)網(wǎng)的結(jié)果；圖10是利用標(biāo)準(zhǔn)差準(zhǔn)則構(gòu)網(wǎng)的結(jié)果。

通過(guò)兩個(gè)圖的配準(zhǔn)對(duì)比可以發(fā)現(xiàn)，其中某些四邊形的剖分結(jié)果不一樣，即選擇了不同的對(duì)角線。再把這些點(diǎn)的坐標(biāo)找出來(lái)，通過(guò)對(duì)空間三角形的邊長(zhǎng)計(jì)算（具體分析類(lèi)似前面四個(gè)點(diǎn)的計(jì)算）可以發(fā)現(xiàn)，標(biāo)準(zhǔn)差準(zhǔn)則選擇的是空間上形狀比較好的三角形，而空外接圓選擇的是平面上形狀較好的三角形。

5結(jié)束語(yǔ)

本文分析指出了二維平面上的Delaunay三角剖分等現(xiàn)有的三角剖分準(zhǔn)則存在的關(guān)鍵問(wèn)題，以空外接圓規(guī)則建立的空間三角形網(wǎng)絡(luò)，其三角形在空間上的形狀不一定好，也就不能保證空間上的網(wǎng)絡(luò)質(zhì)量。所以在逐點(diǎn)插入算法基礎(chǔ)上提出了基于標(biāo)準(zhǔn)差的剖分準(zhǔn)則，研究設(shè)計(jì)了一種基于標(biāo)準(zhǔn)差的三角剖分方法，算法思路簡(jiǎn)單清晰，而且避免了空外接圓準(zhǔn)則的一些明顯不足。該算法在計(jì)算時(shí)考慮了平面三角剖分中忽略的高程信息，生成的三角形能保證空間上具有較好的形狀，因而更符合實(shí)際地形表面。然而通過(guò)該算法生成的表面模型由于建立在逐點(diǎn)插入算法的基礎(chǔ)上，其本質(zhì)上還是2.5維的，并不是三維的。但是與空外接圓準(zhǔn)則比起來(lái)，由于在計(jì)算時(shí)考慮了高程信息，剖分結(jié)果相對(duì)更準(zhǔn)確一些。

參考文獻(xiàn)：

［1］劉學(xué)軍，符鋅砂，趙建三.三角網(wǎng)數(shù)字地面模型快速構(gòu)建算法研究[J].中國(guó)公路學(xué)報(bào)，2000，13（2）：31-36.

[2] 湯國(guó)安，劉學(xué)軍，閭國(guó)年.數(shù)字高程模型及地學(xué)分析的原理與方法[M].北京：科學(xué)出版社，2005:103－133.

[3]TSAI V J D.Delaunay triangulations in TIN creation: an overview and a lineartime algorithm[J].Int J of GIS，1993，7（6）：501-524.

[4] 劉學(xué)軍，符鋅砂.三角網(wǎng)數(shù)字地面模型的理論、方法現(xiàn)狀及發(fā)展[J].長(zhǎng)沙交通學(xué)院學(xué)報(bào)，2001，17（2）：24-31.

[5]LAWSON C L. Software for C1 surface interpolation[C]//Mathematical Software Ⅲ.New York:Academic Press，1977:161－194.

[6]余錦華，石北源，楊維權(quán).概率論與數(shù)理統(tǒng)計(jì)[M].廣州：中山大學(xué)出版社，2000:24-33.

[7]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu):C語(yǔ)言版[M].北京：清華大學(xué)出版社，1996：44-54.

[8]George Shepherd. Visual C++.NET技術(shù)內(nèi)幕[M].6版.北京：清華大學(xué)出版社，2004:243-271.

[9]湯國(guó)安，楊昕.ArcGIS 地理信息系統(tǒng)空間分析實(shí)驗(yàn)教程[M].北京：科學(xué)出版社，2006:308-360.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”