正規(guī)論文發(fā)表快速的等值線生成算法

　　摘 要：本文提出了一種新的等值點位于網(wǎng)格點時，對等值點的調(diào)整方法;在分析已有等值線追蹤算法的基礎(chǔ)上，提出了一種基于TIN網(wǎng)格的快速等值線追蹤算法，實驗表明該算法具有較高的執(zhí)行效率。

　　關(guān)鍵詞：等值線 等值點 TIN網(wǎng)格

　　等值線圖能直觀地展示數(shù)據(jù)的變化趨勢，是眾多領(lǐng)域展示成果的重要圖件之一，被廣泛應(yīng)用于石油勘探、礦物開采、氣象預(yù)報等眾多領(lǐng)域。等值線的繪制是指從大量采樣數(shù)據(jù)中提取出具有相同值的點的信息，并生成形態(tài)完整、位置精確的等值線的過程，包括等值線網(wǎng)格化、等值線追蹤、等值線光滑、等值線填充與標注幾個處理步驟[1]。其中等值線網(wǎng)格化是對網(wǎng)格邊進行線性插值，進而求出等值點的過程。等值線的追蹤則是利用等值線網(wǎng)格化產(chǎn)生的等值點數(shù)據(jù)，將其中相同等值點進行連接的過程。等值線追蹤的傳統(tǒng)方法是，在網(wǎng)格單元邊上選取一個等值點，尋找鄰近的等值點，順次連接成線，直到等值點回到起始點或位于工區(qū)邊界，完成單條等值線的追蹤，并以此為基礎(chǔ)遍歷所有的等值點。在追蹤過程中，等值線分為閉合與非閉合兩種情形，需要先追蹤開曲線，再追蹤閉曲線，否則不能確保結(jié)果正確。特定的搜索順序提高了處理過程的復(fù)雜性，增加了網(wǎng)格單元的重復(fù)搜索次數(shù)，致使效率低下。

　　針對此類問題，很多學(xué)者提出了在不規(guī)則三角網(wǎng)(TIN網(wǎng)格)下的改進方法，成建梅[2]等提出為三角形三邊分別賦予不同的權(quán)值，以方便確定三角形單元內(nèi)等值點的位置。但是這只是對局部的改進，未涉及等值線追蹤過程的優(yōu)化。黃維科[3]等基于三角形單元內(nèi)等值線段容易確定的事實，提出了使用“焊接法”將相同的等值點連接從而生成整條等值線的方法。但是在搜索等值線段間的共同等值點時，需要對已確定的等值線段進行遍歷，執(zhí)行效率提高幅度有限;并且使用的是簡單的坐標值判別法，容易因機器誤差引起錯誤結(jié)果。

　　1 改進的等值線生成算法

　　現(xiàn)在常用的用于生成等值線的網(wǎng)格有矩形網(wǎng)格、TIN網(wǎng)格等。綜合考慮，本文選用TIN網(wǎng)格。生成等值線的主要步驟中，等值線的網(wǎng)格化處理與等值線的追蹤是基礎(chǔ)與關(guān)鍵，直接影響等值線的準確度和生成速度。接下來將針對TIN網(wǎng)格，介紹對這兩個過程的改進。

　　1.1 等值線網(wǎng)格化處理方法

　　在TIN網(wǎng)格中，等值線網(wǎng)格化處理的作用就是在網(wǎng)格邊上計算出各等值點，為之后的等值線追蹤提供基礎(chǔ)數(shù)據(jù)。以三角形單元為單位，遍歷整個TIN網(wǎng)格，判斷三角形棱邊上有無等值點[4]，使用公式：

　　其中z為等值線的高程，zi，zj是對應(yīng)三角形頂點的高程。若存在，則等值點的坐標為：

　　1.2 等值線追蹤算法

　　本文采用的追蹤思想即是：從一個等值點出發(fā)，沿任意方向搜索等值點，直到回到起點或者到達邊界;再從起點開始沿反向搜索未經(jīng)過的點。最終生成一條等值線。

　　為了提高搜索效率，注意到在經(jīng)過網(wǎng)格化處理后，可以保證每條三角形棱邊至多有一個等值點，而與該等值點相連的等值點至多有兩個。所以在以三角形單元為單位遍歷TIN網(wǎng)格時，給每一棱邊指定唯一的序號，若找出等值點，則記錄與之相連的等值點所處的棱邊。接下來以棱邊為基本單元追蹤等值線，這樣的好處是便于構(gòu)造順序存儲結(jié)構(gòu)，進而使用隨機存取機制，加快追蹤速度。

　　序號的引入將問題轉(zhuǎn)化為簡單的數(shù)值匹配，避免了常規(guī)算法中使用的方位信息。同時可以忽略常規(guī)等值線追蹤算法中的特定追蹤順序，對于拓撲復(fù)雜TIN網(wǎng)格，不考慮三角形棱邊是否位于邊界上可以大大簡化處理的復(fù)雜度。

　　2 算法實現(xiàn)

　　2.1 數(shù)據(jù)結(jié)構(gòu)

　　程序要兼顧按索引查找時的快捷和等值點插入的便利，故選擇混合存儲結(jié)構(gòu)。具體實現(xiàn)如下。