周 婷， 彭正洪， 密新武

（武漢大學(xué)城市設(shè)計學(xué)院，湖北 武漢 430072）

Delaunay三角網(wǎng)生長算法改進與實現(xiàn)

周 婷， 彭正洪， 密新武

（武漢大學(xué)城市設(shè)計學(xué)院，湖北 武漢 430072）

對一般三角網(wǎng)生長法做了簡要介紹和分析，針對限制算法效率提高的關(guān)鍵步驟——“搜索符合條件的第三點”，提出了一種“第三點分區(qū)搜索法”的改進算法。通過一系列的圓弧將離散點區(qū)域劃分成多個分區(qū)，構(gòu)網(wǎng)時規(guī)定只可在當(dāng)前分區(qū)和相鄰的下一分區(qū)搜索第三點，當(dāng)該分區(qū)的離散點搜索完畢后進入下一分區(qū)。在Microsoft Visual Studio 2008的環(huán)境下使用C++進行編程測試，結(jié)果表明，該算法能夠加快構(gòu)網(wǎng)速度，生成的三角形形狀良好，具有一定的實際效用。

Delaunay；三角網(wǎng)生長法；分區(qū)搜索

DEM，Digital Elevation Model，數(shù)字高程模型，主要研究如何將密集分布的采樣位置坐標(biāo)點，通過一定的規(guī)則組織在一起，以形成實際的地形空間特征。DEM作為 GIS 數(shù)據(jù)庫中相當(dāng)重要的空間信息和地形分析模型，它的高效構(gòu)建算法一直是許多學(xué)者研究的焦點。在數(shù)字地形建模中，TIN(Triangulated Irregular Network)，不規(guī)則三角網(wǎng)，是DEM的一個主要模型，它通過生成一系列互不重疊又相互臨接的三角形來逼近實際的地形表面。在所有構(gòu)建TIN的構(gòu)網(wǎng)方法中，Delaunay三角網(wǎng)以其相當(dāng)強的地形擬合綜合能力，常常被選取用來生成TIN。

Delaunay三角網(wǎng)是通過滿足空外接圓法則和最大最小角法則來保證三角網(wǎng)的唯一性。Delaunay 構(gòu)網(wǎng)方法一般有3種：分割合并法、逐點插入法和三角網(wǎng)生長法。其中，分割合并法的優(yōu)點是其實現(xiàn)效率高，缺點是由于算法中大量的遞歸調(diào)用導(dǎo)致算法相當(dāng)復(fù)雜，并且耗用內(nèi)存很大；逐點插入法的優(yōu)點是算法實現(xiàn)簡單，內(nèi)存占用少，缺點是時間復(fù)雜度差，構(gòu)網(wǎng)速度慢；而三角網(wǎng)生長法不像分割合并法那樣大量的搜索邊集、子集，進行并網(wǎng)操作，在算法復(fù)雜度上要相對簡單一些。但是三角網(wǎng)生長法的關(guān)鍵步驟“搜索滿足條件的第三點”，由于其搜索的盲目性導(dǎo)致了大量的時間消耗，特別是隨著離散點數(shù)據(jù)量的增加，其時間復(fù)雜度也成倍增加。因此本文首先對三角網(wǎng)生長法的實現(xiàn)算法進行了簡要的介紹和分析，在此基礎(chǔ)上以縮小第三點搜索范圍為原則，對三角網(wǎng)生長法進行了一定程度的優(yōu)化，最后對算法進行實現(xiàn)，并通過結(jié)果分析比較來驗證算法優(yōu)化的效率和可行性。

1 三角網(wǎng)生長法算法與效率分析

三角網(wǎng)生長法的基本算法思路是首先找到所有離散點中相距最短的兩點，將其連接作為首三角形的初始邊（基邊）。然后，按照D-TIN判斷法找到包含此邊的Delaunay三角形的第三點，連接此點與初始邊的兩個頂點構(gòu)成首三角形；再按 D-TIN判斷法以首三角形中另外兩條邊為基線，分別搜索第三點構(gòu)成另外兩條邊的Delaunay三角形，依次循環(huán)，直至所有離散點均成為D-TIN的端點。

現(xiàn)假定待構(gòu)網(wǎng)的離散點的個數(shù)為n，下面對三角網(wǎng)生長法的基本步驟進行簡單介紹與實現(xiàn)效率分析：

第一步：在包含n離散點的點集中尋找任意兩個點之間的距離最小的點對，將此兩點連接起來作為初始基線。此步驟中需要進行 n*(n-1)/2次的距離計算，并在這n*(n-1)/2個距離結(jié)果中找到最小的距離值，因此，此步驟的時間復(fù)雜度為O(n2)；

第二步：找首三角形。應(yīng)用Delaunay判斷法在初始基線的右邊搜索第三點。D-TIN判斷法的具體方法是以基線的兩個端點作為向量的起點，依次將其余的未構(gòu)網(wǎng)的 n-2個點作為向量的終點，利用公式計算兩個向量間夾角的余弦值，其中P1和P2分別為基線的兩個端點，Pi為還未參與構(gòu)網(wǎng)的其他點。在這所有的余弦值中，找余弦值最小的點作為首三角形的第三點。此步驟計算n-2個余弦值，并從結(jié)果中找到最小余弦值，因此時間復(fù)雜度也是O(n)；

第三步：以三角形的三條邊為基線，尋找與基線構(gòu)成三角形的可能的擴展點。一條基線最多是兩個三角形的公共邊，因此，當(dāng)基線在尋找可能擴展點的時候，應(yīng)保證擴展點與基線已構(gòu)成的三角形的第三點分別位于基線的兩側(cè)。否則可能會導(dǎo)致三角形的重疊。以下圖（1）的三角形為例，尋找基線T1T2的可能擴展點判斷方法如下：

首先給出基線T(1)T(2)的直線方程，記T1(x1, y1), T2(x2, y2)，利用向量的叉乘計算基線的函數(shù)方程，直線上任一點(x, y)有：

在這里我們可以對未構(gòu)網(wǎng)的離散點P(x, y)及上圖中T(3)點分別代入直線方程中，并判斷f (x, y)的符號，給定以下約定：

若 f( P)與 f( T (3))同號（即同為正區(qū)域或負(fù)區(qū)域），則 P點不是可能擴展點；若 f( P)與f( T (3))異號，則P點是可能的擴展點。

此步驟主要是對所有未構(gòu)網(wǎng)的點進行比較判斷，其執(zhí)行的效率也是O(n)，但是，以后每次構(gòu)建一個三角形都要進行此步，因此，其最終的時間復(fù)雜度是O(n2)；

第四步：對于可能的擴展點判斷是否滿足Delaunay原則。此步驟類似于尋找首三角形的第三點，即在所有可擴展點中尋找余弦值最小的點且構(gòu)成的邊不能為重復(fù)擴展邊。此過程的時間復(fù)雜度為；

第五步：重復(fù)第三、第四步直到所有點都連線完畢，則構(gòu)網(wǎng)結(jié)束。

上面分五步介紹了三角網(wǎng)生長法構(gòu)網(wǎng)的步驟，并在每一步后面給出了時間復(fù)雜度的分析。由分析可知，此算法的大部分時間都用在搜索符合Delaunay法則的第三點上了，而由于搜索的盲目性使得很多值的計算是多余的，而且計算所得的中間結(jié)果加重了比較篩選的負(fù)擔(dān)，隨著數(shù)據(jù)點的增加，這種弊端更加的明顯，構(gòu)網(wǎng)速度愈發(fā)減緩，因此,需要對一般的三角網(wǎng)生長法進行改進，以提高構(gòu)網(wǎng)速度。

2 三角網(wǎng)生長法的改進算法

改進算法的基本思路是：將所有的離散點進行區(qū)域劃分，依次對每個區(qū)域進行構(gòu)網(wǎng)，構(gòu)網(wǎng)方法依舊以三角網(wǎng)生長法為主體，但在進行第三點搜索時約定只在本區(qū)域和相鄰區(qū)域中進行，第三點搜索范圍這樣設(shè)定既防止了大量不必要的計算比較，又減少了子網(wǎng)的并網(wǎng)操作的復(fù)雜性。

在改進算法中，如何進行合理的區(qū)域劃分成為關(guān)鍵所在，直接影響著最終的構(gòu)網(wǎng)效率。在這里，我們首先找到所有離散點中的X、Y坐標(biāo)的最大最小值，記作Xmin, Ymin, Xmax, Ymax。

這樣點(Xmin, Ymin)和(Xmax, Ymax)可以構(gòu)建成一個矩形區(qū)域，如下圖2所示。我們稱這一矩形區(qū)域為“離散點面積區(qū)域”。

圖2 離散點區(qū)域面積

在離散點面積區(qū)域中，以 (Xmin, Ymin)為圓心，以不同的半徑畫一系列圓弧與矩形邊界相交構(gòu)成閉區(qū)域，每一個閉區(qū)域我們稱為一個分區(qū)，在搜索第三點的時候只允許在當(dāng)前分區(qū)和相鄰的下一分區(qū)進行搜索，其他分區(qū)的點暫時被排除在外。在給出具體算法前，我們先闡述幾個關(guān)鍵點：

1） 圓心選取為(Xmin, Ymin)；

2） 半徑選取。半徑的取值相當(dāng)關(guān)鍵，若半徑取值過小會導(dǎo)致在當(dāng)前分區(qū)中無法找到合理的第三點，若半徑取值過大或?qū)е滤惴ㄐ侍岣卟幻黠@，因此，半徑不能盲目選取。在這里，離散點區(qū)域面積很容易計算得到而離散點的數(shù)據(jù)點個數(shù)已知為n，這樣可以得到離散點的平均密度為ρ =S/n。當(dāng)離散點較為密集的時候，我們可以粗略的認(rèn)為離散點的相鄰兩點間平均距離的平方為以 d為基礎(chǔ)和標(biāo)準(zhǔn)來選取半徑的值就會比較合理。理想情況下，第i個分區(qū)的半徑為但是，由于d的值是一個粗略估計的距離值，而且實際上任意兩點間的距離并不是相等的，因此，直接以為第i個分區(qū)的半徑并不合理。于是，我們引入相關(guān)系數(shù) f，用來將d進行適當(dāng)放大，得到可取值為2,3,4…根據(jù)實際需要f的值是可變的，f的取值也直接影響著分區(qū)個數(shù)的多少。

3） 分區(qū)個數(shù)與分區(qū)指針。當(dāng)f的值取定后，分區(qū)個數(shù)也隨即而定。由于離散點面積區(qū)域的矩形一致，因此，最后一個分區(qū)的半徑應(yīng)該小于等于矩形對角線，于是有因此，分區(qū)個數(shù)為每一個分區(qū)設(shè)定一個指針，作為每一個分區(qū)的標(biāo)志。分區(qū)搜索法的分區(qū)方法如圖3所示，M為圓心，1，2，3，4，5分別代表當(dāng)前分區(qū)的指針，構(gòu)網(wǎng)從A區(qū)開始，A區(qū)使用三角網(wǎng)生長法構(gòu)網(wǎng)時只在A區(qū)和B區(qū)搜索第三點，一旦A區(qū)的所有點都參與構(gòu)網(wǎng)了，則將分區(qū)指針移向B區(qū)，再對B區(qū)進行構(gòu)網(wǎng)，依此類推，直至所有分區(qū)都構(gòu)網(wǎng)結(jié)束。

圖3 分區(qū)搜索法的區(qū)域劃分

3 改進算法的實現(xiàn)與測試

在本算法中采用容器類(Vector)來存儲數(shù)據(jù)。Vector＜CPoint＞T1 用來存儲每一個分區(qū)內(nèi)的離散點，Vector＜CLine＞T2用來存儲基線（邊），Vector＜CTriangles＞T3用來存儲構(gòu)建成的三角形。在讀入點的時候，采用 T1.push_back(point)將點輸入容器中，同理通過 T2.push_back(line)將滿足條件的邊存入容器T2中，將結(jié)果三角形存入T3中。

采用“分區(qū)搜索法”搜索第三點，以三角網(wǎng)生長法為主體來進行分區(qū)構(gòu)網(wǎng)，基本步驟如下：

第一步：對所有點進行搜索比較，找出所有離散點中的Xmin,Ymin, Xmax,Ymax，建立離散點面積區(qū)域；

第二步：以(Xmin,Ymin)為圓心，以f*i*d為半徑畫圓弧，將離散點面積區(qū)域劃分為N個區(qū)域，并給每個區(qū)域賦予指針，唯一標(biāo)示所指區(qū)域。

第三步：計算每一個離散點與圓心的距離，根據(jù)距離值與區(qū)域半徑值得比較可知每一個離散點的所屬區(qū)域，并將該離散點存儲在所屬區(qū)域的容器中。

第四步：在第k區(qū)域，根據(jù)Delaunay原則，按照第二節(jié)所述的三角網(wǎng)生長算法進行三角網(wǎng)的構(gòu)建，直到當(dāng)前區(qū)域內(nèi)的所有點都被擴展完成。

第五步：將區(qū)域指針加1，進入下一區(qū)域，重復(fù)第四步。直到所有的離散點都被擴展。構(gòu)網(wǎng)結(jié)束。

按照以上的算法思路和步驟，筆者在Microsoft Visual Studio 2008的環(huán)境下，進行了三角網(wǎng)生長法改進算法的實驗，計算結(jié)果如圖4所示：

圖4 改進算法測試結(jié)果圖

在相同的計算條件下，將一般的三角網(wǎng)生長法與改進后分區(qū)搜索法的耗時比較結(jié)果如表1所示。通過實驗對比，雖然本算法生成的三角網(wǎng)與一般生長法在某些細(xì)節(jié)地方存在些許差異，但是三角形形狀良好，耗時也有較大幅度的降低，構(gòu)網(wǎng)速度有明顯提高。

表1 改進算法和一般三角網(wǎng)生長法的耗時比較

4 結(jié) 束 語

本文首先對三角網(wǎng)生長算法給出了簡要的介紹和分析，然后針對算法各步的耗時找到限制算法效率的關(guān)鍵步驟——搜索符合條件的第三點，為提高這一步的執(zhí)行效率，給出了三角網(wǎng)生長法的改進算法，改進的三角網(wǎng)生長法的關(guān)鍵所在是確定分區(qū)半徑。最后通過編程實驗，將同等條件下的一般三角網(wǎng)生長法的執(zhí)行時間與改進后的三角網(wǎng)分區(qū)搜索生長法的執(zhí)行時間相比較，測試結(jié)果顯示改進后的算法在效率上有了很大的提高。

[1] 徐道柱, 劉海硯. Delaunay三角網(wǎng)建立的改進算法[J]. 測繪與空間地理信息, 2007, 30(1): 38-41.

[2] 劉永和, 謝洪波, 袁 策. 一種基于三角網(wǎng)擴張法的 Delaunay三角網(wǎng)逐塊歸并算法[J]. 測繪科學(xué), 2007, 32(3): 52-54.

[3] 郭兆勝, 張登榮. 一種改進的高效 Delaunay三角網(wǎng)的生成算法[J]. 遙感信息, 2005, (1): 15-17.

[4] 祝志恒, 傅鶴林, 蒲 浩, 等. 構(gòu)建Delaunay三角網(wǎng)的一種新型生長法——殼外插入法[J]. 鐵道科學(xué)與工程學(xué)報, 2007, 4(6): 67-72.

[5] 侯俊杰. 深入淺出MFC (第2版)[M]. 武漢: 華中科技大學(xué)出版社.

[6] Stanley B L, Josée Lajoie 著. C++ primer(第3版)[M].潘愛民, 張麗譯. 北京: 中國電力出版社, 2002: 210-227.

[7] 湯國安, 劉學(xué)軍, 閭國年. 數(shù)字高程模型及地學(xué)分析的原理與方法[M]. 北京: 科學(xué)出版社, 2005: 1.

An Improved Delaunay Triangle Network Growth Algorithm and its Implementation

Zhao Ting, Peng Zhenghong, Mi Xinwu
( School of Urban Design, Wuhan University, Wuhan Hubei 430072, China )

A brief introduction is given for the general Triangle network growth algorithm. An improved algorithm named as “the partition search method of the third point” is provided. First, a series of circular arcs are used to divide the area of discrete points into multiple partitions. Then - the third point is restricted to be searched only in the current partition and the next adjacent partition when building the triangle network. After all the discrete points are added into the triangle network in current partition, the search can be moved into the next partition. Last, the C++ programming language is used to test the algorithm in Microsoft Visual Studio 2008 environment. The result shows that the improved algorithm can improve the speed of building the network, and the generated triangular shape is good.

Delaunay; triangle network growth algorithm; partition search

P 221.1

A

2095-302X (2013)05-0012-04

2013-07-15；定稿日期：2013-07-15

周 婷（1989-），女，湖北天門人，碩士研究生，主要研究方向為計算機應(yīng)用。E-mail：305302163@qq.com

彭正洪（1967-），男，湖北天門人，教授，博士研究生導(dǎo)師，主要研究方向為計算機圖形圖像處理，數(shù)字化設(shè)計與仿真。

E-mail：laopeng129@vip.sina.com

密新武（1953-），男，湖北武漢人，教授，主要研究方向為計算機輔助設(shè)計。E-mail：mixinwu@126.com