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

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

1 逐點(diǎn)插入法的點(diǎn)定位問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 方向法點(diǎn)定位算法簡(jiǎn)述

2.3.1 跨立實(shí)驗(yàn)

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

圖2 快速排斥實(shí)驗(yàn)和跨立實(shí)驗(yàn)

跨立實(shí)驗(yàn)原理是：如果一個(gè)線段跨立另一個(gè)線段，則另一線段的一個(gè)頂點(diǎn)與這條線段的兩個(gè)頂點(diǎn)連成的兩個(gè)矢量分別與原線段的矢量叉積符號(hào)相反，如圖2（b）所示。

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

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

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

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

2.3.3 方向法點(diǎn)定位

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

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

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

2.4 算法流程

2.4.1 算法概述

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

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

圖5 方向法索引

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

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

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

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

7）移除所有的輔助點(diǎn)。

2.4.2 算法流程

算法流程見圖6。

圖6 算法流程

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

［8］趙巖，張子平.一種動(dòng)態(tài)構(gòu)建Delaunay三角網(wǎng)的算法［J］.測(cè)繪工程，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.