函數(shù)曲線生成器的設(shè)計(jì)

毛開梅，鄒 星

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

1.3 逆波蘭式的求值

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

圖1 逆波蘭式求值

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

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

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

2.2 曲線初始像素點(diǎn)的確定

二分法確定曲線的初始像素點(diǎn):

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

圖2 二分求解曲線的起始像素點(diǎn)流程圖

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

2.3 曲線初始點(diǎn)的運(yùn)動(dòng)方向確定

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

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

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

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

3 曲線的逐點(diǎn)繪制算法

3.1 一個(gè)通用的像素級(jí)曲線生成算法

二維平面上曲線的一般表達(dá)式為

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

圖4 一個(gè)像素的8個(gè)相鄰像素及對(duì)應(yīng)的移動(dòng)方向

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

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

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

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

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

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

根據(jù)2.1小節(jié)的定義，為實(shí)現(xiàn)平移、縮放和曲線粗細(xì)控制，并解決MFC閃屏問題，引入繪圖區(qū)域、視圖區(qū)域和坐標(biāo)區(qū)域的概念［5］。定義一個(gè)的Bitmap對(duì)象，其尺寸定義為寬高分別為屏幕大小的2倍，使用該Bitmap定義一個(gè)兼容的MemDC對(duì)象，此Bitmap可以看成一張畫布，即繪圖區(qū)域。視圖區(qū)域一定是從繪圖區(qū)域截取的某個(gè)矩形，視圖區(qū)域的大小由程序窗體的大小決定。視圖區(qū)域相對(duì)于繪圖畫布有兩個(gè)像素級(jí)的偏移量 (OffsetX，OffsetY)。坐標(biāo)區(qū)域即繪圖區(qū)域所映射的坐標(biāo)矩形范圍。坐標(biāo)區(qū)域由繪圖區(qū)域的坐標(biāo)偏移量和每像素坐標(biāo)值決定。這里的每像素所占坐標(biāo)值的定義，是支持視圖縮放功能的本質(zhì)原理。每像素所占的坐標(biāo)值越大，坐標(biāo)軸刻度越精確，函數(shù)圖像即顯示某個(gè)細(xì)節(jié)部位，便于觀察某個(gè)小范圍內(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é)對(duì)繪圖區(qū)域和視圖區(qū)域的定義，要實(shí)現(xiàn)函數(shù)圖像的平移操作，即實(shí)現(xiàn)視圖區(qū)域的平移。我們已知，視圖區(qū)域包含在繪圖區(qū)域的矩形中，根據(jù)像素偏移量 (OffsetX，OffsetY)進(jìn)行偏移定位。在窗體需要重繪時(shí)，程序從畫布上復(fù)制視圖區(qū)域所對(duì)應(yīng)的像素?cái)?shù)據(jù)，從內(nèi)存BitMap中快速批量地復(fù)制視圖區(qū)域的數(shù)據(jù)到顯存［6］。為了提高效率，避免阻塞UI線程，如果用戶的操作沒有引起繪圖區(qū)域產(chǎn)生重繪，而只是視圖區(qū)域的重繪，那么函數(shù)曲線的逐點(diǎn)繪制過程就不用進(jìn)行，而只需要更新偏移量 (OffsetX，OffsetY)，然后重新刷新內(nèi)存數(shù)據(jù)到顯存即可，這個(gè)效率是非常高的［7］。

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

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

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

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

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

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

5 運(yùn)行及測(cè)試

測(cè)試用例1:

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

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

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

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

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

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

測(cè)試用例2:

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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

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