基于合成算法的Delaunay三角網生成改進算法

潘麗麗,孫玉秋

(長江大學信息與數學學院,湖北荊州434023)

不規則三角網能夠精確的表示復雜的地形。Delaunay三角網因其在所有可能的三角網中表現最為出色而被用于不規則三角網的生成。被人們廣泛采用的Delaunay三角網生成算法有分治法與逐點插入法,這2種算法各有優劣,隨之出現了綜合2種算法的合成算法。合成算法雖然提高了執行效率,但并沒有很好的解決其中的一些 “瓶頸”問題。因此,如何改進現有算法從而提高算法的執行效率成為必須要解決的另一個問題。為此,筆者基于合成算法對子模塊中的關鍵步驟進行改進,提高算法的性能,簡化算法的實現。

1 基本概念及性質

Voronoi圖 (以下簡稱V圖),又叫泰森多邊形或Dirichlet圖,它是由一組連接兩鄰點直線的垂直平分線組成的連續多邊形。N個在平面上有區別的點,按照最鄰近原則劃分平面;每個點與它的最近鄰區域相關聯。Delaunay三角網是由與相鄰Voronoi多邊形共享一條邊的相關點連接而成的三角形。Delaunay三角形的外接圓圓心是與三角形相關的Voronoi多邊形的一個頂點。Voronoi三角網是Delaunay圖的偶圖。

性質1(空外接圓性質) 在由點集V生成的Delaunay三角網中,每個三角網的外接圓均不包含該點集的其他任意點。

性質2(最大最小角度性質) 在由點集V生成的Delaunay三角網中,所有三角形中的最小角度是最大的,即在生成的三角形網格中,各三角形的最小內角和為最大。

性質3(唯一性) 不論從區域何處開始構網,最終都將得到一致的結果。

2 合成算法

合成算法[1,2]的基本思想是將逐點插入法植入到分治算法中,即以分治算法為主體,當遞歸分割數據集的過程進行到子集中的數據量小于一個預定值時,用逐點插入法在子集中生成三角網,以達到互相取長補短,以體現它們的綜合優勢,從而達到較好的時空性能的效果,合成算法包含3個模塊:逐點插入法模塊、尋找上下切線模塊以及合并模塊。

1)逐點插入模塊 ①找出凸殼;②建立初始三角網;③插入點;④優化。

2)尋找上下切線模塊 這個模塊找出連接左右2個子三角網的凸殼HL和H R的上切線和下切線。

3)合并模塊 子三角網TL和TR的合并由一個循環完成。

3 改進算法

改進的合成算法主要分為逐點插入模塊和合并模塊,筆者在插入點的定位問題上以及凸殼生成問題上,改進了傳統的算法,以提高算法的整體執行效率。

1)凸殼的生成與初始化三角網 原合成算法采用Larkin的凸殼生成算法[3]生成凸殼,這需要判斷點的位置等操作,在點的數量大的時候,執行效率不高。凸殼的生成算法中較為經典的是格雷厄姆法[4]。

構建凸殼的算法需要滿足的2個條件:實現簡單,無需大量預處理工作;不影響下一步的點插入步驟。因此,筆者在格雷厄姆方法的基礎上改進以更好的解決凸殼快速生成問題。

①首先對點集預處理,對其進行排序,用點(max(X),max(Y))、(min(X),min(Y))、(max(X),min(Y))和(min(X),max(Y))4個點所圍矩形來構成凸殼,這樣就生成了一個包含所有點的簡單凸殼(如圖1所示)。②連接含有max(X)、max(Y)、min(X)和min(Y)4個值的點并對所構成的多邊形初始三角網(如圖2所示)。③在三角網生成后要將這4個點刪除,同時刪除含有這4個點的三角形。圖3為三角網生成后刪除4個頂點前的三角網圖;圖4為刪除頂點后的三角網圖。

圖1 凸殼

圖2 初始三角形

圖3 刪除矩形頂點前三角網

圖4 刪除矩形頂點后三角網

2)點的快速定位 逐點插入的過程就是對點的定位循環過程,也就是查找點所在三角形的過程。因此,改進點的定位過程可以提高算法的效率。判斷點是否在三角形內,一般的做法是掃描整個或局部三角網,利用點在多邊形中原理判斷計算。當三角形數目較多時是一個費時的過程。因此,點的定位算法為逐點插入過程的關鍵步驟。判斷點是否在多邊形內,常用的有射線法、轉角法[5]以及適用于三角網的快速方向定位法[6]。對于點的定位方法需要遵循2個原則:實現簡單和避免復雜運算。因此,筆者利用點在三角形內的特點來解決。

首先求出三角形頂點X、Y坐標的最大及最小值,并構成矩形,判斷點是否在矩形中,若不在矩形中,則不在三角形中。若在矩形中,則作下面的判斷。連接點A與P,B與P,C與P,得出3向量:

為了判斷點與三角形的位置關系,定義:

圖5 點在邊上

圖6 點在三角形外

圖7 點在三角形內

4 結 語

在對Delaunay三角網生成算法進行深入研究的基礎上,提出了一種基于合成算法的改進的Delaunay三角網生成算法,算法改進了原合成算法在凸殼生成過程以及的快速定位的不足,更好的發揮了分治算法與逐點插入算法合并后的優勢,充分發揮了其兼顧時間、空間的特性,較原合成算法在速度和效率上所有提高。

[1]武曉波,王世新,肖春生.Delaunay三角網的生成算法研究 [J].測繪學報,1999,28(1):28-35.

[2]武曉波,王世新,肖春生.一種生成Delaunay三角網的合成算法[J].遙感學報,2000,4(1):32-35.

[3]Larkin B J.An ANSIC Program to Determine Expected Li near Time the Vertices of the Convex Hull ofa Set ofPlanar Points[J].Computers&Geosciences,1991,17(3):431-443.

[4]周培德.算法設計與分析[M].第2版.北京:清華大學出版社,2004:209-210.

[5]吳立新,史文中.地理信息系統原理與算法 [M].北京:科學出版社,2001:65-70.

[6]蒲浩,宋占峰,詹振炎.快速構建三角網數字地形模型方法的研究 [J].中國鐵道科學,2001,22(6):100-106.