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

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

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

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

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

本文在結(jié)合以上兩種方法的優(yōu)點的基礎(chǔ)上，實現(xiàn)了一種新的基于格網(wǎng)的三角網(wǎng)生成。首先，在三角網(wǎng)的數(shù)據(jù)結(jié)構(gòu)上做了改善，只利用拓?fù)潢P(guān)系存儲三角網(wǎng)。其次，在虛擬格網(wǎng)上加上輔助三角形，作為方向法點定位的起始三角形。最后，方向法點定位中使用跨立實驗和快速排斥實驗結(jié)合的方法。

2 虛擬格網(wǎng)索引建立和方向法算法描述

2.1 虛擬格網(wǎng)方向法構(gòu)建三角網(wǎng)概述

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

2.2 虛擬格網(wǎng)索引的建立

虛擬格網(wǎng)是把點數(shù)據(jù)分成長方形的區(qū)域，當(dāng)插入點到三角網(wǎng)中時，通過點坐標(biāo)計算出格網(wǎng)的數(shù)組位置。每個格網(wǎng)中都有一個處于中心位置的元三角形，如圖1所示。

圖1 2×2虛擬格網(wǎng)

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

虛擬格網(wǎng)索引的建立原則為：

1）所有三角網(wǎng)和點的數(shù)據(jù)均包含在格網(wǎng)內(nèi)。

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

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

2.3 方向法點定位算法簡述

2.3.1 跨立實驗

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

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

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

2.3.2 跨立實驗判斷線段和三角形的關(guān)系

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

圖3 線段之間的關(guān)系

圖4 線段和三角形的關(guān)系

2.3.3 方向法點定位

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

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

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

2.4 算法流程

2.4.1 算法概述

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

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

圖5 方向法索引

3）找出初始三角形的元三角形的地址，記錄在格網(wǎng)數(shù)組里。

4）插入其余的點，在格網(wǎng)內(nèi)使用方向法索引到點定位的三角形，與一般插入法算法一樣構(gòu)建三角網(wǎng)。

5）對插入點的所有影響三角形進(jìn)行局部優(yōu)化。

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

7）移除所有的輔助點。

2.4.2 算法流程

算法流程見圖6。

圖6 算法流程

3 實驗結(jié)果

本文的算法要用配置為：CPU：E2160 1.80GHZ，內(nèi)存2G，基于 Windows XP操作系統(tǒng).net框架實現(xiàn)Delaunay三角網(wǎng)的構(gòu)建。采用一般的逐點插入法和本文的基于虛擬格網(wǎng)的點插入法進(jìn)行比較如表1所示。

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

表1 兩種算法結(jié)果比較

15 000個點構(gòu)建出的三角網(wǎng)效果如圖7所示。

圖7 兩種方法生成的三角網(wǎng)

4 結(jié)束語

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

［1］魏向輝，夏春林，魯慶偉.一種基于凸包的Delaunay三角網(wǎng)算法設(shè)計［J］.測繪科學(xué)，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三角網(wǎng)中任意約束線段嵌入的算法［J］.測繪科學(xué)，2013，38（4）：61-63.

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

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

［7］李小秋，許民獻(xiàn)，尹志勇.Delaunay三角網(wǎng)關(guān)鍵技術(shù)探討［J］.測繪工程，2011，20（6）：61-63.

［8］趙巖，張子平.一種動態(tài)構(gòu)建Delaunay三角網(wǎng)的算法［J］.測繪工程，2008，17（3）：24-27.

［9］吳立新，史文中.地理信息系統(tǒng)原理與算法［M］.北京：科學(xué)出版社，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.