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

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

3 TIN拓撲重構(gòu)

重建TIN拓撲的主要目的是實現(xiàn)等值線的快速追蹤。本文中假設(shè)TIN是采用某種三角剖分算法預(yù)先生成的模型，因此在生成等值線之前需要讀入TIN數(shù)據(jù)，并在讀取TIN數(shù)據(jù)的同時完成TIN拓撲重建。

TIN拓撲包括“頂點—頂點”、“頂點—邊”、“邊—面（三角面片）”之間的鄰接關(guān)系，常見的可用來表示這種拓撲關(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拓撲關(guān)系，共包含：TIN（三角網(wǎng)）、Face（面，TIN中的三角面片）、Edge（邊）、Half edge（半邊）、Vertex（頂點）等5類節(jié)點。TIN中每個三角面片由3條首尾相連的有向半邊組成，兩個相鄰的三角面片一定存在一對重合的、方向相反的半邊，稱之為伙伴半邊，兩個伙伴半邊構(gòu)成一條整邊，如圖2所示。

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

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

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

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

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

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

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

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

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

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

圖3 TIN半邊合并示意圖

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

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

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

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

頂點聚合與半邊合并時，將半邊加入到各頂點的鄰接半邊集合，將三角面片加入到各半邊的鄰接三角面片集合，即完成了對TIN的拓撲重構(gòu)。

4 等值線生成

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

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

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

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

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

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

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

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

4.2 起始等值邊查找

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

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

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

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

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

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

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

4.3 等值點計算

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

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

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

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

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

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

③maxV=minV=v，該邊不含等值點。

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

4.4 等值線追蹤

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

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

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

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

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

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

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

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

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

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

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

5.1 實驗分析

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

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

從表1實驗結(jié)果可知，本文與文獻[8]算法分別建立TIN紅黑樹索引與區(qū)間樹索引來提高起始等值邊的查找效率，盡管在預(yù)處理階段需要耗費一定的時間，但等值線生成的整體時間效率均顯著優(yōu)于無索引算法。在理論上，本文提出的紅黑樹索引算法與文獻[8]提出的區(qū)間樹索引算法其構(gòu)建與查找效率均為O(lbN)（N為TIN中三角面片數(shù)），但文獻[8]算法在構(gòu)建區(qū)間樹時，需要預(yù)先確定同時顧及區(qū)間樹深度、平衡程度以及樹節(jié)點中元素個數(shù)的節(jié)點最優(yōu)分割值，無論采用排序方法還是統(tǒng)計方法都需要耗費大量時間，而本文算法在構(gòu)建以TIN三角面片單元為節(jié)點的紅黑樹過程中，是通過節(jié)點旋轉(zhuǎn)和顏色調(diào)整來動態(tài)保持樹的平衡狀態(tài)，不需要預(yù)先確定節(jié)點最優(yōu)分割值，因此，本文算法在預(yù)處理階段的實際時間效率要明顯優(yōu)于文獻[8]算法；此外，本文算法基于散列與半邊數(shù)據(jù)結(jié)構(gòu)重構(gòu)TIN拓撲，在等值點內(nèi)插計算的同時，根據(jù)“邊—面”拓撲關(guā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)用證明，本文算法運行穩(wěn)定，生成的等值線精度可靠，能夠滿足較大數(shù)據(jù)量條件下基于各種離散的地質(zhì)、地形數(shù)據(jù)快速生成等值線的需要。

6 結(jié)束語

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

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

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

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

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

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

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

[7]李強，李超，甘建紅.基于三角網(wǎng)的等值線填充算法研究[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].鄧俊輝，譯.北京：清華大學出版社，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格式實體的快速拓撲重建[J].工程圖學學報，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生成等值線圖是利用有限的離散空間信息恢復地質(zhì)屬性和地學變量空間分布狀態(tài)的重要手段之一，其時間效率主要取決于起始等值邊查找與等值線追蹤。通過構(gòu)建以TIN三角面片單元為節(jié)點的紅黑樹，將起始等值邊查找的時間復雜度由O(M×N)提高到O(lbN)；基于散列與半邊數(shù)據(jù)結(jié)構(gòu)重建TIN拓撲，根據(jù)TIN中“邊—面”拓撲關(guān)系，在等值點內(nèi)插計算的同時完成等值線追蹤。實驗及應(yīng)用表明，算法時間效率高，生成的等值線精度可靠，可滿足大數(shù)據(jù)量條件下等值線快速生成的需要，具有廣泛的實際應(yīng)用價值。

不規(guī)則三角網(wǎng)（TIN）；等值線；紅黑樹；散列；半邊數(shù)據(jù)結(jié)構(gòu)；拓撲重構(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.

國家自然科學基金（No.51174106）；遼寧省教育廳科學研究一般項目（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