等值線圖在地質(zhì)、物探、水文等許多工程領(lǐng)域都有廣泛的應(yīng)用，因此等值線圖的自動(dòng)生成問(wèn)題一直是人們研究的熱點(diǎn)。一般等值線圖的生成分為等值線生成和等值線填充兩個(gè)部分。目前，等值線的生成方法已經(jīng)很成熟，最常用的是等值線追蹤算法" title="等值線追蹤算法">等值線追蹤算法。近年來(lái)關(guān)于等值線填充算法的研究也很多，大致可分為掃描填充和區(qū)域填充兩類。其中掃描填充法出現(xiàn)較早，它通過(guò)插值計(jì)算每個(gè)待填充點(diǎn)的顏色值，進(jìn)行逐點(diǎn)填充。算法簡(jiǎn)單、可靠，但是填充速度慢，而且與追蹤法生成的等值線存在一些細(xì)微差異，因此目前關(guān)于掃描填充的研究已經(jīng)不多了。區(qū)域填充算法出現(xiàn)較晚^[1]，是研究的熱點(diǎn)。算法的基本思想是尋找等值區(qū)域，然后利用圖形庫(kù)的多邊形填充函數(shù)進(jìn)行充填。該算法對(duì)于填充大幅等值線圖效果明顯，但是由于需要追蹤等值區(qū)域并且判斷區(qū)域包含關(guān)系，因此算法比較復(fù)雜，而且對(duì)于等值線較多的情況，處理速度也較慢。
　　考慮到前面兩種算法的不足，本文借鑒了圖形學(xué)中關(guān)于多邊形快速填充的經(jīng)典算法——掃描線轉(zhuǎn)換算法" title="轉(zhuǎn)換算法">轉(zhuǎn)換算法^[2]，提出了一種利用掃描線填充等值線圖的快速算法。該算法利用掃描線與等值線的拓?fù)潢P(guān)系確定填充顏色，并充分利用掃面線間的相關(guān)性快速填充。無(wú)需計(jì)算每個(gè)填充點(diǎn)的顏色值，也無(wú)需尋找等值區(qū)域后再進(jìn)行多邊形填充，因此速度明顯優(yōu)于前兩類填充算法，而且填充效果與區(qū)域填充算法一致。
1 等值線追蹤算法
　　等值線追蹤是生成等值線圖的第一步。目前等值線追蹤算法的研究已經(jīng)比較成熟，根據(jù)追蹤的原始數(shù)據(jù)不同，分為規(guī)則矩形網(wǎng)格追蹤^[3]和三角網(wǎng)追蹤^[4]兩類。其中常用的等值線繪制軟件Surfer就是基于矩形數(shù)據(jù)網(wǎng)格的。當(dāng)然矩形網(wǎng)格不能用于不規(guī)則的圖形，因此后來(lái)又出現(xiàn)了基于三角網(wǎng)的等值線追蹤方法。本文主要介紹等值線填充算法，因?yàn)樘畛渌惴▋H需要利用等值線追蹤的結(jié)果，而與具體采用何種追蹤方法無(wú)關(guān)，因此這里不過(guò)多討論等值線追蹤算法，僅以矩形網(wǎng)格追蹤為例進(jìn)行簡(jiǎn)要說(shuō)明。
　　等值線追蹤的第一步是，計(jì)算出所有對(duì)應(yīng)某一值的等值點(diǎn)在網(wǎng)格邊線上的坐標(biāo)。這對(duì)于矩形網(wǎng)格來(lái)說(shuō)比較簡(jiǎn)單：先判斷網(wǎng)格邊線上是否存在等值點(diǎn)，如果存在則利用線性插值計(jì)算等值點(diǎn)在網(wǎng)格上的坐標(biāo)。得到全部邊線上的等值點(diǎn)后就需要使用一種追蹤策略，將孤立的等值點(diǎn)連接在一起形成等值線。一般先追蹤開曲線，即起止于網(wǎng)格邊界線上的等值線。追蹤開曲線可以順著四個(gè)邊界進(jìn)行，對(duì)于某個(gè)邊界任意選取一個(gè)等值點(diǎn)作為開始點(diǎn)，追蹤下一個(gè)等值點(diǎn)，直到追蹤到的下一個(gè)等值點(diǎn)也是邊界上的點(diǎn)，就完成了一條等值線的追蹤。
　　要從一個(gè)等值點(diǎn)追蹤到下一個(gè)等值點(diǎn)，這通常是利用上一次的追蹤方向來(lái)確定的。對(duì)于矩形網(wǎng)格來(lái)說(shuō)追蹤方向有4種，即向下、向左、向上和向右。如果上一次等值點(diǎn)所在網(wǎng)格的列比本次等值點(diǎn)所在列小1，則追蹤方向向右。對(duì)于每一種追蹤方向可能出現(xiàn)的情況有兩種。這里以向右追蹤為例進(jìn)行說(shuō)明，其余方向可以類推。向右追蹤時(shí)，如果網(wǎng)格其他三個(gè)邊上僅有一邊存在等值點(diǎn)，則選擇它作為下一個(gè)點(diǎn)；如果其他三邊均存在等值點(diǎn)則從相鄰的上、下邊中選取，計(jì)算上一個(gè)等值點(diǎn)到上、下邊中待選等值點(diǎn)的距離，取距離小的作為下一個(gè)等值點(diǎn)。利用上面的" title="面的">面的追蹤方法追蹤等值線一般都符合實(shí)際情況，并且不會(huì)出現(xiàn)交叉現(xiàn)象。
　　當(dāng)追蹤出一個(gè)等值點(diǎn)后需要將它刪除，這樣追蹤完一條等值線后就不會(huì)重復(fù)追蹤該等值線上的點(diǎn)了。當(dāng)某一邊界已沒有等值點(diǎn)可以追蹤后，就完成了該邊界的開曲線追蹤，對(duì)于矩形網(wǎng)格需要在四個(gè)邊界上都進(jìn)行開曲線追蹤。開曲線追蹤完畢后，可能還存在一些等值點(diǎn)，它們將構(gòu)成封閉的閉曲線，可以任取一點(diǎn)進(jìn)行追蹤，直至回到該點(diǎn)則完成追蹤。如果所有等值點(diǎn)都被追蹤過(guò)了，則關(guān)于該等值的等值線就全部追蹤完畢了。圖1是使用網(wǎng)格法追蹤生成的等值線圖。后面的填充算法將對(duì)它進(jìn)行快速填充。
　　利用追蹤算法得到的等值線，在網(wǎng)格比較稀疏的情況下顯得不夠平滑，往往還需要采用一種擬合方法對(duì)等值線進(jìn)行圓滑。一般可以使用三次參數(shù)樣條曲線或三次B樣條曲線^[2]來(lái)擬合加密曲線，達(dá)到圓滑的效果。不過(guò)為了保證曲線通過(guò)原有等值點(diǎn)，使用這兩種擬合方式時(shí)都需要求解線性方程組，速度比較慢，但是圓滑效果很好，因?yàn)槟軌虮ＷC二階連續(xù)。如果需要提高速度則可以采用HB曲線^[5]。該方法不需要求解方程，可以保證一階連續(xù)，對(duì)于大多數(shù)情況都可以取得滿意的效果，圖1中的等值線就使用了該方法進(jìn)行圓滑。

2 掃描線轉(zhuǎn)換算法
　　利用等值線追蹤算法已經(jīng)得到了全部的等值線，現(xiàn)在的問(wèn)題是如何選擇一組色標(biāo)并充填整幅等值線圖。色標(biāo)中的顏色數(shù)應(yīng)等于等值線的級(jí)數(shù)。由于人眼對(duì)灰度等級(jí)分辨能力不高，通常只有十幾個(gè)等級(jí)，因此應(yīng)當(dāng)選擇多個(gè)鍵色內(nèi)插形成色標(biāo)。另外為了提高填充速度，應(yīng)當(dāng)將內(nèi)插形成的色標(biāo)顏色組存儲(chǔ)下來(lái)，以便按等級(jí)數(shù)提取相應(yīng)的填充顏色。
2.1 填充掃描線
　　選定填充色標(biāo)后，就需要用色標(biāo)中的顏色來(lái)填充等值線圖了。但在介紹掃描線轉(zhuǎn)換算法之前，先考慮一下如何填充一條掃描線。圖2表示了一條水平掃描線與等值線相交的拓?fù)潢P(guān)系。這里假設(shè)等值線從0開始，間隔為10米，[0，10)對(duì)應(yīng)顏色為c0，[30，40)對(duì)應(yīng)顏色為c3，以此類推。算法首先需要求出掃描線與所有等值線的交點(diǎn)，并按照X坐標(biāo)的大小排序，接著根據(jù)等值線間的拓?fù)潢P(guān)系，確定相鄰兩個(gè)交點(diǎn)間應(yīng)該填充的顏色。觀察圖2可以發(fā)現(xiàn)相鄰交點(diǎn)有兩類情況：(1)前后交點(diǎn)的等高值不同，相差一個(gè)等級(jí)，如p0、p1交點(diǎn)對(duì)；(2)前后交點(diǎn)的等高值相同，如p3、p4交點(diǎn)對(duì)。

　　對(duì)于第(1)種情況，顏色的確定比較容易，如p0、p1交點(diǎn)對(duì)，因?yàn)榍昂蟮戎稻€的等值不同且必然相差一個(gè)等級(jí)，因此填充顏色應(yīng)當(dāng)取為[30，40)區(qū)段對(duì)應(yīng)的顏色c3。在實(shí)際計(jì)算中可以計(jì)算相鄰交點(diǎn)對(duì)應(yīng)等高值的平均值v，并令填充顏色為v對(duì)應(yīng)顏色。
　　第(2)種情況要復(fù)雜一些，因?yàn)榍昂髢蓚€(gè)交點(diǎn)不存在級(jí)差，因此無(wú)法直接判斷填充顏色，如p3、p4和p4、p5交點(diǎn)對(duì)。這時(shí)需要利用前一段填充的顏色來(lái)輔助判斷，例如填充p3、p4交點(diǎn)對(duì)時(shí)，考慮到p2、p3交點(diǎn)對(duì)對(duì)應(yīng)的等高值為50、60，而當(dāng)前填充交點(diǎn)對(duì)對(duì)應(yīng)的等高值為60、60，說(shuō)明當(dāng)前交點(diǎn)對(duì)對(duì)應(yīng)的顏色應(yīng)當(dāng)比上一段高一個(gè)色階，因而取為c6。這樣就可以利用前一段的色階推斷等高值相同的后一段對(duì)應(yīng)的填充顏色。在實(shí)際計(jì)算中，可以記下前一段的顏色等級(jí)g0，并且用當(dāng)前交點(diǎn)對(duì)中任意交點(diǎn)對(duì)應(yīng)的等高值計(jì)算出顏色等級(jí)g1。如果g0＜g1，則令g0=g1，當(dāng)前顏色取為cg0，否則取g0=g0-1，取當(dāng)前顏色為cg0。
　　前面討論了第一次出現(xiàn)等高值相同交點(diǎn)對(duì)的情況，但是有時(shí)候等高值相同的交點(diǎn)對(duì)會(huì)連續(xù)出現(xiàn)，例如p3、p4交點(diǎn)對(duì)后面的p4、p5交點(diǎn)對(duì)等高值也相同，這時(shí)是否可以繼續(xù)使用前面的算法呢？不妨用前面的算法試一下，p3、p4交點(diǎn)對(duì)使用填充色c6，即g0=6，p5對(duì)應(yīng)的顏色等級(jí)g1=6，按照前面的算法g0不小于g1，因此取g0=6-1=5，顏色取c5，恰巧正確。這是因?yàn)楦鶕?jù)等值線不會(huì)相交的特點(diǎn)，如果連續(xù)出現(xiàn)等高值相同的交點(diǎn)對(duì)，那么交點(diǎn)對(duì)的顏色取值將會(huì)是交替變化的。利用前面的算法處理連續(xù)相同的交點(diǎn)對(duì)，也會(huì)得到交替變化的顏色，測(cè)試對(duì)于其他情況前面的算法也都是成立的。
2.2 掃描線轉(zhuǎn)換算法快速填充等值線圖
　　前面介紹了填充一條掃描線的方法，如果將一幅等值線圖的所有掃描線都按上面的算法填充，就可以得到填充后的等值線圖。不過(guò)填充的速度比較慢，因?yàn)槊織l掃描線都需要與全部等值線求交，并按交點(diǎn)水平坐標(biāo)大小排序，工作量很大，耗時(shí)較多。然而實(shí)際上一條掃描線僅僅會(huì)與一些等值線的某個(gè)邊相交，并且與上一條掃描線相交的邊一般也會(huì)與下一條掃描線相交，掃描線之間存在著相關(guān)性。因此可以借鑒圖形學(xué)中填充多邊形的掃描線轉(zhuǎn)換算法，充分利用這些相關(guān)性，提高填充速度。下面詳細(xì)介紹掃描線轉(zhuǎn)換算法所需要使用的數(shù)據(jù)結(jié)構(gòu)和算法流程。
　　為了有效利用掃描線的相關(guān)性，在掃描線轉(zhuǎn)換算法中需要建立如下數(shù)據(jù)結(jié)構(gòu)：
　　(1)等值線Y桶。等值線Y桶用于記錄等值線的基本信息，桶的長(zhǎng)度與掃描線的條數(shù)一樣多，其編號(hào)與掃描線序號(hào)一致。每條等值線都要生成一個(gè)桶記錄項(xiàng)，記錄該等值線的最大Y坐標(biāo)ymax、指向等值線的指針和指向該等值線邊Y桶的指針。桶記錄項(xiàng)按等值線的最小Y坐標(biāo)插入到桶中。圖3為等值線Y桶數(shù)據(jù)結(jié)構(gòu)的示意圖。

　　(2)有效等值線表AIT。該表存儲(chǔ)與當(dāng)前掃描線相交的所有等值線在等值線Y桶中的記錄指針。
　　(3)邊Y桶。每條等值線都由一系列的邊組成，為了利用相關(guān)性，需要建立等值線的邊Y桶，記錄每條邊的基本信息。等值線邊Y桶的長(zhǎng)度等于與該等值線相交的掃描線的條數(shù)。對(duì)于等值線中的每條邊都要產(chǎn)生一個(gè)邊記錄，記錄該邊的最大Y坐標(biāo)ymax，Y值較小端對(duì)應(yīng)的X坐標(biāo)xmin，當(dāng)掃描線增大1時(shí)X坐標(biāo)的增量Δx，以及等值線的值value。每一個(gè)邊記錄按該邊的最小Y坐標(biāo)和整條等值線的最小Y坐標(biāo)的差值存入邊桶中，圖4為邊Y桶數(shù)據(jù)結(jié)構(gòu)的示意圖。

　　(4)有效邊表AET。該表存儲(chǔ)與當(dāng)前掃描線相交的所有等值線的邊在邊Y桶中的記錄指針。
　　利用上面的數(shù)據(jù)結(jié)構(gòu)，一個(gè)完整的掃描線轉(zhuǎn)化填充算法如下：
　　(1)遍歷所有的等值線，為每一條等值線生成一個(gè)等值線Y桶中的記錄，并根據(jù)等值線的最小Y坐標(biāo)將該記錄加入到等值線Y桶中。
　　(2)將有效等值線表AIT和有效邊表AET初始化為空。
　　(3)對(duì)于每一條掃描線i，它從最小值開始，做以下工作。①檢查等值線Y桶對(duì)于掃描線i是否有新的等值線記錄，如果有則生成該掃描線對(duì)應(yīng)的邊Y桶，并在有效等值線表AIT中加入該掃描線的桶記錄。②遍歷AIT中的每一條等值線對(duì)應(yīng)的桶記錄，檢查該等值線對(duì)應(yīng)的邊Y桶對(duì)于掃描線i是否有新的邊記錄加入，如果有則將新的邊記錄按xmin字段的大小加入到有效邊表AET中。③利用有效邊表AET和掃描線填充算法填充該掃描線。④遍歷AET，檢查是否有邊記錄的ymax字段等于i，如果有則刪除該邊記錄，否則令該邊記錄的xmin=xmin+Δx。⑤遍歷AIT表，檢查是否有等值線記錄的ymax字段等于i，如果有則刪除該記錄。
　　利用上面的算法可以實(shí)現(xiàn)等值線的填充，由于使用了掃描線轉(zhuǎn)換算法，其算法復(fù)雜度與多邊形填充一致，因而速度優(yōu)勢(shì)很明顯。圖5和圖6是利用上面算法填充的等值線圖。其中圖5原始網(wǎng)格數(shù)據(jù)為10行×15列，圖幅450×300像素，色標(biāo)含35個(gè)色階，由4個(gè)鍵色插值生成，在主頻為1.4GHz的電腦上填充時(shí)間約為40ms。圖6原始網(wǎng)格數(shù)據(jù)為215行×330列，圖幅990×645像素，色標(biāo)含42個(gè)色階，由4個(gè)鍵色插值生成，在主頻為1.4GHz的電腦上填充時(shí)間約為120ms。從填充效果來(lái)看，填充結(jié)果與等值線一致，色階正確沒有出現(xiàn)任何誤填和漏填錯(cuò)誤。填充結(jié)果與其他填充算法結(jié)果一致。