3-中点画线算法

1中点法绘制直线段内容大纲1中点法的基本思想2中点法的基本判别式3中点法的递推公式4任意方向直线段的中点法5直线段的线宽处理

1中点法的基本思想假定直线段在第1像限方向，斜率在0～1之间MPP2P1Q1Q2直线方程：F(x,y)=y-kx-b=0中点判别式：d=F(xM,yM)=(y+0.5)-k(x+1)-b根据中点与直线的关系判断下一个像素：若

d<

0，M在直线之下,取P2

d>=0，M在直线之上，取P1

MP(x,y)P2P1Q1Q2设P为当前离直线最接近的像素2中点法的基本判别式MP2P1PM1M2（xi,yi)di+1

=F(xM1,yM1)=(yi+0.5)-k(xi+2)-b=di=

F(xM,yM)<0di+1=F(xM2,yM2)

=(yi+1.5)-k(xi+2)-bF(xM,yM)=(yi+0.5)-k(xi+1)-bdi=

F(xM,yM)>=0di=取P1di–

k

取P2

=di+1-

k3中点法的递推公式xi+1=xi+1，yi+1=yixi+1=xi+1，yi+1=yi+1MP2P1P（xs,ys)d0=(ys+0.5)-k(xs+1)-b=ys-k·xs-b+0.5-k=0.5-kx0=xs,y0=ys,d0=0.5-kxi+1=xi+1，di>=0,yi+1=yi,

di+1=di-kdi<0,yi+1=yi+1,

di+1=di-k+1di=F(xM,yM)>0di+1=di–

kdi=F(xM,yM)<0di+1=di+1-

k3中点法的递推公式消除小数运算

x=xe-xs,

y=ye-ys,k=

y/

xD0d0=0.5-

y/

x2

xd0=

x-2

yD0=

x-2

y3中点法的递推公式x0=xs,y0=ys,d0=0.5-kxi+1=xi+1di>=0,yi+1=yi,

di+1=di-kdi<0,yi+1=yi+1,

di+1=di-k+18用Di=2

xdi代替didi>=0,di+1=di-

y/

x2

xdi>=0Di>=0,Di+1=Di-2

y3中点法的递推公式x0=xs,y0=ys,

x=xe-xs,

y=ye-ysD0=

x-2

yxi+1=xi+1di>=0,yi+1=yi,

di+1=di-kdi<0,yi+1=yi+1,

di+1=di-k+1消除小数运算2

xdi+1=2

xdi-2

y9用Di=2

xdi代替didi<0,di+1=di-

y/

x+12

xdi<0Di<0,Di+1=Di-2

y+2

x3中点法的递推公式x0=xs,y0=ys,

x=xe-xs,

y=ye-ysD0=

x-2

yxi+1=xi+1Di>=0,Di+1=Di-2

ydi<0,yi+1=yi+1,

di+1=di-k+1消除小数运算2

xdi+1=2

xdi-2

y+2

x

仅包含整数运算的直线斜率在0～1之间中点法绘制直线段：

x0=xs，y0=ys，

x=xe-xs，

y=ye-ys，D0=

x-2

y

当di≥0时，xi+1=xi+1，yi+1=yi，Di+1=Di-2

y

当di<0时，xi+1=xi+1，yi+1=yi+1，Di+1=Di+2

x-2

y(i=0,1,2,…,

x)3中点法的递推公式【例】已知直线段的起点为(1,1)，终点为(5,2)，用中点法求出线段中间的各像素坐标值。d0>0，(2,1)，d1=d0-2=0d1=0，(3,1)，d2=d1-2=-2d2<0，(4,2)，d3=d2+8-2=4d3>0，(5,2)d0=

x-2

y，xi+1=xi+1di≥0，yi+1=yi，di+1=di-2

ydi<0，yi+1=yi+1，di+1=di+2

x-2

y3中点法的递推公式x0=1,y0=1,

x=4,y=1,d0=4–2=2第1象限直线斜率>1中点法MP2P1PM1M2(xi,yi)4任意方向直线段的中点法di+1=F(xM1,yM1)=(yi+2)-k(xi+1.5)-bdi<0di+1=F(xM2,yM2)=(yi+2)-k(xi+0.5)-bF(xM,yM)=(yi+1)-k(xi+0.5)-bdi>=0di=取P1

取P2=di+1xi+1=xi+1，yi+1=yi+1xi+1=xi，yi+1=yi+1=di+1–

kd0=(y0+1)-k(x0+0.5)-b=1-0.5k4任意方向直线段的中点法MP2P1PM1M2(xi,yi)第4象限|k|<1直线di+1=F(xM1,yM1)=(yi-1.5)-k(xi+2)-bdi<0di+1=F(xM2,yM2)=(yi-0.5)-k(xi+2)-bF(xM,yM)=(yi-0.5)-k(xi+1)-bdi=>0di=取P2

取P1=di-

kxi+1=xi+1，yi+1=yi-1xi+1=xi+1，yi+1=yi=di-1–

kd0=(y0-0.5)-k(x0+1)-b=-0.5-kMP2P1PM1M2(xi,yi)4任意方向直线段的中点法x0=xs,y0=ys,d0=-0.5-k,xi+1=xi+1di<0,yi+1=yi,

di+1=di-k,di>=0,yi+1=yi-1,

di+1=di-1-k

x0=xs,y0=ys,d0=0.5-k,xi+1=xi+1di>=0,yi+1=yi,

di+1=di-k,di<0,

yi+1=yi+1,

di+1=di+1-kx0=xs,y0=ys,d0=1+0.5k,yi+1=yi+1di>=0,xi+1=xi,

di+1=di+1,di<0,xi+1=xi-1,

di+1=di+1+kx0=xs,y0=ys,d0=1-0.5k,yi+1=yi+1di<0,xi+1=xi,

di+1=di+1,di>=0,xi+1=xi+1,

di+1=di+1-k4任意方向直线段的中点法交换起点和终点坐标4任意方向直线段的中点法if(ye<ys)交换(xs,ys)与(xe,ye)x=xe-xs,y=ye-ys,x0=xs,y0=ys

xe≥xs

:d0=2

x-

y,yi+1=yi+1,di<0,xi+1=xi,di+1=di+2

xdi≥0,xi+1=xi+1,di+1=di+2x-2

yxe<xs

:d0=2

x+

y,yi+1=yi+1,di≥0,xi+1=xi,di+1=di+2x

di<0,xi+1=xi-1,di+1=di+2

x+2

yif(xe<xs)交换(xs,ys)与(xe,ye)x=xe-xs,y=ye-ys,x0=xs,y0=ys,ye≥ys:

d0=x-2

y,xi+1=xi+1di≥0,yi+1=yi,di+1=di-2

ydi<0,yi+1=yi+1,di+1=di+2

x-2

y

ye<ys:

d0=-x-2

y,xi+1=xi+1