直线生成dda算法原理

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

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时，在x方向进行单位步进；当斜率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| <1，设m =0,计算P0，如果Pm>0，下一个要绘制的点为（Xm+单位步进，Ym），
Pm+1 = Pm -2*△Y;
否则要绘制的点为（Xm+单位步进，Ym+单位步进）
Pm+1 = Pm+2*△X-2*△Y；
8. 重复执行第七步△X-1次；
9. 若|k| <1，设m =0,计算Q0，如果Qm>0，下一个要绘制的点为（Xm，Ym+单位步进），
Pm+1 = Pm -2*△X;
否则要绘制的点为（Xm+单位步进，Ym+单位步进）
Pm+1 = Pm+2*△Y-2*△X；
10. 重复执行第9步△Y-1次；

Ⅱ 生成算法的步骤是( )

直线生成算法中的数值/字微分分析法是一种增量计算方法。它按照斜率绝对值|k|<1和|k|>1来递增画描点。|k|<1时，取像素（x，（int）(y+0.5)；|k|>1时，取像素（（int）(x+0.5)，y)。

循环结构需要重复执行同一操作的结构称为循环结构，即从某处开始，按照一定条件反复执行某一处理步骤，反复执行的处理步骤称为循环体。循环结构中通常都有一个起循环计数作用的变量，这个变量的取值一般都包含在执行或终止循环的条件中。

算法原理

SJT算法，即Steinhaus–Johnson–Trotter algorithm，是一种全排列生成算法。在该算法中，不断的寻找一种相邻元素相互交换的顺序，根据这种交换的顺序，依次计算下一个排列。在SJT算法中，每次循环都进行一次满足条件的相邻元素的交换，直到不存在满足条件的可交换的元素，此时说明所有排列的情况均已输出，算法结束。

Ⅲ 分别解释直线生成算法DDA法、中点画线法和Bresenham法的基本原理

DDA称为数值微分画线算法，是直线生成算法中最简单的一种。原理相当简单，就是最直观的根据斜率的偏移程度，决定是以x为步进方向还是以y为步进方向。然后在相应的步进方向上，步进变量每次增加一个像素，而另一个相关坐标变量则为Yk_1=Yk+m（以x为步进变量为例，m为斜率）
假定直线斜率k在0~1之间，当前象素点为（xp,yp），则下一个象素点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1）。若P1与P2的中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。这就是中点画线法的基本原理

Bresenham：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。该算法的优点在于可以采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列所求的像素。

大概就是这样，预知详细，可以参考图形学的书籍

Ⅳ 计算机图形学的题：已知起点A(16,-5)和终点B(-4,8)，用DDA法在A和B之间生成一段直线

楼主，你是用对称DDA算法还是简单DDA算法呢？

我用对称DDA算法给你做了下，答案如下，供参考（由于贴上去格式会乱，附了一张图片）：

对称DDA算法

1.计算初值△x=-4-16=-20，△y=8-(-5)=13，则n=5，ε=2-n=0.03125

因此，增量分别为：ε*△x=-0.625，ε*△y=0.40625

2.按递推公式循环计算点的坐标，并取整数显示。

i计算坐标显示坐标i计算坐标显示坐标

x1y1xipyipX1y1xipyip

016.5-4.516-4175.2252.4062552

115.875-4.0937515-4184.62.812542

215.25-3.687515-3193.9753.2187533

314.625-3.2812514-2203.353.62533

414-2.87514-2212.7254.0312524

513.375-2.4687513-2222.14.437524

612.125-2.062512-2231.4754.8437514

711.5-1.6562511-1240.855.2505

810.875-1.2510-1250.2255.6562505

910.25-0.8437510026-0.46.062506

109.6-0.43759027-1.0256.46875-16

118.975-0.031258028-1.656.875-16

128.350.3758029-2.2757.28125-27

137.7250.781257030-2.97.6875-27

147.11.18757131-3.5258.09375-38

156.4751.593756132-4.158.5-48

165.85252

3.画一张图XY轴，将（xip，yip）标上去，描绘成一条直线即可。