dda法生成直线的基本原理是什么?为什么说Bersenham画圆的算法效率较高?

Question

dda法生成直线的基本原理是什么?为什么说Bersenham画圆的算法效率较高?

Answer 1

DDA算法主要是根据直线公式y = kx + b来推导出来的,其关键之处在于如何设定单位步进,即一个方向的步进为单位步进,另一个方向的步进必然是小于1.算法的具体思路如下：
1.输入直线的起点、终点；
2.计算x方向的间距：△X和y方向的间距：△Y.
3.确定单位步进,取MaxSteps = max（△X,△Y）; 若△X>=△Y,则X方向的步进为单位步进,X方向步进一个单位,Y方向步进△Y/MaxSteps;否则相反.
4.设置第一个点的像素值
5.令循环初始值为1,循环次数为MaxSteps,定义变量x,y,执行以下计算：
a.x增加一个单位步进,y增加一个单位步进
b.设置位置为（x,y）的像素值
Bresenham算法是DDA算法画线算法的一种改进算法.本质上它也是采取了步进的思想.不过它比DDA算法作了优化,避免了步进时浮点数运算,同时为选取符合直线方程的点提供了一个好思路.首先通过直线的斜率确定了在x方向进行单位步进还是y方向进行单位步进：当斜率k的绝对值|k|1时,在y方向进行单位步进.
1.输入线段的起点和终点.
2.判断线段的斜率是否存在（即起点和终点的x坐标是否相同）,若相同,即斜率不存在,
只需计算y方向的单位步进（△Y+1次）,x方向的坐标保持不变即可绘制直线.
3.计算线段的斜率k,分为下面几种情况处理
a.k等于0,即线段平行于x轴,即程序只需计算x方向的单位步进,y方向的值不变
b.|k|等于1,即线段的x方向的单位步进和y方向的单位步进一样,皆为1.直接循环△X次计算x和y坐标.
4.根据输入的起点和终点的x、y坐标值的大小决定x方向和y方向的单位步进是1还是-1
6.画出第一个点.
7.若|k| 0,下一个要绘制的点为（Xm+单位步进,Ym）,
Pm+1 = Pm -2*△Y;
否则要绘制的点为（Xm+单位步进,Ym+单位步进）
Pm+1 = Pm+2*△X-2*△Y；
8.重复执行第七步△X-1次；
9.若|k| 0,下一个要绘制的点为（Xm,Ym+单位步进）,
Pm+1 = Pm -2*△X;
否则要绘制的点为（Xm+单位步进,Ym+单位步进）
Pm+1 = Pm+2*△Y-2*△X；
10.重复执行第9步△Y-1次；