Delaunay三角剖分的快速重建算法

潘榮麗

山東省勞動廳服務技工學校 山東 濟南

0 引言

平面點集的Delaunay 三角剖分是計算幾何的一個重要問題，有著廣泛的應用背景，在虛擬現(xiàn)實、地理信息系統(tǒng)（GIS）等許多方面都有著很重要的意義。 實際應用中經(jīng)常包含幾百萬個點和三角形， 必須進行數(shù)據(jù)壓縮才能適應現(xiàn)有的網(wǎng)絡傳輸技術， 特別是進行實時處理時更需要壓縮技術的支持。 在網(wǎng)絡環(huán)境下把模型從服務器傳送到客戶端，一般有兩種方法：1）只傳送點集，在客戶端對點集進行Delaunay三角化。 這一般需要O(nlogn)的時間。這方面的研究主要集中在提高Delaunay三角剖分算法的時間復雜性上。2） 傳送點集和連接關系。 這樣傳輸數(shù)據(jù)量大，因此需要進行壓縮處理，以減少傳輸時間。這方面的研究主要集中在對點集和三角網(wǎng)格連接關系進行壓縮［2-5］。

最近，Snoeyink 和van Kreveld 提出了第三種可能的方法［6］：找出點集的一種特殊排序，按這種序列傳輸點集，在O(n)的時間內(nèi)重建Delaunay三角剖分。 具體算法是首先根據(jù)已經(jīng)生成的Delaunay三角剖分，分成O(nlogn)個階段計算點集序列，在每個階段刪除一個獨立點集，對產(chǎn)生的空洞進行三角化， 按DFS或BFS遍歷新產(chǎn)生的三角剖分，輸出點集序列。 整個計算過程可以在O(n)的時間內(nèi)完成。重建算法與計算點集序列的算法相對應，也分成O(nlogn)個階段，在每個階段進行點定位、局部插入調(diào)整，重建過程也可以在O（n）的時間內(nèi)完成。 1999年Christian Sohler 對算法進行了改進。

上述計算點集序列和重建算法都比較復雜，而且不能在Delaunay三角化過程中直接計算點集序列，重建時需要進行點定位、局部插入調(diào)整等操作，影響了重建速度。 我們提出了一種新的Delaunay三角剖分的快速重建算法，在基于均勻網(wǎng)格的Delaunay三角化過程中，直接生成點集序列。這種方法也可以應用到其他Delaunay三角剖分方法的輸出結(jié)果上，在O（n）的時間內(nèi)生成點集序列。 重建時不需要插入調(diào)整就可以在O（n）的時間內(nèi)生成Delaunay三角剖分。

1 計算點集序列算法

基于均勻網(wǎng)格的Delaunay三角化算法運算速度非?？?，具有近似線性的時間復雜性［10］，是一種比較成熟、穩(wěn)定、實際的Delaunay三角化算法。 這個算法的主要步驟如下：

1）預處理數(shù)據(jù)

把數(shù)據(jù)點分布的平面區(qū)域劃分成網(wǎng)格，使網(wǎng)格單元數(shù)和點數(shù)大致相同。 根據(jù)點的坐標值，把所有的點放進相應的網(wǎng)格單元中。在靠近中間的網(wǎng)格單元中找到一個初始點，然后找一個距離初始點最近的點，把這兩個頂點填加到一個鏈表Q中

2）找一個三角形

取鏈表的頭結(jié)點Qs、 鏈表的尾結(jié)點Qe形成一條有向邊，方向為從Qs到Qe。在這條邊的右邊尋找與這條邊的兩個端點角度最大的點。 然后掃描通過這條邊的兩個端點與該點所形成的圓的區(qū)域，如果圓內(nèi)存在一個點，用那個點重新形成一個圓，再掃描直到圓內(nèi)沒有點為止。 這樣就找到一個Delaunay三角形。

3）連接三角形

按“右接觸”、“左接觸”、“洞”、“邊界邊”等情況分別進行處理、調(diào)整鏈表。

4）重復步驟（2）、（3），直到鏈表中的點全為邊界點為止，結(jié)束三角化過程。

下面對基于均勻網(wǎng)格的Delaunay三角化算法進行修改，在生成過程中輸出點集序列。

算法1

（1） 找到靠近平面區(qū)域中間的初始點P1以及距離P1最近的點P2，構(gòu)成初始邊P1P2，把這兩個頂點填加到一個鏈表Q中：輸出P1、P2

（2）取鏈表的頭結(jié)點Qs、鏈表的尾結(jié)點Qe，形成一條有向邊，方向為從Qs到Qe。 在QsQe的右邊尋找與QsQe兩個端點角度最大的點。 然后掃描通過Qs、Q e與該點所形成的圓的區(qū)域，如果圓內(nèi)存在一個點，用那個點重新形成一個圓，再掃描直到圓內(nèi)沒有點為止。 這樣就找到一個Delaunay三角形的第三點P，并按“右接觸”、“左接觸”、“洞”、“邊界邊”等情況分別進行處理、調(diào)整鏈表。

①如果QsQe屬于“邊界邊”的情況（不存在P），則把Qs移到Q的末尾，輸出標志F3

②如果P屬于“右接觸”的情況（P已經(jīng)出現(xiàn)過，且等于Qs.next），則刪除Qs，輸出標志F1

③如果P屬于“左接觸”的情況（P已經(jīng)出現(xiàn)過，且等于Qe.previous），則刪除Qe，輸出標志F2

④如果P屬于“洞”的情況（P已經(jīng)出現(xiàn)過，但不等于Qs.next和Qe.previous），則把Qs移到Q的末尾，輸出標志F3

⑤否則（P沒有出現(xiàn)過），把P追加到隊列Q中，輸出P

（3）重復（2），直到鏈表中結(jié)點全為邊界點為止。

例如：

圖1 測試數(shù)據(jù)點

圖2 初始點P1、初始邊P1P2，輸出P1、P2

圖3 第一個三角形P1P2P3 ，輸出P3

圖4 第二個三角形P1P3P4 ，輸出P4

圖5 第五個三角形P1P6P7 ，輸出P7

圖6 “右接觸”的情況，輸出標志F1

圖7 “洞”的情況，輸出標志F3

圖8 “右接觸”的情況，輸出標志F1

圖9 “左接觸”的情況，則輸出標志F2

圖10 “邊界邊”的情況，輸出標志F3

圖11 三角形P10P9P18 ，輸出P18

圖12 三角化結(jié)束

根據(jù)上述算法，在生成過程中輸出的點集序列為：P1、P2、P3、P4、P5、P6、P7、F1、F1、P8、P9、P10、F1、P11、P12、P13、P14、F1、P15、P16、F1、F3、F1、F2、P17、F3、F3、P18、F1、P19、P20、F1、F3、F3、F1、F2、F3、F1、F3、F1、F3

顯而易見，增加的標志大部分位于點集序列的最后（邊界邊的情況）。 點越多，點集序列中出現(xiàn)的標志所占比例就越小。

上述算法也可以推廣到其他Delaunay三角剖分方法的輸出結(jié)果，輸出點集序列。

算法2

（1） 找到靠近平面區(qū)域中間的初始點P1以及初始邊P1P2，把這兩個頂點填加到一個鏈表Q中：輸出P1、P2

（2） 取鏈表的頭結(jié)點Qs、鏈表的尾結(jié)點Qe，形成一條有向邊，方向為從Qs到Qe。 尋找QsQe右三角形［12］的第三點P，并按“右接觸”、“左接觸”、“洞”、“邊界邊”等情況分別進行處理、調(diào)整鏈表。

①如果QsQe屬于“邊界邊”的情況（不存在P），則把Qs移到Q的末尾，輸出標志F3

②如果P屬于“右接觸”的情況（P已經(jīng)出現(xiàn)過，且等于Qs.next），則刪除Qs，輸出標志F1

③如果P屬于“左接觸”的情況（P已經(jīng)出現(xiàn)過，且等于Qe.previous），則刪除Qe，輸出標志F2

④如果P屬于“洞”的情況（P已經(jīng)出現(xiàn)過，但不等于Qs.next和Qe.previous），則把Qs移到Q的末尾，輸出標志F3

⑤否則（P沒有出現(xiàn)過），把P追加到隊列Q中，輸出P

（3） 重復（2），直到鏈表中結(jié)點全為邊界點為止。

在算法1和算法2中都考慮了所有可能出現(xiàn)的五種情況，因此算法是完備。

2 快速重建算法

在重建Delaunay三角化算法中，根據(jù)上面生成的點集序列在重建過程中動態(tài)維護一個隊列Q。

算法3

（1） 初始隊列為空

（2） 從點集序列中取第一個點P1和第一個點P2，放入隊列Q中，連接邊P1P2

（3） 從點集序列中取下一個點P3

①如果P3為標志F1， 則Qs、Qe、P3構(gòu)成一個三角形，刪除隊列Q的頭結(jié)點Qs，連接隊列Q新的頭結(jié)點Qs和尾結(jié)點Qe，形成一條邊

②如果P3為標志F2， 則Qs、Qe、P3構(gòu)成一個三角形，刪除隊列Q的尾結(jié)點Qe，連接隊列Q的頭結(jié)點和新的尾結(jié)點，形成一條邊

③如果P3為標志F3， 則把隊列Q的頭結(jié)點移動到隊列Q的末尾

④否則，Qs、Qe、P3構(gòu)成一個三角形，分別連接Qs和P3，Qe和P3，形成兩條邊，把P3追加到隊列Q中。

（4） 重復（3），直到把點集序列的所有點處理完畢。

3 結(jié)論

算法2和算法3具有線性時間復雜性， 而算法1具有近似線性的時間復雜性。這種重建方法實現(xiàn)了三角網(wǎng)格連接關系的高效壓縮 （只增加了三種標志），在基于均勻網(wǎng)格的Delaunay三角化過程中，直接生成點集序列，還可以應用于其他Delaunay三角剖分方法的輸出結(jié)果，并可結(jié)合對幾何信息(如坐標、顏色等)的其它壓縮算法如Huffman編碼等，算法簡單、使用。

如何利用文中提出的算法對三維點集的Delaunay三角剖分［10］進行重建，是作者下一步研究的方向之一。

［1］武曉波， 王世新， 肖春生.Delaunay三角網(wǎng)的生成算法研究［J］. 測繪學報，1999， 28（1）：28-35.

［2］M. Deering. Geometry Compression. Computer Graphics（Proc. SIGGRAPH），1995：13-20.

［3］G. Taubin， J. Rossignac. Geometric Compression through topological surgery. ACM Trans. on Graphics，1998，17（2）：84-115.

［4］H. Hoppe. Progressive Meshes. Proc. SIGGRAPH ’96，pages 99-108. ACMSIGGRAPH， 1996.

［5］Stefan Gumhold， W. Stra?er： Real Time Compression of Triangle Mesh Connectivity.SIGGRAPH ’98： 133-140.

［6］J. Snoeyink， M. van Kreveld. Linear-time reconstruction of Delaunay triangulations with applications， European Symposium on Algorithms， 1997.

［7］Christian Sohler， Fast Reconstruction of Delaunay Triangulations， Proceedings of the 11th Canadian Conference on Computational Geometry，1999：142-145.

［8］Tsung-Pao Fang， Les A. piegl. Delaunay triangulation using a uniform grid ［J］. IEEE Computer Graphics and Applications 1993，13（3）， 36-47.

［9］潘榮江，屠長河等.基于均勻網(wǎng)格的Delaunay三角網(wǎng)算法在隨機聚合網(wǎng)屏中的應用 ［J］. 中國圖象圖形學報，2002，7A（5）：495-500.

［10］Tsung-Pao Fang， Les A. piegl. Delaunay triangulation in three dimensions， IEEE Computer Graphics and Applications， September 1995,15（5）.