毛開梅，鄒 星

(西安鐵路職業(yè)技術(shù)學(xué)院電子信息學(xué)院，西安 710014)

0 引言

隨著圖形技術(shù)的日益廣泛應(yīng)用，計算機繪圖方法的研究也就顯得愈來愈重要。目前已提出通用的像素級曲線生成算法。其中較為卓著的有我國劉勇奎教授提出的“曲線的逐點生成算法”［1］，它只用整數(shù)運算，可以繪制多種曲線，包括Bezier曲線、B樣條曲線、多項式函數(shù)曲線等［2-3］。該算法本身能自動調(diào)整前進的方向，因此無論曲線的走向如何變化，該算法都能隨著曲線走向的變化而調(diào)整自己，使其總能與曲線的走向保持一致。該課題的目的就是為了研究通用函數(shù)曲線的繪制算法，實現(xiàn)函數(shù)曲線繪制的軟件。本課題依據(jù)現(xiàn)有的曲線逐點繪制算法，并結(jié)合開發(fā)語言的特性，實現(xiàn)像素級的函數(shù)曲線生成器，并使用圖像緩沖技術(shù)，解決可能遇到的閃屏等問題。本課題實現(xiàn)函數(shù)曲線生成器將解決多項式函數(shù)、常用數(shù)學(xué)函數(shù)等的繪制問題，并允許函數(shù)相互嵌套組合，用戶自由輸入表達式，即可得到函數(shù)圖像。本課題所實現(xiàn)的軟件能夠智能地判斷所輸入的方程式的正確性，如果出現(xiàn)錯誤，可以指示出錯誤位置。軟件不限制顯示區(qū)域，并可以同時顯示多個函數(shù)圖像，用顏色區(qū)分。軟件同時可以對可視區(qū)域進行坐標(biāo)的縮放操作，可以觀察函數(shù)在某個微小區(qū)域內(nèi)的曲線變化。這對數(shù)學(xué)教學(xué)、研究等用途的函數(shù)模型參考具有重要的意義。

1 函數(shù)方程式的解析求值

1.1 方程式的節(jié)點解析

本課題研究的函數(shù)表達式默認(rèn)以y=f(x)的形式輸入。用戶需要輸入的部分為f(x)，程序?qū)⒆詣犹砑訛閒(x)－y=0的形式，即最終解析形式仍為f(x，y)=0。課題的方程式解析器，期望輸入方程式的字符串和變量參考表，輸出解析結(jié)果對象。解析結(jié)果將包含解析正確與否的信息，若正確，結(jié)果對象中將包含分解后的節(jié)點對象列表;若失敗，結(jié)果對象中也應(yīng)包含錯誤原因和錯誤位置。

1.2 節(jié)點列表的逆波蘭處理

通過上文的處理，輸入的表達式已分解成由節(jié)點組成的列表，并且，除了括號的匹配問題之外，節(jié)點列表的順序是合法的中序表達式順序。要使表達式可以方便求值，需要將節(jié)點順序轉(zhuǎn)化為逆波蘭式。將一個普通的中序表達式轉(zhuǎn)換為逆波蘭表達式的一般算法是:

首先需要分配1個棧，作為臨時存儲運算符的棧S1(含一個結(jié)束符節(jié)點)，一個隊列，作為輸入逆波蘭式的列表S2(空隊列)，S1?？上确湃雰?yōu)先級最低的運算符‘#’號節(jié)點，注意，中綴式應(yīng)以此最低優(yōu)先級的節(jié)點結(jié)束，這里擴展出‘#’號操作符節(jié)點作為終結(jié)符節(jié)點。為了與S1棧中的終結(jié)節(jié)點呼應(yīng)，需要在中綴式最后加入終結(jié)符，以便算法可以正確結(jié)束［4］。從中綴式的左端開始取出節(jié)點，逐序進行如下步驟:

1)若取出的節(jié)點是值型節(jié)點，則將該節(jié)點直接送入S2棧;

2)若取出的節(jié)點是非值型節(jié)點，則將該節(jié)點與S1棧棧頂元素比較，如果該節(jié)點優(yōu)先級大于S1棧棧頂節(jié)點的優(yōu)先級，則將該運算符進S1棧，否則，將S1棧的棧頂節(jié)點彈出，送入S2隊列中，直至S1棧棧頂節(jié)點低于 (不包括等于)該節(jié)點優(yōu)先級，則將該節(jié)點送入S1棧;

3)若取出的非值型節(jié)點是右括號或終結(jié)符節(jié)點，則將S1棧棧頂彈出，該節(jié)點不進入S2隊列中，直接銷毀;

4)重復(fù)上面的1～3步，直至處理完所有的中綴式節(jié)點列表。

完成以上步驟，隊列S2便為逆波蘭式輸出結(jié)果。

1.3 逆波蘭式的求值

上文可以得到正確的逆波蘭式順序的節(jié)點列表，而得到逆波蘭式的目的便是求值。如圖1所示。

圖1 逆波蘭式求值

2 繪圖區(qū)域內(nèi)曲線初始值的確定

2.1 繪圖區(qū)域、視圖區(qū)域和坐標(biāo)區(qū)域模型

在研究曲線繪制前，首先應(yīng)明確程序繪圖區(qū)域、視圖區(qū)域和坐標(biāo)區(qū)域的概念模型。為實現(xiàn)平移、縮放和曲線粗細控制，并解決MFC閃屏問題，引入繪圖區(qū)域的概念。定義一個的Bit Map對象，其尺寸定義為寬高分別為屏幕大小的2倍，使用該Bit Map定義一個兼容的Mem DC對象，此Bit Map可以看成一張畫布，即繪圖區(qū)域，其生成的兼容的Mem DC對象即為畫布的DC對象，它控制著畫布的繪制和顯示。函數(shù)圖像都將繪制在此畫布上。因此畫布需要定義左上角的坐標(biāo)偏移量和每像素所占的坐標(biāo)值。將畫布放大到像素級，想象成稀疏的網(wǎng)格，以網(wǎng)格的左上角的點代表該像素，則根據(jù)左上角像素的坐標(biāo)偏移量和每像素坐標(biāo)值，可以計算出畫布上任意一點所處的坐標(biāo)值。同樣的，已知某個坐標(biāo)值，需要定位到畫布上的某個像素點，那么，可以做如下假定:若該坐標(biāo)值的點落在某網(wǎng)格內(nèi)，則認(rèn)為其對應(yīng)的像素點即為該網(wǎng)格所對應(yīng)的像素點。這樣假設(shè)的誤差在半個像素范圍內(nèi)，因此假設(shè)可以接受。

2.2 曲線初始像素點的確定

二分法確定曲線的初始像素點:

可以將繪制區(qū)域內(nèi)曲線初始化像素點轉(zhuǎn)化為，確定像素點的x值后，尋找距離曲線最近的像素點，即確定像素點的y值。圖2展示了使用二分法尋找距離曲線最近像素點的算法過程。

圖2 二分求解曲線的起始像素點流程圖

如圖2的流程。Get Point On Curve函數(shù)接受3個參數(shù)，第一個參數(shù)為當(dāng)前像素列的x值，第二個參數(shù)為求得的像素點的point對象，第3個參數(shù)為畫布的矩形對象。初始時，top、bottom分別為畫布的頂端和底部，即指示出該列像素的頂部和底部兩個像素。將這兩個像素所對應(yīng)的坐標(biāo)值(x，y)帶入函數(shù)方程式f(x，y)，得到兩個值。

2.3 曲線初始點的運動方向確定

要確定曲線的運動方向，即需要計算曲線在該點處的導(dǎo)數(shù)值。根據(jù)導(dǎo)數(shù)值就可以判斷出曲線在該點處的走向。導(dǎo)數(shù)的定義如下:

式 (1)中的dx期望取得足夠小，而實際dx的值取繪圖區(qū)域的每像素所占坐標(biāo)值的0.5倍，產(chǎn)生的誤差就可以在可接受的范圍內(nèi)。

根據(jù)這個導(dǎo)數(shù)值，可以確定曲線的走向。以該點位中心，劃分出8個方向，這8個方向分別記為m1至m8，則導(dǎo)數(shù)值和方向區(qū)間的對應(yīng)關(guān)系如圖3。

圖3 曲線導(dǎo)數(shù)值和方向向量

3 曲線的逐點繪制算法

3.1 一個通用的像素級曲線生成算法

二維平面上曲線的一般表達式為

根據(jù)曲線的正負性質(zhì)提出的算法如下:一個像素級繪制算法就是要逐點地選擇距離實際曲線最近的那些象素點。設(shè)當(dāng)前點的坐標(biāo)為(x，y)，則下一步就要從其相鄰象素點中選擇一個距離實際曲線最近的象素。8個前進方向依次設(shè)為m1至m8，如圖4所示。為實現(xiàn)曲線繪制，在算法中，根據(jù)曲線的不同走向被分為8個部分，并進行了處理。例如，根據(jù)曲線趨勢，假如某一小段曲線的切線方向在m1和m2之間，即大于0°而小于45°，則由算法的P1部分進行繪制。假如這小段曲線的切線方向在m2和m3之間，則由P2部分進行繪制，以此類推，如圖4所示。

圖4 一個像素的8個相鄰像素及對應(yīng)的移動方向

下面以第一部分P1為例討論算法的實現(xiàn)。首先判斷象素(x，y+1)和(x+1，y+1)中距離曲線較近的像素，即將(x，y+1)和(x+1，y+1)分別代入式 (2)，比較兩者絕對值的大小。如果|f(x，y+1)|的絕對值較小，則說明(x，y+1)點距離曲線較近，該點就成為下一步的當(dāng)前點，否則下一步就前進到(x+1，y+1)點。

如果當(dāng)曲線的走向發(fā)生變化時，如何判斷，以便轉(zhuǎn)到算法中相應(yīng)的部分。這是該算法的一個關(guān)鍵技術(shù)，即算法的自動方向調(diào)整。具體方法如下:

當(dāng)f(x，y+1)和f(x+1，y+1)皆為正或皆為負，則說明(x+1，y+1)和(x，y+1)兩點在曲線的同一側(cè)。這時曲線的走向已脫離R1方向的范圍，曲線的走向最大可能為R2或者R8。通過判斷f(x，y+1)和f(x+1，y+1)之間的絕對值大小可以確定是R2還是R8。若后者小于前者，則是R2，否則是R8。如果曲線的走向既不在R2方向域內(nèi)，也不在R8方向域內(nèi)，那么在轉(zhuǎn)到算法的P2或P8部分后仍可以繼續(xù)判斷曲線的走向 (見下面的算法，其中首先要判斷的是曲線走向是否屬于其它方向，以便轉(zhuǎn)到算法的相應(yīng)部分)，否則，算法是不前進的。因此，它可以生成任何彎曲度的曲線，包括在某些點處具有很大轉(zhuǎn)向的曲線。

3.2 繪圖區(qū)域內(nèi)的函數(shù)繪制

根據(jù)上節(jié)的算法，可以從已知點，逐點繪制出函數(shù)曲線。該算法的迭代出口是處理點不在繪圖區(qū)域內(nèi)。然而，考慮到繪圖區(qū)域的特殊性，算法退出后，繪圖區(qū)域的右邊可能仍有函數(shù)圖像。根據(jù)1.2節(jié)所指示，算法退出后，將繼續(xù)進入下一個初始值尋找的迭代過程，直到橫坐標(biāo)超出繪圖區(qū)域。這樣就保證了繪圖區(qū)域圖像的完全覆蓋。

4 函數(shù)圖像的平移和縮放

根據(jù)2.1小節(jié)的定義，為實現(xiàn)平移、縮放和曲線粗細控制，并解決MFC閃屏問題，引入繪圖區(qū)域、視圖區(qū)域和坐標(biāo)區(qū)域的概念［5］。定義一個的Bitmap對象，其尺寸定義為寬高分別為屏幕大小的2倍，使用該Bitmap定義一個兼容的MemDC對象，此Bitmap可以看成一張畫布，即繪圖區(qū)域。視圖區(qū)域一定是從繪圖區(qū)域截取的某個矩形，視圖區(qū)域的大小由程序窗體的大小決定。視圖區(qū)域相對于繪圖畫布有兩個像素級的偏移量 (OffsetX，OffsetY)。坐標(biāo)區(qū)域即繪圖區(qū)域所映射的坐標(biāo)矩形范圍。坐標(biāo)區(qū)域由繪圖區(qū)域的坐標(biāo)偏移量和每像素坐標(biāo)值決定。這里的每像素所占坐標(biāo)值的定義，是支持視圖縮放功能的本質(zhì)原理。每像素所占的坐標(biāo)值越大，坐標(biāo)軸刻度越精確，函數(shù)圖像即顯示某個細節(jié)部位，便于觀察某個小范圍內(nèi)函數(shù)圖像的變化過程。每像素所占的坐標(biāo)值越小，繪圖區(qū)域所代表的坐標(biāo)區(qū)域就越大，函數(shù)圖像即顯示在更宏觀的視圖狀態(tài)下的情形。

區(qū)域模型如圖5所示。

圖5 視圖區(qū)域、繪圖區(qū)域、坐標(biāo)區(qū)域模型

4.1 函數(shù)圖像的平移操作

根據(jù)3.1小節(jié)對繪圖區(qū)域和視圖區(qū)域的定義，要實現(xiàn)函數(shù)圖像的平移操作，即實現(xiàn)視圖區(qū)域的平移。我們已知，視圖區(qū)域包含在繪圖區(qū)域的矩形中，根據(jù)像素偏移量 (OffsetX，OffsetY)進行偏移定位。在窗體需要重繪時，程序從畫布上復(fù)制視圖區(qū)域所對應(yīng)的像素數(shù)據(jù)，從內(nèi)存BitMap中快速批量地復(fù)制視圖區(qū)域的數(shù)據(jù)到顯存［6］。為了提高效率，避免阻塞UI線程，如果用戶的操作沒有引起繪圖區(qū)域產(chǎn)生重繪，而只是視圖區(qū)域的重繪，那么函數(shù)曲線的逐點繪制過程就不用進行，而只需要更新偏移量 (OffsetX，OffsetY)，然后重新刷新內(nèi)存數(shù)據(jù)到顯存即可，這個效率是非常高的［7］。

平移操作在用戶對視圖區(qū)域按下左鍵開始，彈起左鍵結(jié)束。當(dāng)按下左鍵時，在消息映射的處理函數(shù)中，首先記錄下拖拽起始點，并置拖拽標(biāo)識量為真，設(shè)置捕獲鼠標(biāo)事件，讓鼠標(biāo)離開窗口后程序依然可以捕獲消息［8］。

在鼠標(biāo)移動的消息處理函數(shù)中，判斷如果目前正處于拖拽狀態(tài)，則獲得當(dāng)前鼠標(biāo)位置，計算出鼠標(biāo)偏移量，將這個偏移量累加到視圖區(qū)域相對繪圖區(qū)域的偏移量上，然后觸發(fā)視圖區(qū)域重繪，并更新拖拽起始點。

在鼠標(biāo)彈起時，釋放捕獲動作，并設(shè)置拖拽標(biāo)識量為非真。再次觸發(fā)鼠標(biāo)移動事件時，則只更新狀態(tài)欄而不移動視圖區(qū)域中的函數(shù)圖像。這樣，給用戶的感覺是，函數(shù)圖像隨著鼠標(biāo)的拖拽而移動。

在更新視圖區(qū)域的偏移量時，應(yīng)注意，避免讓視圖區(qū)域超出繪圖區(qū)域。如果視圖區(qū)域因偏移，到達繪圖區(qū)域的邊緣，則說明繪圖區(qū)域需要進行重繪。該重繪動作需要使得視圖區(qū)域偏移回到中心，這需要重新計算繪圖區(qū)域的左上角坐標(biāo)偏移量，使得視圖區(qū)域的坐標(biāo)不發(fā)生變化，即繪圖區(qū)域的函數(shù)圖像不發(fā)生位移。

4.2 函數(shù)圖像的縮放操作

函數(shù)圖像的縮放操作與平移類似。其不同點在于，縮放操作必然會觸發(fā)繪圖區(qū)域的重繪，因為縮放操作需要更新繪圖區(qū)域的畫布的每像素所占坐標(biāo)值大?。?10］。在縮放前后，需要保證視圖區(qū)域的中心點的坐標(biāo)值不變，這樣產(chǎn)生的縮放動作才符合邏輯。這就需要在縮放前記錄下視圖區(qū)域中心的坐標(biāo)值，在改變每像素所占坐標(biāo)值大小后，將視圖區(qū)域平移到繪圖區(qū)域中心，同時根據(jù)當(dāng)前視圖區(qū)域的偏移，改變繪圖區(qū)域的左上角坐標(biāo)偏移，使得視圖區(qū)域中心坐標(biāo)值不變。這樣，在縮放前后，視圖區(qū)域總是以中心點在進行放大或縮小操作。

5 運行及測試

測試用例1:

用例名稱:不連續(xù)函數(shù)曲線繪制測試。

測試用例輸入和預(yù)期結(jié)果如表1。

測試結(jié)論及說明:

程序能夠正確處理非連續(xù)函數(shù)的繪制，包括對極限的處理和不存在導(dǎo)數(shù)值的點的處理。

表1 測試用例1輸入預(yù)期表

圖6 非連續(xù)函數(shù)繪制圖

測試用例2:

用例名稱:三角函數(shù)周期極限測試。

測試用例輸入和預(yù)期結(jié)果如表2。

預(yù)期結(jié)果:呈現(xiàn)有規(guī)則的正弦線而不出現(xiàn)紊亂。

測試結(jié)果如圖2～9。

測試結(jié)論及說明:

在能夠接受的精度范圍內(nèi)，程序正確地繪制出了函數(shù)曲線，當(dāng)精度要求更高時，程序繪制出現(xiàn)交疊。當(dāng)出現(xiàn)精度不夠，令圖像產(chǎn)生紊亂時，可以通過放大坐標(biāo)精度，產(chǎn)生更精確的圖像

表2 測試用例2輸入預(yù)期表

圖7 y=2sin(10x)測試截圖

圖8 y=2sin(20x)測試截圖

圖9 放大10倍坐標(biāo)后的y=2sin(40x)測試截圖

6 結(jié)論

本課題所研究的函數(shù)曲線繪圖算法，實現(xiàn)了任意形如y=f(x)的函數(shù)曲線的繪制，支持常用數(shù)學(xué)三角函數(shù)、多項式、指數(shù)對數(shù)函數(shù)及其相互的嵌套，并能夠一次顯示多條函數(shù)曲線。本課題所實現(xiàn)的軟件具有可操作性和實用性，完成了課題任務(wù)的基本要求。

課題未來可繼續(xù)深入研究的方向有，對任意參數(shù)曲線的繪制、極坐標(biāo)下的任意方程曲線繪制、隱函數(shù)的求解和曲線繪制等。這些有待研究的問題，極富挑戰(zhàn)性，具有很深刻的研究意義。