基于標準差的地形三維表面模型建立方法

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

關鍵詞：標準差；算法；表面模型；三角剖分；地形

中圖分類號：TP311文獻標志碼：A

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

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

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

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

1三角剖分準則分析

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

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

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

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

也就是說，空外接圓準則選擇了平面上是等邊三角形而空間上是等腰三角形的那組三角形，這顯然與真實地形是不符合的。正確的選擇應該是空間上形狀較好的三角形而不是平面上形狀較好的三角形。對于這個問題用下面的標準差準則就可以作出正確的選擇。

4算法驗證

為了驗證標準差算法，在Visual C++ 6.0下編程實現該算法，并用大數據量的數據進行測試，將實驗結果與空外接圓算法進行比較。圖9是利用空外接圓準則構網的結果；圖10是利用標準差準則構網的結果。

通過兩個圖的配準對比可以發現，其中某些四邊形的剖分結果不一樣，即選擇了不同的對角線。再把這些點的坐標找出來，通過對空間三角形的邊長計算（具體分析類似前面四個點的計算）可以發現，標準差準則選擇的是空間上形狀比較好的三角形，而空外接圓選擇的是平面上形狀較好的三角形。

5結束語

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

參考文獻：

［1］劉學軍，符鋅砂，趙建三.三角網數字地面模型快速構建算法研究[J].中國公路學報，2000，13（2）：31-36.

[2] 湯國安，劉學軍，閭國年.數字高程模型及地學分析的原理與方法[M].北京：科學出版社，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] 劉學軍，符鋅砂.三角網數字地面模型的理論、方法現狀及發展[J].長沙交通學院學報，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]余錦華，石北源，楊維權.概率論與數理統計[M].廣州：中山大學出版社，2000:24-33.

[7]嚴蔚敏，吳偉民.數據結構:C語言版[M].北京：清華大學出版社，1996：44-54.

[8]George Shepherd. Visual C++.NET技術內幕[M].6版.北京：清華大學出版社，2004:243-271.

[9]湯國安，楊昕.ArcGIS 地理信息系統空間分析實驗教程[M].北京：科學出版社，2006:308-360.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”