M 3 (x3, y3 )
M1(x1, y1)
o
x
M2 处的偏差为
F2 y2 xA yAx2 y1xA xA yAx1 F1 xA
若 F2 0 ，则应走+x一步到 M3 ，即：
处的偏差为
F3 y3xA yAx3 y2 xA yAx2 yA F2 yA
图形的扫描转换：在光栅显示 器等数字设备上确定一个最佳 逼近于图形的象素集的过程。
图5.1 用象素点集逼近直线
3
5.1 直线的扫描转换
直线的绘制要求 （1）直线要直； （2）直线的端点要准确，无定向性无断裂； （3）直线的亮度、色泽要均匀； （4）画线的速度要快； （5）具有不同的色泽、亮度、线型等。
对应

xi yi

x1 y1
(x2 ( y2
x1) ti y1) ti

而

xi1 yi1

x1 y1

dx(ti dy(ti
dt) dt)

xi yi
dx dt dy dt

这里
dx x2 x1, dy
终点判断 设绘图机的步距为 t，直线在x,y方向的增量分别为x和 y 。
按照上述运算方法，绘图笔从直线的起点画到终点，在x方
向上应走 x 步，在y方向上应走 y 步。因为对于任一条给
t
t
定的直线，各种方法所产生的x方向和y方向的走步信号总和
在同一台设备上是相同的，所以我们取 n x y 作为终点
如图所示，设笔的当前位置 是 M1(x1, y1) ，此时 F1 y1xA yAx1 0
应走+y一步到 M2，即:

x2 y2

x1 y1

1
此处+1表示向正方向走一个设 备单位步长。这里，我们假设 x,y坐标值均已转换为当前设备 单位。
y
A(xA, yA )
M 2 (x2 , y2 )
笔的当前位置为M。我们以 O
X
OM,OA斜率的大小来计算
偏差。偏差值d为：
d tg tg yM yA
xM xA yM xA yA xM
xM xA
当 d 0 时，表示笔在OA线段下方，根据约定，此 时应走+y一步；当 d 0 时，表示笔在OA线段上方 （或在OA线上），则应走+x一步。
数值微分法(DDA法)
DDA算法的原理是，由于直线的一阶导数是连续的，而且 dx
和 dy 是成比例的，因此可以通过在当前位置 (xi , yi ) 分别加 上两个小增量 xinc , yinc 来求出下一点的x，y坐标。
DDA法是一种基于直线的微分方程来生成直线的方法。
设一直线段由 (x1, y1)至(x2 , y2 )，此直线的参数方程可表示
y2 y1,
斜率 k dy
dx
xinc dx dt

yinc

dy dt
则
xi1 xi xinc

yi
1

yi

yinc
这里dt是某个很小的量，其取值方法的不同，决定了有2种 不同的DDA法。
简单DDA法
这样递推下去，就可以得出第i步的结果：
如 Fi 0 ，则走+x一步，此时 Fi1 Fi yA 如 Fi 0 ，则走+y一步，此时 Fi1 Fi xA 由于偏差 Fi 的推算只用到了终点坐标值 xA ，yA
而与中间点的坐标值无关，且只需要进行加减运算， 因而大大减少了计算量。
这种算法只需判断d的正负，其值的大小并不重要。 对于第一象限，因为分母 xM xA永远为正，所以只需 判断分子项的正负即可。我们得到偏差的判断公式 为：
FM yM xA yA xM
递推公式
用上式来计算偏差时，每次都要计算两次乘法，一 次减法，计算工作量还是很大的。如果我们设法用 前一点的偏差来推算走步方向以及走步以后的偏差， 则偏差计算就可以大大简化，也更适于计算机实现。 现在仍以第一象限为例，简述这种递推过程。
下面讨论这种算法的判别规则。
我们先以直线起点为坐标原点，并且约定直线在四 个象限中画笔的走向如图所示。
y
Ⅱ
Ⅰ
x
Ⅲ
Ⅳ
偏差计算
我们先以第一象限为例推导出偏差计算公式，然后 再扩展到其他象限。
Y
A(xA, yA )
一般公式
M (xM , yM )
设要画的线段为OA，而画

4
直线的扫描转换
解 决 的 问 题 ： 给 定 直 线 两 端 点 P0(x0,y0) 和
P1(x1,y1)，画出该直线。 逐点比较法 数值微分法 Bresenham算法 中点Bresenham算法 改进的Bresenham算法
5
逐点比较法
所谓逐点比较法，是指在绘图过程中，绘图笔每画 一笔，就与目标图形相比较，然后决定下一步走向， 用步步逼近的方法画出目标图形。
第五章 基本图形生成算法
如何在指定的输出设备上根据坐标描述构造基本 二维几何图形（点、直线、圆、椭圆、多边形域、 字符串及其相关属性等）。
1
第五章 基本图形生成算法
图形生成的概念 直线段的扫描转换 圆的扫描转换 多边形的扫描转换与区域填充
2
图形生成的概念
图形的生成：是在指定的输出 设备上，根据坐标描述构造二 维几何图形。
为：

x y

x1 y1
(x2 ( y2
x1)t y1)t
其中参数t由0变化到1时，x从x1变化到x2，y从y1变到y2,
如果从 (x1, y1)至(x2 , y2 ) 分成n步，每一步的t变化dt，则第
i步时：
ti i dt， (i 1, 2, , n)
t t
判断的控制数，并将此数存入计数器内。在x或y方向上每走
一步，计数器减1，当计数器减至零时，作图停止。

也可以取
n

max


x t
,
y t

作为长度控制数（即选取x
或y方向上增量较大的方向作为计长方向），并将n存入计数
器中。在计长方向上每走一步，计数器减1，直至n为零止。