基于格網和方向法索引的Delaunay三角網生成算法

姜志偉，王山東，王伶俐，毛澤紅

（1.河海大學 地球科學與工程學院，江蘇 南京210098；2.徐州市賈汪區國土資源局，江蘇 徐州221000）

1 逐點插入法的點定位問題

近年來有許多學者對Delaunay三角網的構建算法進行了研究，基于離散點的三角網的構建算法目前較為常用的有生長法［1］、分治法［2］和逐點插入［3］法及兩種算法的結合。逐點插入法構建Delaunay三角網的思想是把集中的點依次插入一個已知的三角網中，每插入一個點都會構建新的三角形，對新生成的三角形需要進行局部優化［4］，最后使得三角網符合Delaunay規則。逐點插入法［5］思想簡單、靈活，這種算法比起生長法效率高很多、比起分治法占用更少的內存且容易實現。但是這種算法構網時，當隨著插入的點數增加時，三角形鏈表中的三角形也會成倍增加。算法耗時很多都浪費在目標三角形的查找上，即點定位。一般將在三角網中查找包含插入點的三角形算法稱為點定位問題［6］。

常見的對逐點插入法改進的算法中，最終目的都是對點定位的改進。如：李小秋等人在Delaunay三角網關鍵技術探討中提出使用方向法搜索技術進行快速定位［7］。趙巖等人選擇適當的格網大小對三角網進行存儲從而減小點定位時遍歷次數［8］。方向法利用三角網本身的拓撲關系進行點定位，可以有效減少判斷點是否在三角形內的次數。然而，當三角網過多時，還是會進行許多拓撲關系的運算。格網對三角形存儲的目的同樣是減少判斷點是否在三角形內的次數。然而，當單個網格過大時，遍歷格網中的三角形也需要大量的耗時；單個格網過小時，格網數量會很大，對三角網在格網中的存儲、內存的占用都會有影響。

本文在結合以上兩種方法的優點的基礎上，實現了一種新的基于格網的三角網生成。首先，在三角網的數據結構上做了改善，只利用拓撲關系存儲三角網。其次，在虛擬格網上加上輔助三角形，作為方向法點定位的起始三角形。最后，方向法點定位中使用跨立實驗和快速排斥實驗結合的方法。

2 虛擬格網索引建立和方向法算法描述

2.1 虛擬格網方向法構建三角網概述

常見的逐點插入法構建三角網時，對于點定位的算法是遍歷三角形鏈表，找出點所在的三角形。這種算法對于大量點插入時，三角形的數量會隨著點插入的數量的增加而增加。大量點插入時，效率變得很低。虛擬格網是將點集分塊管理，格網中心有一個輔助元三角形，元三角形的外接圓內不包含點集中的任何點。當點插入的時候，根據點坐標確定點屬于哪個格網，再用格網中的元三角形作為起始三角形，利用方向法確定目標三角形。通過以上兩個步驟尋找包含插入點的三角形，提高點定位的效率。

2.2 虛擬格網索引的建立

虛擬格網是把點數據分成長方形的區域，當插入點到三角網中時，通過點坐標計算出格網的數組位置。每個格網中都有一個處于中心位置的元三角形，如圖1所示。

圖1 2×2虛擬格網

虛擬格網的元三角形是在格網中央包含格網中心點的輔助三角形。在點定位時都是以元三角形作為起始三角形。元三角形的外接圓內中不包含任何點數據。在實際程序中，如果計算精度不是很高時，可以選擇合適大小的元三角形，先移除少量的元三角形外接圓內的點。

虛擬格網索引的建立原則為：

1）所有三角網和點的數據均包含在格網內。

2）格網中三角形不能太多，格網不能太大。如果三角形太多，在格網中用方向法檢索三角形效率會變低。

3）格網中三角形不能太少，格網不能太小。如果三角形太少，建立過多的格網，處理元三角形會占用大量資源和算法耗時。且在格網中元三角形刪除時耗時會更多。

2.3 方向法點定位算法簡述

2.3.1 跨立實驗

跨立實驗［9］和快速排斥實驗結合可以有效快速地判斷出兩條線段的位置關系。在格網內索引目標三角形點定位時會用到判斷三角形邊的相交情況，從而判斷三角形的走向。快速排斥法是判斷線段是否相交的必要條件。根據以兩條線段為對角線的兩個矩形是否相交判斷兩條線段相交的可能性。如果矩形不相交則兩條線段肯定不相交，如果矩形相交再進行跨立實驗，如圖2（a）所示。

圖2 快速排斥實驗和跨立實驗

跨立實驗原理是：如果一個線段跨立另一個線段，則另一線段的一個頂點與這條線段的兩個頂點連成的兩個矢量分別與原線段的矢量叉積符號相反，如圖2（b）所示。

2.3.2 跨立實驗判斷線段和三角形的關系

如圖4所示，根據線段和三角形的關系可以分為9種關系。用跨立實驗判斷線段的頂點和三角形的頂點是否是同一點可以準確判斷出線段和三角形的位置關系。實際在程序中不需要對這9種結果一一做出判斷。在這9種結果中只有上面3個是線穿越三角形，其他6種線沒有穿越三角形，即要么目標點在三角形內，要么目標點在三角形邊或頂點上。所以，可以根據跨立實驗簡單地判斷兩種結果：①三角形被線段穿越；②三角形沒有被三角形穿越。

圖3 線段之間的關系

圖4 線段和三角形的關系

2.3.3 方向法點定位

如圖5（a）所示，A點所在的三角形是起始元三角形，插入點是P點。在起始元三角形中的格網中心點作為起始點（A點），使用跨立試驗得出起始三角形的一條邊和線段AP相交，作為起始方向邊。根據起始方向邊得出第一個方向三角形。再利用跨立實驗得出下一個方向邊和方向三角形。

當線段AP可能出現如圖5（b）和圖5（c）所示的情況時，沒有方向邊和線段AP相交時取積極跨立AP的邊作為方向邊。

當線段AP穿越方向邊進入方向三角形時，如果沒有與三角形的另兩個邊出現跨立或積極跨立，則出現了線段和三角形關系中的第②種關系即點在三角形內或點在三角形邊或頂點上。此時點定位完成。

2.4 算法流程

2.4.1 算法概述

1）根據點的密度和點邊界劃分合適大小的格網，并計算格網編號、生成格網數組、格網元三角形。

2）用外邊界的格網4個角點和各元三角形的點建立初始三角網。

圖5 方向法索引

3）找出初始三角形的元三角形的地址，記錄在格網數組里。

4）插入其余的點，在格網內使用方向法索引到點定位的三角形，與一般插入法算法一樣構建三角網。

5）對插入點的所有影響三角形進行局部優化。

6）重復上面的4）和5），直到所有的點插入完畢。

7）移除所有的輔助點。

2.4.2 算法流程

算法流程見圖6。

圖6 算法流程

3 實驗結果

本文的算法要用配置為：CPU：E2160 1.80GHZ，內存2G，基于 Windows XP操作系統.net框架實現Delaunay三角網的構建。采用一般的逐點插入法和本文的基于虛擬格網的點插入法進行比較如表1所示。

從表1中測試的數據可以看出：利用虛擬格網法構建三角網的效率較一般的插入法效率大大提高，且虛擬格網構建三角網效率和點的個數幾乎成線性關系。從表1中分析得出：當密度大時，格網分得越多，效果越理想。但是密度小時，格網太多卻效率差。

表1 兩種算法結果比較

15 000個點構建出的三角網效果如圖7所示。

圖7 兩種方法生成的三角網

4 結束語

本文提出一種對逐點插入法構建三角網的改進算法。通過虛擬格網管理每一個插入點，根據格網內的元三角形作為起始三角形進行方向法索引，較大程度上縮小了搜索目標三角形的范圍。方向法索引很巧妙地利用三角網的聯系性和三角網元素之間的拓撲關系，大量提高點定位的速度。實驗證明該算法效果理想。但是使用該算法時需要注意網格的大小不是越小越好，網格過小時，初始三角網的構建、三角網生成后輔助點的刪除會影響構建效率，同時內存使用也會增大。在構建帶約束條件的三角網時，同樣可以根據本文中的點定位方法，快速找到約束線段的影響三角形。

［1］魏向輝，夏春林，魯慶偉.一種基于凸包的Delaunay三角網算法設計［J］.測繪科學，2010，35（5）：152-153.

［2］SHAMOS M，HOEY D.Closet-point problem［A］.Processing of the 16th Annual Symposium on Foundations of Computer Science［C］.1975：151-162.

［3］LAWSON C L.Software for C1surface interpolation［A］.Mathematical SoftwareⅢ［C］.New York：Academic Press，1977：161-194.

［4］俞亞磊，羅永龍，郭良敏，等.Delaunay三角網中任意約束線段嵌入的算法［J］.測繪科學，2013，38（4）：61-63.

［5］邵春麗，胡鵬，黃承義，等.Delaunay三角網的算法詳述及其應用發展前景［J］.測繪科學，2004，29（6）：68-70.

［6］陳定造，林奕新，劉東峰.三維Delaunay三角剖分快速點定位算法研究［J］.計算機工程與科學，2009，31（5）：79-81.

［7］李小秋，許民獻，尹志勇.Delaunay三角網關鍵技術探討［J］.測繪工程，2011，20（6）：61-63.

［8］趙巖，張子平.一種動態構建Delaunay三角網的算法［J］.測繪工程，2008，17（3）：24-27.

［9］吳立新，史文中.地理信息系統原理與算法［M］.北京：科學出版社，2003.

［10］LAWSON C L.Generation of a triangular grid with application to contour plotting［A］.In：Technical Memorandum［C］.Institute of Technology，Jet Pollution Laboratory，California，1972：299.