結合二叉樹和Graham掃描技術的高效Delaunay三角網構建算法
2010-01-01 00:00:00李根鄒志鞠時光
計算機應用研究 2010年3期
摘 要:為了提高不規則三角網的構建速度，提出了一種高效構建Delaunay三角網算法。首先對平面上的離散點集按一定的閾值進行分塊，建立子塊索引二叉樹，然后利用Graham掃描技術對各子塊構建Delaunay三角網，最后自底向上合并具有相同父節點的子塊。通過具體實驗與其他構網算法比較，該算法在構網速度上具有明顯的優越性。
關鍵詞:二叉樹; Delaunay三角網; Graham掃描技術; 數據分塊
中圖分類號:TP2文獻標志碼:A
文章編號:1001-3695(2010)03-0894-03
doi:10.3969/j.issn.1001-3695.2010.03.023
Efficient algorithm of constructing Delaunay triangulation based on
binary tree and Graham scanning technique
LI Gen， ZOU Zhi-wen，JU Shi-guang
(College of Computer， Jiangsu University， Zhenjiang Jiangsu 212013， China)
Abstract:In order to enhance the speed of constructing triangulated irregular network， this paper proposed an efficient algorithm of constructing Delaunay triangulation. Firstly， split the set of discrete points into several subsets with a threshold value and built an index binary tree during that process. Secondly it built Delaunay triangulation on these subsets by Graham scanning technique. Finally， merged the blocks with the same parent node from bottom to top. The result of the experiments shows that the algorithm， compared with other ways， has a distinct superiority in the speed of constructing irregular network.
Key words:binary tree; Delaunay triangulation; Graham scanning technique; dataset partition
不規則三角網(TIN)是一種表示數字高程模型的方法，它既能夠避免地形平坦時的數據冗余，又比網格更能反映原始地形的細節， 而且具有地表重構精度高以及對不規則區域數據點分布適應能力強的特點。Delaunay三角網在這方面表現最為出色，因此常被用于TIN 的生成。Delaunay三角網的實現算法有很多，主要分為三角網生長法、逐點插入法和分治法[1~4]三類。三角網生長法較為簡單， 但每次尋找最優點時需要遍歷整個點集并比較， 平均時間復雜度為O(n2)[5] ，不適合大數據量的三角網生成;逐點插入法實現較簡單、占用內存較小，但在插入新點時需要在三角形鏈表中搜索包含新點的三角形， 算法的平均時間復雜度為O(n log n)， 最壞情況下的時間復雜度為O(n2)[5];分治算法最為高效，構網耗用時間與離散點數量基本成正比[6]，由于用遞歸的方法實現，對內存要求較高，算法相對較復雜。
劉永和等人[7]提出了一種逐塊歸并算法，先把平面離散點集劃分成若干個子塊，再對各子塊用三角網擴張法構網，然后對相鄰子網合并優化。該算法采用分塊的思想使構網時間與點數接近線性關系，但對子網進行分塊時沒有建立子塊的索引，對子網合并時效率不高，且子塊中點的數量比較大時，三角網擴張法效率很低。宋曉宇等人[8]在構網時采用Graham掃描法，算法簡單易于實現，但是在構網過程中尋找待判斷點的可見點時需要對排在該點后面所有的點進行判斷，時間復雜度接近O(n2)。郭兆勝等人[9]在構建三角網時結合了分治法和逐點插入法，但子塊構建效率不高。石松等人[10]提出了一種基于四叉樹分塊構建三角網算法，較好地解決了分治算法在構建大數據量不規則三角網時的不足， 總體時間復雜度下降了， 但算法變得較為復雜，不易實現。
針對上述算法構網時存在的一些不足，本文提出了一種結合二叉樹和Graham掃描技術的Delaunay三角網高效構建算法。對于平面上的離散點集，通過對點集的最小外包矩形進行多次分割得到子塊集合，在分割過程中伴隨著子塊索引二叉樹的生成;然后利用Graham掃描技術對各子塊構建初始三角網再優化成Delaunay三角網;最后從下到上對具有相同父節點的子塊進行合并，直到根節點的生成，此時Delaunay三角網構造完成。
1 數據的二叉樹分割
采用分割—合并算法的前提是對數據進行分割，并能進行高效的搜索，二叉樹顯然符合這兩點。由于點集分布的不均勻性，如何對點集進行分割直接影響后面子集的合并效率。設點集P的最小外包矩形為R〈pl，pr〉。其中pl(x1，y1)、pr(x2，y2)分別為矩形R的左下角點和右上角點。如果R中包含點的個數超過指定的閾值，則對其分割:當(x2-x1)>(y2-y1)，則對R進行縱向分割生成左右相等的子塊，否則進行橫向分割生成上下相等的子塊，這樣保證分割的子塊橫向縱向長度相接近。繼續對新產生的子塊進行分割，依此遞推直到所有分割的子塊中點的個數在指定的閾值內。最終子塊的個數取決于離散點的分布和子塊包含點數的閾值。圖1為對區域R進行分割產生的子塊，子塊包含點數的閾值為10，生成的子塊索引二叉樹如圖2所示。
分割過程中生成的索引二叉樹T的每一個節點包含一個矩形區域，父節點的矩形區域是其左右子節點矩形區域的和，左右子節點矩形區域大小相等。父節點的左右子節點包含的矩形區域總是相鄰的，因此子塊合并時能保證對應區域相鄰。二叉樹的葉子節點對應最終的分割子塊，每個子塊包含一定數量的離散點。如果子塊中點的個數小于3，則將其與兄弟節點合并形成新的葉子節點。查找點所屬的子塊就是搜索二叉樹葉子節點的過程，根據點是否在節點包含的區域內決定搜索路徑，因為二叉樹同一層次的節點不包含重疊的區域，所以搜索路徑是惟一的，且判斷次數不大于二叉樹的高度。
2 Delaunay三角網的構建
2.1 數據結構
在Delaunay三角網的構建過程中，數據結構的設計直接影響算法的性能，合理的數據結構不僅能減少數據存儲容量，還能提高算法執行效率。本算法定義以下數據結構:
struct Point{//頂點類
double px; //頂點橫坐標
double py; //頂點縱坐標
};
struct Edge{//有向邊類
Point * begPt;//邊的起點
Point * endPt;//邊的終點
Triangle * leftTri;//邊的左鄰三角形
Triangle * rightTri; //邊的右鄰三角形
};
struct Triangle{//三角形類
Edge * edge[3]; //三角形的三條邊
Point * pt[3]; //三角形的三個頂點
};
為了便于三角形的擴張和拓撲關系的自動構建，邊和頂點都按逆時針方向存儲，而且點和邊有一定的對應關系(圖3)。三角形ABC的有向邊edge[0]的起點與pt[0]對應，終點與pt[1]對應，同理edge[1]、edge[2]的起點分別對應pt[1]和pt[2]，終點分別對應pt[2]和pt[0]。生成一個三角形T時，根據其三個頂點便可以決定相應的三條有向邊，且每條邊的左鄰接三角形就是三角形T。
2.2 利用Graham掃描技術構建各子塊三角網
2.2.1 子塊三角網構建算法
點集區域二叉樹分割后，對各葉子節點對應的子塊利用Graham掃描技術構建初始三角網。在構網過程中，搜索到待判斷點的可見點后將可見點壓入凸包頂點集C，新生成的三角形T插入三角形鏈表，T對應的三條有向邊插入有向邊鏈表，同時更新相關有向邊對應的右鄰接三角形為T。
定義1 通過Graham 掃描法按照與水平方向夾角對離散點進行排序得到P={p0，p1，p2，…，pn-1}，pi為待判斷點，線段pipj+1與線段p0pj相交(j>i)，當j取最小值時，稱pj為pi可見點，pi為pj的被可見點。
構建子塊三角網具體步驟如下:
a)找出點集中縱坐標值最小點設為p0，將p0與點集中其他點連線求出直線p0pi與水平方向的夾角θi，按θi從小到大的順序對點的序號進行編號，經過排序后P={p0，p1，p2，…，pn-1}。把p0、p1分別壓入凸包頂點集C，索引t初始值為1。
b)確定C中最后的點為待判斷點pi，找到pi的可見點pk，將pk壓入C，連接pipi+1，pipi+2，…，pipk，新生成Δp0pipi+1，t加1。
c)如果t≥k，轉步驟d)，連接線段ptpt+1，生成新的Δp0ptpt+1和Δptpipt+1，t加1，轉步驟c)。
d)如果C中點的個數小于4，轉步驟e)，設C中最后三個點分別為pi、pj、pk，如果線段p0pj與pipk相交則pj是凸包頂點，轉步驟e);否則將pj從C中刪除，連接線段pipk生成新的Δpjpipk，轉步驟d)。
e)如果t 2.2.2 子塊構網實例 下面以點集P為例描述利用Graham掃描技術生成初始三角網的過程，利用Graham 掃描法按照與水平方向夾角對離散點進行排序，得到P={p0，p1，p2，p3，p4，p5，p6}，如圖4(a)所示。 a)初始情況下，凸包頂點集C={p0，p1}，以p1為待判斷點，因為線段p1p5與p0p4相交，所以p4為p1的可見點，連接p1p2、p1p3、p1p4，新生成Δp0p1p2，點p4壓入C;連接p2p3生成Δp0p2p3和Δp2p1p3;連接p3p4生成Δp0p3p4和p3p1p4(圖4(b))。 b)C={p0，p1，p3}，以p4為待判斷點搜索到可見點p6，連接p4p5、p4p6新生成Δp0p4p5，點p5壓入C;連接p5p6產生新的Δp0p5p6和Δp5p4p6(圖4(c))。 c)C={p0，p1，p4，p6}，C中最后三個點分別為p1、p4、p6，因為線段p0p4與p1p6不相交，則判定p4不是凸包頂點，將p4從C中刪除;連接p1p6，新生成Δp4p1p6。C中點的個數為3，結束判斷，最后得到凸包頂點C={p0，p1，p6}，初始三角網如圖4(d)所示。 2.2.3 子網優化 利用Graham掃描技術構建的子三角網并不完全符合Delaunay三角網的兩個性質，即空外接圓特性以及最小角最大原則，需要對子三角網進行優化。根據上文設計的數據結構，有向邊存儲了左右鄰接三角形，因此以有向邊為單位進行子網優化更為高效。 子網優化方法是判斷有向邊的左右鄰接三角形的對角之和是否大于180°(圖5)，如果是則滿足性質;否則交換對角線，生成新的兩個三角形插入三角形鏈表，有向邊插入有向邊鏈表，刪除原來的有向邊和三角形，同時更新相關有向邊指向的鄰接三角形。 2.3 基于二叉樹的子網合并 子網合并從二叉樹的葉子節點開始自底向上合并，具有相同父節點的葉子節點合并后生成新的節點取代其父節點，于是合并后新生成的節點成了葉子節點。重復上述合并過程直到二叉樹的根節點產生為止，此時所有的子網合并結束，平面離散點集的Delaunay三角網生成。以圖2為例，a)1000與1001合并成100，1100與1101合并成110;b)000與001合并成00，100與101合并成10，110與111合并成11;c)00與01合并成0，10與11合并成1;d)0與1合并成根節點，合并過程結束。 對子塊構建三角網時存儲了子塊的凸包頂點，合并子網時所關聯的點都是凸包上的頂點，因此合并子網先要找出子網對應凸包的上切線和下切線，確定合并過程中考慮的點集，之后再逐步構造三角網，最后對新生成的三角形優化使之符合Delaunay三角網性質。如圖6所示，先找出凸包的上切線p1p5和下切線p4p8，以p1p5為起始擴展邊找到的最優點為p6，由p1p6擴展得到的最優點為p2，直到最優點為p4或p8，合并結束。 子網合并算法在尋找最優的頂點時只從已經生成的凸包頂點集中查找， 減少了尋找最優點時的遍歷時間， 使得在數據量較大、分塊較多的情況下合并子網時間與凸包中頂點的個數呈線性關系。 3 性能分析和耗時測試 假設平面離散點個數為N，平均每個子塊包含M個點，則至少將點集分割成N/M個子塊，因此在分割過程中建立的二叉樹高度為log(N/M)。對包含M個點的子塊利用Graham掃描技術構網時，先要對子塊中的點集進行排序，使用快速排序法，最好情況下時間復雜度為O(M log M)。子塊構網過程中，確定凸包頂點時搜索范圍比較小，不需要判斷點集中所有的點，平均時間復雜度為O(M)，子網優化只是對有向邊判斷或優化數遍， 復雜度為O(K)，K為有向邊條數。綜合以上分析，當對點集合理分割，使子塊中點的數量在一定的閾值內，構建Delaunay三角網所需時間與點的數量近似呈線性關系。 筆者在VC 6.0上用C++語言實現了構網程序，運行結果正確。圖7為隨機生成的2 000個點所構建的Delaunay三角網。下面用隨機生成的點根據子塊閾值不同對運行結果進行比較，微機環境為Pentium4 1.8 GHz CPU，256 MB內存。對于隨機生成的離散點集，可以認為是均勻分布在平面上，采用二叉樹分割法產生子塊的個數只與子塊包含點的閾值有關，閾值越大，子塊個數越少，反之子塊個數越多。測試數據如下:隨機點數為2 000，設定子塊包含點的閾值分別為1 000、500、400、300、200、150、100、50，記錄各自構網消耗的時間及分割子塊個數。實驗結果如表1所示，當閾值為200時，子塊個數為14，此時構網時間最短，當閾值小于200時，構網速度開始下降。經過分析得出如下結論:閾值很大時，分割生成的子塊數量小，對單個子塊構網時間長;閾值很小時，分割生成的子塊數量大，雖然對單個子塊構網時間比較短，但需要多次對相鄰子塊合并，總體效率不高。 表1 不同閾值的2 000個離散點構網耗時和子塊數 閾值構網時間/ms生成子塊數閾值構網時間/ms生成子塊數 1 0001 440320063714 5001 176515064317 4001 024610066824 30083595067349 對平面點集構建三角網時，只有合理確定閾值才能保證構網速度最快。閾值的選取根據經驗來決定，對于隨機生成的點集，可認為均勻分布在平面上，閾值一般取[N/15，N/10]間的值，N為總的點數。同時為了驗證本文提出的構網算法的優越性，對一定數量的點集構網所需時間與其他構網算法所需時間進行比較，子塊閾值取經驗值N/12，結果如圖8所示。 4 結束語 本文提出的Delaunay三角網生成算法先對平面點集最小外包矩形分割，建立子塊索引二叉樹，利用Graham掃描技術構建各子塊三角網，最后自底向上合并具有相同父節點的子塊最終得到點集的Delaunay三角網。該算法采用二叉樹分塊提高了子網合并效率，利用Graham掃描技術構建各子塊三角網加快了構網速度，使構網時間和點的數量接近線性關系，比較適合大數據量不規則三角網的生成。同時與其他分塊算法相比，本文提出的算法比較簡單，易于實現。 參考文獻: [1]鄒徐文，武百超. 基于平衡二叉樹的三角網快速生成算法[J]. 遼寧工程技術大學學報，2007，26(4):513-517. [2]趙巖，張子平. 一種動態構建Delaunay三角網的算法[J]. 測繪工程，2008，17(3):24-28. [3]DWYER R A. A fast divide and conquer algorithm for constructing delaunay triangulations[J]. Algorithmica， 1987(2):137-151. [4]SLOAN S W. A fast algorithm for constructing Delaunay triangulation in the plane[J]. Advanced Engineering Software，1987，9(1):34-55. [5]欒曉巖. 一種TIN生成算法及其三維顯示[J]. 測繪科學， 2004，29(5):39-41. [6]向傳杰， 朱玉文. 一種高效的Delaunay三角網合并生成技術[J]. 計算機應用， 2002，22(11): 34-36. [7]劉永和，謝洪波，袁策. 一種基于三角網擴張法的Delaunay三角網逐塊歸并算法[J]. 測繪科學， 2007，32(3):52-55. [8]宋曉宇，李東，王永會. 一種基于Graham三角剖分生成Delaunay三角網的算法[J]. 沈陽建筑大學學報，2007，23(2):328-332. [9]郭兆勝， 張登榮. 一種改進的高效Delaunay三角網的生成算法[J]. 遙感信息， 2005(1):15-17. [10]石松，陳崇成，唐麗玉. Delaunay三角網的交互編輯算法設計與實現[J]. 測繪科學，2005，30(6):113-116.
