計(jì)算機(jī)地圖制圖原理與方法基本圖形生成算法PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1計(jì)算機(jī)地圖制圖原理與方法基本圖形生計(jì)算機(jī)地圖制圖原理與方法基本圖形生成算法成算法第1頁(yè)/共34頁(yè)幾何圖形幾何圖形i | Pi 最接近圖形的象素最接近圖形的象素 基本圖形的生成算法任務(wù)之一就是找出所有的基本圖形的生成算法任務(wù)之一就是找出所有的i .l點(diǎn)表示為象素（點(diǎn)表示為象素（Pixel），對(duì)應(yīng)于顯存地址單），對(duì)應(yīng)于顯存地址單元元l讀寫(xiě)某一象素是硬件設(shè)備提供的最基本功能讀寫(xiě)某一象素是硬件設(shè)備提供的最基本功能l一維圖形，由一個(gè)象素寬的直線或曲線表示一維圖形，由一個(gè)象素寬的直線或曲線表示l二維圖形由確定區(qū)域的象素表示二維圖形由確定區(qū)域的象素表示l線圖元的掃描轉(zhuǎn)換是基本圖形生算法的基礎(chǔ)線圖元的

2、掃描轉(zhuǎn)換是基本圖形生算法的基礎(chǔ)；第2頁(yè)/共34頁(yè)(X i+1 ,Yi + k)(X i , Int(Yi +0.5)(X i , Yi)柵格交點(diǎn)表示象素點(diǎn)位置柵格交點(diǎn)表示象素點(diǎn)位置第3頁(yè)/共34頁(yè)第4頁(yè)/共34頁(yè)起點(diǎn)起點(diǎn)終終點(diǎn)點(diǎn)未四舍五入前未四舍五入前最后選定的點(diǎn)最后選定的點(diǎn)1723456089123456780第5頁(yè)/共34頁(yè)缺點(diǎn)：缺點(diǎn)：浮點(diǎn)運(yùn)算、取整浮點(diǎn)運(yùn)算、取整廢時(shí)，且不利于硬件實(shí)現(xiàn)。廢時(shí)，且不利于硬件實(shí)現(xiàn)。問(wèn)題：為什么問(wèn)題：為什么k？，若？，若k，上述算法會(huì)出現(xiàn)什么情況？應(yīng)如何處理？上述算法會(huì)出現(xiàn)什么情況？應(yīng)如何處理？第6頁(yè)/共34頁(yè)假定直線斜率假定直線斜率k在在0 01 1之間，當(dāng)前

3、象素點(diǎn)為之間，當(dāng)前象素點(diǎn)為（xp,yp），則下一個(gè)象素點(diǎn)有，則下一個(gè)象素點(diǎn)有兩種可選擇點(diǎn)兩種可選擇點(diǎn)P1（xp+1,+1,yp）或）或P2 2（xp+1,+1,yp+1+1）。若）。若P1與與P2的中點(diǎn)（的中點(diǎn)（xp+1,+1,yp+0.5+0.5）稱(chēng)為）稱(chēng)為M，Q為理想直線與為理想直線與x= =xp+1+1垂線的交點(diǎn)。當(dāng)垂線的交點(diǎn)。當(dāng)M在在Q的的下方時(shí)，則取下方時(shí)，則取P2應(yīng)為下一個(gè)象素點(diǎn)；當(dāng)應(yīng)為下一個(gè)象素點(diǎn)；當(dāng)M在在Q的上方時(shí)，則取的上方時(shí)，則取P1為下一為下一個(gè)象素點(diǎn)。這就是中點(diǎn)畫(huà)線法的基本原理個(gè)象素點(diǎn)。這就是中點(diǎn)畫(huà)線法的基本原理過(guò)點(diǎn)過(guò)點(diǎn)(x0,y0)、(x1, , y1)的直線段的直線

4、段L的方程式為的方程式為F(x, y)=ax+by+c=0，欲判斷中點(diǎn)，欲判斷中點(diǎn)M在在Q點(diǎn)的點(diǎn)的上方還是下方，只要把上方還是下方，只要把M代入代入F（x，y），），并判斷它的符號(hào)即可。為此，我們構(gòu)造判別并判斷它的符號(hào)即可。為此，我們構(gòu)造判別式式:d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c 當(dāng)當(dāng)d0時(shí)，時(shí)，M在在L(Q點(diǎn)點(diǎn))上方，取上方，取P1為下一為下一個(gè)象素；個(gè)象素； 當(dāng)當(dāng)d=0時(shí)，選時(shí)，選P1或或P2均可，約定取均可，約定取P1為下為下一個(gè)象素；一個(gè)象素；第7頁(yè)/共34頁(yè)若當(dāng)前象素處于若當(dāng)前象素處于d=d=0 0情況，則取正右方象素情況，則取正右

5、方象素P P1 1( (x xp p+1, y+1, yp p),),要判下一個(gè)象要判下一個(gè)象素位置，應(yīng)計(jì)算素位置，應(yīng)計(jì)算 d d1 1= =F F( (x xp p+2, +2, y yp p+0.5)=+0.5)=a a( (x xp p+2)+2)+b b( (y yp p+0.5)=+0.5)=d d+ +a a，增量為，增量為a a。 若若d d00時(shí)，則取右上方象素時(shí)，則取右上方象素P P2 2( (x xp p+1, +1, y yp p+1)+1)。要判斷再下一象素，則要。要判斷再下一象素，則要計(jì)算計(jì)算d d2 2= = F F( (x xp p+2, +2, y yp p+1

6、.5)=+1.5)=a a( (x xp p+2)+2)+b b( (y yp p+1.5)+1.5)+c c= =d d+ +a a+ +b b ，增量為，增量為a ab b。畫(huà)線從畫(huà)線從( (x x0 0, , y y0 0) )開(kāi)始，開(kāi)始，d d的初值的初值 d d0 0= =F F( (x x0 0+1, +1, y y0 0+0.5)=+0.5)=F F( (x x0 0, , y y0 0)+)+a a+0.5+0.5b b，因因 F F( (x x0 0, , y y0 0)=0)=0，所以，所以d d0 0= =a a+0.5+0.5b b。其中，其中，a=ya=y0 0- -

7、y y1 1, , b b= =x x1 1- -x x0 0, , c c= =x x0 0y y1 1- -x x1 1y y0 0。void MidpointLine (int x0void MidpointLine (int x0，int y0int y0，int int x1x1， int y1int y1，int color)int color) int a int a， b b， d1d1， d2d2， d d， x x， y y； a=y0-y1a=y0-y1； b=x1-x0b=x1-x0；d=2d=2* *a+ba+b； d1=2d1=2* *a a；d2=2d2=2* *

8、 (a+b) (a+b)； x=x0 x=x0；y=y0y=y0； while (x=x1)while (x=x1) SetPixel (x SetPixel (x， y y， color);color);if (d0)if (d0) x+ x+；y+y+； d+=d2; d+=d2; elseelse x+ x+； d+=d1;d+=d1; / /* * while while * */ / / /* * midPointLine midPointLine * */ / 第8頁(yè)/共34頁(yè)起點(diǎn)起點(diǎn)終點(diǎn)終點(diǎn)初始值：初始值：a=-4; b=7; d= 2*a+b=-1;d1=2*a=-8; d2=

9、2*(a+b)=61、X0=0, Y0=0, d=-12、X1=1, Y1=1, d=53、X2=2, Y2=1, d=-34、X3=3, Y3=2, d=35、X4=4, Y4=2, d=-56、X5=5, Y5=3, d=17、X6=6, Y6=3, d=-7712345612345678008、X6=7, Y6=4, d=-1第9頁(yè)/共34頁(yè)第10頁(yè)/共34頁(yè)假定直線斜率假定直線斜率,0k1 時(shí)時(shí) d=d-1 ;當(dāng)當(dāng)d=0.5取取 (x+1,y)，否則取，否則取(x+1,y+1)。令。令e=d-0.5, 顯然顯然 e 的初值為的初值為-0.5。這樣可用。這樣可用e的符號(hào)來(lái)進(jìn)行判斷。的符號(hào)

10、來(lái)進(jìn)行判斷。dddd第11頁(yè)/共34頁(yè)程序如下：第12頁(yè)/共34頁(yè)第13頁(yè)/共34頁(yè)從速度考慮，還有那些可以改進(jìn)？第14頁(yè)/共34頁(yè)起點(diǎn)起點(diǎn)終點(diǎn)終點(diǎn)初始值：初始值：dx=7; dy=4; k= 4/7 e=-7/141、X0=0, Y0=0, e=1/142、X1=1, Y1=1, e=-5/143、X2=2, Y2=1, e=3/144、X3=3, Y3=2, e=-3/145、X4=4, Y4=2, e=5/146、X5=5, Y5=3, e=-1/147、X6=6, Y6=3, e=7/14712345612345678008、X6=7, Y6=4, e=1/14討論象素點(diǎn)的選取是否有規(guī)

11、律？有何用第15頁(yè)/共34頁(yè)第16頁(yè)/共34頁(yè)第17頁(yè)/共34頁(yè)第18頁(yè)/共34頁(yè)第19頁(yè)/共34頁(yè)第20頁(yè)/共34頁(yè)第21頁(yè)/共34頁(yè)MP1P2P（Xp ，Yp ）P為當(dāng)前點(diǎn)亮象素，那么，下一個(gè)點(diǎn)亮的為當(dāng)前點(diǎn)亮象素，那么，下一個(gè)點(diǎn)亮的象素可能是象素可能是P1（Xp+1，Yp）或）或P2（Xp +1，Yp +1)。第22頁(yè)/共34頁(yè)第23頁(yè)/共34頁(yè)p+3.第24頁(yè)/共34頁(yè)第25頁(yè)/共34頁(yè)該程序如何改進(jìn)，提高效率？第26頁(yè)/共34頁(yè)第27頁(yè)/共34頁(yè)y j第28頁(yè)/共34頁(yè)在上半部分在上半部分,法向量的法向量的y分量大分量大在下半部分在下半部分,法向量的法向量的x分量大分量大上半部分上半部分下半部分下半部分法向量法向量?jī)煞至肯嗟葍煞至肯嗟萂1M2在當(dāng)前中點(diǎn)處，法向量（在當(dāng)前中點(diǎn)處，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的的y分量比分量比x分分量大量大,即：即： b2 (Xp+1) a2 (Yp-0.5), 而在下一中點(diǎn)，不等式改變方而在下一中點(diǎn)，不等式改變方向，則說(shuō)明橢圓弧從上部分轉(zhuǎn)入下部分向，則說(shuō)明橢圓弧從上部分轉(zhuǎn)入下部分第29頁(yè)/共34頁(yè)第30頁(yè)/共34頁(yè)第31頁(yè)/共34頁(yè)第32頁(yè)/共34頁(yè)程序：程序：void draw_Ellipe_Mid(int a,int b) int x,y; float d1,d2; x = 0;