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

董肇偉++盧海達(dá)++倪廣元++王劍秦

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

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

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）04（a）-0033-02

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

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

1 改進(jìn)的等值線生成算法

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

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

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

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

1.2 等值線追蹤算法

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

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

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

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

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

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

等值點(diǎn)的數(shù)據(jù)結(jié)構(gòu)見表1。

三角單元棱邊的數(shù)據(jù)結(jié)構(gòu)見表2。

其中訪問標(biāo)記指示是否追蹤過該邊，初始時(shí)置為False。等值點(diǎn)1是位于該邊上的等值點(diǎn)。等值點(diǎn)2指針指向當(dāng)前等值線上的另一個(gè)端點(diǎn)（隊(duì)尾）。鄰接邊1，2上的等值點(diǎn)與該邊上的相連。

當(dāng)完成等值線網(wǎng)格化處理后，所有等值點(diǎn)被計(jì)算出，三角網(wǎng)格邊中的棱邊序號(hào)、等值點(diǎn)1指針、鄰接棱邊1與鄰接棱邊2的序號(hào)均被確定。特別的，當(dāng)棱邊上的等值點(diǎn)為一條非閉合等值線的端點(diǎn)時(shí)，它只有一個(gè)有效的鄰接棱邊。

2.2 算法流程

（1）從TIN網(wǎng)格中順次讀取一個(gè)棱邊E1。如果E1上不存在等值點(diǎn)，或訪問標(biāo)記為TRUE，重復(fù)步驟（1）。否則，置訪問標(biāo)記為True，根據(jù)鄰接邊1序號(hào)讀取棱邊Ei，轉(zhuǎn)到步驟（2）。

（2）置Ei的訪問標(biāo)記為True，并將它的等值點(diǎn)移動(dòng)到前一個(gè)等值點(diǎn)的末尾。若Ei即是E1，完成單條等值線的搜索，轉(zhuǎn)到步驟（1）。否則，讀取Ei上不同于前一棱邊的鄰接邊序號(hào)。若存在，則在讀取新的棱邊Ei，重復(fù)步驟（2）。若不存在，根據(jù)E1的鄰接邊2序號(hào)取出棱邊Ej，轉(zhuǎn)到步驟（3）。

（3）置Ej的訪問標(biāo)記為True，將等值線頭結(jié)點(diǎn)移動(dòng)到Ej上等值點(diǎn)的末尾。讀取Ej上不同于后一個(gè)點(diǎn)所在邊的鄰接邊序號(hào)。若存在，則取出新的棱邊Ej，重復(fù)步驟（3）。若不存在，完成單條等值線的搜索，轉(zhuǎn)到步驟（1）。

當(dāng)所有棱邊都在步驟（1）中被讀取過后，算法完成。

3 實(shí)驗(yàn)結(jié)果與分析

筆者將本文提出的改進(jìn)算法運(yùn)用到“裂縫性儲(chǔ)層精細(xì)描述軟件”當(dāng)中，利用該算法獲得層面模型的等值線，并經(jīng)過平滑、著色處理后，得到如圖4所示的效果圖。

為進(jìn)一步測(cè)試算法效率，利用圖4中的層面，計(jì)算傳統(tǒng)追蹤算法和改進(jìn)算法的運(yùn)行時(shí)間。層面模型包含22827個(gè)坐標(biāo)點(diǎn)，出于確保結(jié)果有效性的考慮，指定等值線高程值的個(gè)數(shù)分別為5，10，15，…，60，從而獲得12組測(cè)試數(shù)據(jù)。隨著高程值個(gè)數(shù)的增加，程序會(huì)多次調(diào)用追蹤算法，相當(dāng)于增多了模型坐標(biāo)點(diǎn)與等值點(diǎn)的個(gè)數(shù)。

采用改進(jìn)算法追蹤等值線，速度平均提升30%以上。這是因?yàn)橛捎赥IN網(wǎng)格拓?fù)鋸?fù)雜，追蹤等值線時(shí)大量時(shí)間消耗在對(duì)網(wǎng)格的遍歷上。傳統(tǒng)算法在計(jì)算等值點(diǎn)時(shí)需要遍歷一遍網(wǎng)格，在進(jìn)行等值線追蹤時(shí)，又要遍歷兩遍：第一遍以位于網(wǎng)格邊界的等值點(diǎn)為起點(diǎn)，查找非閉合等值線；第二遍再查找閉合等值線。而本文提出的改進(jìn)算法只需要在計(jì)算等值點(diǎn)時(shí)遍歷一遍網(wǎng)格，由于遍歷時(shí)為三角形單元的棱邊設(shè)置索引，在追蹤等值線時(shí)，直接按索引遍歷從而避開了TIN網(wǎng)格的復(fù)雜性對(duì)程序的不良影響。并且，改進(jìn)算法中不區(qū)分等值線的開閉性，可以用統(tǒng)一的過程追蹤，又減少一次對(duì)棱邊的遍歷。故改進(jìn)算法的時(shí)間性能大幅優(yōu)于傳統(tǒng)算法。

4 結(jié)論

本文基于TIN網(wǎng)格，提出了一種快速的等值線生成算法，該算法改進(jìn)了等值點(diǎn)位于網(wǎng)格頂點(diǎn)時(shí)，對(duì)其進(jìn)行偏移的方法，盡最大限度減小偏移量的不確定性，使結(jié)果更貼合原始數(shù)據(jù)。之后，針對(duì)現(xiàn)有主流追蹤算法過程繁瑣，實(shí)現(xiàn)復(fù)雜的弱點(diǎn)，為三角單元棱邊設(shè)置索引，簡(jiǎn)化遍歷過程，并將閉合和非閉合兩種等值線的追蹤方法統(tǒng)一，大大簡(jiǎn)化追蹤流程。在等值線繪圖中，采用TIN網(wǎng)格有兩大優(yōu)點(diǎn)：一是等值線連接方式唯一，不會(huì)出現(xiàn)矩形網(wǎng)格中的二義性問題；二是TIN網(wǎng)格使用的是原始數(shù)據(jù)點(diǎn)，避免了網(wǎng)格擬合帶來的誤差，尤其在原始數(shù)據(jù)密集的情況下，能高度還原地形地貌。本文的工作使得TIN網(wǎng)格下等值線的追蹤更加方便快捷，從而可以較好的應(yīng)用于地質(zhì)建模領(lǐng)域。

參考文獻(xiàn)

[1] 王鵬.等值線快速繪圖方法研究及系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].電子科技大學(xué)，2011.

[2] 成建梅，陳崇希，孫紅林.三角網(wǎng)格等值線自動(dòng)生成方法及程序?qū)崿F(xiàn)[J].水利學(xué)報(bào)，1998，10（10）：23-26.

[3] 黃維科，王弘琪.在AutoCAD中用“焊接法”繪制等高線[J].公路與汽運(yùn)，2005，1：29.

[4] 李瑞雪.球物理等值線構(gòu)建及屬性建立[D].中南大學(xué)，2012.

[5] 韓麗娜.地質(zhì)等值線圖的生成與繪制[D].西安：西安科技大學(xué)，2006.endprint

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

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

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）04（a）-0033-02

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

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

1 改進(jìn)的等值線生成算法

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

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

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

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

1.2 等值線追蹤算法

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

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

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

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

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

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

等值點(diǎn)的數(shù)據(jù)結(jié)構(gòu)見表1。

三角單元棱邊的數(shù)據(jù)結(jié)構(gòu)見表2。

其中訪問標(biāo)記指示是否追蹤過該邊，初始時(shí)置為False。等值點(diǎn)1是位于該邊上的等值點(diǎn)。等值點(diǎn)2指針指向當(dāng)前等值線上的另一個(gè)端點(diǎn)（隊(duì)尾）。鄰接邊1，2上的等值點(diǎn)與該邊上的相連。

當(dāng)完成等值線網(wǎng)格化處理后，所有等值點(diǎn)被計(jì)算出，三角網(wǎng)格邊中的棱邊序號(hào)、等值點(diǎn)1指針、鄰接棱邊1與鄰接棱邊2的序號(hào)均被確定。特別的，當(dāng)棱邊上的等值點(diǎn)為一條非閉合等值線的端點(diǎn)時(shí)，它只有一個(gè)有效的鄰接棱邊。

2.2 算法流程

（1）從TIN網(wǎng)格中順次讀取一個(gè)棱邊E1。如果E1上不存在等值點(diǎn)，或訪問標(biāo)記為TRUE，重復(fù)步驟（1）。否則，置訪問標(biāo)記為True，根據(jù)鄰接邊1序號(hào)讀取棱邊Ei，轉(zhuǎn)到步驟（2）。

（2）置Ei的訪問標(biāo)記為True，并將它的等值點(diǎn)移動(dòng)到前一個(gè)等值點(diǎn)的末尾。若Ei即是E1，完成單條等值線的搜索，轉(zhuǎn)到步驟（1）。否則，讀取Ei上不同于前一棱邊的鄰接邊序號(hào)。若存在，則在讀取新的棱邊Ei，重復(fù)步驟（2）。若不存在，根據(jù)E1的鄰接邊2序號(hào)取出棱邊Ej，轉(zhuǎn)到步驟（3）。

（3）置Ej的訪問標(biāo)記為True，將等值線頭結(jié)點(diǎn)移動(dòng)到Ej上等值點(diǎn)的末尾。讀取Ej上不同于后一個(gè)點(diǎn)所在邊的鄰接邊序號(hào)。若存在，則取出新的棱邊Ej，重復(fù)步驟（3）。若不存在，完成單條等值線的搜索，轉(zhuǎn)到步驟（1）。

當(dāng)所有棱邊都在步驟（1）中被讀取過后，算法完成。

3 實(shí)驗(yàn)結(jié)果與分析

筆者將本文提出的改進(jìn)算法運(yùn)用到“裂縫性儲(chǔ)層精細(xì)描述軟件”當(dāng)中，利用該算法獲得層面模型的等值線，并經(jīng)過平滑、著色處理后，得到如圖4所示的效果圖。

為進(jìn)一步測(cè)試算法效率，利用圖4中的層面，計(jì)算傳統(tǒng)追蹤算法和改進(jìn)算法的運(yùn)行時(shí)間。層面模型包含22827個(gè)坐標(biāo)點(diǎn)，出于確保結(jié)果有效性的考慮，指定等值線高程值的個(gè)數(shù)分別為5，10，15，…，60，從而獲得12組測(cè)試數(shù)據(jù)。隨著高程值個(gè)數(shù)的增加，程序會(huì)多次調(diào)用追蹤算法，相當(dāng)于增多了模型坐標(biāo)點(diǎn)與等值點(diǎn)的個(gè)數(shù)。

采用改進(jìn)算法追蹤等值線，速度平均提升30%以上。這是因?yàn)橛捎赥IN網(wǎng)格拓?fù)鋸?fù)雜，追蹤等值線時(shí)大量時(shí)間消耗在對(duì)網(wǎng)格的遍歷上。傳統(tǒng)算法在計(jì)算等值點(diǎn)時(shí)需要遍歷一遍網(wǎng)格，在進(jìn)行等值線追蹤時(shí)，又要遍歷兩遍：第一遍以位于網(wǎng)格邊界的等值點(diǎn)為起點(diǎn)，查找非閉合等值線；第二遍再查找閉合等值線。而本文提出的改進(jìn)算法只需要在計(jì)算等值點(diǎn)時(shí)遍歷一遍網(wǎng)格，由于遍歷時(shí)為三角形單元的棱邊設(shè)置索引，在追蹤等值線時(shí)，直接按索引遍歷從而避開了TIN網(wǎng)格的復(fù)雜性對(duì)程序的不良影響。并且，改進(jìn)算法中不區(qū)分等值線的開閉性，可以用統(tǒng)一的過程追蹤，又減少一次對(duì)棱邊的遍歷。故改進(jìn)算法的時(shí)間性能大幅優(yōu)于傳統(tǒng)算法。

4 結(jié)論

本文基于TIN網(wǎng)格，提出了一種快速的等值線生成算法，該算法改進(jìn)了等值點(diǎn)位于網(wǎng)格頂點(diǎn)時(shí)，對(duì)其進(jìn)行偏移的方法，盡最大限度減小偏移量的不確定性，使結(jié)果更貼合原始數(shù)據(jù)。之后，針對(duì)現(xiàn)有主流追蹤算法過程繁瑣，實(shí)現(xiàn)復(fù)雜的弱點(diǎn)，為三角單元棱邊設(shè)置索引，簡(jiǎn)化遍歷過程，并將閉合和非閉合兩種等值線的追蹤方法統(tǒng)一，大大簡(jiǎn)化追蹤流程。在等值線繪圖中，采用TIN網(wǎng)格有兩大優(yōu)點(diǎn)：一是等值線連接方式唯一，不會(huì)出現(xiàn)矩形網(wǎng)格中的二義性問題；二是TIN網(wǎng)格使用的是原始數(shù)據(jù)點(diǎn)，避免了網(wǎng)格擬合帶來的誤差，尤其在原始數(shù)據(jù)密集的情況下，能高度還原地形地貌。本文的工作使得TIN網(wǎng)格下等值線的追蹤更加方便快捷，從而可以較好的應(yīng)用于地質(zhì)建模領(lǐng)域。

參考文獻(xiàn)

[1] 王鵬.等值線快速繪圖方法研究及系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].電子科技大學(xué)，2011.

[2] 成建梅，陳崇希，孫紅林.三角網(wǎng)格等值線自動(dòng)生成方法及程序?qū)崿F(xiàn)[J].水利學(xué)報(bào)，1998，10（10）：23-26.

[3] 黃維科，王弘琪.在AutoCAD中用“焊接法”繪制等高線[J].公路與汽運(yùn)，2005，1：29.

[4] 李瑞雪.球物理等值線構(gòu)建及屬性建立[D].中南大學(xué)，2012.

[5] 韓麗娜.地質(zhì)等值線圖的生成與繪制[D].西安：西安科技大學(xué)，2006.endprint

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

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

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2014）04（a）-0033-02

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

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

1 改進(jìn)的等值線生成算法

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

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

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

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

1.2 等值線追蹤算法

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

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

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

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

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

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

等值點(diǎn)的數(shù)據(jù)結(jié)構(gòu)見表1。

三角單元棱邊的數(shù)據(jù)結(jié)構(gòu)見表2。

其中訪問標(biāo)記指示是否追蹤過該邊，初始時(shí)置為False。等值點(diǎn)1是位于該邊上的等值點(diǎn)。等值點(diǎn)2指針指向當(dāng)前等值線上的另一個(gè)端點(diǎn)（隊(duì)尾）。鄰接邊1，2上的等值點(diǎn)與該邊上的相連。

當(dāng)完成等值線網(wǎng)格化處理后，所有等值點(diǎn)被計(jì)算出，三角網(wǎng)格邊中的棱邊序號(hào)、等值點(diǎn)1指針、鄰接棱邊1與鄰接棱邊2的序號(hào)均被確定。特別的，當(dāng)棱邊上的等值點(diǎn)為一條非閉合等值線的端點(diǎn)時(shí)，它只有一個(gè)有效的鄰接棱邊。

2.2 算法流程

（1）從TIN網(wǎng)格中順次讀取一個(gè)棱邊E1。如果E1上不存在等值點(diǎn)，或訪問標(biāo)記為TRUE，重復(fù)步驟（1）。否則，置訪問標(biāo)記為True，根據(jù)鄰接邊1序號(hào)讀取棱邊Ei，轉(zhuǎn)到步驟（2）。

（2）置Ei的訪問標(biāo)記為True，并將它的等值點(diǎn)移動(dòng)到前一個(gè)等值點(diǎn)的末尾。若Ei即是E1，完成單條等值線的搜索，轉(zhuǎn)到步驟（1）。否則，讀取Ei上不同于前一棱邊的鄰接邊序號(hào)。若存在，則在讀取新的棱邊Ei，重復(fù)步驟（2）。若不存在，根據(jù)E1的鄰接邊2序號(hào)取出棱邊Ej，轉(zhuǎn)到步驟（3）。

（3）置Ej的訪問標(biāo)記為True，將等值線頭結(jié)點(diǎn)移動(dòng)到Ej上等值點(diǎn)的末尾。讀取Ej上不同于后一個(gè)點(diǎn)所在邊的鄰接邊序號(hào)。若存在，則取出新的棱邊Ej，重復(fù)步驟（3）。若不存在，完成單條等值線的搜索，轉(zhuǎn)到步驟（1）。

當(dāng)所有棱邊都在步驟（1）中被讀取過后，算法完成。

3 實(shí)驗(yàn)結(jié)果與分析

筆者將本文提出的改進(jìn)算法運(yùn)用到“裂縫性儲(chǔ)層精細(xì)描述軟件”當(dāng)中，利用該算法獲得層面模型的等值線，并經(jīng)過平滑、著色處理后，得到如圖4所示的效果圖。

為進(jìn)一步測(cè)試算法效率，利用圖4中的層面，計(jì)算傳統(tǒng)追蹤算法和改進(jìn)算法的運(yùn)行時(shí)間。層面模型包含22827個(gè)坐標(biāo)點(diǎn)，出于確保結(jié)果有效性的考慮，指定等值線高程值的個(gè)數(shù)分別為5，10，15，…，60，從而獲得12組測(cè)試數(shù)據(jù)。隨著高程值個(gè)數(shù)的增加，程序會(huì)多次調(diào)用追蹤算法，相當(dāng)于增多了模型坐標(biāo)點(diǎn)與等值點(diǎn)的個(gè)數(shù)。

采用改進(jìn)算法追蹤等值線，速度平均提升30%以上。這是因?yàn)橛捎赥IN網(wǎng)格拓?fù)鋸?fù)雜，追蹤等值線時(shí)大量時(shí)間消耗在對(duì)網(wǎng)格的遍歷上。傳統(tǒng)算法在計(jì)算等值點(diǎn)時(shí)需要遍歷一遍網(wǎng)格，在進(jìn)行等值線追蹤時(shí)，又要遍歷兩遍：第一遍以位于網(wǎng)格邊界的等值點(diǎn)為起點(diǎn)，查找非閉合等值線；第二遍再查找閉合等值線。而本文提出的改進(jìn)算法只需要在計(jì)算等值點(diǎn)時(shí)遍歷一遍網(wǎng)格，由于遍歷時(shí)為三角形單元的棱邊設(shè)置索引，在追蹤等值線時(shí)，直接按索引遍歷從而避開了TIN網(wǎng)格的復(fù)雜性對(duì)程序的不良影響。并且，改進(jìn)算法中不區(qū)分等值線的開閉性，可以用統(tǒng)一的過程追蹤，又減少一次對(duì)棱邊的遍歷。故改進(jìn)算法的時(shí)間性能大幅優(yōu)于傳統(tǒng)算法。

4 結(jié)論

本文基于TIN網(wǎng)格，提出了一種快速的等值線生成算法，該算法改進(jìn)了等值點(diǎn)位于網(wǎng)格頂點(diǎn)時(shí)，對(duì)其進(jìn)行偏移的方法，盡最大限度減小偏移量的不確定性，使結(jié)果更貼合原始數(shù)據(jù)。之后，針對(duì)現(xiàn)有主流追蹤算法過程繁瑣，實(shí)現(xiàn)復(fù)雜的弱點(diǎn)，為三角單元棱邊設(shè)置索引，簡(jiǎn)化遍歷過程，并將閉合和非閉合兩種等值線的追蹤方法統(tǒng)一，大大簡(jiǎn)化追蹤流程。在等值線繪圖中，采用TIN網(wǎng)格有兩大優(yōu)點(diǎn)：一是等值線連接方式唯一，不會(huì)出現(xiàn)矩形網(wǎng)格中的二義性問題；二是TIN網(wǎng)格使用的是原始數(shù)據(jù)點(diǎn)，避免了網(wǎng)格擬合帶來的誤差，尤其在原始數(shù)據(jù)密集的情況下，能高度還原地形地貌。本文的工作使得TIN網(wǎng)格下等值線的追蹤更加方便快捷，從而可以較好的應(yīng)用于地質(zhì)建模領(lǐng)域。

參考文獻(xiàn)

[1] 王鵬.等值線快速繪圖方法研究及系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].電子科技大學(xué)，2011.

[2] 成建梅，陳崇希，孫紅林.三角網(wǎng)格等值線自動(dòng)生成方法及程序?qū)崿F(xiàn)[J].水利學(xué)報(bào)，1998，10（10）：23-26.

[3] 黃維科，王弘琪.在AutoCAD中用“焊接法”繪制等高線[J].公路與汽運(yùn)，2005，1：29.

[4] 李瑞雪.球物理等值線構(gòu)建及屬性建立[D].中南大學(xué)，2012.

[5] 韓麗娜.地質(zhì)等值線圖的生成與繪制[D].西安：西安科技大學(xué)，2006.endprint