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

王會然

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

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

王會然?

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

針對DEM制作過程中大數(shù)據(jù)量構(gòu)建三角網(wǎng)效率問題，提出了一種多級索引支持的三角網(wǎng)生長算法，該算法邏輯結(jié)構(gòu)簡單，編程實現(xià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)簡單、直觀的特點，但在對復(fù)雜地形特征表達(dá)和分析方面，不規(guī)則三角網(wǎng)與其他兩種方法相比，具有較高的精度和效率，目前Delaunay三角網(wǎng)是公認(rèn)的最優(yōu)三角網(wǎng)。通過離散高程點和特征線、等高線構(gòu)造生成三角網(wǎng)，已有許多專家進(jìn)行了算法研究和改進(jìn)，其方法類型主要有3類；

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

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

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

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

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

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

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

圖1 三基形生長示意圖

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

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

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

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

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

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

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

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

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

4.2 算法實現(xiàn)

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

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

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

5 結(jié) 論

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

6 存在問題

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

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

[2]唐麗玉，朱泉鋒，石松.基于STL的DelaunayTIN構(gòu)建的研究與實現(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

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