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

周 婷， 彭正洪， 密新武

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

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

周 婷， 彭正洪， 密新武

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

這樣點(diǎn)(Xmin, Ymin)和(Xmax, Ymax)可以構(gòu)建成一個(gè)矩形區(qū)域，如下圖2所示。我們稱這一矩形區(qū)域?yàn)椤半x散點(diǎn)面積區(qū)域”。

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

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

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

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

3） 分區(qū)個(gè)數(shù)與分區(qū)指針。當(dāng)f的值取定后，分區(qū)個(gè)數(shù)也隨即而定。由于離散點(diǎn)面積區(qū)域的矩形一致，因此，最后一個(gè)分區(qū)的半徑應(yīng)該小于等于矩形對(duì)角線，于是有因此，分區(qū)個(gè)數(shù)為每一個(gè)分區(qū)設(shè)定一個(gè)指針，作為每一個(gè)分區(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)生長(zhǎng)法構(gòu)網(wǎng)時(shí)只在A區(qū)和B區(qū)搜索第三點(diǎn)，一旦A區(qū)的所有點(diǎn)都參與構(gòu)網(wǎng)了，則將分區(qū)指針移向B區(qū)，再對(duì)B區(qū)進(jìn)行構(gòu)網(wǎng)，依此類推，直至所有分區(qū)都構(gòu)網(wǎng)結(jié)束。

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

3 改進(jìn)算法的實(shí)現(xiàn)與測(cè)試

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

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

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

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

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

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

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

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

圖4 改進(jìn)算法測(cè)試結(jié)果圖

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

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

4 結(jié) 束 語

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

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

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

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

[4] 祝志恒, 傅鶴林, 蒲 浩, 等. 構(gòu)建Delaunay三角網(wǎng)的一種新型生長(zhǎng)法——?dú)ね獠迦敕╗J]. 鐵道科學(xué)與工程學(xué)報(bào), 2007, 4(6): 67-72.

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

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

[7] 湯國(guó)安, 劉學(xué)軍, 閭國(guó)年. 數(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àn)橛?jì)算機(jī)應(yīng)用。E-mail：305302163@qq.com

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

E-mail：laopeng129@vip.sina.com

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