一種基于TIN的等值線快速生成算法

趙景昌，白潤才，劉光偉，劉 威

1.遼寧工程技術(shù)大學(xué) 礦業(yè)學(xué)院，遼寧 阜新 123000

2.遼寧工程技術(shù)大學(xué) 理學(xué)院，遼寧 阜新 123000

一種基于TIN的等值線快速生成算法

趙景昌1，白潤才1，劉光偉1，劉 威2

1.遼寧工程技術(shù)大學(xué) 礦業(yè)學(xué)院，遼寧 阜新 123000

2.遼寧工程技術(shù)大學(xué) 理學(xué)院，遼寧 阜新 123000

1 引言

在數(shù)字礦山建設(shè)過程中，應(yīng)用三維地學(xué)模擬（3D Geoscience Modeling，3DGM）技術(shù)建立三維礦床地質(zhì)模型是重要的基礎(chǔ)工作之一。以各種勘測方法與手段獲得的地質(zhì)與地形數(shù)據(jù)，在空間上的分布呈離散形式且數(shù)據(jù)量有限，利用這些有限的離散空間信息恢復(fù)地質(zhì)屬性和地學(xué)變量的空間分布狀態(tài)，研究它們在空間上的分布特征和變化規(guī)律，最常用的一種方法就是繪制等值線圖。

基于離散數(shù)據(jù)生成等值線圖的方法主要有規(guī)則矩形格網(wǎng)（Grid）法和不規(guī)則三角網(wǎng)（Triangulated Irregular Network，TIN）法等兩種。規(guī)則矩形格網(wǎng)法首先要根據(jù)已知的離散點(diǎn)數(shù)據(jù)進(jìn)行網(wǎng)格化插值，構(gòu)建矩形網(wǎng)格模型，然后從邊界或者內(nèi)部網(wǎng)格單元出發(fā)，根據(jù)網(wǎng)格單元各邊端點(diǎn)的屬性值內(nèi)插等值點(diǎn)，并連接等值點(diǎn)形成等值線；不規(guī)則三角網(wǎng)法則是將已知的離散點(diǎn)按一定規(guī)則進(jìn)行三角剖分構(gòu)建TIN模型，然后在TIN各三角面片單元中內(nèi)插等值點(diǎn)生成等值線。格網(wǎng)法對邊界擬合能力較差，無法處理等值線斷續(xù)等現(xiàn)象，并且在利用離散點(diǎn)數(shù)據(jù)進(jìn)行網(wǎng)格化插值過程中，必然造成原始數(shù)據(jù)附近的數(shù)據(jù)失真，影響等值線分布的準(zhǔn)確性；而不規(guī)則三角網(wǎng)法可基于原始離散點(diǎn)數(shù)據(jù)直接生成TIN模型，在保持原有數(shù)據(jù)精度的情況下，能較為準(zhǔn)確地表達(dá)復(fù)雜地質(zhì)構(gòu)造的地層局部特征，且三角形構(gòu)造靈活，對內(nèi)外邊界擬合較好，因此應(yīng)用廣泛[1]。

基于TIN生成等值線圖可分解為兩個基本步驟：（1）在TIN中確定含某等值線起點(diǎn)的起始等值邊，即：起始等值邊查找；（2）從起點(diǎn)出發(fā)按某種訪問策略在TIN中內(nèi)插等值點(diǎn)并連接成等值線，即：等值點(diǎn)內(nèi)插與等值線追蹤。隨著TIN數(shù)據(jù)規(guī)模的不斷增長以及對離散數(shù)據(jù)分布特征和變化規(guī)律進(jìn)行實時分析的需要，對以上兩個步驟的時間效率提出了越來越高的要求，而以往基于TIN生成等值線的研究成果主要集中于有斷層情況下等值線的生成[1]、傳統(tǒng)等值線生成方法的改進(jìn)[2-4]、等值線內(nèi)插[5]以及等值線填充[6-7]等。在上述研究成果中，關(guān)于如何提高等值線生成算法時間效率的研究較少，在起始等值邊查找、等值點(diǎn)內(nèi)插計算及等值線追蹤時，通常采用遍歷策略，算法時間效率較低，很難滿足大數(shù)據(jù)量條件下等值線快速生成的需要。

Marc Van Kreveld在文獻(xiàn)[8]中提出了一種區(qū)間樹索引算法，將起始等值邊的查找效率從O(M×N)（M為生成的等值線條數(shù)，N為TIN中三角面片數(shù)）提高到O(lbN+k)（k為目標(biāo)區(qū)間數(shù)目），但由于在構(gòu)建區(qū)間樹索引時，需要預(yù)先確定各級樹節(jié)點(diǎn)的最優(yōu)分割值而導(dǎo)致算法整體效率下降，并且，關(guān)于如何提高等值線追蹤的時間效率問題，在文獻(xiàn)[8]中也未進(jìn)行深入探討。

本文在進(jìn)行數(shù)字露天礦軟件研發(fā)過程中，針對大數(shù)據(jù)量條件下等值線生成的時間效率問題，設(shè)計并實現(xiàn)了一種基于TIN的等值線快速生成算法，實驗及應(yīng)用表明，該算法時間效率高，等值線生成精度可靠，能夠滿足大數(shù)據(jù)量條件下等值線快速生成的需要。

2 本文算法思想與數(shù)據(jù)結(jié)構(gòu)

從三角面片規(guī)模為N的TIN中查找一條含有某等值線起點(diǎn)的起始等值邊時，最直接的方法就是對TIN中的每個三角面片進(jìn)行順序遍歷，當(dāng)生成的等值線規(guī)模為M時，查找起始等值邊的時間效率為O(M×N)，當(dāng)?shù)戎稻€所經(jīng)過的三角面片數(shù)很少或者分布零散時，這種遍歷算法的時間效率顯然太低了，在TIN數(shù)據(jù)規(guī)模比較大的情況下尤為明顯。

如果將TIN中的三角面片以所關(guān)心的等值線屬性值進(jìn)行升序或降序排列，然后在有序的三角面片集合中用二分查找思想查找含有某給定等值線屬性值的三角面片，對等值線生成算法效率的提高無疑是有益的。假設(shè)某三角面片的三個頂點(diǎn)分別為 P1(x1，y1，v1)，P2(x2，y2，v2)，P3(x3,y3,v3)，擬生成的某等值線屬性值為v，則該三角面片包含等值點(diǎn)的充要條件是：min{v1,v2,v3}≤max{v1,v2,v3}。TIN中每個三角面片三個頂點(diǎn)的屬性值所對應(yīng)的是一個一維區(qū)間[min{v1，v2，v3}，max{v1，v2，v3}]（當(dāng)三個頂點(diǎn)屬性值相等時會退化為一個點(diǎn)），相當(dāng)于將三角面片投影到等值線屬性值所對應(yīng)的坐標(biāo)軸上，因此，可以將查找含有某等值點(diǎn)的起始等值邊問題看作是一維查找問題，即：在某坐標(biāo)軸上給定一組區(qū)間，將包含待查詢屬性值v的所有區(qū)間報告出來。解決這類問題的有效方法之一就是利用區(qū)間樹索引[6]，然而，在構(gòu)建區(qū)間樹時，需要預(yù)先確定能夠同時顧及區(qū)間樹深度、平衡程度以及樹節(jié)點(diǎn)中元素個數(shù)的最優(yōu)分割值，無論采用排序方法還是統(tǒng)計方法都需要耗費(fèi)大量時間，當(dāng)TIN數(shù)據(jù)規(guī)模較大時，時間效率較低，難以滿足實際應(yīng)用需要。

本文算法借鑒區(qū)域樹[9]思想，首先建立一棵以三角面片頂點(diǎn)最小屬性值為鍵值的平衡二叉樹（本文選用查找效率較高的紅黑樹），其中序遍歷序列為按頂點(diǎn)最小屬性值升序排序的三角面片序列，按三角面片包含等值點(diǎn)的充要條件，將中序遍歷序列位于某節(jié)點(diǎn)以左的所有三角面片再按頂點(diǎn)最大屬性值降序排列，在降序序列中用線性查找方法即可快速確定包含某等值線起點(diǎn)的三角面片以及該三角面片中的起始等值邊，用上述算法思想查找起始等值邊的時間復(fù)雜度為O(lbN)，實驗證明，由于不需要預(yù)先確定節(jié)點(diǎn)的最優(yōu)分割值，本文紅黑樹索引算法在起始等值邊查找時的整體效率要優(yōu)于區(qū)間樹索引算法。

影響等值線生成效率的另一個因素就是等值線追蹤。由TIN生成的等值線是由內(nèi)插計算得到的等值點(diǎn)連接而成的，每個被等值線穿過的三角面片必有兩條含有等值點(diǎn)的邊，一條為等值線“入邊”，另一條為等值線“出邊”，如果在內(nèi)插計算等值點(diǎn)時，能夠確定與當(dāng)前“出邊”存在鄰接關(guān)系的下一個三角面片，則只需順序記錄各三角面片“出邊”上的等值點(diǎn)，并按最終得到的頂點(diǎn)序列繪制等值線就完成了等值線的追蹤。“出邊”與三角面片的鄰接關(guān)系可根據(jù)TIN中“邊—面（三角面片）”拓?fù)浯_定，本文算法在讀取TIN數(shù)據(jù)時，基于散列與半邊數(shù)據(jù)結(jié)構(gòu)快速重建TIN拓?fù)?，從而使等值線追蹤與等值點(diǎn)內(nèi)插計算同步完成，進(jìn)一步提高了算法的整體時間效率。

本文算法中的主要數(shù)據(jù)結(jié)構(gòu)如圖1所示。

圖1 本文算法主要數(shù)據(jù)結(jié)構(gòu)

3 TIN拓?fù)渲貥?gòu)

重建TIN拓?fù)涞闹饕康氖菍崿F(xiàn)等值線的快速追蹤。本文中假設(shè)TIN是采用某種三角剖分算法預(yù)先生成的模型，因此在生成等值線之前需要讀入TIN數(shù)據(jù)，并在讀取TIN數(shù)據(jù)的同時完成TIN拓?fù)渲亟ā?/p>

TIN拓?fù)浒ā绊旤c(diǎn)—頂點(diǎn)”、“頂點(diǎn)—邊”、“邊—面（三角面片）”之間的鄰接關(guān)系，常見的可用來表示這種拓?fù)潢P(guān)系的數(shù)據(jù)結(jié)構(gòu)有：四邊結(jié)構(gòu)[10]（Quad-edge Structure）、半邊結(jié)構(gòu)（Half-edge Structure）[11]、翼邊結(jié)構(gòu)（Wing-edge Structure）、放射邊結(jié)構(gòu)（Radial-edge Structure）[12]等。其中半邊數(shù)據(jù)結(jié)構(gòu)可以使TIN中三角面片之間的鄰接關(guān)系更加容易表示，因此本文中選擇半邊數(shù)據(jù)結(jié)構(gòu)來描述TIN拓?fù)潢P(guān)系，共包含：TIN（三角網(wǎng)）、Face（面，TIN中的三角面片）、Edge（邊）、Half edge（半邊）、Vertex（頂點(diǎn)）等5類節(jié)點(diǎn)。TIN中每個三角面片由3條首尾相連的有向半邊組成，兩個相鄰的三角面片一定存在一對重合的、方向相反的半邊，稱之為伙伴半邊，兩個伙伴半邊構(gòu)成一條整邊，如圖2所示。

圖2 TIN半邊數(shù)據(jù)結(jié)構(gòu)示意圖

頂點(diǎn)聚合與半邊合并是建立TIN拓?fù)浔硎镜年P(guān)鍵，而頂點(diǎn)聚合又是半邊合并的基礎(chǔ)，其任務(wù)是將在TIN各三角面片中重復(fù)出現(xiàn)的頂點(diǎn)表示為唯一頂點(diǎn)。頂點(diǎn)聚合算法大致可分為直接法、平衡二叉樹法和散列法等三類，其中直接法的時間復(fù)雜度為O(N2)（N為TIN頂點(diǎn)個數(shù)），平衡二叉樹方法的時間復(fù)雜度為O(N lbN)，而基于散列的方法在理想情況下的時間復(fù)雜度為O(N)。

本文采用散列法進(jìn)行頂點(diǎn)聚合，計算散列地址的散列函數(shù)為：

其中X，Y，Z為頂點(diǎn)坐標(biāo)；α，β，γ為頂點(diǎn)坐標(biāo)系數(shù)，Jan[13]等通過大量實驗研究認(rèn)為α=3，β=5，γ=7較合理；C為比例系數(shù)，一般盡量使計算機(jī)所能表達(dá)的整型數(shù)的字長范圍都被利用，T為散列表的長度，一般是計算機(jī)所能表達(dá)的整型數(shù)的范圍，其值在(0，2k)之間。

采用散列函數(shù)計算頂點(diǎn)散列地址時，兩個不同頂點(diǎn)的散列地址可能會發(fā)生“沖突”，本文采用鏈地址法處理“沖突”，即：將發(fā)生地址沖突的頂點(diǎn)存儲在散列表同一個槽內(nèi)的線性鏈表中。

半邊合并的任務(wù)是將兩個端點(diǎn)完全相同的半邊設(shè)置成伙伴半邊，從而建立起“邊—邊”、“邊—面（三角面片）”之間的鄰接關(guān)系。在頂點(diǎn)聚合的同時，可通過為每個頂點(diǎn)建立一個入射半邊索引表[14]進(jìn)行半邊合并。

基于散列與半邊數(shù)據(jù)結(jié)構(gòu)的頂點(diǎn)聚合及半邊合并步驟如下：

（1）讀入一個新三角面片F(xiàn)i。

（2）應(yīng)用式（1）所示散列函數(shù)計算Fi三個頂點(diǎn)V1，V2，V3散列地址，若散列表中此地址槽鏈表非空，判斷當(dāng)前頂點(diǎn)與該地址槽內(nèi)的其他頂點(diǎn)是否重合，若不重合，為此頂點(diǎn)設(shè)置ID為num+1（num非重復(fù)頂點(diǎn)數(shù)），并將其插入到該地址槽內(nèi)的頂點(diǎn)鏈表中，若重合，則將此頂點(diǎn)ID設(shè)置為與其重合的頂點(diǎn)ID。

（3）如圖3所示，F(xiàn)i中半邊He1的兩個頂點(diǎn)V1，V2均存在重合頂點(diǎn)，則對半邊He1進(jìn)行合并（即找出與He1端點(diǎn)相同但方向相反的半邊—伙伴半邊）。

圖3 TIN半邊合并示意圖

（4）He1以V1為起點(diǎn)，它的伙伴半邊一定以V1為終點(diǎn)，故只需在V1的入射半邊表中，根據(jù)半邊端點(diǎn)ID是否相等查找He1的伙伴半邊即可，在圖3中，V1的入射半邊表包括半邊H4，H5，H6，H7，其中H4與He1的端點(diǎn)重合且方向相反，因此H4為He1的伙伴半邊。

（5）更新相應(yīng)頂點(diǎn)的入射半邊表。以圖3為例，將He1從V1的入射半邊表中刪除（不會再出現(xiàn)He1的伙伴半邊），同時需要給V1增加一個新的入射半邊He3，對新頂點(diǎn)V3建立入射半邊表，并將He2作為V3入射半邊插入到表中。

（6）將Fi中的半邊He1，He2，He3加入到TIN半邊集合中。

（7）重復(fù)執(zhí)行步驟（1）～（6），直至TIN中所有三角面片均被讀入為止。

頂點(diǎn)聚合與半邊合并時，將半邊加入到各頂點(diǎn)的鄰接半邊集合，將三角面片加入到各半邊的鄰接三角面片集合，即完成了對TIN的拓?fù)渲貥?gòu)。

4 等值線生成

4.1 構(gòu)建以TIN三角面片為節(jié)點(diǎn)的紅黑樹

為快速查找待插等值線的起始等值邊，需要構(gòu)建以TIN三角面片為節(jié)點(diǎn)的紅黑樹。

紅黑樹[15]是由Rudolf Bayer在1972年設(shè)計出來的一種每個節(jié)點(diǎn)都具有顏色特性的自平衡二叉搜索樹，通過對樹中節(jié)點(diǎn)適當(dāng)染色，可以使樹處于近乎完美的平衡狀態(tài)。除了具有一般二叉搜索樹的特征外，紅黑樹必須遵循如下規(guī)則：（1）樹中的每個節(jié)點(diǎn)或為紅色，或為黑色；（2）根節(jié)點(diǎn)永遠(yuǎn)為黑色；（3）所有葉子節(jié)點(diǎn)都是空節(jié)點(diǎn)，且為黑色；（4）若某節(jié)點(diǎn)為紅色，則其子節(jié)點(diǎn)必須是黑色；（5）從某一節(jié)點(diǎn)到其子孫葉子節(jié)點(diǎn)的每條簡單路徑上都必須包含相同數(shù)目的黑色節(jié)點(diǎn)。

遵循上述規(guī)則構(gòu)建的含有N個內(nèi)部節(jié)點(diǎn)的紅黑樹，其高度至多為2lb(N+1)，所以上述約束條件強(qiáng)制規(guī)定了紅黑樹的關(guān)鍵屬性，即：從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)最長可能路徑不超過最短可能路徑的兩倍，因此，紅黑樹可保證在最壞情況下在O(lbN)時間內(nèi)完成動態(tài)集合操作（如查找、插入和刪除），是一種查找效率非常高的自平衡二叉樹。

設(shè)TIN中某三角面片三個頂點(diǎn)屬性值分別為v1，v2，v3，待插等值點(diǎn)屬性值為v，則該三角面片中包含待插等值點(diǎn)的充要條件為：min{v1，v2，v3}≤v且max{v1，v2，v3}≥v。

基于以上特性，本文以TIN中的三角面片為節(jié)點(diǎn)，以三角面片三個頂點(diǎn)的最小屬性值為鍵值構(gòu)建紅黑樹，當(dāng)新節(jié)點(diǎn)插入紅黑樹時，必須滿足紅黑樹的建樹條件，節(jié)點(diǎn)顏色屬性可以遵循紅黑樹的5點(diǎn)規(guī)則設(shè)定，同時為了使新節(jié)點(diǎn)插入后仍滿足建立二叉搜索樹所必須的條件，定義節(jié)點(diǎn)比較規(guī)則為：

其中VNode1，VNode2為三角面片節(jié)點(diǎn)屬性值。滿足以上條件時，節(jié)點(diǎn)Node1＜Node2，當(dāng)新插入節(jié)點(diǎn)與某節(jié)點(diǎn)最小與最大屬性值均相等時，將新節(jié)點(diǎn)插入到該節(jié)點(diǎn)的左子樹中。

關(guān)于紅黑樹的具體實現(xiàn)，在文獻(xiàn)[16]中有詳細(xì)介紹，在此不作贅述。

4.2 起始等值邊查找

紅黑樹創(chuàng)建后，需要先對紅黑樹進(jìn)行一次中序遍歷，并將各節(jié)點(diǎn)在中序遍歷序列中的順序ID存入到節(jié)點(diǎn)中，以提高后續(xù)查找操作的效率。

在紅黑樹中查找某待插等值線起始等值邊的步驟如下：

（1）以紅黑樹根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)current=root，判斷當(dāng)前節(jié)點(diǎn)最小屬性值minV與待插等值線屬性值V的關(guān)系。

（2）若 current.minV＜V，查找當(dāng)前節(jié)點(diǎn)右子樹current=current.right，直到current.minV＞V（或葉子節(jié)點(diǎn)），若當(dāng)前節(jié)點(diǎn)非葉子節(jié)點(diǎn)時，轉(zhuǎn)而查找當(dāng)前節(jié)點(diǎn)左子樹current=current.left，直到current.minV＞V（或葉子節(jié)點(diǎn)）。

（3）若 current.minV＞V，查找當(dāng)前節(jié)點(diǎn)左子樹current=current.left，直到current.minV＜V（或葉子節(jié)點(diǎn)）時，若當(dāng)前節(jié)點(diǎn)非葉子節(jié)點(diǎn)時，轉(zhuǎn)而查找當(dāng)前節(jié)點(diǎn)右子樹current=current.right，直到current.minV＜V（或葉子節(jié)點(diǎn)）。

（4）在紅黑樹中序遍歷序列中，取當(dāng)前節(jié)點(diǎn)中序遍歷順序ID以左的所有節(jié)點(diǎn)（即中序遍歷順序ID小于當(dāng)前節(jié)點(diǎn)中序遍歷ID），按節(jié)點(diǎn)最大屬性值降序排序。

（5）以順序查找方式在節(jié)點(diǎn)最大屬性值降序序列中，查找最大屬性值小于待插等值線屬性值的節(jié)點(diǎn)，則該節(jié)點(diǎn)以左的所有節(jié)點(diǎn)即構(gòu)成包含待插等值點(diǎn)的候選三角面片集合。

4.3 等值點(diǎn)計算

完成包含待插等值點(diǎn)的三角面片查找后，即可在候選三角面片集合中以半邊為單位進(jìn)行等值點(diǎn)內(nèi)插計算。設(shè)三角面片按逆時針方向排列的三個頂點(diǎn)分別為P1(x1，y1，z1)，P2(x2，y2，z2)，P3(x3，y3，z3)，以頂點(diǎn)命名的三條半邊分別為P1P2，P2P3，P3P1，每條半邊頂點(diǎn)最大屬性值為maxV，最小屬性值為minV，當(dāng)前追蹤的等值線的屬性值為v，在判斷三角面片中某條邊是否含有等值點(diǎn)時，包括以下三種情況：

（1）(maxV-v)(minV-v)＞0，則該半邊不含等值點(diǎn)；

（2）(maxV-v)(minV-v)＜0，則該半邊含等值點(diǎn)；

（3）(maxV-v)(minV-v)=0，分為以下三種情況分別處理：

①maxV=v，此時將maxV進(jìn)行正擾動，即給maxV所對應(yīng)的頂點(diǎn)屬性值加上一個較小的正小數(shù)ε（本文中ε=10-6）。

②minV=v，此時將minV進(jìn)行負(fù)擾動，即在minV所對應(yīng)的頂點(diǎn)屬性值減去一個較小的正小數(shù)ε（本文中ε=10-6）。

③maxV=minV=v，該邊不含等值點(diǎn)。

位于某條半邊上的等值點(diǎn)的坐標(biāo)可用線性內(nèi)插公式求出：

4.4 等值線追蹤

為了敘述方便，將TIN中的半邊和三角面片按以下方式命名：TIN中不存在伙伴半邊的半邊為“邊界半邊”，存在伙伴半邊的半邊為“內(nèi)部半邊”；TIN中含有“邊界半邊”的三角面片為“邊界三角面片”，不含“邊界半邊”的三角面片為“內(nèi)部三角面片”。

等值線追蹤的任務(wù)就是在含有等值點(diǎn)的候選三角面片集合中以正確的順序獲取屬于同一條等值線的等值點(diǎn)并將其連接成為等值線。等值線包括閉合等值線與非閉合等值線兩種，其中非閉合等值線的起點(diǎn)位于TIN“邊界三角面片”上，而閉合等值線的起點(diǎn)則位于“內(nèi)部三角面片”上。

基于本文第3章所建立的TIN拓?fù)浣Y(jié)構(gòu)，在候選三角面片集合中追蹤某給定屬性值的非閉合等值線可在等值點(diǎn)內(nèi)插計算的同時按以下步驟進(jìn)行：

（1）從候選三角面片集合中選取一個“邊界三角面片”。

（2）以該三角面片中含等值點(diǎn)的“邊界半邊”為等值線在該三角面片中追蹤的“入邊”，計算等值點(diǎn)位置并將其加入當(dāng)前追蹤等值線的頂點(diǎn)集合中。

（3）在三角面片中確定等值線的“出邊”，計算等值點(diǎn)并將其加入當(dāng)前追蹤等值線的頂點(diǎn)集合中，同時將該三角面片從候選三角面片集合中刪除。

（4）根據(jù)TIN中“邊—邊”、“邊—面”拓?fù)潢P(guān)系，確定當(dāng)前三角面片等值線“出邊”的伙伴半邊及其所在三角面片。

（5）在其伙伴半邊所在的三角面片中，伙伴半邊即為等值線追蹤“入邊”，該邊不需再計算等值點(diǎn)，只需確定等值線在該三角面片中的“出邊”，計算出邊等值點(diǎn)并將其加入到當(dāng)前追蹤等值線的頂點(diǎn)集合中。

（6）若當(dāng)前含等值點(diǎn)的半邊無伙伴半邊（即該邊是TIN的“邊界半邊”），則當(dāng)前等值線追蹤結(jié)束，根據(jù)等值線頂點(diǎn)集合中的坐標(biāo)繪制等值線，否則，重復(fù)步驟（4），（5），直到當(dāng)前等值邊為TIN“邊界半邊”為止。

閉合等值線的追蹤步驟與非閉合等值線類似，所不同的是閉合等值線的起始半邊是“內(nèi)部半邊”，并且等值線追蹤結(jié)束的條件為當(dāng)前等值邊與該等值線起始等值邊為伙伴半邊。當(dāng)候選三角面片集合為空時，當(dāng)前給定屬性值的所有等值線追蹤完畢。

5 實驗分析與應(yīng)用實例

5.1 實驗分析

本文算法基于Visual Studio.NET平臺用C#語言實現(xiàn)，并與無索引算法以及文獻(xiàn)[8]中提出的區(qū)間樹索引算法進(jìn)行了對比分析。測試平臺：Windows 7中文旗艦版，Intel?CoreTMi7-2720QM CPU 2.20 GHz，4 GB內(nèi)存。

表1為不同數(shù)據(jù)規(guī)模條件下三種算法在預(yù)處理階段、等值線生成階段的效率對比（表中所列預(yù)處理時間包括TIN拓?fù)渲貥?gòu)以及紅黑樹或區(qū)間樹構(gòu)建時間）。

從表1實驗結(jié)果可知，本文與文獻(xiàn)[8]算法分別建立TIN紅黑樹索引與區(qū)間樹索引來提高起始等值邊的查找效率，盡管在預(yù)處理階段需要耗費(fèi)一定的時間，但等值線生成的整體時間效率均顯著優(yōu)于無索引算法。在理論上，本文提出的紅黑樹索引算法與文獻(xiàn)[8]提出的區(qū)間樹索引算法其構(gòu)建與查找效率均為O(lbN)（N為TIN中三角面片數(shù)），但文獻(xiàn)[8]算法在構(gòu)建區(qū)間樹時，需要預(yù)先確定同時顧及區(qū)間樹深度、平衡程度以及樹節(jié)點(diǎn)中元素個數(shù)的節(jié)點(diǎn)最優(yōu)分割值，無論采用排序方法還是統(tǒng)計方法都需要耗費(fèi)大量時間，而本文算法在構(gòu)建以TIN三角面片單元為節(jié)點(diǎn)的紅黑樹過程中，是通過節(jié)點(diǎn)旋轉(zhuǎn)和顏色調(diào)整來動態(tài)保持樹的平衡狀態(tài)，不需要預(yù)先確定節(jié)點(diǎn)最優(yōu)分割值，因此，本文算法在預(yù)處理階段的實際時間效率要明顯優(yōu)于文獻(xiàn)[8]算法；此外，本文算法基于散列與半邊數(shù)據(jù)結(jié)構(gòu)重構(gòu)TIN拓?fù)洌诘戎迭c(diǎn)內(nèi)插計算的同時，根據(jù)“邊—面”拓?fù)潢P(guān)系同步完成等值線追蹤，從而使本文算法在等值線生成階段的時間效率也較文獻(xiàn)[8]算法有較大提高。

表1 本文算法與區(qū)間樹及無索引算法效率比較

5.2 應(yīng)用實例

本文算法已應(yīng)用在筆者開發(fā)的露天煤礦采剝計劃CAD軟件系統(tǒng)中，圖4與圖5分別為應(yīng)用本文算法基于某礦煤層底板TIN與地形TIN生成的煤層底板等值線與地形等高線圖。

圖4 某礦煤層底板TIN與底板等值線

圖5 某礦地形TIN與地形等高線

實際應(yīng)用證明，本文算法運(yùn)行穩(wěn)定，生成的等值線精度可靠，能夠滿足較大數(shù)據(jù)量條件下基于各種離散的地質(zhì)、地形數(shù)據(jù)快速生成等值線的需要。

6 結(jié)束語

基于TIN生成等值線能夠在保持原有數(shù)據(jù)精度的情況下，較為精細(xì)地表達(dá)含復(fù)雜地質(zhì)構(gòu)造的地層局部特征，且三角形構(gòu)造靈活，對內(nèi)外邊界擬合較好，因此使用最廣泛。起始等值邊查找與等值線追蹤是決定等值線生成效率的兩個關(guān)鍵因素，本文算法通過構(gòu)建以TIN三角面片單元為節(jié)點(diǎn)的紅黑樹進(jìn)行起始等值邊的快速查找，并基于散列與半邊數(shù)據(jù)結(jié)構(gòu)重建TIN拓?fù)?，在等值點(diǎn)內(nèi)插計算的同時，根據(jù)TIN中“邊—面”拓?fù)潢P(guān)系完成等值線追蹤。實驗及實際應(yīng)用表明，本文算法時間效率高，運(yùn)行穩(wěn)定，生成的等值線精度可靠，能夠滿足大數(shù)據(jù)量條件下等值線快速生成的需要，具有廣泛的實際應(yīng)用價值。

[1]陳學(xué)工，付金華，馬金金，等.約束TIN生成帶斷層等值線圖的方法[J].計算機(jī)工程與應(yīng)用，2011，47（33）：198-201.

[2]李利軍，袁尤軍，王乘.一種基于不規(guī)則三角網(wǎng)TIN的等值線計算方法[J].計算機(jī)與數(shù)字工程，2007，35（9）：34-36.

[3]胡金虎.基于不規(guī)則三角網(wǎng)的高精度等值線生成方法[J].工程勘察，2011（2）：64-68.

[4]張梅華，梁文康.一個三角形網(wǎng)格上等值線圖的繪制算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，1997，9（3）：213-217.

[5]徐道柱，劉海硯.一種基于約束邊Delaunay三角網(wǎng)的等高線內(nèi)插方法[C]//第十二屆全國圖象圖形學(xué)學(xué)術(shù)會議論文集.北京：清華大學(xué)出版社，2005：505-508.

[6]湯子?xùn)|，鄭明璽，王思群，等.一種基于三角網(wǎng)的等值線自動填充算法[J].中國圖象圖形學(xué)報，2009，14（12）：2577-2581.

[7]李強(qiáng)，李超，甘建紅.基于三角網(wǎng)的等值線填充算法研究[J].計算機(jī)工程與應(yīng)用，2013，49（5）：185-189.

[8]van Kreveld M.Efficient methods for isoline extraction from a TIN[J].International Journal of Geographical Information Systems，1996，10（5）：523-540.

[9]Berg M，Cheong O，Kreveld M V，等.計算幾何——算法與應(yīng)用[M].鄧俊輝，譯.北京：清華大學(xué)出版社，2009：136-141.

[10]O’Rourke J.Computational geometry in C[M].2nd ed. Cambridge：Cambridge University Press，1998：146-149.

[11]Mantyla M.An introduction to solid modeling[M].[S.l.]：Computer Science Press，1988：110-132.

[12]Weiler K.Edge-based data structures for solid modeling in curved-surface environments[J].IEEE Computer Graphics and Applications，1985，5（1）：21-40.

[13]Skala V，Hrádek J，Kucha? M.Hash function for triangular mesh reconstruction[C]//WSEAS International Conference：Recent Advances in Computer Engineering，WSEAS，2009：233-238.

[14]劉金義，侯寶明.STL格式實體的快速拓?fù)渲亟╗J].工程圖學(xué)學(xué)報，2003（4）：34-39.

[15]左飛.C++數(shù)據(jù)結(jié)構(gòu)原理與經(jīng)典問題求解[M].北京：電子工業(yè)出版社，2008：418-433.

[16]Michael M.Data structures and algorithms using C#[M]. Cambridge：Cambridge University Press，2007：270-275.

ZHAO Jingchang1,BAI Runcai1,LIU Guangwei1,LIU Wei2

1.School of Mining,Liaoning Technical University,Fuxin,Liaoning 123000,China
2.College of Science,Liaoning Technical University,Fuxin,Liaoning 123000,China

Generating isogram based on TIN is one of the important means to recover the geological properties and variables distribution with the finite discrete spatial information.Its time efficiency mainly depends on the initial edge with isoline point checking and isolines tracking.By building the red-black tree with triangular facets units as TIN node,the time complexity of the initial edge checking is improved fromO(M×N)toO(lbN);TIN topology is reconstructed based on hash and half-edge data structure.According to“side-face”topology,isolines tracking is synchronously completed with the isoline points interpolation.Experiments and practical application show that the algorithm is stable,the precision of the isolines generation is reliable,and the algorithm can meet the needs to quickly generate isolines with the large amount of data,and has a wide range of practical application value.

Triangulated Irregular Network（TIN）;isoline;red-black tree;hash;half-edge data structure;topology reconstruction

基于TIN生成等值線圖是利用有限的離散空間信息恢復(fù)地質(zhì)屬性和地學(xué)變量空間分布狀態(tài)的重要手段之一，其時間效率主要取決于起始等值邊查找與等值線追蹤。通過構(gòu)建以TIN三角面片單元為節(jié)點(diǎn)的紅黑樹，將起始等值邊查找的時間復(fù)雜度由O(M×N)提高到O(lbN)；基于散列與半邊數(shù)據(jù)結(jié)構(gòu)重建TIN拓?fù)?，根?jù)TIN中“邊—面”拓?fù)潢P(guān)系，在等值點(diǎn)內(nèi)插計算的同時完成等值線追蹤。實驗及應(yīng)用表明，算法時間效率高，生成的等值線精度可靠，可滿足大數(shù)據(jù)量條件下等值線快速生成的需要，具有廣泛的實際應(yīng)用價值。

不規(guī)則三角網(wǎng)（TIN）；等值線；紅黑樹；散列；半邊數(shù)據(jù)結(jié)構(gòu)；拓?fù)渲貥?gòu)

A

TP391.7

10.3778/j.issn.1002-8331.1404-0482

ZHAO Jingchang,BAI Runcai,LIU Guangwei,et al.Fast isolines generation algorithm based on TIN.Computer Engineering and Applications,2014,50（24）：10-15.

國家自然科學(xué)基金（No.51174106）；遼寧省教育廳科學(xué)研究一般項目（No.L2011051）。

趙景昌（1974—），男，博士研究生，講師，研究領(lǐng)域為數(shù)字露天礦，露天開采理論與技術(shù)；白潤才（1961—），男，博士，教授，研究領(lǐng)域為數(shù)字礦山，露天開采理論與技術(shù)，露天礦邊坡穩(wěn)定與控制；劉光偉（1981—），男，博士，講師，研究領(lǐng)域為數(shù)字礦山，露天開采理論與技術(shù)；劉威（1977—），男，博士研究生，副教授，研究領(lǐng)域為數(shù)字露天礦，礦業(yè)系統(tǒng)工程，數(shù)據(jù)挖掘理論及應(yīng)用。E-mail：lntuzjc@126.com

2014-05-05

2014-07-04

1002-8331（2014）24-0010-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-08-19，http∶//www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1404-0482.html