第三章 基本图
形生成算法
计算机学院
苏小红
基本图形生成算法
图元扫描转换
? 直线段扫描转换
? 圆弧扫描转换
实区域填充
图形反走样
光栅图形中点的表示
…
(x,y)坐标
地址线性表
1D表示
显示屏幕
2D表示
像素由其左下角坐标表示
光栅图形中点的表示
地址 = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址
x
y
xmaxxmin
ymax
ymin
每行像素点数 行数 行中位置
光栅图形中点的表示
Address(x,y) = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址
= k1 + k2y + x
Address(x± 1,y) = k1 + k2y + (x± 1) = Address(x,y) ± 1
Address(x,y± 1) = k1 + k2(y ± 1) + x = Address(x,y) ± k2
Address(x± 1,y± 1) = k1 + k2(y ± 1) + (x± 1)
= Address(x,y)± k2 ± 1
对像素连续寻址时，如何减少计算量？
增量法的优点？
图形显示的几种方式
图形显示前需要：扫描转换 +裁剪
裁剪 → 扫描转换：最常用，节约计算时间
扫描转换 → 裁剪：算法简单
直线段扫描转换
假设
? 像素间均匀网格, 整型坐标系, 直线段斜率 0<m<1
? 对 m＞ 1,x,y互换
直线段的扫描转换算法
直线的扫描转换
? 确定最佳逼近于该直线的一组象素
? 按扫描线顺序，对这些象素进行写操作
三个常用算法,
1数值微分法（ DDA）
2中点画线法
3Bresenham算法。
数值微分 (DDA)法 (1/5)
已知线段端点,P0(x0,y0),P1(x1,y1)
直线方程
y=kx+b
{(xi,yi)},i=0,….n.
浮点数取整, yi=round(yi)=(int)(yi+0.5)
? 用到浮点数的乘法, 加法和取整运算
数值微分 (DDA)法 (2/5)
增量算法
? yi+1=kxi+1+b=k(xi+1)+b=yi+k
? (xi,yi)→(x i+1,yi+k)
缺点,
? 有浮点数取整运算
? 不利于硬件实现
? 效率低
? 仅适用于 ?k? ≤ 1的情形,x每增加 1,y最多增加 1。 当
?k??1时, 必须把 x,y互换 。
数值微分 (DDA)法 (3/5)
digital differential analyzer
基本思想
? 用数值方法解微分方程
dy/dt = ?x
dy/dt = ?y
xn+1 = xn + ??x
yn+1 = yn + ??y
如何选取 ?？
选取 ?的原则：使 0.5≤|??x|,|??y|≤1
数值微分 (DDA)法 (4/5)
对称的 DDA
? 取 ?=2-n
? 使 2n-1≤max(|?x |,|?y|)≤2n
简单的 DDA
? 取 ?= 1/max(|?x |,|?y|)
? 使 ?|?x |,?|?y|中必有一个是单位步长
? ?x为最大时,??x =1,??x =k
? ?y为最大时,??y =1,??y =1/k
数值微分 (DDA)法 (5/5)
缺点：
? 浮点数运算
? 不易硬件实现
中点画线法（ 1/4）
问题：判断距离理想直线最近的下一个象素点
已知：线段两端点 (x0,y0),(x1,y1)
直线方程,F(x,y)=ax+by+c=0
? a=y0-y1
? b=x1-x0
? c=x0y1-x1y0
? ?
? ?
? ???
?
?
?
?
?
?
点在直线下方
点在直线上方
点在直线上面
0,
0,
0,
yxF
yxF
yxF
P=( x p,y p )
Q
P2
P1
M
如何判断 M点在 Q点上方还是在 Q点下方？
M
P1
P2
P
直线上方点,F(x,y)＞ 0 直线下方点, F(x,y)＜ 0
构造判别式,d=F(M)=F(Xp+1,Yp+0.5)
由 d＞ 0,d＜ 0可判定下一个象素
(Xp+1,Yp+0.5)
中点画线法（ 2/4）
分两种情形考虑再一下个象素的判定,
若 d≥0,中点 M在直线上方, 取正右方象素 P1 (Xp+1,Yp)
? 再下一个象素的判别式为：
d1=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c
= d+a
d的增量为 a
若 d＜ 0,中点 M在直线下方, 取右上方象素 P2 (Xp+1,Yp+1)
? 再下一个象素的判别式为：
d2=F((Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c
=d+a+b
d的增量为 a+b
M
P1
P2
M
P1
P2
d的初始值
? d0=F(X0+1,Y0+0.5)
=F(X0,Y0)+a+0.5
=a+0.5b
? 用 2d代替 d后, d0=2a+b
? d的增量都是整数
优点：
? 只有整数运算, 不含乘除法
? 可用硬件实现
因 (X0,Y0)在直线上，
所以 F(X0,Y0)=0
中点画线法（ 4/4）
Bresenham画线算法（ 1/7）
使用最广泛
与中点画线法的思想类似
由误差项符号决定下一个象素取正右方像素
还是右上方像素
Bresenham画线算法（ 2/7）
基本思想
?比较从理想直线到位于直线上方的像素的距离 d1和相
邻的位于直线下方的像素的距离 d2
?根据距离误差项的符号确定与理想直线最近的象素
}
}
y
y k + 1
y
y k
x k x k + 1
x
P 2
P 1
d 2
d 1
0
Bresenham画线算法（ 3/7）
最大位移方向每次走一步
? k<1时,x为最大位移方向
y方向走步与否
? 取决于误差 e值的大小
误差计算
初值,e0= ?y/ ?x
当 e≥ 0.5时，最接近 P2(xi+1,yi+1)
? y方向走一步
当 e<0.5时，最接近 P1(xi+1,yi)
? y方向不走步
e
P1
P2
P
e’
e
P1
P2
P
e’
Bresenham画线算法（ 4/7）
为方便与 0比较，设 e=e-0.5
e0=?y/ ?x-0.5
当 e≥ 0时，最接近 P2(xi+1,yi+1)
? y方向走一步
当 e<0时，最接近 P1(xi+1,yi)
? y方向不走步
有除法，不宜硬件实现
e
P1
P2
P
e’
e
P1
P2
P
e’
Bresenham画线算法（ 5/7）
设 e=e× 2?x，不影响判断的准确性
e0=2?y - ?x
当 e≥ 0时，最接近 P2(xi+1,yi+1)
? y方向走一步
当 e<0时，最接近 P1(xi+1,yi)
? y方向不走步
e
P1
P2
P
e’
e
P1
P2
P
e’
Bresenham画线算法（ 6/7）
下一步误差的计算
当 e≥ 0时,y方向走一步
?e’=2?y/ ?x - 1 =e + ?y/ ?x - 1
?e’=e + 2?y - 2?x
当 e<0时,y方向不走步
?e’=2?y/ ?x=e + ?y/ ?x
?e’=e + 2?y
e
P1
P2
P
e’
e
P1
P2
P
e’
Bresenham画线算法（ 7/7）
优点
? 整数运算，速度快
? 精度高
? 乘 2运算可用移位实现，适于硬件实现
圆弧的扫描转换
圆的八对称性
? 只考虑第二个八分圆
假设圆心在原点
x2+y2=R2
y
x
(-x,y) (x,y)
(-y,x) (y,x)
(y,-x)(-y,-x)
(-x,-y) (x,-y)
o
R
圆弧的扫描转换
两种直接离散生成方法
? 离散点
开方运算
? 离散角度
三角函数运算
缺点,
? 计算量大
? 所画像素位置间的间距不一致
22 )( xxryy cc ????
?
?
?
???
???
ici
ici
ryy
rxx
?
?
s i n
c os
中点画圆法（ 1/2）
F(X,Y)=X2+Y2-R2=0
中点 M=(Xp+1,Yp-0.5)
当 F(M)＜ 0时, M在圆内, P1距离圆弧近, 取 P1
当 F(M)＞ 0时, M在圆外, P2距离圆弧近, 取 P2
P=( x p,y p )
P1
P2
M
222 )5.0()1(
)5.0,1()(
Ryx
yxFMFd
pp
pp
?????
????
中点画圆法（ 2/2）
若 d<0,取 P2为下一象素，再下一象素的判别式为
若 d>=0,取 P1为下一象素，再下一象素的判别式为
初始象素是（ 0,R），判别式 d的初值为
32)5.0()2()5.0,2(' 222 ??????????? ppppp xdRyxyxFd
5)(2)5.1()2()5.1,2(' 222 ???????????? pppppp yxdRyxyxFd
RRFd ???? 25.1)5.0,1(0
P=( x p,y p ) P1
P2
M
P1(Xp+1,Yp)
P2(Xp+1,Yp-1)使用 e=d-0.25代替 d
e0=1-R
DDA画圆法（ 1/3）
圆的方程,f(x,y)=x2+y2-R2=0
全微分,df(x,y)=2xdx+2ydy=0
微分方程,dy/dx=-x/y
递推方程,
(yn+1-yn)/ (xn+1-xn)=-?xn/ ?yn
xn+1 - xn = ?yn
yn+1 - yn = -?xn
实际画出的曲线
不是圆，而是螺
旋线，为什么？
DDA画圆法（ 2/3）
将递推公式写成矢量形式：
构造一个行列式值为 1的矩阵
对应的圆方程递推关系为
xn+1 = xn + ?yn
yn+1 = -?xn +(1-?2)yn= yn- ?xn+1
]
1
1
][[][ 11
?
??
??? nnnn yxyx
]
1
1
[ 2
??
?
?
?
DDA画圆法（ 3/3）
针对不同象限及顺逆时针画圆，赋给 ?适当
的符号
?不同，圆形状不同,?大近似椭圆
Bresenham画圆算法（ 1/7）
顺时针画第一四分圆，下一步选择哪个点？
基本思想,
? 通过比较像素与圆的距离平方来避免开方运算
下一像素有 3种可能的选择
? mH=|(xi+1)2+yi2-R2|
? mD=|(xi+1)2+(yi-1)2-R2|
? mV=|xi2 +(yi-1)2-R2 |
选择像素的原则
? 使其与实际圆弧的距离平方达到最小
(xi,yi) HPi
①
V D
(xi+1,yi)
(xi,yi-1)
(xi+1,yi-1)
②
③④
⑤
Bresenham画圆算法（ 2/7）
圆弧与点 (xi,yi)附近光栅网格 的相交关系有 5种
右下角像素 D (xi,yi)与实际圆弧的近似程度
? ?i=(xi+1)2+(yi-1)2-R2
? 当 ?i<0时,D在圆内,①②
? 当 ?i>0时,D在圆外,③④
? 当 ?i=0时,D在圆上,⑤ (xi,yi) HPi
①
V D
(xi+1,yi)
(xi,yi-1)
(xi+1,yi-1)
②
③④
⑤
Bresenham画圆算法（ 3/7）
当 ?i<0时,D在圆内,①②
情形①，选 mH, mD 中最小者
d=mH - mD
=|(xi+1)2+yi2-R2| - |(xi+1)2+(yi-1)2-R2|
=(xi+1)2+yi2-R2 + (xi+1)2+(yi-1)2-R2
=2 (?i+yi)-1
? 若 d<0，则选 H
? 若 d>0，则选 D
? 若 d=0，则选 H
情形 ②也
适用
Bresenham画圆算法（ 4/7）
当 ?i>0时,D在圆外,③④
情形③，选 mv, mD 中最小者
d’=mD - mV
=|(xi+1)2+(yi-1)2-R2 | - |xi2+(yi-1)2-R2|
=(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2
=2 (?i-xi)-1
? 若 d’<0，则选 D
? 若 d’>0，则选 V
? 若 d’=0，则选 D
情形 ④也
适用
Bresenham画圆算法（ 5/7）
当 ?i=0时,D在圆上,⑤
按 d判别，有 d>0，应选 D
按 d’判别，有 d’<0，应选 D
Bresenham画圆算法（ 6/7）
当 ?i<0时,
? 若 d≤0，选 H
? 若 d>0，选 D
当 ?i>0时,
? 若 d’ ≤0，选 D
? 若 d’>0，选 V
当 ?i=0时，选 D
Bresenham画圆算法（ 7/7）
判别式的递推关系
当取 H(xi+1,yi)时
? ?i+1=(xi+1+1)2+(yi-1)2-R2= ?i+2(xi+1)+1
当取 V(xi,yi-1)时
? ?i+1=(xi+1)2+(yi-1-1)2-R2= ?i-2(yi-1)+1
当取 D(xi+1,yi-1)时
? ?i+1=(xi+1+1)2+(yi-1-1)2-R2= ?i+2(xi+1)-2(yi-1)+2
多边形逼近法
当圆的正内接多边形边数足够多时, 可以用画该
多边形近似代替画圆
,以直代曲, 的代表方法之一
内接正 n边形顶点为 Pi(xi,yi)
每条边对应的圆心角为 θ, 则有
??
?
??
?
??
?
??
? ??
??
?
??
?
?
?
i
i
i
i
y
x
y
x
??
??
c o ss in
s inc o s
1
1
形生成算法
计算机学院
苏小红
基本图形生成算法
图元扫描转换
? 直线段扫描转换
? 圆弧扫描转换
实区域填充
图形反走样
光栅图形中点的表示
…
(x,y)坐标
地址线性表
1D表示
显示屏幕
2D表示
像素由其左下角坐标表示
光栅图形中点的表示
地址 = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址
x
y
xmaxxmin
ymax
ymin
每行像素点数 行数 行中位置
光栅图形中点的表示
Address(x,y) = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址
= k1 + k2y + x
Address(x± 1,y) = k1 + k2y + (x± 1) = Address(x,y) ± 1
Address(x,y± 1) = k1 + k2(y ± 1) + x = Address(x,y) ± k2
Address(x± 1,y± 1) = k1 + k2(y ± 1) + (x± 1)
= Address(x,y)± k2 ± 1
对像素连续寻址时，如何减少计算量？
增量法的优点？
图形显示的几种方式
图形显示前需要：扫描转换 +裁剪
裁剪 → 扫描转换：最常用，节约计算时间
扫描转换 → 裁剪：算法简单
直线段扫描转换
假设
? 像素间均匀网格, 整型坐标系, 直线段斜率 0<m<1
? 对 m＞ 1,x,y互换
直线段的扫描转换算法
直线的扫描转换
? 确定最佳逼近于该直线的一组象素
? 按扫描线顺序，对这些象素进行写操作
三个常用算法,
1数值微分法（ DDA）
2中点画线法
3Bresenham算法。
数值微分 (DDA)法 (1/5)
已知线段端点,P0(x0,y0),P1(x1,y1)
直线方程
y=kx+b
{(xi,yi)},i=0,….n.
浮点数取整, yi=round(yi)=(int)(yi+0.5)
? 用到浮点数的乘法, 加法和取整运算
数值微分 (DDA)法 (2/5)
增量算法
? yi+1=kxi+1+b=k(xi+1)+b=yi+k
? (xi,yi)→(x i+1,yi+k)
缺点,
? 有浮点数取整运算
? 不利于硬件实现
? 效率低
? 仅适用于 ?k? ≤ 1的情形,x每增加 1,y最多增加 1。 当
?k??1时, 必须把 x,y互换 。
数值微分 (DDA)法 (3/5)
digital differential analyzer
基本思想
? 用数值方法解微分方程
dy/dt = ?x
dy/dt = ?y
xn+1 = xn + ??x
yn+1 = yn + ??y
如何选取 ?？
选取 ?的原则：使 0.5≤|??x|,|??y|≤1
数值微分 (DDA)法 (4/5)
对称的 DDA
? 取 ?=2-n
? 使 2n-1≤max(|?x |,|?y|)≤2n
简单的 DDA
? 取 ?= 1/max(|?x |,|?y|)
? 使 ?|?x |,?|?y|中必有一个是单位步长
? ?x为最大时,??x =1,??x =k
? ?y为最大时,??y =1,??y =1/k
数值微分 (DDA)法 (5/5)
缺点：
? 浮点数运算
? 不易硬件实现
中点画线法（ 1/4）
问题：判断距离理想直线最近的下一个象素点
已知：线段两端点 (x0,y0),(x1,y1)
直线方程,F(x,y)=ax+by+c=0
? a=y0-y1
? b=x1-x0
? c=x0y1-x1y0
? ?
? ?
? ???
?
?
?
?
?
?
点在直线下方
点在直线上方
点在直线上面
0,
0,
0,
yxF
yxF
yxF
P=( x p,y p )
Q
P2
P1
M
如何判断 M点在 Q点上方还是在 Q点下方？
M
P1
P2
P
直线上方点,F(x,y)＞ 0 直线下方点, F(x,y)＜ 0
构造判别式,d=F(M)=F(Xp+1,Yp+0.5)
由 d＞ 0,d＜ 0可判定下一个象素
(Xp+1,Yp+0.5)
中点画线法（ 2/4）
分两种情形考虑再一下个象素的判定,
若 d≥0,中点 M在直线上方, 取正右方象素 P1 (Xp+1,Yp)
? 再下一个象素的判别式为：
d1=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c
= d+a
d的增量为 a
若 d＜ 0,中点 M在直线下方, 取右上方象素 P2 (Xp+1,Yp+1)
? 再下一个象素的判别式为：
d2=F((Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c
=d+a+b
d的增量为 a+b
M
P1
P2
M
P1
P2
d的初始值
? d0=F(X0+1,Y0+0.5)
=F(X0,Y0)+a+0.5
=a+0.5b
? 用 2d代替 d后, d0=2a+b
? d的增量都是整数
优点：
? 只有整数运算, 不含乘除法
? 可用硬件实现
因 (X0,Y0)在直线上，
所以 F(X0,Y0)=0
中点画线法（ 4/4）
Bresenham画线算法（ 1/7）
使用最广泛
与中点画线法的思想类似
由误差项符号决定下一个象素取正右方像素
还是右上方像素
Bresenham画线算法（ 2/7）
基本思想
?比较从理想直线到位于直线上方的像素的距离 d1和相
邻的位于直线下方的像素的距离 d2
?根据距离误差项的符号确定与理想直线最近的象素
}
}
y
y k + 1
y
y k
x k x k + 1
x
P 2
P 1
d 2
d 1
0
Bresenham画线算法（ 3/7）
最大位移方向每次走一步
? k<1时,x为最大位移方向
y方向走步与否
? 取决于误差 e值的大小
误差计算
初值,e0= ?y/ ?x
当 e≥ 0.5时，最接近 P2(xi+1,yi+1)
? y方向走一步
当 e<0.5时，最接近 P1(xi+1,yi)
? y方向不走步
e
P1
P2
P
e’
e
P1
P2
P
e’
Bresenham画线算法（ 4/7）
为方便与 0比较，设 e=e-0.5
e0=?y/ ?x-0.5
当 e≥ 0时，最接近 P2(xi+1,yi+1)
? y方向走一步
当 e<0时，最接近 P1(xi+1,yi)
? y方向不走步
有除法，不宜硬件实现
e
P1
P2
P
e’
e
P1
P2
P
e’
Bresenham画线算法（ 5/7）
设 e=e× 2?x，不影响判断的准确性
e0=2?y - ?x
当 e≥ 0时，最接近 P2(xi+1,yi+1)
? y方向走一步
当 e<0时，最接近 P1(xi+1,yi)
? y方向不走步
e
P1
P2
P
e’
e
P1
P2
P
e’
Bresenham画线算法（ 6/7）
下一步误差的计算
当 e≥ 0时,y方向走一步
?e’=2?y/ ?x - 1 =e + ?y/ ?x - 1
?e’=e + 2?y - 2?x
当 e<0时,y方向不走步
?e’=2?y/ ?x=e + ?y/ ?x
?e’=e + 2?y
e
P1
P2
P
e’
e
P1
P2
P
e’
Bresenham画线算法（ 7/7）
优点
? 整数运算，速度快
? 精度高
? 乘 2运算可用移位实现，适于硬件实现
圆弧的扫描转换
圆的八对称性
? 只考虑第二个八分圆
假设圆心在原点
x2+y2=R2
y
x
(-x,y) (x,y)
(-y,x) (y,x)
(y,-x)(-y,-x)
(-x,-y) (x,-y)
o
R
圆弧的扫描转换
两种直接离散生成方法
? 离散点
开方运算
? 离散角度
三角函数运算
缺点,
? 计算量大
? 所画像素位置间的间距不一致
22 )( xxryy cc ????
?
?
?
???
???
ici
ici
ryy
rxx
?
?
s i n
c os
中点画圆法（ 1/2）
F(X,Y)=X2+Y2-R2=0
中点 M=(Xp+1,Yp-0.5)
当 F(M)＜ 0时, M在圆内, P1距离圆弧近, 取 P1
当 F(M)＞ 0时, M在圆外, P2距离圆弧近, 取 P2
P=( x p,y p )
P1
P2
M
222 )5.0()1(
)5.0,1()(
Ryx
yxFMFd
pp
pp
?????
????
中点画圆法（ 2/2）
若 d<0,取 P2为下一象素，再下一象素的判别式为
若 d>=0,取 P1为下一象素，再下一象素的判别式为
初始象素是（ 0,R），判别式 d的初值为
32)5.0()2()5.0,2(' 222 ??????????? ppppp xdRyxyxFd
5)(2)5.1()2()5.1,2(' 222 ???????????? pppppp yxdRyxyxFd
RRFd ???? 25.1)5.0,1(0
P=( x p,y p ) P1
P2
M
P1(Xp+1,Yp)
P2(Xp+1,Yp-1)使用 e=d-0.25代替 d
e0=1-R
DDA画圆法（ 1/3）
圆的方程,f(x,y)=x2+y2-R2=0
全微分,df(x,y)=2xdx+2ydy=0
微分方程,dy/dx=-x/y
递推方程,
(yn+1-yn)/ (xn+1-xn)=-?xn/ ?yn
xn+1 - xn = ?yn
yn+1 - yn = -?xn
实际画出的曲线
不是圆，而是螺
旋线，为什么？
DDA画圆法（ 2/3）
将递推公式写成矢量形式：
构造一个行列式值为 1的矩阵
对应的圆方程递推关系为
xn+1 = xn + ?yn
yn+1 = -?xn +(1-?2)yn= yn- ?xn+1
]
1
1
][[][ 11
?
??
??? nnnn yxyx
]
1
1
[ 2
??
?
?
?
DDA画圆法（ 3/3）
针对不同象限及顺逆时针画圆，赋给 ?适当
的符号
?不同，圆形状不同,?大近似椭圆
Bresenham画圆算法（ 1/7）
顺时针画第一四分圆，下一步选择哪个点？
基本思想,
? 通过比较像素与圆的距离平方来避免开方运算
下一像素有 3种可能的选择
? mH=|(xi+1)2+yi2-R2|
? mD=|(xi+1)2+(yi-1)2-R2|
? mV=|xi2 +(yi-1)2-R2 |
选择像素的原则
? 使其与实际圆弧的距离平方达到最小
(xi,yi) HPi
①
V D
(xi+1,yi)
(xi,yi-1)
(xi+1,yi-1)
②
③④
⑤
Bresenham画圆算法（ 2/7）
圆弧与点 (xi,yi)附近光栅网格 的相交关系有 5种
右下角像素 D (xi,yi)与实际圆弧的近似程度
? ?i=(xi+1)2+(yi-1)2-R2
? 当 ?i<0时,D在圆内,①②
? 当 ?i>0时,D在圆外,③④
? 当 ?i=0时,D在圆上,⑤ (xi,yi) HPi
①
V D
(xi+1,yi)
(xi,yi-1)
(xi+1,yi-1)
②
③④
⑤
Bresenham画圆算法（ 3/7）
当 ?i<0时,D在圆内,①②
情形①，选 mH, mD 中最小者
d=mH - mD
=|(xi+1)2+yi2-R2| - |(xi+1)2+(yi-1)2-R2|
=(xi+1)2+yi2-R2 + (xi+1)2+(yi-1)2-R2
=2 (?i+yi)-1
? 若 d<0，则选 H
? 若 d>0，则选 D
? 若 d=0，则选 H
情形 ②也
适用
Bresenham画圆算法（ 4/7）
当 ?i>0时,D在圆外,③④
情形③，选 mv, mD 中最小者
d’=mD - mV
=|(xi+1)2+(yi-1)2-R2 | - |xi2+(yi-1)2-R2|
=(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2
=2 (?i-xi)-1
? 若 d’<0，则选 D
? 若 d’>0，则选 V
? 若 d’=0，则选 D
情形 ④也
适用
Bresenham画圆算法（ 5/7）
当 ?i=0时,D在圆上,⑤
按 d判别，有 d>0，应选 D
按 d’判别，有 d’<0，应选 D
Bresenham画圆算法（ 6/7）
当 ?i<0时,
? 若 d≤0，选 H
? 若 d>0，选 D
当 ?i>0时,
? 若 d’ ≤0，选 D
? 若 d’>0，选 V
当 ?i=0时，选 D
Bresenham画圆算法（ 7/7）
判别式的递推关系
当取 H(xi+1,yi)时
? ?i+1=(xi+1+1)2+(yi-1)2-R2= ?i+2(xi+1)+1
当取 V(xi,yi-1)时
? ?i+1=(xi+1)2+(yi-1-1)2-R2= ?i-2(yi-1)+1
当取 D(xi+1,yi-1)时
? ?i+1=(xi+1+1)2+(yi-1-1)2-R2= ?i+2(xi+1)-2(yi-1)+2
多边形逼近法
当圆的正内接多边形边数足够多时, 可以用画该
多边形近似代替画圆
,以直代曲, 的代表方法之一
内接正 n边形顶点为 Pi(xi,yi)
每条边对应的圆心角为 θ, 则有
??
?
??
?
??
?
??
? ??
??
?
??
?
?
?
i
i
i
i
y
x
y
x
??
??
c o ss in
s inc o s
1
1
