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

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

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

　　(2)有效等值線表AIT。該表存儲與當前掃描線相交的所有等值線在等值線Y桶中的記錄指針。
　　(3)邊Y桶。每條等值線都由一系列的邊組成，為了利用相關性，需要建立等值線的邊Y桶，記錄每條邊的基本信息。等值線邊Y桶的長度等于與該等值線相交的掃描線的條數。對于等值線中的每條邊都要產生一個邊記錄，記錄該邊的最大Y坐標ymax，Y值較小端對應的X坐標xmin，當掃描線增大1時X坐標的增量Δx，以及等值線的值value。每一個邊記錄按該邊的最小Y坐標和整條等值線的最小Y坐標的差值存入邊桶中，圖4為邊Y桶數據結構的示意圖。

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