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

2 掃描線(xiàn)轉(zhuǎn)換算法
　　利用等值線(xiàn)追蹤算法已經(jīng)得到了全部的等值線(xiàn),，現(xiàn)在的問(wèn)題是如何選擇一組色標(biāo)并充填整幅等值線(xiàn)圖,。色標(biāo)中的顏色數(shù)應(yīng)等于等值線(xiàn)的級(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 填充掃描線(xiàn)
　　選定填充色標(biāo)后,，就需要用色標(biāo)中的顏色來(lái)填充等值線(xiàn)圖了,。但在介紹掃描線(xiàn)轉(zhuǎn)換算法之前，先考慮一下如何填充一條掃描線(xiàn),。圖2表示了一條水平掃描線(xiàn)與等值線(xiàn)相交的拓?fù)潢P(guān)系,。這里假設(shè)等值線(xiàn)從0開(kāi)始，間隔為10米,，[0,，10)對(duì)應(yīng)顏色為c0，[30,，40)對(duì)應(yīng)顏色為c3,，以此類(lèi)推,。算法首先需要求出掃描線(xiàn)與所有等值線(xiàn)的交點(diǎn),，并按照X坐標(biāo)的大小排序，接著根據(jù)等值線(xiàn)間的拓?fù)潢P(guān)系,，確定相鄰兩個(gè)交點(diǎn)間應(yīng)該填充的顏色,。觀察圖2可以發(fā)現(xiàn)相鄰交點(diǎn)有兩類(lèi)情況：(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)榍昂蟮戎稻€(xià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ù)等值線(xiàn)不會(huì)相交的特點(diǎn)，如果連續(xù)出現(xiàn)等高值相同的交點(diǎn)對(duì),，那么交點(diǎn)對(duì)的顏色取值將會(huì)是交替變化的,。利用前面的算法處理連續(xù)相同的交點(diǎn)對(duì)，也會(huì)得到交替變化的顏色,，測(cè)試對(duì)于其他情況前面的算法也都是成立的,。
2.2 掃描線(xiàn)轉(zhuǎn)換算法快速填充等值線(xiàn)圖
　　前面介紹了填充一條掃描線(xiàn)的方法，如果將一幅等值線(xiàn)圖的所有掃描線(xiàn)都按上面的算法填充,，就可以得到填充后的等值線(xiàn)圖,。不過(guò)填充的速度比較慢，因?yàn)槊織l掃描線(xiàn)都需要與全部等值線(xiàn)求交,，并按交點(diǎn)水平坐標(biāo)大小排序,，工作量很大，耗時(shí)較多,。然而實(shí)際上一條掃描線(xiàn)僅僅會(huì)與一些等值線(xiàn)的某個(gè)邊相交,，并且與上一條掃描線(xiàn)相交的邊一般也會(huì)與下一條掃描線(xiàn)相交，掃描線(xiàn)之間存在著相關(guān)性,。因此可以借鑒圖形學(xué)中填充多邊形的掃描線(xiàn)轉(zhuǎn)換算法,，充分利用這些相關(guān)性，提高填充速度,。下面詳細(xì)介紹掃描線(xiàn)轉(zhuǎn)換算法所需要使用的數(shù)據(jù)結(jié)構(gòu)和算法流程,。
　　為了有效利用掃描線(xiàn)的相關(guān)性，在掃描線(xiàn)轉(zhuǎn)換算法中需要建立如下數(shù)據(jù)結(jié)構(gòu)：
　　(1)等值線(xiàn)Y桶,。等值線(xiàn)Y桶用于記錄等值線(xiàn)的基本信息,，桶的長(zhǎng)度與掃描線(xiàn)的條數(shù)一樣多,，其編號(hào)與掃描線(xiàn)序號(hào)一致,。每條等值線(xiàn)都要生成一個(gè)桶記錄項(xiàng)，記錄該等值線(xiàn)的最大Y坐標(biāo)ymax,、指向等值線(xiàn)的指針和指向該等值線(xiàn)邊Y桶的指針,。桶記錄項(xiàng)按等值線(xiàn)的最小Y坐標(biāo)插入到桶中。圖3為等值線(xiàn)Y桶數(shù)據(jù)結(jié)構(gòu)的示意圖。

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

　　(4)有效邊表AET,。該表存儲(chǔ)與當(dāng)前掃描線(xiàn)相交的所有等值線(xiàn)的邊在邊Y桶中的記錄指針,。
　　利用上面的數(shù)據(jù)結(jié)構(gòu)，一個(gè)完整的掃描線(xiàn)轉(zhuǎn)化填充算法如下：
　　(1)遍歷所有的等值線(xiàn),，為每一條等值線(xiàn)生成一個(gè)等值線(xiàn)Y桶中的記錄,，并根據(jù)等值線(xiàn)的最小Y坐標(biāo)將該記錄加入到等值線(xiàn)Y桶中。
　　(2)將有效等值線(xiàn)表AIT和有效邊表AET初始化為空,。
　　(3)對(duì)于每一條掃描線(xiàn)i,，它從最小值開(kāi)始，做以下工作,。①檢查等值線(xiàn)Y桶對(duì)于掃描線(xiàn)i是否有新的等值線(xiàn)記錄,，如果有則生成該掃描線(xiàn)對(duì)應(yīng)的邊Y桶，并在有效等值線(xiàn)表AIT中加入該掃描線(xiàn)的桶記錄,。②遍歷AIT中的每一條等值線(xiàn)對(duì)應(yīng)的桶記錄,，檢查該等值線(xiàn)對(duì)應(yīng)的邊Y桶對(duì)于掃描線(xiàn)i是否有新的邊記錄加入，如果有則將新的邊記錄按xmin字段的大小加入到有效邊表AET中,。③利用有效邊表AET和掃描線(xiàn)填充算法填充該掃描線(xiàn),。④遍歷AET，檢查是否有邊記錄的ymax字段等于i,，如果有則刪除該邊記錄,，否則令該邊記錄的xmin=xmin+Δx。⑤遍歷AIT表,，檢查是否有等值線(xiàn)記錄的ymax字段等于i,，如果有則刪除該記錄,。
　　利用上面的算法可以實(shí)現(xiàn)等值線(xiàn)的填充，由于使用了掃描線(xiàn)轉(zhuǎn)換算法,，其算法復(fù)雜度與多邊形填充一致,，因而速度優(yōu)勢(shì)很明顯。圖5和圖6是利用上面算法填充的等值線(xiàn)圖,。其中圖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)一致,，色階正確沒(méi)有出現(xiàn)任何誤填和漏填錯(cuò)誤,。填充結(jié)果與其他填充算法結(jié)果一致。