來源：電子技術(shù)應(yīng)用  作者：鄧飛 王美平 周杲

摘要：提出了一種基于掃描線轉(zhuǎn)換的等值線快速填充算法。與現(xiàn)有的逐點掃描法和區(qū)域填充算法相比，該算法既不需要進行逐點插值計算，也不需要追蹤等值區(qū)域，判斷區(qū)域包含關(guān)系，因而填充速度很快，且填充結(jié)果與區(qū)域填充法結(jié)果一致。實踐證明該算法可以在毫秒級完成等值線圖的填充。

關(guān)鍵詞：等值線掃描線填充

等值線圖在地質(zhì)、物探、水文等許多工程領(lǐng)域都有廣泛的應(yīng)用，因此等值線圖的自動生成問題一直是人們研究的熱點。一般等值線圖的生成分為等值線生成和等值線填充兩個部分。目前，等值線的生成方法已經(jīng)很成熟，最常用的是等值線追蹤算法。近年來關(guān)于等值線填充算法的研究也很多，大致可分為掃描填充和區(qū)域填充兩類。其中掃描填充法出現(xiàn)較早，它通過插值計算每個待填充點的顏色值，進行逐點填充。算法簡單、可靠，但是填充速度慢，而且與追蹤法生成的等值線存在一些細微差異，因此目前關(guān)于掃描填充的研究已經(jīng)不多了。區(qū)域填充算法出現(xiàn)較晚，是研究的熱點。算法的基本思想是尋找等值區(qū)域。然后利用圖形庫的多邊形填充函數(shù)進行充填。該算法對于填充大幅等值線圖效果明顯，但是由于需要追蹤等值區(qū)域并且判斷區(qū)域包含關(guān)系．因此算法比較復(fù)雜，而且對于等值線較多的情況，處理速度也較慢。

考慮到前面兩種算法的不足，本文借鑒了圖形學(xué)中關(guān)于多邊形快速填充的經(jīng)典算法——掃描線轉(zhuǎn)換算法，提出了一種利用掃描線填充等值線圖的快速算法。該算法利用掃描線與等值線的拓?fù)潢P(guān)系確定填充顏色，并充分利用掃面線問的相關(guān)性快速填充。無需計算每個填充點的顏色值，也無需尋找等值區(qū)域后再進行多邊形填充，因此速度明顯優(yōu)于前兩類填充算法，而且填充效果與區(qū)域填充算法一致。

1 等值線追蹤算法
等值線追蹤是生成等值線圖的第一步。目前等值線追蹤算法的研究已經(jīng)比較成熟，根據(jù)追蹤的原始數(shù)據(jù)不同，分為規(guī)則矩形網(wǎng)格追蹤和三角網(wǎng)追蹤兩類。其中常用的等值線繪制軟件Surfer就是基于矩形數(shù)據(jù)網(wǎng)格的。當(dāng)然矩形網(wǎng)格不能用于不規(guī)則的圖形．因此后來又出現(xiàn)了基于三角網(wǎng)的等值線追蹤方法。本文主要介紹等值線填充算法，因為填充算法僅需要利用等值線追蹤的結(jié)果，而與具體采用何種追蹤方法無關(guān)，因此這里不過多討論等值線追蹤算法．僅以矩形網(wǎng)格追蹤為例進行簡要說明。

等值線追蹤的第一步是，計算出所有對應(yīng)某一值的等值點在網(wǎng)格邊線上的坐標(biāo)。這對于矩形網(wǎng)格來說比較簡單：先判斷網(wǎng)格邊線上是否存在等值點，如果存在則利用線性插值計算等值點在網(wǎng)格上的坐標(biāo)。得到全部邊線上的等值點后就需要使用一種追蹤策略，將孤立的等值點連接在一起形成等值線。一般先追蹤開曲線，即起止于網(wǎng)格邊界線上的等值線。追蹤開曲線可以順著四個邊界進行，對于某個邊界任意選取一個等值點作為開始點，追蹤下一個等值點，直到追蹤到的下一個等值點也是邊界上的點，就完成了一條等值線的追蹤。

要從一個等值點追蹤到下一個等值點，這通常是利用上一次的追蹤方向來確定的。對于矩形網(wǎng)格來說追蹤方向有4種，即向下、向左、向上和向右。如果上一次等值點所在網(wǎng)格的列比本次等值點所在列小1，則追蹤方向向右。對于每一種追蹤方向可能出現(xiàn)的情況有兩種。這里以向右追蹤為例進行說明，其余方向可以類推。向右追蹤時，如果網(wǎng)格其他三個邊上僅有一邊存在等值點．則選擇它作為下一個點；如果其他三邊均存在等值點則從相鄰的上、下邊中選取，計算上一個等值點到上、下邊中待選等值點的距離，取距離小的作為下一個等值點。利用上面的追蹤方法追蹤等值線一般都符合實際情況，并且不會出現(xiàn)交叉現(xiàn)象。

當(dāng)追蹤出一個等值點后需要將它刪除，這樣追蹤完一條等值線后就不會重復(fù)追蹤該等值線上的點了。當(dāng)某一邊界已沒有等值點可以追蹤后，就完成了該邊界的開曲線追蹤，對于矩形網(wǎng)格需要在四個邊界上都進行開曲線追蹤。開曲線追蹤完畢后，可能還存在一些等值點，它們將構(gòu)成封閉的閉曲線，可以任取一點進行追蹤，直至回到該點則完成追蹤。如果所有等值點都被追蹤過了。則關(guān)于該等值的等值線就全部追蹤完畢了。圖1是使用網(wǎng)格法追蹤生成的等值線圖。后面的填充算法將對它進行快速填充。

利用追蹤算法得到的等值線，在網(wǎng)格比較稀疏的情況下顯得不夠平滑，往往還需要采用一種擬合方法對等值線進行圓滑。一般可以使用三次參數(shù)樣條曲線或三次B樣條曲線來擬合加密曲線，達到圓滑的效果。不過為了保證曲線通過原有等值點，使用這兩種擬合方式時都需要求解線性方程組，速度比較慢，但是圓滑效果很好．因為能夠保證二階連續(xù)。如果需要提高速度則可以采用HB曲線。該方法不需要求解方程，可以保證一階連續(xù)，對于大多數(shù)情況都可以取得滿意的效果，圖1中的等值線就使用了該方法進行圓滑。

來源：電子技術(shù)應(yīng)用  作者：鄧飛 王美平 周杲

摘要：提出了一種基于掃描線轉(zhuǎn)換的等值線快速填充算法。與現(xiàn)有的逐點掃描法和區(qū)域填充算法相比，該算法既不需要進行逐點插值計算，也不需要追蹤等值區(qū)域，判斷區(qū)域包含關(guān)系，因而填充速度很快，且填充結(jié)果與區(qū)域填充法結(jié)果一致。實踐證明該算法可以在毫秒級完成等值線圖的填充。

關(guān)鍵詞：等值線掃描線填充

等值線圖在地質(zhì)、物探、水文等許多工程領(lǐng)域都有廣泛的應(yīng)用，因此等值線圖的自動生成問題一直是人們研究的熱點。一般等值線圖的生成分為等值線生成和等值線填充兩個部分。目前，等值線的生成方法已經(jīng)很成熟，最常用的是等值線追蹤算法。近年來關(guān)于等值線填充算法的研究也很多，大致可分為掃描填充和區(qū)域填充兩類。其中掃描填充法出現(xiàn)較早，它通過插值計算每個待填充點的顏色值，進行逐點填充。算法簡單、可靠，但是填充速度慢，而且與追蹤法生成的等值線存在一些細微差異，因此目前關(guān)于掃描填充的研究已經(jīng)不多了。區(qū)域填充算法出現(xiàn)較晚，是研究的熱點。算法的基本思想是尋找等值區(qū)域。然后利用圖形庫的多邊形填充函數(shù)進行充填。該算法對于填充大幅等值線圖效果明顯，但是由于需要追蹤等值區(qū)域并且判斷區(qū)域包含關(guān)系．因此算法比較復(fù)雜，而且對于等值線較多的情況，處理速度也較慢。

考慮到前面兩種算法的不足，本文借鑒了圖形學(xué)中關(guān)于多邊形快速填充的經(jīng)典算法——掃描線轉(zhuǎn)換算法，提出了一種利用掃描線填充等值線圖的快速算法。該算法利用掃描線與等值線的拓?fù)潢P(guān)系確定填充顏色，并充分利用掃面線問的相關(guān)性快速填充。無需計算每個填充點的顏色值，也無需尋找等值區(qū)域后再進行多邊形填充，因此速度明顯優(yōu)于前兩類填充算法，而且填充效果與區(qū)域填充算法一致。

1 等值線追蹤算法
等值線追蹤是生成等值線圖的第一步。目前等值線追蹤算法的研究已經(jīng)比較成熟，根據(jù)追蹤的原始數(shù)據(jù)不同，分為規(guī)則矩形網(wǎng)格追蹤和三角網(wǎng)追蹤兩類。其中常用的等值線繪制軟件Surfer就是基于矩形數(shù)據(jù)網(wǎng)格的。當(dāng)然矩形網(wǎng)格不能用于不規(guī)則的圖形．因此后來又出現(xiàn)了基于三角網(wǎng)的等值線追蹤方法。本文主要介紹等值線填充算法，因為填充算法僅需要利用等值線追蹤的結(jié)果，而與具體采用何種追蹤方法無關(guān)，因此這里不過多討論等值線追蹤算法．僅以矩形網(wǎng)格追蹤為例進行簡要說明。

等值線追蹤的第一步是，計算出所有對應(yīng)某一值的等值點在網(wǎng)格邊線上的坐標(biāo)。這對于矩形網(wǎng)格來說比較簡單：先判斷網(wǎng)格邊線上是否存在等值點，如果存在則利用線性插值計算等值點在網(wǎng)格上的坐標(biāo)。得到全部邊線上的等值點后就需要使用一種追蹤策略，將孤立的等值點連接在一起形成等值線。一般先追蹤開曲線，即起止于網(wǎng)格邊界線上的等值線。追蹤開曲線可以順著四個邊界進行，對于某個邊界任意選取一個等值點作為開始點，追蹤下一個等值點，直到追蹤到的下一個等值點也是邊界上的點，就完成了一條等值線的追蹤。

要從一個等值點追蹤到下一個等值點，這通常是利用上一次的追蹤方向來確定的。對于矩形網(wǎng)格來說追蹤方向有4種，即向下、向左、向上和向右。如果上一次等值點所在網(wǎng)格的列比本次等值點所在列小1，則追蹤方向向右。對于每一種追蹤方向可能出現(xiàn)的情況有兩種。這里以向右追蹤為例進行說明，其余方向可以類推。向右追蹤時，如果網(wǎng)格其他三個邊上僅有一邊存在等值點．則選擇它作為下一個點；如果其他三邊均存在等值點則從相鄰的上、下邊中選取，計算上一個等值點到上、下邊中待選等值點的距離，取距離小的作為下一個等值點。利用上面的追蹤方法追蹤等值線一般都符合實際情況，并且不會出現(xiàn)交叉現(xiàn)象。

當(dāng)追蹤出一個等值點后需要將它刪除，這樣追蹤完一條等值線后就不會重復(fù)追蹤該等值線上的點了。當(dāng)某一邊界已沒有等值點可以追蹤后，就完成了該邊界的開曲線追蹤，對于矩形網(wǎng)格需要在四個邊界上都進行開曲線追蹤。開曲線追蹤完畢后，可能還存在一些等值點，它們將構(gòu)成封閉的閉曲線，可以任取一點進行追蹤，直至回到該點則完成追蹤。如果所有等值點都被追蹤過了。則關(guān)于該等值的等值線就全部追蹤完畢了。圖1是使用網(wǎng)格法追蹤生成的等值線圖。后面的填充算法將對它進行快速填充。

利用追蹤算法得到的等值線，在網(wǎng)格比較稀疏的情況下顯得不夠平滑，往往還需要采用一種擬合方法對等值線進行圓滑。一般可以使用三次參數(shù)樣條曲線或三次B樣條曲線來擬合加密曲線，達到圓滑的效果。不過為了保證曲線通過原有等值點，使用這兩種擬合方式時都需要求解線性方程組，速度比較慢，但是圓滑效果很好．因為能夠保證二階連續(xù)。如果需要提高速度則可以采用HB曲線。該方法不需要求解方程，可以保證一階連續(xù)，對于大多數(shù)情況都可以取得滿意的效果，圖1中的等值線就使用了該方法進行圓滑。