角度dda法画圆算法

⑴ c语言问题

一、 算法设计及流程

1. 点

不管什么样的图形归根结底到屏幕，都是由一些颜色不一的象素点组成，为提高图形的显示效率，没有用到系统的画点函数，而采用了640*480*16模式下的直接写屏技术画点，该模式下的直接写屏比320*200*256的直接写屏要复杂的多，后者的视频缓冲区是线性编址的，一个字节对应屏幕上一点的颜色，而前者的视频缓冲区被分成四个位面，屏幕上一点的颜色由每个位面上的一位组成的四位二进制数决定，由于四位二进制数的最大表示范围是16，所以在这种模式下最多可同时显示16种颜色。

在对视频缓冲区的读写时，是一个字节一个字节写的，只需要其中某一位时，就要用到位掩码屏蔽掉其他的位，位掩码就在图形控制寄存器的位屏蔽寄存器里设置。先通过向端口号为0x3ce的索引寄存器写入位屏蔽寄存器的索引号8，然后向端口号为0x3cf的寄存器写入位掩码值。设置好位掩码后，直接向视频缓冲区相应位置写入颜色即为画点函数。

取屏幕上一点颜色其实也就是画点的反操作，画点是将一个四位的二进制颜色值分配到四个位面，而取一点的颜色是将四个位面的颜色组合成一个四位二进制数。

2. 线

线其实就是由点组成的，通过连续的改变点的坐标，也就可以得到一条线。所以画线的函数归根结底也就是如何改变画点的坐标。

画线通常有DDA算法，BRESENHAM算法，这里采用的是BRESENHAM算法。这种算法从根本上讲，是通过横线与竖线的倍数关系来实现的。每次循环画点后x、y中位移大的坐标变化一个单位，而当循环次数是两者倍数关系时，x、y中位移小的坐标变化一个单位。为了使画线函数能在八个方向都能画，将增量为负的都转化正的增量。

画图程序经常要用到moveto、lineto等函数，用于把点移动到某点或从当前点画线到某点，为了模拟这些函数，设置了SX，SY两个全局变量用来作为Moveto（）的目的地和Drawlineto（）的起始坐标。

3. 矩形及填充矩形

矩形是通过两点确定的对角线来画的，直接连上各点的坐标就可以了。填充矩形是通过一条线一条线画的。这种算法速度比较慢，较好的方法是用Fillscreen（）里面用到的方法，那是一个字节一个字节处理的。就因为画矩形并不一定是整字节开始整字节结束的，开始处和结尾处就有了问题。我也把它们单独拿出来处理，但还是没做好，等有时间了再改吧。

4. 圆及弧

画圆采用的是参数方程的方法。为了提高速度，角度的sin、cos值建立了一个表，要用时直接查表。这是因为在用BRESENHAM算法画椭圆时，效果不是很好，画的椭圆不但厚薄不一，而且不闭合。估计是程序哪里出问题了，干脆都用参数方程的方法，又简单，又省事。我这人通常是比较懒的。

弧主要是用来画圆角矩形的，且只能画圆弧。这也是用参数方程来画的，跟画圆不同的只是有了角度的限制。

5. 贝塞尔曲线

贝塞尔曲线其实主要也就是一个公式，跟参数方程画圆是一回事，只是要传入的参数要多一些。在用鼠标控制时，因为有四个点，而用鼠标对多点的采集有点不好做，于是先就初始化了一个四点的数组，用不按键、按左键、按右键分别控制三个点，左右键同时按时，确定下一条曲线。

其实用鼠标画贝塞尔曲线因该把一次、二次、三次的处理函数都写出来，在按下左键时，标记下这点，再一次按下左键时，用画一次贝塞尔曲线的函数画，按下第三次时，用画二次曲线的函数画，按下第四次时才用画三次曲线的函数画。这样就不用为每个点分配一个鼠标按键了。

6. 填充

填充也是采用的种子填充法，不过不是直接从种子开始填色，而是先从种子出发，找到种子沿x最小的边界，然后填上一点，判断这一点的上边一点和下边一点，如果不为边界并且未被填色，则压入栈中，然后x增1后判断是否到达这一行x的最大值（既边界），如不是，则循环处理这一行，直到到达边界，再弹出一个点继续循环处理。由于是一个点一个点处理，所以速度比较慢。

为了对一个图形的不同颜色边界也能填充，填色时没有传入图形的边界颜色，而是采用先取出种子的颜色，在填充下一个点时，把下一点的颜色和种子颜色比较，如果相同则填色，不同则作为边界。

7. 汉字及字符

图形模式下显示汉字其实是一件比较麻烦的事，一般要用到汉字字库，生成的可执行文件也得在有字库的环境下运行。我这里采用了汉字无字库技术，生成的文件不依赖任何其他文件。

无字库技术是通过从字库文件提取需要的中文点阵字模建立一个类似字库的字库数组。它可以大大提高汉字的显示速度。在建立字库数组时，将字模数组进行了排序，所以在显示汉字时

文章来自: 好喜爱学习网(http://www.haoxiai.net) 网址：http://www.haoxiai.net/bianchengyuyan/cyuyan/11968.html

⑵ 计算机图形学的一些题目

答案为bbcaabca

⑶ 求DDA算法画椭圆

我要是会就告诉你~~多看看书吧

⑷ 直线和圆的显示（在线等答案）

实验2 圆与椭圆
给出圆心坐标(xc, yc)和半径r，逐点画出一个圆周的公式有下列两种。
一 直角坐标法
直角坐标系的圆的方程为

由上式导出：

当x-xc从-r到r做加1递增时，就可以求出对应的圆周点的y坐标。但是这样求出的圆周上的点是不均匀的，| x-xc | 越大，对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆不美观。
二 中点画圆法
如图1所示，函数为F(x, y)=x2+y2-R2的构造圆，圆上的点为F(x, y)=0，圆外的点F(x, y)>0，圆内的点F(x, y)<0，构造判别式：
d=F(M)=F(xp+1, yp-0.5)=(xp+1)2+(yp-0.5)2
若d＜0，则应取P1为下一像素，而且下一像素的判别式为
d=F(xp+2, yp-0.5)= (xp+2)2+(yp-0.5)2-R2=d+2xp+3
若d≥0，则应取P2为下一像素，而且下一像素的判别式为
d=F(xp+2, yp-1.5)= (xp+2)2+(yp-1.5)2-R2=d+2(xp- yp)+5
我们讨论按顺时针方向生成第二个八分圆，则第一个像素是（0, R），判别式d的初始值为
d0=F(1, R-0.5)=1.25-R
三 圆的Bresenham算法
设圆的半径为r，先考虑圆心在(0, 0)，从x=0、y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束，即有xi+1 = xi + 1；相应的，yi+1则在两种可能中选择：yi+1=yi或者yi+1 = yi - 1。选择的原则是考察精确值y是靠近yi还是靠近yi-1（见图2），计算式为
y2= r2-(xi+1)2
d1 = yi2-y2 = yi2-r2+(xi+1)2
d2 = y2- (yi - 1)2 = r2-(xi+1)2-(yi - 1)2
令pi=d1-d2，并代入d1、d2，则有
pi = 2(xi+1)2 + yi2+ (yi - 1)2 -2r2 （1.6）
pi称为误差。如果pi＜0，则yi+1=yi，否则yi+1=yi - 1。
pi的递归式为
pi+1 = pi + 4xi +6+2(yi2+1- yi2)-2(yi+1-yi) （1.7）
pi的初值由式(1.6)代入xi=0，yi=r，得
p1 = 3-2r （1.8）
根据上面的推导，圆周生成算法思想如下：
（1）求误差初值，p1=3-2r，i=1，画点(0, r)。
（2）求下一个光栅位置，其中xi+1=xi+1，如果pi＜0则yi+1=yi，否则yi+1=yi - 1。
（3）画点(xi+1, yi+1)。
（4）计算下一个误差，如果pi＜0则pi+1=pi+4xi+6，否则pi+1=pi+4(xi - yi)+10。
（5）i=i+1，如果x=y则结束，否则返回步骤（2）。
程序设计步骤如下。
（1）创建应用程序框架，以上面建立的单文档程序框架为基础。
（2）编辑菜单资源。
在工作区的ResourceView标签中，单击Menu项左边"+"，然后双击其子项IDR_MAINFRAME，并根据表1中的定义添加编辑菜单资源。此时建好的菜单如图3所示。
表1 菜单资源表
菜单标题 菜单项标题 标示符ID
圆 中点画圆 ID_MIDPOINTCIRCLE
Bresenham画圆 ID_BRESENHAMCIRCLE
（3）添加消息处理函数。
利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表2建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。
表2 菜单项的消息处理函数
菜单项ID 消 息 消息处理函数
ID_MIDPOINTCIRCLE CONMMAN OnMidpointcircle
ID_BRESENHAMCIRCLE CONMMAN OnBresenhamcircle
（4）程序结构代码，在CMyView.cpp文件中的相应位置添加如下代码。

void CMyView::OnMidpointcircle() //中点算法绘制圆，如图4所示
{
// TODO: Add your command handler code here
CDC* pDC=GetDC();
int xc=300, yc=300, r=50, c=0;
int x,y;
float d;
x=0; y=r; d=1.25-r;
pDC->SetPixel ((xc+x),(yc+y),c);
pDC->SetPixel ((xc-x),(yc+y),c);
pDC->SetPixel ((xc+x),(yc-y),c);
pDC->SetPixel ((xc-x),(yc-y),c);
pDC->SetPixel ((xc+y),(yc+x),c);
pDC->SetPixel ((xc-y),(yc+x),c);
pDC->SetPixel ((xc+y),(yc-x),c);
pDC->SetPixel ((xc-y),(yc-x),c);
while(x<=y)
{ if(d<0) d+=2*x+3;
else { d+=2*(x-y)+5; y--;}
x++;
pDC->SetPixel ((xc+x),(yc+y),c);
pDC->SetPixel ((xc-x),(yc+y),c);
pDC->SetPixel ((xc+x),(yc-y),c);
pDC->SetPixel ((xc-x),(yc-y),c);
pDC->SetPixel ((xc+y),(yc+x),c);
pDC->SetPixel ((xc-y),(yc+x),c);
pDC->SetPixel ((xc+y),(yc-x),c);
pDC->SetPixel ((xc-y),(yc-x),c);
}
}
void CMyView::OnBresenhamcircle() //// Bresenham算法绘制圆，如图5所示
{
CDC* pDC=GetDC();
int xc=100, yc=100, radius=50, c=0;
int x=0,y=radius,p=3-2*radius;
while(x<y)
{
pDC->SetPixel(xc+x, yc+y, c);
pDC->SetPixel(xc-x, yc+y, c);
pDC->SetPixel(xc+x, yc-y, c);
pDC->SetPixel(xc-x, yc-y, c);
pDC->SetPixel(xc+y, yc+x, c);
pDC->SetPixel(xc-y, yc+x, c);
pDC->SetPixel(xc+y, yc-x, c);
pDC->SetPixel(xc-y, yc-x, c);
if (p<0)
p=p+4*x+6;
else
{
p=p+4*(x-y)+10;
y-=1;
}
x+=1;
}
if(x==y)
pDC->SetPixel(xc+x, yc+y, c);
pDC->SetPixel(xc-x, yc+y, c);
pDC->SetPixel(xc+x, yc-y, c);
pDC->SetPixel(xc-x, yc-y, c);
pDC->SetPixel(xc+y, yc+x, c);
pDC->SetPixel(xc-y, yc+x, c);
pDC->SetPixel(xc+y, yc-x, c);
pDC->SetPixel(xc-y, yc-x, c);
}

四 椭圆扫描转换中点算法
下面讨论椭圆的扫描转换中点算法，设椭圆为中心在坐标原点的标准椭圆，其方 程为
F(x, y)=b2x2+a2y2-a2b2=0
（1）对于椭圆上的点，有F(x, y)=0；
（2）对于椭圆外的点，F(x, y)>0；
（3）对于椭圆内的点，F(x, y)<0。
以弧上斜率为-1的点作为分界将第一象限椭圆弧分为上下两部分（如图6所示）。
法向量：

而在下一个点，不等号改变方向，则说明椭圆弧从上部分转入下部分。
与中点绘制圆算法类似，一个像素确定后，在下面两个候选像素点的中点计算一个判别式的值，再根据判别式符号确定离椭圆最近的点。先看椭圆弧的上半部分，具体算法如下：
假设横坐标为xp的像素中与椭圆最近点为（xp, yp），下一对候选像素的中点应为（xp+1，yp-0.5），判别式为

，表明中点在椭圆内，应取正右方像素点，判别式变为

若 ，表明中点在椭圆外，应取右下方像素点，判别式变为

判别式 的初始条件确定。椭圆弧起点为(0, b)，第一个中点为(1,b - 0.5)，对应判别式为

在扫描转换椭圆的上半部分时，在每步迭代中需要比较法向量的两个分量来确定核实从上部分转到下半部分。在下半部分算法有些不同，要从正上方和右下方两个像素中选择下一个像素。在从上半部分转到下半部分时，还需要对下半部分的中点判别式进行初始化。即若上半部分所选择的最后一个像素点为(xp, yp)，则下半部分中点判别式应在（xp+0.5, yp-1）的点上计算。其在正下方与右下方的增量计算同上半部分。具体算法的实现请参考下面的程序设计。
程序设计步骤如下。
（1）创建应用程序框架，以上面建立的单文档程序框架为基础。
（2）编辑菜单资源。
在工作区的ResourceView标签中，单击Menu项左边"+"，然后双击其子项IDR_MAINFRAME，并根据表3中的定义添加编辑菜单资源。此时建好的菜单如图7所示。
表3 菜单资源表
菜单标题 菜单项标题 标示符ID
椭圆 中点画椭圆 ID_MIDPOINTELLISPE

图7 程序主菜单
（3）添加消息处理函数。
利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表4建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。
表4 菜单项的消息处理函数
菜单项ID 消 息 消息处理函数
ID_MIDPOINTELLISPE CONMMAN OnMidpointellispe
（4）程序结构代码如下：

void CMyView:: OnMidpointellispe () //中点算法绘制椭圆，如图8所示
{
CDC* pDC=GetDC();
int a=200,b=100,xc=300,yc=200,c=0;
int x,y;
double d1,d2;
x=0;y=b;
d1=b*b+a*a*(-b+0.25);
pDC->SetPixel(x+300,y+200,c);
pDC->SetPixel(-x+300,y+200,c);
pDC->SetPixel(x+300,-y+200,c);
pDC->SetPixel(-x+300,-y+200,c);
while(b*b*(x+1)<a*a*(y-0.5))
{
if(d1<0){
d1+=b*b*(2*x+3);
x++;}
else
{d1+=b*b*(2*x+3)+a*a*(-2*y+2);
x++;y--;
}
pDC->SetPixel(x+xc,y+yc,c);
pDC->SetPixel(-x+xc,y+yc,c);
pDC->SetPixel(x+xc,-y+yc,c);
pDC->SetPixel(-x+xc,-y+yc,c);
}
d2=sqrt(b*(x+0.5))+a*(y-1)-a*b;
while(y>0)
{
if(d2<0){
d2+=b*b*(2*x+2)+a*a*(-2*y+3);
x++;y--;}
else
{d2+=a*a*(-2*y+3);
y--;}
pDC->SetPixel(x+xc,y+yc,c);
pDC->SetPixel(-x+xc,y+yc,c);
pDC->SetPixel(x+xc,-y+yc,c);
pDC->SetPixel(-x+xc,-y+yc,c);
}
}

实验一: 直 线
数学上，理想的直线是由无数个点构成的集合，没有宽度。计算机绘制直线是在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，实现显示器绘制直线，即通常所说的直线的扫描转换，或称直线光栅化。
由于一图形中可能包含成千上万条直线，所以要求绘制直线的算法应尽可能地快。本节介绍一个像素宽直线的常用算法：数值微分法（DDA）、中点画线法、Bresenham 算法。
一. DDA（数值微分）算法
DDA算法原理：如图1-1所示，已知过端点 的直线段 ；直线斜率为 ，从 的左端点 开始，向 右端点步进画线，步长=1（个像素），计算相应的 坐标 ；取像素点 [ , round（y）] 作为当前点的坐标。计算 ，当 ，即当x每递增1，y递增k（即直线斜率）。
注意：上述分析的算法仅适用于k1的情形。在这种情况下，x每增加1, y最多增加1。当 时，必须把x，y地位互换，y每增加1，x相应增加1/k（请参阅后面的Visual C++程序）。
二. 生成直线的中点画线法
中点画线法的基本原理如图1-2所示。在画直线段的过程中，当前像素点为P，下一个像素点有两种选择，点P1或P2。M为P1与P2中点，Q为理想直线与X=Xp+1垂线的交点。当M在Q的下方时，则P2应为下一个像素点；当M在Q的上方时，应取P1为下一点。
中点画线法的实现：令直线段为L[ p0(x0,y0), p1(x1, y1)]，其方程式F(x, y)=ax+by+c=0。
其中，a=y0–y1, b=x1–x0, c=x0y1–x1y0；点与L的关系如下。
在直线上，F(x, y)=0；
在直线上方，F(x, y)>0；
在直线下方，F(x, y)<0。
把M代入F（x, y），判断F的符号，可知Q点在中点M的上方还是下方。为此构造判别式d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c。
当d < 0，L(Q点)在M上方，取P2为下一个像素。
当d > 0，L(Q点)在M下方，取P1为下一个像素。
当d=0，选P1或P2均可，取P1为下一个像素。
其中d是xp, yp的线性函数。
三. Bresenham算法
Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。由误差项符号决定下一个像素取右边点还是右上方点。
设直线从起点(x1, y1)到终点(x2, y2)。直线可表示为方程y = mx+b，其中b=y1–mx1， m = (y2–y1)/(x2–x1)=dy/dx；此处的讨论直线方向限于第一象限，如图1-3所示，当直线光栅化时，x每次都增加1个单元，设x像素为(xi，yi)。下一个像素的列坐标为xi+1，行坐标为yi或者递增1为yi+1，由y与yi及yi+1的距离d1及d2的大小而定。计算公式为
y = m(xi + 1) + b （1.1）
d1 = y – yi （1.2）
d2=yi+1–y （1.3）
如果d1–d2>0，则yi+1=yi+1，否则yi+1=yi。
式（1.1）、（1.2）、（1.3）代入d1–d2，再用dx乘等式两边，并以Pi=(d1–d2)，dx代入上述等式，得
Pi = 2xidy–2yidx+2dy+(2b–1)dx （1.4）
d1–d2是用以判断符号的误差。由于在第一象限，dx总大于0，所以Pi仍旧可以用做判断符号的误差。Pi+1为
Pi+1 = Pi+2dy–2(yi+1–yi)dx （1.5）
求误差的初值P1，可将x1、y1和b代入式（1.4）中的xi、yi，而得到
P1 = 2dy–dx
综述上面的推导，第一象限内的直线Bresenham算法思想如下：
（1）画点（x1, y1），dx=x2–x1，dy=y2–y1，计算误差初值P1=2dy–dx，i=1。
（2）求直线的下一点位置xi+1 = xi + 1，如果Pi>0，则yi+1=yi+1，否则yi+1=yi。
（3）画点(xi+1, yi+1)。
（4）求下一个误差Pi+1，如果Pi>0，则Pi+1=Pi+2dy–2dx，否则Pi+1=Pi+2dy。
（5）i=i+1；如果i<dx+1则转步骤（2）；否则结束操作。
四. 程序设计
1 程序设计功能说明
为编程实现上述算法，本程序利用最基本的绘制元素（如点、直线等），绘制图形。如图1-4所示，为程序运行主界面，通过选择菜单及下拉菜单的各功能项分别完成各种对应算法的图形绘制。

图1-4 基本图形生成的程序运行界面
2 创建工程名称为“基本图形的生成”单文档应用程序框架
（1）启动VC，选择“文件”|“新建”菜单命令，并在弹出的新建对话框中单击“工程”标签。
（2）选择MFC AppWizard(exe)，在“工程名称”编辑框中输入 “基本图形的生成”作为工程名称，单击“确定”按钮，出现Step 1对话框。
（3）选择“单个文档”选项，单击“下一个”按钮，出现Step 2对话框。
（4）接受默认选项，单击“下一个”按钮，在出现的Step 3～Step 5对话框中，接受默认选项，单击“下一个”按钮。
（5）在Step 6对话框中单击“完成”按钮，即完成“基本图形的生成”应用程序的所有选项，随后出现工程信息对话框（记录以上步骤各选项选择情况），如图1-5所示，单击“确定”按钮，完成应用程序框架的创建。

图1-5 信息程序基本
3 编辑菜单资源
设计如图1-4所示的菜单项。在工作区的ResourceView标签中，单击Menu项左边“+”，然后双击其子项IDR_MAINFRAME，并根据表1-1中的定义编辑菜单资源。此时VC已自动建好程序框架，如图1-5所示。
表1-1 菜单资源表
菜单标题 菜单项标题 标示符ID
直线 DDA算法生成直线 ID_DDALINE
Bresenham算法生成直线 ID_BRESENHAMLINE
中点算法生成直线 ID_MIDPOINTLINE
4 添加消息处理函数
利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表1-2建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。
表1-2 菜单项的消息处理函数
菜单项ID 消 息 消息处理函数
ID_DDALINE CONMMAN OnDdaline
ID_MIDPOINTLINE CONMMAN OnMidpointline
ID_BRESENHAMLINE CONMMAN OnBresenhamline
5 程序结构代码，在CMyView.cpp文件中相应位置添加如下代码：
// DDA算法生成直线
void CMyView:: OnDdaline()
{
CDC* pDC=GetDC();//获得设备指针
int xa=100,ya=300,xb=300,yb=200,c=RGB(255,0,0);//定义直线的两端点，直线颜色
int x,y;
float dx, dy, k;
dx=(float)(xb-xa), dy=(float)(yb-ya);
k=dy/dx, y=ya;
if(abs(k)<1)
{
for (x=xa;x<=xb;x++)
{pDC->SetPixel (x,int(y+0.5),c);
y=y+k;}
}
if(abs(k)>=1)
{
for (y=ya;y<=yb;y++)
{pDC->SetPixel (int(x+0.5),y,c);
x=x+1/k;}
}
ReleaseDC(pDC);
}

说明：
（1）以上代码理论上通过定义直线的两端点，可得到任意端点之间的一直线，但由于一般屏幕坐标采用右手系坐标，屏幕上只有正的x, y值，屏幕坐标与窗口坐标之间转换知识请参考第3章。
（2）注意上述程序考虑到当k1的情形x每增加1，y最多增加1；当k>1时，y每增加1，x相应增加1/k。在这个算法中，y与k用浮点数表示，而且每一步都要对y进行四舍五入后取整。

//中点算法生成直线
void CMyView::OnMidpointline()
{
CDC* pDC=GetDC();
int xa=300, ya=200, xb=450, yb=300,c=RGB(0,255,0);
int a, b, d1, d2, d, x, y;
a=ya-yb, b=xb-xa, d=2*a+b;
d1=2*a, d2=2* (a+b);
x=xa, y=ya;
pDC->SetPixel(x, y, c);
while (x<xb)
{ if (d<0) {x++, y++, d+=d2; }
else {x++, d+=d1;}
pDC->SetPixel(x, y, c);
}
ReleaseDC(pDC);
}

说明：
（1）其中d是xp, yp的线性函数。为了提高运算效率，程序中采用增量计算。具体算法如下：若当前像素处于d>0情况，则取正右方像素P1(xp+1, yp)，判断下一个像素点的位置，应计算d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；，其中增量为a。若d<0时，则取右上方像素P2（xp+1, yp+1）。再判断下一像素，则要计算d2 = F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5) + c=d+a+b，增量为a+b。
（2） 画线从(x0, y0)开始，d的初值d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b，因F(x0, y0)=0，则d0=a+0.5b。
（3）程序中只利用d的符号，d的增量都是整数，只是初始值包含小数，用2d代替d，使程序中仅包含整数的运算。

//Bresenham算法生成直线
void CMyView::OnBresenhamline()
{
CDC* pDC=GetDC();
int x1=100, y1=200, x2=350, y2=100,c=RGB(0,0,255);
int i,s1,s2,interchange;
float x,y,deltax,deltay,f,temp;
x=x1;
y=y1;
deltax=abs(x2-x1);
deltay=abs(y2-y1);
if(x2-x1>=0) s1=1; else s1=-1;
if(y2-y1>=0) s2=1; else s2=-1;
if(deltay>deltax){
temp=deltax;
deltax=deltay;
deltay=temp;
interchange=1;
}
else interchange=0;
f=2*deltay-deltax;
pDC->SetPixel(x,y,c);
for(i=1;i<=deltax;i++){
if(f>=0){
if(interchange==1) x+=s1;
else y+=s2;
pDC->SetPixel(x,y,c);
f=f-2*deltax;
}
else{
if(interchange==1) y+=s2;
else x+=s1;
f=f+2*deltay;
}
}
}

说明：
（1）以上程序已经考虑到所有象限直线的生成。
（2）Bresenham算法的优点如下：
① 不必计算直线的斜率，因此不做除法。
② 不用浮点数，只用整数。
③ 只做整数加减运算和乘2运算，而乘2运算可以用移位操作实现。
④ Bresenham算法的运算速度很快。

⑸ 为什么用dda算法生成圆周或椭圆不需要用到三角运算，所以运算效率高

一个自耕农家庭里，牛顿诞生了。牛顿是一个早产儿，出生时只有三磅重，接生婆和他的亲人都担心他能否活下来。谁也没有料到这个看起来微不足道的小东西会成为了一位震古烁今的科学巨人，并且竟活到了85岁的高龄。

牛顿出生前三个月父亲便去世了。在他两岁时，母亲改嫁给一个牧师，把牛顿留在外祖母身边抚养。11岁时，母亲的后夫去世，母亲带着和后夫所生的一子二女回到牛顿身边。牛顿自幼沉默寡言，性格倔强，这种习性可能来自它的家庭处境。

大约从五岁开始，牛顿被送到公立学校读书。少年时的牛顿并不是神童，他资质平常，成绩一般，但他喜欢读书，喜欢看一些介绍各种简单机械模型制作方法的读物，并从中受到启发，自己动手制作些奇奇怪怪的小玩意，如风车、木钟、折叠式提灯等等。

传说小牛顿把风车的机械原理摸透后，自己制造了一架磨坊的模型，他将老鼠绑在一架有轮子的踏车上，然后在轮子的前面放上一粒玉米，刚好那地方是老鼠可望不可及的位置。老鼠想吃玉米，就不断的跑动，于是轮子不停的转动；又一次他放风筝时，在绳子上悬挂着小灯，夜间村人看去惊疑是彗星出现；他还制造了一个小水钟。每天早晨，小水钟会自动滴水到他的脸上，催他起床。他还喜欢绘画、雕刻，尤其喜欢刻日晷，家里墙角、窗台上到处安放着他刻画的日晷，用以验看日影的移动。

牛顿12岁时进了离家不远的格兰瑟姆中学。牛顿的母亲原希望他成为一个农民，但牛顿本人却无意于此，而酷爱读书。随着年岁的增大，牛顿越发爱好读书，喜欢沉思，做科学小实验。他在格兰瑟姆中学读书时，曾经寄宿在一位剂师家里，使他受到了化学试验的熏陶。

牛顿在中学时代学习成绩并不出众，只是爱好读书，对自然现象由好奇心，例如颜色、日影四季的移动，尤其是几何学、哥白尼的日心说等等。他还分门别类的记读书笔记，又喜欢别出心裁的作些小工具、小技巧、小发明、小试验。

当时英国社会渗透基督教新思想，牛顿家里有两位都以神父为职业的亲戚，这可能影响牛顿晚年的宗教生活。从这些平凡的环境和活动中，还看不出幼年的牛顿是个才能出众异于常人的儿童。

后来迫于生活，母亲让牛顿停学在家务农，赡养家庭。但牛顿一有机会便埋首书卷，以至经常忘了干活。每次，母亲叫他同佣人一道上市场，熟悉做交易的生意经时，他便恳求佣人一个人上街，自己则躲在树丛后看书。有一次，牛顿的舅父起了疑心，就跟踪牛顿上市镇去，发现他的外甥伸着腿，躺在草地上，正在聚精会神地钻研一个数学问题。牛顿的好学精神感动了舅父，于是舅父劝服了母亲让牛顿复学，并鼓励牛顿上大学读书。牛顿又重新回到了学校，如饥似渴地汲取着书本上的营养。有一次，他去郊外游玩，之后靠在一棵苹果树下休息，忽然，一个苹果从树上掉下来。他觉得很奇怪，为什么苹果会从上往下掉而不是从下往上掉？他带着这个疑问回到了家里研究，后来他发现原来地球是有引力的能把物体吸住。随后，就出现了《牛顿物理引力学》。

求学岁月

1661年，19岁的牛顿以减费生的身份进入剑桥大学三一学院，靠为学院做杂务的收入支付学费，1664年成为奖学金获得者，1665年获学士学位。

17世纪中叶，剑桥大学的教育制度还渗透着浓厚的中世纪经院哲学的气味，当牛顿进入剑桥时，哪里还在传授一些经院式课程，如逻辑、古文、语法、古代史、神学等等。两年后三一学院出现了新气象，卢卡斯创设了一个独辟蹊径的讲座，规定讲授自然科学知识，如地理、物理、天文和数学课程。

讲座的第一任教授伊萨克·巴罗是个博学的科学家。这位学者独具慧眼，看出了牛顿具有深邃的观察力、敏锐的理解力。于是将自己的数学知识，包括计算曲线图形面积的方法，全部传授给牛顿，并把牛顿引向了近代自然科学的研究领域。

在这段学习过程中，牛顿掌握了算术、三角，读了开普勒的《光学》，笛卡尔的《几何学》和《哲学原理》，伽利略的《两大世界体系的对话》，胡克的《显微图集》，还有皇家学会的历史和早期的哲学学报等。

牛顿在巴罗门下的这段时间，是他学习的关键时期。巴罗比牛顿大12岁，精于数学和光学，他对牛顿的才华极为赞赏，认为牛顿的数学才超过自己。后来，牛顿在回忆时说道：“巴罗博士当时讲授关于运动学的课程，也许正是这些课程促使我去研究这方面的问题。”

当时，牛顿在数学上很大程度是依靠自学。他学习了欧几里得的《几何原本》、笛卡儿的《几何学》、沃利斯的《无穷算术》、巴罗的《数学讲义》及韦达等许多数学家的着作。其中，对牛顿具有决定性影响的要数笛卡儿的《几何学》和沃利斯的《无穷算术》，它们将牛顿迅速引导到当时数学最前沿～解析几何与微积分。1664年，牛顿被选为巴罗的助手，第二年，剑桥大学评议会通过了授予牛顿大学学士学位的决定。

1665～1666年严重的鼠疫席卷了伦敦，剑桥离伦敦不远，为恐波及，学校因此而停课，牛顿于1665年6月离校返乡。

由于牛顿在剑桥受到数学和自然科学的熏陶和培养，对探索自然现象产生浓厚的兴趣，家乡安静的环境又使得他的思想展翅飞翔。1665～1666年这段短暂的时光成为牛顿科学生涯中的黄金岁月，他在自然科学领域内思潮奔腾，才华迸发，思考前人从未思考过的问题，踏进了前人没有涉及的领域，创建了前所未有的惊人业绩。

1665年初，牛顿创立级数近似法,以及把任意幂的二项式化为一个级数的规则；同年11月，创立正流数法(微分)；次年1月，用三棱镜研究颜色理论；5月，开始研究反流数法(积分)。这一年内，牛顿开始想到研究重力问题，并想把重力理论推广到月球的运动轨道上去。他还从开普勒定律中推导出使行星保持在它们的轨道上的力必定与它们到旋转中心的距离平方成反比。牛顿见苹果落地而悟出地球引力的传说，说的也是此时发生的轶事。

总之，在家乡居住的两年中，牛顿以比此后任何时候更为旺盛的精力从事科学创造，并关心自然哲学问题。他的三大成就：微积分、万有引力、光学分析的思想都是在这时孕育成形的。可以说此时的牛顿已经开始着手描绘他一生大多数科学创造的蓝图。

1667年复活节后不久，牛顿返回到剑桥大学，10月1日被选为三一学院的仲院侣(初级院委)，翌年3月16日获得硕士学位，同时成为正院侣(高级院委)。1669年10月27日，巴罗为了提携牛顿而辞去了教授之职，26岁的牛顿晋升为数学教授，并担任卢卡斯讲座的教授。巴罗为牛顿的科学生涯打通了道路，如果没有牛顿的舅父和巴罗的帮助，牛顿这匹千里马可能就不会驰骋在科学的大道上。巴罗让贤，这在科学史上一直被传为佳话。

伟大的成就～建立微积分

在牛顿的全部科学贡献中，数学成就占有突出的地位。他数学生涯中的第一项创造性成果就是发现了二项式定理。据牛顿本人回忆，他是在1664年和1665年间的冬天，在研读沃利斯博士的《无穷算术》时，试图修改他的求圆面积的级数时发现这一定理的。

笛卡尔的解析几何把描述运动的函数关系和几何曲线相对应。牛顿在老师巴罗的指导下，在钻研笛卡尔的解析几何的基础上，找到了新的出路。可以把任意时刻的速度看是在微小的时间范围里的速度的平均值，这就是一个微小的路程和时间间隔的比值，当这个微小的时间间隔缩小到无穷小的时候，就是这一点的准确值。这就是微分的概念。

求微分相当于求时间和路程关系得在某点的切线斜率。一个变速的运动物体在一定时间范围里走过的路程，可以看作是在微小时间间隔里所走路程的和，这就是积分的概念。求积分相当于求时间和速度关系的曲线下面的面积。牛顿从这些基本概念出发，建立了微积分。

微积分的创立是牛顿最卓越的数学成就。牛顿为解决运动问题，才创立这种和物理概念直接联系的数学理论的，牛顿称之为"流数术"。它所处理的一些具体问题，如切线问题、求积问题、瞬时速度问题以及函数的极大和极小值问题等，在牛顿前已经得到人们的研究了。但牛顿超越了前人，他站在了更高的角度，对以往分散的努力加以综合，将自古希腊以来求解无限小问题的各种技巧统一为两类普通的算法——微分和积分，并确立了这两类运算的互逆关系，从而完成了微积分发明中最关键的一步，为近代科学发展提供了最有效的工具，开辟了数学上的一个新纪元。

牛顿没有及时发表微积分的研究成果，他研究微积分可能比莱布尼茨早一些，但是莱布尼茨所采取的表达形式更加合理，而且关于微积分的着作出版时间也比牛顿早。

在牛顿和莱布尼茨之间，为争论谁是这门学科的创立者的时候，竟然引起了一场悍然大波，这种争吵在各自的学生、支持者和数学家中持续了相当长的一段时间，造成了欧洲大陆的数学家和英国数学家的长期对立。英国数学在一个时期里闭关锁国，囿于民族偏见，过于拘泥在牛顿的“流数术”中停步不前，因而数学发展整整落后了一百年。

应该说，一门科学的创立决不是某一个人的业绩，它必定是经过多少人的努力后，在积累了大量成果的基础上，最后由某个人或几个人总结完成的。微积分也是这样，是牛顿和莱布尼茨在前人的基础上各自独立的建立起来的。

1707年，牛顿的代数讲义经整理后出版，定名为《普遍算术》。他主要讨论了代数基础及其(通过解方程)在解决各类问题中的应用。书中陈述了代数基本概念与基本运算，用大量实例说明了如何将各类问题化为代数方程，同时对方程的根及其性质进行了深入探讨，引出了方程论方面的丰硕成果，如，他得出了方程的根与其判别式之间的关系，指出可以利用方程系数确定方程根之幂的和数，即“牛顿幂和公式”。

牛顿对解析几何与综合几何都有贡献。他在1736年出版的《解析几何》中引入了曲率中心，给出密切线圆(或称曲线圆)概念，提出曲率公式及计算曲线的曲率方法。并将自己的许多研究成果总结成专论《三次曲线枚举》，于1704年发表。此外，他的数学工作还涉及数值分析、概率论和初等数论等众多领域。

伟大的成就～对光学的三大贡献

在牛顿以前，墨子、培根、达·芬奇等人都研究过光学现象。反射定律是人们很早就认识的光学定律之一。近代科学兴起的时候，伽利略靠望远镜发现了“新宇宙”，震惊了世界。荷兰数学家斯涅尔首先发现了光的折射定律。笛卡尔提出了光的微粒说……

牛顿以及跟他差不多同时代的胡克、惠更斯等人，也象伽利略、笛卡尔等前辈一样，用极大的兴趣和热情对光学进行研究。1666年，牛顿在家休假期间，得到了三棱镜，他用来进行了着名的色散试验。一束太阳光通过三棱镜后，分解成几种颜色的光谱带，牛顿再用一块带狭缝的挡板把其他颜色的光挡住，只让一种颜色的光在通过第二个三棱镜，结果出来的只是同样颜色的光。这样，他就发现了白光是由各种不同颜色的光组成的，这是第一大贡献。

牛顿为了验证这个发现，设法把几种不同的单色光合成白光，并且计算出不同颜色光的折射率，精确地说明了色散现象。揭开了物质的颜色之谜，原来物质的色彩是不同颜色的光在物体上有不同的反射率和折射率造成的。公元1672年，牛顿把自己的研究成果发表在《皇家学会哲学杂志》上，这是他第一次公开发表的论文。

许多人研究光学是为了改进折射望远镜。牛顿由于发现了白光的组成，认为折射望远镜透镜的色散现象是无法消除的(后来有人用具有不同折射率的玻璃组成的透镜消除了色散现象)，就设计和制造了反射望远镜。

牛顿不但擅长数学计算，而且能够自己动手制造各种试验设备并且作精细实验。为了制造望远镜，他自己设计了研磨抛光机，实验各种研磨材料。公元1668年，他制成了第一架反射望远镜样机，这是第二大贡献。公元1671年，牛顿把经过改进得反射望远镜献给了皇家学会，牛顿名声大震，并被选为皇家学会会员。反射望远镜的发明奠定了现代大型光学天文望远镜的基础。

同时，牛顿还进行了大量的观察实验和数学计算，比如研究惠更斯发现的冰川石的异常折射现象，胡克发现的肥皂泡的色彩现象，“牛顿环”的光学现象等等。

牛顿还提出了光的“微粒说”，认为光是由微粒形成的，并且走的是最快速的直线运动路径。他的“微粒说”与后来惠更斯的“波动说”构成了关于光的两大基本理论。此外，他还制作了牛顿色盘等多种光学仪器。

伟大的成就～构筑力学大厦

牛顿是经典力学理论的集大成者。他系统的总结了伽利略、开普勒和惠更斯等人的工作，得到了着名的万有引力定律和牛顿运动三定律。

在牛顿以前，天文学是最显赫的学科。但是为什么行星一定按照一定规律围绕太阳运行？天文学家无法圆满解释这个问题。万有引力的发现说明，天上星体运动和地面上物体运动都受到同样的规律——力学规律的支配。

早在牛顿发现万有引力定律以前，已经有许多科学家严肃认真的考虑过这个问题。比如开普勒就认识到，要维持行星沿椭圆轨道运动必定有一种力在起作用，他认为这种力类似磁力，就像磁石吸铁一样。1659年，惠更斯从研究摆的运动中发现，保持物体沿圆周轨道运动需要一种向心力。胡克等人认为是引力，并且试图推到引力和距离的关系。

1664年，胡克发现彗星靠近太阳时轨道弯曲是因为太阳引力作用的结果；1673年，惠更斯推导出向心力定律；1679年，胡克和哈雷从向心力定律和开普勒第三定律，推导出维持行星运动的万有引力和距离的平方成反比。

牛顿自己回忆，1666年前后，他在老家居住的时候已经考虑过万有引力的问题。最有名的一个说法是：在假期里，牛顿常常在花园里小坐片刻。有一次，象以往屡次发生的那样，一个苹果从树上掉了下来……

一个苹果的偶然落地，却是人类思想史的一个转折点，它使那个坐在花园里的人的头脑开了窍，引起他的沉思：究竟是什么原因使一切物体都受到差不多总是朝向地心的吸引呢？牛顿思索着。终于，他发现了对人类具有划时代意义的万有引力。

牛顿高明的地方就在于他解决了胡克等人没有能够解决的数学论证问题。1679年，胡克曾经写信问牛顿，能不能根据向心力定律和引力同距离的平方成反比的定律，来证明行星沿椭圆轨道运动。牛顿没有回答这个问题。1685年，哈雷登门拜访牛顿时，牛顿已经发现了万有引力定律：两个物体之间有引力，引力和距离的平方成反比，和两个物体质量的乘积成正比。

当时已经有了地球半径、日地距离等精确的数据可以供计算使用。牛顿向哈雷证明地球的引力是使月亮围绕地球运动的向心力，也证明了在太阳引力作用下，行星运动符合开普勒运动三定律。

在哈雷的敦促下，1686年底，牛顿写成划时代的伟大着作《自然哲学的数学原理》一书。皇家学会经费不足，出不了这本书，后来靠了哈雷的资助，这部科学史上最伟大的着作之一才能够在1687年出版。

牛顿在这部书中，从力学的基本概念(质量、动量、惯性、力)和基本定律(运动三定律)出发，运用他所发明的微积分这一锐利的数学工具，不但从数学上论证了万有引力定律，而且把经典力学确立为完整而严密的体系，把天体力学和地面上的物体力学统一起来，实现了物理学史上第一次大的综合。

站在巨人的肩上

牛顿的研究领域非常广泛，他除了在数学、光学、力学等方面做出卓越贡献外，他还花费大量精力进行化学实验。他常常六个星期一直留在实验室里，不分昼夜的工作。他在化学上花费的时间并不少，却几乎没有取得什么显着的成就。为什么同样一个伟大的牛顿，在不同的领域取得的成就竟那么不一样呢？

其中一个原因就是各个学科处在不同的发展阶段。在力学和天文学方面，有伽利略、开普勒、胡克、惠更斯等人的努力，牛顿有可能用已经准备好的材料，建立起一座宏伟壮丽的力学大厦。正象他自己所说的那样“如果说我看得远，那是因为我站在巨人的肩上”。而在化学方面，因为正确的道路还没有开辟出来，牛顿没法走到可以砍伐材料的地方。

牛顿在临终前对自己的生活道路是这样总结的：“我不知道在别人看来，我是什么样的人；但在我自己看来，我不过就象是一个在海滨玩耍的小孩，为不时发现比寻常更为光滑的一块卵石或比寻常更为美丽的一片贝壳而沾沾自喜，而对于展现在我面前的浩瀚的真理的海洋，却全然没有发现。”

这当然是牛顿的谦逊。

怪异的牛顿

牛顿并不善于教学，他在讲授新近发现的微积分时，学生都接受不了。但在解决疑难问题方面的能力，他却远远超过了常人。还是学生时，牛顿就发现了一种计算无限量的方法。他用这个秘密的方法，算出了双曲面积到二百五十位数。他曾经高价买下了一个棱镜，并把它作为科学研究的工具，用它试验了白光分解为的有颜色的光。

开始，他并不愿意发表他的观察所得，他的发现都只是一种个人的消遣，为的是使自己在寂静的书斋中解闷，他独自遨游于自己所创造的超级世界里。后来，在好友哈雷的竭力劝说下，才勉强同意出版他的手稿，才有划时代巨着《自然哲学的数学原理》的问世。

作为大学教授，牛顿常常忙得不修边幅，往往领带不结，袜带不系好，马裤也不纽扣，就走进了大学餐厅。有一次，他在向一位姑娘求婚时思想又开了小差，他脑海了只剩下了无穷量的二项式定理。他抓住姑娘的手指，错误的把它当成通烟斗的通条，硬往烟斗里塞，痛得姑娘大叫，离他而去。牛顿也因此终生未娶。

牛顿从容不迫地观察日常生活中的小事，结果作出了科学史上一个个重要的发现。他马虎拖沓，曾经闹过许多的笑话。一次，他边读书，边煮鸡蛋，等他揭开锅想吃鸡蛋时，却发现锅里是一只怀表。还有一次，他请朋友吃饭，当饭菜准备好时，牛顿突然想到一个问题，便独自进了内室，朋友等了他好久还是不见他出来，于是朋友就自己动手把那份鸡全吃了，鸡骨头留在盘子，不告而别了。等牛顿想起，出来后，发现了盘子里的骨头，以为自己已经吃过了，便转身又进了内室，继续研究他的问题。

牛顿晚年

但是由于受时代的限制，牛顿基本上是一个形而上学的机械唯物主义者。他认为运动只是机械力学的运动，是空间位置的变化；宇宙和太阳一样是没有发展变化的；靠了万有引力的作用，恒星永远在一个固定不变的位置上……

随着科学声誉的提高，牛顿的政治地位也得到了提升。1689年，他被当选为国会中的大学代表。作为国会议员，牛顿逐渐开始疏远给他带来巨大成就的科学。他不时表示出对以他为代表的领域的厌恶。同时，他的大量的时间花费在了和同时代的着名科学家如胡克、莱布尼兹等进行科学优先权的争论上。

晚年的牛顿在伦敦过着堂皇的生活，1705年他被安妮女王封为贵族。此时的牛顿非常富有，被普遍认为是生存着的最伟大的科学家。他担任英国皇家学会会长，在他任职的二十四年时间里，他以铁拳统治着学会。没有他的同意，任何人都不能被选举。

晚年的牛顿开始致力于对神学的研究，他否定哲学的指导作用，虔诚地相信上帝，埋头于写以神学为题材的着作。当他遇到难以解释的天体运动时，竟提出了“神的第一推动力”的谬论。他说“上帝统治万物，我们是他的仆人而敬畏他、崇拜他”。

1727年3月20日，伟大艾萨克·牛顿逝世。

⑹ DDA算法的介绍

DDA算法，是计算机图形学中一种基于直线的微分方程来生成直线的方法，由于有浮点数运算与取整，该算法不利于硬件实现1。

⑺ 哪位仁兄帮帮忙

画圆的算法

http://www.qcode.org/article/qcode/code5/cj/cj8/200511/12993.html

http://www.21codes.com/Soft/pro/VCCYY/255/2005/10/Soft_24456.html

画直线的算法

能和API中的LineTo一样就行
---------------------------------------------------------------

//TheDDAalgorithm
#defineROUND(a)((int)a+0.5)
voidlineDDA(intxa,intya,intxb,intyb,HDCdc)
{
intdx=xb-xa,dy=yb-ya;
intsteps,k;
floatxincrement,yincrement,x=xa,y=ya;
if(abs(dx)>abs(dy))
steps=abs(dx);
else
steps=abs(dy);
xincrement=dx/(float)steps;
yincrement=dy/(float)steps;
SetPixel(dc,ROUND(x),ROUND(y),RGB(255,0,0));
for(k=0;k{
x+=xincrement;
y+=yincrement;
SetPixel(dc,ROUND(x),ROUND(y),RGB(255,0,0));
}
}
//theBresenhamalgorithm
voidlineBres(intxa,intya,intxb,intyb,HDCdc)
{
intdx=abs(xa-xb);
intdy=abs(ya-yb);
intp=2*dy-dx;
inttwody=2*dy;
inttwodydx=2*(dy-dx);
intx,y,xend;
if(xa>xb)
{
x=xb;y=yb;
xend=xa;

}
else
{
x=xa;y=ya;
xend=xb;
}
SetPixel(dc,(x),(y),RGB(255,0,0));
while(x{
x++;
if(p<0)
p+=twody;
else
{
y++;
p+=twodydx;
}
SetPixel(dc,(x),(y),RGB(255,0,0));
}

}

⑻ 如何简单理解DDA算法

DDA称为数值微分画线算法。
是直线生成算法中最简单的一种.原理相当简单,就是最直观的根据斜率的偏移程度,决定是以x为步进方向还是以y为步进方向.然后在相应的步进方向上,步进变量每次增加一个像素,而另一个相关坐标变量则为Yk_1=Yk+m（以x为步进变量为例,m为斜率）。

⑼ 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次；

⑽ 画圆的常见算法

画圆的基本算法有逐点比较和DDA积分法，
代码示例 WinC下运行

#include "Conio.h"
#include "graphics.h"
#include "process.h"
#define Ni_circle 0
#define Shun_circle 1
#define closegr closegraph

void initgr();
void draw_Base_circle();
void draw_cabu_circle();
void close_graph();
void acrroods();
static float x0,y0;

void initgr(void) /* BGI初始化 */
{
int gd = DETECT, gm = 0; /* 和gd = VGA,gm = VGAHI是同样效果 */
registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */
initgraph(&gd, &gm, "");
}

void acrroods() /*屏幕中心坐标 */
{
x0=getmaxx()/2;
y0=getmaxy()/2;
}

void draw_Base_circle() /*画圆及写参数*/
{
line(x0-200,y0,x0+200,y0); outtextxy(x0+220,y0,"Z");
line(x0,y0-180,x0,y0+180); outtextxy(x0+10,y0+180,"X");
outtextxy(x0-10,y0+10,"O");
circle(x0,y0,150);
textcolor(YELLOW);
directvideo=0;
gotoxy(46,2);cprintf("Circle start:X0 Y0 Z150");
gotoxy(46,3);cprintf("Circle end :X0 Y0 Z150");
gotoxy(46,4);cprintf("Units :Pixel");
gotoxy(46,5);cprintf("Circle now:");
}

void close_graph() /*关图形系统*/
{
closegraph();
}

void draw_cabu_circle(int sstep,int Directory)/*关键的圆插补函数*/
{
int flag=0;
float Fm,Xm,Ym;
Xm=x0+150; Ym=y0;
moveto(Xm,Ym);
setcolor(RED);
while(1) /*分象限，顺圆和逆圆讨论*/
{
Fm=(Xm-x0)/(Xm-x0)+(Ym-y0)/(Ym-y0)-150/150;/*圆判断公式*/
if(Fm>=0){
if(!Directory){ /*逆圆判断*/
if(Xm>=x0&&Ym<=y0)
{
if(flag) break; /*if语句判断象限，以下一样*/
else Xm=Xm-sstep;
}
if(Xm<=x0&&Ym<=y0)
{
flag=1; Ym=Ym+sstep;
}
if(Xm<=x0&&Ym>=y0)
Xm=Xm+sstep;
if(Xm>=x0&&Ym>=y0)
Ym=Ym-sstep;
}
else { /*it is Directory's else*/
if(Xm>x0&&Ym<y0)
Ym=Ym+sstep;
if(Xm<=x0&&Ym<=y0)
Xm=Xm+sstep;
if(Xm<x0&&Ym>y0) {
flag=1; Ym=Ym-sstep;}
if(Xm>=x0&&Ym>=y0) {
if(flag) break;
Xm=Xm-sstep;}
}
}
else{ /*it is Fm's else*/
if(!Directory) {
if(Xm>x0&&Ym<y0)
{
if(flag) break;
else Ym=Ym-sstep;
}
if(Xm<=x0&&Ym<=y0)
{
flag=1; Xm=Xm-sstep;
}
if(Xm<=x0&&Ym>=y0)
Ym=Ym+sstep;
if(Xm>=x0&&Ym>=y0)
Xm=Xm+sstep;
}
else{
if(Xm>x0&&Ym<y0)
Xm=Xm+sstep;
if(Xm<=x0&&Ym<=y0)
Ym=Ym-sstep;
if(Xm<=x0&&Ym>=y0){
flag=1; Xm=Xm-sstep;}
if(Xm>=x0&&Ym>=y0) {
if(flag) break;
else Ym=Ym+sstep;}
}
}
lineto(Xm,Ym);
gotoxy(58,5); printf("X%3.0f Y0 Z%3.0f ",Ym-y0,Xm-x0);
delay(800);
}
}

void circle_demo(int Directory) /*控制圆插补两次*/
{
int i=0,sstep;
initgr(); /* BGI初始化 */
sleep(2);
acrroods(&x0,&y0);
for(i=0;i<2;i++)
{
draw_Base_circle(150);
if(i==0){
sstep=6;
draw_cabu_circle(sstep,Directory);}
else{
sstep=1;
draw_cabu_circle(sstep,Directory);}
getch();
cleardevice();
setcolor(WHITE);
}
}

/* 圆插补部分的函数区结束*/

int main(void)
{
int choice=0;
initgr(); /* BGI初始化 */

while(choice!=4)
{
setfillstyle(1,RED);
bar(200,30,400,80);
setcolor(GREEN);
settextstyle(3,0,10);
outtextxy(220,50,"DEMO PROGRAM BY P.Y.F");
setcolor(WHITE);
settextstyle(0,0,1);
outtextxy(200,140,"2. Shun_Circle demo.");
outtextxy(200,160,"3. Ni_Circle demo.");
outtextxy(200,180,"4. Quit the program.");
outtextxy(160,200,"Please enter your choice:"); gotoxy(46,13);
scanf("%d",&choice);

switch(choice)
{
case 2: circle_demo(Ni_circle);break;
case 3: circle_demo(Shun_circle);break;
case 4: break;
default: printf("\nChoice wrong,try again!");
}
}

getch(); /* 暂停一下，看看前面绘图代码的运行结果 */
closegr(); /* 恢复TEXT屏幕模式 */
return 0;
}

具体看看《计算机图形学》。