第5章基本图形生成算法 提出问题 如何在指定的输出设备上根据坐标描述构造基 本二维几何图形(点、直线、圆、椭圆、多边 形域、字符串及其相关属性等)。 2021/2/21 华中理工大学计算机学院陆枫 99-7
2021/2/21 华中理工大学计算机学院 陆枫 99-7 1 第5章 基本图形生成算法 • 提出问题 如何在指定的输出设备上根据坐标描述构造基 本二维几何图形（点、直线、圆、椭圆、多边 形域、字符串及其相关属性等）
图形的生成:是在指定的输出设备上,根据坐标描述 构造二维几何图形。 图形的扫描转换:在光栅显示器等数字设备上确定 个最佳逼近于图形的象素集的过程。 图5-1用一系列的象素点来逼近直线 2021/2/21 华中理工大学计算机学院陆枫 2 99-7
2021/2/21 华中理工大学计算机学院 陆枫 99-7 2 图形的生成：是在指定的输出设备上，根据坐标描述 构造二维几何图形。 图形的扫描转换：在光栅显示器等数字设备上确定一 个最佳逼近于图形的象素集的过程。 图5-1 用一系列的象素点来逼近直线
51直线的扫描转换 直线的绘制要求 1.直线要直 2.直线的端点要准确,即无定向性和断裂情况 3直线的亮度、色泽要均匀 4画线的速度要快 5要求直线具有不同的色泽、亮度、线型等 2021/2/21 华中理工大学计算机学院陆枫 3 99-7
2021/2/21 华中理工大学计算机学院 陆枫 99-7 3 5.1 直线的扫描转换 直线的绘制要求： 1.直线要直 2.直线的端点要准确，即无定向性和断裂情况 3.直线的亮度、色泽要均匀 4.画线的速度要快 5.要求直线具有不同的色泽、亮度、线型等
解决的问题 给定直线两端点Pxy)和P1(x1y1),画出该直线。 511数值微分法DDA法) 直线的微分方程: sy- Vivo k dx△xx1=xo 2021/2/21 华中理工大学计算机学院陆枫 4 99-7
2021/2/21 华中理工大学计算机学院 陆枫 99-7 4 5.1.1 数值微分法(DDA法) 解决的问题： 给定直线两端点P0 (x0 ,y0 )和P1 (x1 ,y1 )，画出该直线。 直线的微分方程： (5 -1) 1 0 1 0 k x x y y x y dx dy = − − = =
DDA算法原理: y+1------ e△y yi Xi e △ X Xi+ 图5-2DA算法原理 x.,=x+E·△x V+1=v+E·△y (5-2) e=1max(△x△y) 2021/2/21 华中理工大学计算机学院陆枫 5 99-7
2021/2/21 华中理工大学计算机学院 陆枫 99-7 5 DDA算法原理： (5 - 2) 1 1 y y y x x x i i i i = + = + + + xi ε△x y x yi xi+1 yi+1 ε△y 图5-2 DDA算法原理 ε=1/max(|△x|,|△y|)
max(△x△y)=△x,即k≤1的情况: x1=x1+E·Ax=x1+,·△x=x1±1 1 =y+6y=y+y=y±k max(△x△y)=△y,此时k≥1: x1=x+E.△x=x1+,△x=x k yH=y+EAy=y+,2y=y±1 2021/2/21 华中理工大学计算机学院陆枫 6 99-7
2021/2/21 华中理工大学计算机学院 陆枫 99-7 6 max(|△x|,|△y|)=|△x|，即|k|≤1的情况： max(|△x|,|△y|)=|△y|，此时|k|≥1： (5 - 3) 1 1 1 1 1 y y k x y y y y x x x x x x x i i i i i i i i = = + = + = = + = + + + 1 (5 - 4) 1 1 1 1 1 = = + = + = = + = + + + i i i i i i i i y y y y y y y k x x y x x x x
(round(xi+1/k),Ivi+1 (xi, yi) Kxi+1,lround (yi+h)) 图53DDA算法生成直线段 程序 注意: round(x=(int)(x+0.5) 2021/2/21 华中理工大学计算机学院陆枫 7 99-7
2021/2/21 华中理工大学计算机学院 陆枫 99-7 7 程序 注意： round(x)=(int)(x+0.5) 图5-3 DDA算法生成直线段 (xi,yi) (xi+ 1,round(yi+ k)) (round(xi+1/k),yi+ 1)
特点: 增量算法 直观、易实现 不利于用硬件实现 2021/2/21 华中理工大学计算机学院陆枫 8 99-7
2021/2/21 华中理工大学计算机学院 陆枫 99-7 8 特点： 增量算法 直观、易实现 不利于用硬件实现
51.2中点 Bresenham算法 直线的方程 △ F(x,y)=y-kx-b=0,其中k= yyy △xx 0 该直线方程将平面分为三个区域: 对于直线上的点,F(xy)=0 对于直线上方的点,F(xy)>0; 对于直线下方的点,F(xy)<0 2021/2/21 华中理工大学计算机学院陆枫 9 99-7
2021/2/21 华中理工大学计算机学院 陆枫 99-7 9 5.1.2 中点Bresenham算法 直线的方程 该直线方程将平面分为三个区域： • 对于直线上的点，F(x,y)=0； • 对于直线上方的点，F(x,y)>0； • 对于直线下方的点，F(x,y)<0。 ( , ) 0 , (5 -5) 1 0 1 0 x x y y x y F x y y k x b k − − = = − − = 其中 =
y F(x,y)=0 D F(XN)=0 F(x,y)>0 F(x,y)>0 F(x,y)<0 X F(x,y)<0 图5-4直线将平面分为三个区域 2021/2/21 华中理工大学计算机学院陆枫 10 99-7
2021/2/21 华中理工大学计算机学院 陆枫 99 - 7 10 x y F(x,y)>0 F(x,y)=0 F(x,y)0 F(x,y)=0 F(x,y)<0