【正文】 y。 ， 重復(fù)步驟 3和 4。 e+k， 判斷 e的符號(hào) 。 △ x、 △ y、 e=、 x=x0、 y=y0。 2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 21 改進(jìn) 1：令 e= ????????????????0)(e 0)(e 1111iiiiiyyyxx? e初 =， ? 每走一步有 e=e+k。 ， 重復(fù)步驟 3和 4。 d+k， 判斷 d的符號(hào) 。 △ x、 △ y、 d=0、 x=x0、 y=y0。 否則結(jié)束 。 若 d0， 則 (x,y)更新為 (x+1,y+1)， d更新為 d+2△ x2△ y； 否則 (x,y)更新為 (x+1,y), d更新為 d2△ y。 (x,y)。 2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 17 改進(jìn) ：用 2d△ x代替 d P0(x0,y0)和 P1(x1,y1)。 ， 重復(fù)步驟 3。 △ x、 △ y、 d=、 x=x0、 y=y0； (x,y)。 直線的微分方程： 1)(5 0101 kxxyyxydxdy ???????2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 5 DDA算法原理 ： 2)(5 11yyyxxxiiii????????????ε △xx iyxy ix i +1y i +1ε △y圖5 2 D D A 算法原理ε=1/max(|△ x|,|△ y|) 2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 6 max(|△ x|,|△ y|)=|△ x|， 即 |k|≤1的情況： max(|△ x|,|△ y|)=|△ y|， 此時(shí) |k|≥1： 3)(5 11111kyyxyyyyxxxxxxxiiiiiiii??????????????????????????4)(5 111111????????????????????????iiiiiiiiyyyyyyykxxyxxxx??2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 7 程序 注意 ： round(x)=(int)(x+) 圖5 3 D D A 算法生成直線段(x i ,y i )(x i +1 , r ou n d ( y i +k ))( r ou n d ( x i + 1 / k ) ,y i +1 )2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 8 特點(diǎn) ： ? 增量算法 ? 直觀 、 易實(shí)現(xiàn) ? 不利于用硬件實(shí)現(xiàn) 2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 9 中點(diǎn) Bresenham算法 直線的方程 該直線方程將平面分為三個(gè)區(qū)域： ? 對(duì)于直線上的點(diǎn) ， F(x,y)=0； ? 對(duì)于直線上方的點(diǎn) ， F(x,y)0； ? 對(duì)于直線下方的點(diǎn) ， F(x,y)0。 圖形的掃描轉(zhuǎn)換 ： 在光柵顯示器等數(shù)字設(shè)備上確定一個(gè)最佳逼近于圖形的象素集的過(guò)程 。2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 1 第 5章 基本圖形生成算法 ? 提出問(wèn)題 如何在指定的輸出設(shè)備上根據(jù)坐標(biāo)描述構(gòu)造基本二維幾何圖形 （ 點(diǎn) 、 直線 、 圓 、 橢圓 、 多邊形域 、 字符串及其相關(guān)屬性等 ） 。 2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 2 圖形的生成： 是在指定的輸出設(shè)備上 ， 根據(jù)坐標(biāo)描述構(gòu)造二維幾何圖形 。 圖5 1 用一系列的象素點(diǎn)來(lái)逼近直線2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 3 直線的掃描轉(zhuǎn)換 直線的繪制要求： ? ? ， 即無(wú)定向性和斷裂情況 ? 、 色澤要均勻 ? ? 、 亮度 、 線型等 2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 4 數(shù)值微分法 (DDA法 ) 解決的問(wèn)題 ： 給定直線兩端點(diǎn) P0(x0,y0)和 P1(x1,y1)， 畫出該直線 。 5)(5 , 0),(0101xxyyxykbkxyyxF?????????? 其中2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 10 xyF ( x, y ) 0F ( x, y ) =0F ( x, y ) 0圖5 4 直線將平面分為三個(gè)區(qū)域xyF ( x, y ) 0F ( x, y ) =0F ( x, y ) 02020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 11 基本原理 ： 假定 0≤k≤1， x是最大位移方向 P u (x i + 1 , y i +1)M(x i + 1 , y i + 1 / 2 )P(x i ,y i )P d (x i + 1 , y i )圖5 5 B r e n s e m h a m 算法生成直線的原理Q2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 12 判別式 ： 6)(5 )1(),1(),( bxkyyxFyxFd iiiiMM ?????????則有： ???????)0( )0( 1dydyyP u (x i + 1 , y i +1)M(x i + 1 , y i + 1 / 2 )P(x i ,y i )P d (x i + 1 , y i )圖5 5 B r e n s e m h a m 算法生成直線的原理Q2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 13 d0(x i ,y i )(x i+1 ,y i+ )(x i+2 ,y i+ )誤差項(xiàng)的遞推 d0： kdkbxkybxkyyxFdiiiiii?????????????????1 )1( )2( ),2(2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 14 誤差項(xiàng)的遞推 d≥0： kdkbxkybxkyyxFdiiiiii???????????????? )1( )2( ),2(d =0(x i ,y i )(x i+1 ,y i+ )(x i+2 ,y i+ )2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 15 初始值 d的計(jì)算 kkbkxybxkyyxFd??????????????? )1( ),1(00000002020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 16 0≤k≤1時(shí) Bresenham算法的 算法步驟 為 ： P0(x0,y0)和 P1(x1,y1)。 判斷 d的符號(hào)； 若 d0， 則 (x,y)更新為 (x+1,y+1)， d更新為 d+1k； 否則 (x,y)更新為 (x+1,y)， d更新為 dk。 否則結(jié)束 。 △ x、 △ y、 d=△ x2△ y、 x=x0、 y=y0。 判斷 d的符號(hào) 。 ， 重復(fù)步驟 3。 程序 2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 18 改進(jìn)的 Bresenham算法 假定直線段的 0≤k≤1 基本原理 ： 圖5 8 改進(jìn)的B r en s e m h am 算法繪制直線的原理ddddkkkkk2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 19 ????????????????0 . 5 )(d 0 . 5 )(d 1111iiiiiyyyxx誤差項(xiàng)的計(jì)算 ? d初 =0， ? 每走一步： d=d+k ? 一旦 y方向上走了一步 ， d=d1 2020/10/7 華中理工大學(xué)計(jì)算機(jī)學(xué)院 陸楓 997 20 算法步驟 ： P0(x0,y0)和 P1(