王會(huì)然

(河北省地礦局測繪院，河北廊坊 065000)

一種生長法快速構(gòu)造三角網(wǎng)的算法研究

王會(huì)然?

(河北省地礦局測繪院，河北廊坊 065000)

針對(duì)DEM制作過程中大數(shù)據(jù)量構(gòu)建三角網(wǎng)效率問題，提出了一種多級(jí)索引支持的三角網(wǎng)生長算法，該算法邏輯結(jié)構(gòu)簡單，編程實(shí)現(xiàn)容易，可以驗(yàn)正該算法比通用軟件提供的相應(yīng)未優(yōu)化算法速度提高很多。

不規(guī)則三角網(wǎng)；Delaunay三角網(wǎng)；索引

1 引 言

數(shù)字高程模型(DEM)，是一種描述地形起伏的數(shù)學(xué)模型。其可分為規(guī)則格網(wǎng)、不規(guī)則三角網(wǎng)和等高線幾種類型。規(guī)則格網(wǎng)具有結(jié)構(gòu)簡單、直觀的特點(diǎn)，但在對(duì)復(fù)雜地形特征表達(dá)和分析方面，不規(guī)則三角網(wǎng)與其他兩種方法相比，具有較高的精度和效率，目前Delaunay三角網(wǎng)是公認(rèn)的最優(yōu)三角網(wǎng)。通過離散高程點(diǎn)和特征線、等高線構(gòu)造生成三角網(wǎng)，已有許多專家進(jìn)行了算法研究和改進(jìn)，其方法類型主要有3類；

①分而治之法(由Shamos和Hoey提出)，即對(duì)大量點(diǎn)分塊構(gòu)網(wǎng)，再合并成一個(gè)整體。構(gòu)網(wǎng)時(shí)采用局部優(yōu)化(Lop)算法保證其成為Delaunay三角網(wǎng)。其運(yùn)算中大量使用遞歸，故實(shí)現(xiàn)起來有困難。

②數(shù)據(jù)點(diǎn)漸次插入算法(由Lawson提出)，其方法是先找到最外層點(diǎn)作多邊形將所有點(diǎn)包括進(jìn)去形成一個(gè)凸殼。在此基礎(chǔ)上構(gòu)網(wǎng)，將內(nèi)部點(diǎn)逐一加入，并采用Lop算法保證其成為Delaunay三角網(wǎng)，此算法簡單，但效率不高。

③三角網(wǎng)生長算法，該方法算法簡便，如果不加優(yōu)化，則效率亦不高。本文就針對(duì)生長算法，提出了一種優(yōu)化算法——區(qū)域索引加正方形搜索區(qū)域的方法。使生長法具有很高的效率。

2 關(guān)于Delaunay三角網(wǎng)

Delaunay三角網(wǎng)為相互鄰接不重疊的三角形的集合。每一個(gè)三角形的外接圓內(nèi)不包含其他點(diǎn)。Delaunay三角形有3個(gè)相鄰點(diǎn)連接而成，這3個(gè)相鄰頂點(diǎn)對(duì)應(yīng)的Voronoi多邊形有一個(gè)公共的頂點(diǎn)，此頂點(diǎn)也是Delaunay三角形外接圓的圓心。Delaunay法則就是在構(gòu)造三角網(wǎng)時(shí)，確保每個(gè)三角形內(nèi)角是銳角或者三邊近似相等，避免鈍角和過小銳角出現(xiàn)。

3 三角網(wǎng)的構(gòu)建算法

三角網(wǎng)生長算法，就是首先在已知離散點(diǎn)中任選一點(diǎn)做起始點(diǎn)，找到其最近點(diǎn)，以兩點(diǎn)連線作為起始基線，在基線右側(cè)，應(yīng)用Delaunay法則搜索第三點(diǎn)，生成Delaunay三角形(每條基線方向如圖1，AB為起始基線)，再以三角形新的兩條邊作為新基線(AC和CB)，重復(fù)該過程，直到所有基線處理完畢。

圖1 三基形生長示意圖

4 算法優(yōu)化及實(shí)現(xiàn)

4.1 構(gòu)網(wǎng)方法優(yōu)化

(1)索引的建立:對(duì)采集的高程點(diǎn)(或等高線點(diǎn))進(jìn)行預(yù)處理。將數(shù)據(jù)讀入后，按坐標(biāo)計(jì)算范圍，并統(tǒng)計(jì)點(diǎn)數(shù)，提出對(duì)話框詢問是否建立點(diǎn)的分區(qū)索引以及要建立索引的分區(qū)行數(shù)和列數(shù)，根據(jù)點(diǎn)密度情況人工輸入合理值。這里所說的對(duì)點(diǎn)進(jìn)行分區(qū)，就是對(duì)所有點(diǎn)按坐標(biāo)最小和最大所限定的范圍在水平和垂直兩方向等分，把這個(gè)范圍均分成若干行若干列，見圖2。對(duì)一個(gè)點(diǎn)，根據(jù)點(diǎn)的兩坐標(biāo)值與分區(qū)邊緣比較一下，落在哪個(gè)區(qū)就統(tǒng)計(jì)在哪個(gè)區(qū)內(nèi)，每個(gè)區(qū)有多少個(gè)點(diǎn)記錄在一個(gè)由區(qū)號(hào)標(biāo)識(shí)的數(shù)組變量中，每個(gè)區(qū)中的點(diǎn)，也記錄在一個(gè)由區(qū)號(hào)標(biāo)識(shí)的數(shù)組變量中。該數(shù)組變量除了包括點(diǎn)號(hào)和坐標(biāo)外，還包括一個(gè)屬性值表示該點(diǎn)是否參與過一次構(gòu)網(wǎng)，初始值為0，表示未構(gòu)網(wǎng)。因?yàn)榉謪^(qū)數(shù)和區(qū)內(nèi)點(diǎn)數(shù)是在運(yùn)行中得到的，故這些變量都用到動(dòng)態(tài)數(shù)組。

圖2 對(duì)離散點(diǎn)進(jìn)行索引示意圖

(2)搜索正方形的使用:對(duì)要搜索的點(diǎn)，如果在一個(gè)正方形范圍內(nèi)進(jìn)行搜索，搜到后再做點(diǎn)與基線關(guān)系的有關(guān)計(jì)算，則會(huì)使計(jì)算量進(jìn)一步減少。以合適點(diǎn)為中心做一正方形，通過對(duì)正方形4頂點(diǎn)計(jì)算落在哪幾個(gè)分區(qū)中這一簡單比較運(yùn)算，得到該正方形所用到的分區(qū)，在分區(qū)中將落在正方形中的點(diǎn)找到，再進(jìn)行點(diǎn)與基線關(guān)系的運(yùn)算，找出最佳點(diǎn)。開始構(gòu)網(wǎng)時(shí)，是在所有點(diǎn)中先任選一個(gè)點(diǎn)(當(dāng)然也可以選最左上一個(gè)點(diǎn))，在所有點(diǎn)中找到離它最近的點(diǎn)，此兩點(diǎn)為起始邊(起始生長基線，之后的生長基線統(tǒng)稱基線)，起始點(diǎn)可不在整個(gè)區(qū)域邊緣，如取點(diǎn)時(shí)取文件的第一個(gè)點(diǎn)，該點(diǎn)就可能在中間某一位置，如圖3，A為起始點(diǎn)，B為與A的最近點(diǎn)，線段AB為起始生長基線，圖中搜索正方形中心點(diǎn)選基線的中點(diǎn)，邊長選已分區(qū)水平方向邊長的1/4，當(dāng)正方形中無點(diǎn)或無合適點(diǎn)(如在AB所在直線左側(cè)有點(diǎn)，右側(cè)沒發(fā)現(xiàn)點(diǎn)，或有點(diǎn)但它們已經(jīng)構(gòu)網(wǎng)且夠兩次即該點(diǎn)已完成了構(gòu)網(wǎng)，當(dāng)前基線不再構(gòu)網(wǎng)，要進(jìn)行基線轉(zhuǎn)移，要到其他未完成的三角形上去找新基線)時(shí)，對(duì)正方形按一定數(shù)量增大邊長(但不能增大超過三角網(wǎng)預(yù)設(shè)最大邊長一定量級(jí)，如兩倍，如果超過，基線右側(cè)點(diǎn)有可能與基線距離會(huì)超過最大邊長允許值，這個(gè)最大搜索正方形邊長也是在開始根據(jù)三角網(wǎng)允許最大邊長大小給定的)，直到找到合適點(diǎn)或右側(cè)無點(diǎn)(見圖4和圖5)。圖4中，虛線正方形表示許可的最大搜索正方形。在圖3中，如當(dāng)不是開始構(gòu)網(wǎng)而是在構(gòu)網(wǎng)中間時(shí)段，則AB基線表示當(dāng)前生長基線。圖3為正方形落在一個(gè)分區(qū)內(nèi)的情景，當(dāng)然還可以落在幾個(gè)分區(qū)內(nèi)，即跨幾個(gè)分區(qū)，見圖6。

圖3 搜索正方形構(gòu)建示意圖

圖4 當(dāng)前生長基線AB右側(cè)無點(diǎn)的情況

圖5 當(dāng)前生長基線AB右側(cè)有點(diǎn) 但再?zèng)]有未曾構(gòu)網(wǎng)點(diǎn)的情況

圖6 搜索正方形跨幾個(gè)索引區(qū)的情形

4.2 算法實(shí)現(xiàn)

當(dāng)無優(yōu)化時(shí)，構(gòu)造三角網(wǎng)如圖7，當(dāng)前基線為AB，為了找到符合條件的C點(diǎn)，需要對(duì)所選點(diǎn)與基線位置關(guān)系進(jìn)行判斷，將最好的點(diǎn)如C作為下一個(gè)構(gòu)網(wǎng)點(diǎn)，這就要將可能構(gòu)網(wǎng)的所有點(diǎn)都要進(jìn)行這種判斷計(jì)算，如圖6中的D、E、F、G、H、I……等等，即每構(gòu)一個(gè)新三角形，就要對(duì)可能點(diǎn)進(jìn)行遍歷搜索。當(dāng)構(gòu)網(wǎng)點(diǎn)數(shù)很大時(shí)，構(gòu)網(wǎng)速度和效率就會(huì)很低。本方法所論述就是為改善這種情況的優(yōu)化方法。首先進(jìn)行分區(qū):對(duì)讀入數(shù)據(jù)變量應(yīng)包括:點(diǎn)號(hào)(按讀入順序)、x、y、z三坐標(biāo)、區(qū)編號(hào)q(初始值為0)，假如x、y坐標(biāo)最小值和最大值分別為xmin和xmax，ymin和ymax，如果分成m行n列，則共有m×n分區(qū)，記△x＝(xmax－xmin)/n，△y＝(ymax－ymin)/m，當(dāng)讀入數(shù)據(jù)后再給出行列數(shù)，這些值就可以算出。接著就是對(duì)所有點(diǎn)按分區(qū)歸檔，進(jìn)行第一次遍歷數(shù)據(jù)，對(duì)一個(gè)點(diǎn)(x，y)，當(dāng)xmin＋(kh－1)×△x≤x＜xmin＋kh×△x則點(diǎn)所在區(qū)落在第kh列(1≤kh≤n的整數(shù))，同理，當(dāng)ymin＋(kl－1)×△y≤y＜ymin＋kl×△y則點(diǎn)所在區(qū)落在第kl行(1≤kl≤m的整數(shù))。當(dāng)kh和kl求得后，分區(qū)號(hào)q＝kh×n＋kl，將q值賦與該點(diǎn)區(qū)編號(hào)。用一個(gè)數(shù)組變量記錄每個(gè)區(qū)的點(diǎn)數(shù)累加值。接著進(jìn)行第二次遍歷數(shù)據(jù)，根據(jù)所得每個(gè)區(qū)的點(diǎn)數(shù)累加值d(q)，取d(q)最大者，創(chuàng)建分區(qū)點(diǎn)信息數(shù)組p[q，d(q)，5]，第三維中包括點(diǎn)號(hào)dh、三坐標(biāo)x、y、z、是否曾構(gòu)網(wǎng)判斷值gw。如果為了節(jié)省內(nèi)存，可將第三維數(shù)組分開表示為:pdh[q，d(q)，1]、px[q，d(q)，1]、py[q，d(q)，1]、pz[q，d (q)，1]、pgw[q，d(q)，1]，這樣就可以用整型變量表示點(diǎn)號(hào)和用短整型表示點(diǎn)已構(gòu)網(wǎng)次數(shù)。

圖7 構(gòu)造三角網(wǎng)無優(yōu)化時(shí)情況示意圖

下面是搜索正方形建立及搜索構(gòu)網(wǎng)點(diǎn)的具體過程:構(gòu)網(wǎng)的第一個(gè)點(diǎn)從坐標(biāo)最外圍為原則如左上、左下等，這樣構(gòu)網(wǎng)是從邊緣開時(shí)的。如果第一個(gè)點(diǎn)按文件數(shù)據(jù)順序，則第一個(gè)點(diǎn)可能出現(xiàn)在區(qū)域內(nèi)任一位置，這樣構(gòu)網(wǎng)可能在區(qū)域內(nèi)開始，兩種情況沒實(shí)質(zhì)差別。第一個(gè)點(diǎn)確定后，先判斷它在哪個(gè)索引區(qū)，然后在該區(qū)和所有相鄰區(qū)內(nèi)(有時(shí)該點(diǎn)可能與相鄰區(qū)內(nèi)某點(diǎn)最近)查找最近點(diǎn)，兩點(diǎn)連線作為第一條生長基線。以基線中心點(diǎn)坐標(biāo)為中心，構(gòu)造搜索正方形，正方形起始邊長，可取分區(qū)的寬的四分之一。構(gòu)造正方形時(shí)，以基線中點(diǎn)坐標(biāo)，由邊推算出對(duì)應(yīng)四角點(diǎn)坐標(biāo)，然后對(duì)正方形四頂點(diǎn)坐標(biāo)值與各分區(qū)邊縱橫坐標(biāo)進(jìn)行比較，確定該正方形所在的分區(qū)(一個(gè)或幾個(gè))。在這些分區(qū)內(nèi)，將所有區(qū)內(nèi)點(diǎn)與正方形邊范圍比較，找出所有在正方形內(nèi)的點(diǎn)。當(dāng)無點(diǎn)時(shí)，把正方形按起始邊長的一半擴(kuò)大正方形，直到找到點(diǎn)。找到點(diǎn)后，計(jì)算所有在正方形內(nèi)點(diǎn)與基線關(guān)系，選出離基線最近的點(diǎn)，直到右側(cè)無點(diǎn)。對(duì)找到的點(diǎn)，計(jì)算該點(diǎn)與基線關(guān)系，應(yīng)滿足以下兩種要求:①該點(diǎn)要在基線的右側(cè)。方法是按下面函數(shù)計(jì)算: F(x，y)＝y(tǒng)＋Ax＋B。式中A＝(y2－y1)/(x1－x2)；B＝(x1×y2－x2×y1)/(x2－x1)。 x1，x2，y1，y2分別為基線兩端點(diǎn)坐標(biāo)。當(dāng)F(x，y)〉0時(shí)，該點(diǎn)在基線左側(cè)，相反在右側(cè)。F(x，y)＝0表示該點(diǎn)在基線上。②讀取該點(diǎn)是否已構(gòu)網(wǎng)狀態(tài)，判斷該點(diǎn)是否參與構(gòu)網(wǎng)，未曾構(gòu)網(wǎng)時(shí)直接進(jìn)行下一步。當(dāng)已構(gòu)網(wǎng)時(shí)在已構(gòu)網(wǎng)邊中判斷是否與該基線兩點(diǎn)中任意點(diǎn)達(dá)到兩次，達(dá)到兩次時(shí)，該點(diǎn)不再使用。③該點(diǎn)為頂點(diǎn)的角要取最大的。根據(jù)余弦定理c2＝a2＋b2－2abcosC可得cosC＝(a2＋b2－c2)/2ab，取cosC最小的，此時(shí)C值最大，cosC＜0時(shí)說明C角是鈍角，這里不排除鈍角這一情況，當(dāng)點(diǎn)位不均勻或等高線平行性發(fā)生突變時(shí)，會(huì)出現(xiàn)這種情況。對(duì)合適的點(diǎn)，構(gòu)建好三角形后，以新邊為基線，重復(fù)以上過程，直到把所有邊都進(jìn)行了搜點(diǎn)構(gòu)網(wǎng)。

5 結(jié) 論

該算法運(yùn)算公式簡單，可容易地用VC＋＋和VB編寫程序?qū)崿F(xiàn)，由于建立格網(wǎng)索引只需兩次遍歷所有點(diǎn)，在對(duì)搜索正方形時(shí)，也只用一些簡單坐標(biāo)比較就可以在一個(gè)或幾個(gè)分區(qū)內(nèi)找到在搜索正方形內(nèi)的所有點(diǎn)，這樣就避免了在大量的點(diǎn)中判斷符合與基線構(gòu)造三角形的條件計(jì)算問題。當(dāng)點(diǎn)數(shù)很大時(shí)，設(shè)有一萬個(gè)點(diǎn)甚至幾十萬個(gè)，如果不優(yōu)化，每構(gòu)一個(gè)三角形都要對(duì)所有點(diǎn)進(jìn)行是否在基線右側(cè)、點(diǎn)是否已構(gòu)網(wǎng)兩次、到基線距離是否最小這些判斷，其中第1和第3兩項(xiàng)有公式運(yùn)算，構(gòu)網(wǎng)效率就很低。當(dāng)用該方法優(yōu)化時(shí)，先生成搜索正方形，再定位其4個(gè)角點(diǎn)所在索引格，然后在所有索引格中找正方形內(nèi)點(diǎn)，最后在正方形內(nèi)點(diǎn)進(jìn)行上述判斷。所處理點(diǎn)數(shù)與正方形內(nèi)點(diǎn)數(shù)有關(guān)，所以當(dāng)正方形不用擴(kuò)大時(shí)，其邊長為一個(gè)索引格寬1/4，如果我們共有M×N索引格，且我們索引時(shí)在水平和垂直兩個(gè)方向上索引格邊長大致相當(dāng)，且我們同時(shí)設(shè)定高程點(diǎn)分布是比較均勻的(不均勻也沒關(guān)系，點(diǎn)的稀密也使落在正方形內(nèi)的點(diǎn)同樣多或少，不影響最終全部處理的時(shí)間，這里假設(shè)這種情況，是為了好理解)，那么，每個(gè)正方形占全部點(diǎn)分布面積的比例為:1/(M×N×16)，也就是說，對(duì)點(diǎn)進(jìn)行計(jì)算時(shí)所用點(diǎn)數(shù)為原來的1/(M×N×16)，由此可知，速度可以提高到(M×N×16)倍，值得一提的是，沒有計(jì)算生成搜索正方形、判斷正方形所在索引格、在索引格中找正方形中的點(diǎn)這些時(shí)間，實(shí)際上，我們處理的是當(dāng)數(shù)據(jù)量很大時(shí)的情況，當(dāng)數(shù)據(jù)量不大時(shí)，什么算法都不會(huì)有明顯優(yōu)勢(shì)(計(jì)算機(jī)很快)。數(shù)據(jù)很大時(shí)每個(gè)索引格不會(huì)太小(至少幾百個(gè)點(diǎn))，對(duì)于生成正方形是一個(gè)加減法運(yùn)算，對(duì)正方形所在索引格判斷也只是4個(gè)點(diǎn)坐標(biāo)與幾個(gè)索引格坐標(biāo)比較，對(duì)落在正形內(nèi)點(diǎn)判斷也只是幾個(gè)索引(1～4)內(nèi)點(diǎn)與正方形邊坐標(biāo)比較，這些做比較的次數(shù)不多且簡單，會(huì)使最終效果與上面估計(jì)的有所降低，但不是很大。對(duì)于正方形需增大找點(diǎn)的情況并不多，實(shí)際上每個(gè)起始正方形內(nèi)往往會(huì)有上百個(gè)點(diǎn)。由此可知，此方法與不進(jìn)行優(yōu)化相比，速度提高幾十倍到幾百倍并不困難。只是注意，我們對(duì)索引格建立時(shí)，要大小合理，當(dāng)太大時(shí)M和N都變小，根據(jù)效率倍數(shù)估算(M×N×16)可知會(huì)使率降低，但當(dāng)太小時(shí)，會(huì)使最終搜索正方形內(nèi)點(diǎn)太少，正方形內(nèi)出現(xiàn)無點(diǎn)情況就增多，擴(kuò)大正方形情況也就多了，同時(shí)相關(guān)比較運(yùn)算也會(huì)增多。所以合適的索引格大小，也是保證最佳速度的關(guān)鍵。

6 存在問題

由于索引建立和其他相關(guān)數(shù)組建立，需要更多的內(nèi)存，主要體現(xiàn)在:①對(duì)每個(gè)點(diǎn)要增加一個(gè)索引區(qū)號(hào)分量(整型)，增加內(nèi)存1/7。②分區(qū)后又按區(qū)進(jìn)行統(tǒng)計(jì)，等于是復(fù)制一遍數(shù)據(jù)，對(duì)于新增的判斷構(gòu)網(wǎng)次數(shù)分量，可能其他方法也都用到，這里不妨也算上，共增加內(nèi)存1.2倍。③為索引等服務(wù)的少量變量。最后估計(jì)多用內(nèi)存近1.5倍。但現(xiàn)在計(jì)算機(jī)的內(nèi)存已很大，這方面已不是主要問題。還有，沒有論述對(duì)所有點(diǎn)進(jìn)行優(yōu)化篩選，通過篩選，可以把一些對(duì)相對(duì)平坦或坡度均勻的多余點(diǎn)進(jìn)行去除。同時(shí)沒有考慮特征線的情況，希望以后把這方面內(nèi)容考慮進(jìn)去(就是一條特征線間點(diǎn)是一定要連線構(gòu)網(wǎng)的，這項(xiàng)做起來相對(duì)簡單些。)以使算法更加完善。

[1]彭李，劉少華，盧學(xué)軍.一種基于動(dòng)態(tài)正方形的TIN的構(gòu)建算法[J].現(xiàn)代測繪，第30卷第2期，2007

[2]唐麗玉，朱泉鋒，石松.基于STL的DelaunayTIN構(gòu)建的研究與實(shí)現(xiàn)[J].遙感技術(shù)與應(yīng)用，第20卷第3期，2005

Research of an Algorithm to the TIN Construction with the Growing Method

Wang HuiRan
(The institute of surverying and mapping of geologic Bureau of Hebei Province，LangFang 065000，China)

Aiming at inefficiency of triangulation construction for large data in the DEM production process，a triangulation growth algorithm supported by multi－level index is proposed in this paper.The logical structure of the algorithm is simple so that it can be implemented easily by programming.It can be tested that the new method will process more faster than the corresponding algorithm provided by some common softwares.

Irregular Triangulation；Delaunay Triangulation；Index

1672－8262(2010)02－146－04

P209

A

2009—06—29

王會(huì)然(1966—)，男，工程師，現(xiàn)從事測繪遙感工作。