0≤m≤1且x121、输入线段的两个端点坐标和画线颜色：
x1，y1，x2，y2，color；2、设置象素坐标初值：
x=x1，y=y1；3、设置初始误差判别值：
p=2y-x；·ΔΔ4、分别计算：
x=x2-x1、y=y2-y1；ΔΔ5、循环实现直线的生成：
for（x=x1；x<=x2；x++）{putpixel（x,y,color）；if（p>=0）{y=y+1；p=p+2（y-x）；·ΔΔ}else{p=p+2y；·Δ}}五、直线Bresenham算法完善：
现在我们修正（2-16）公式，以适应对任何方向及任何斜率线段的绘制。
如下图所示，线段的方向可分为八种，从原点出发射向八个区。
由线段按图中所示的区域位置可决定x和yi+1i+1的变换规律。
容易证明：
当线段处于①、④、⑧、⑤区时，以|x|和|y|代替前面公式中的x和y，△△△△当线段处于②、③、⑥、⑦区时，将公式中的|x|和|y|对换，则上述两公式仍有效。
△△
在线段起点区分线段方向七、直线Bresenham算法特点：
由于程序中不含实型数运算，因此速度快、效率高，是一种有效的画线算法。
2.2.2中点算法生成圆中点画圆算法在一个方向上取单位间隔，在另一个方向的取值由两种可能取值的中点离圆的远近而定。
实际处理中，用决策变量的符号来确定象素点的选择，因此算法效率较高。
一、中点画圆算法描述设要显示圆的圆心在原点（0，0），半径为R，起点在（0，R）处，终点在（，）处，顺时针生成八分之一圆，利用对称性扫描转换全部圆。
为了应用中点画圆法，我们定义一个圆函数222+y-R（2－19）F（x，y）=x任何点（x，y）的相对位置可由圆函数的符号来检测：
<0点（x，y）位于数学圆内（2－20）=0点（x，y）位于数学圆上F（x，y）>0点（x，y）位于数学圆外（x），如果顺时针生成圆，如下图所示，图中有两条圆弧A和B，假定当前取点为P，yiii+1，y）或右下方的点SE（x+1，y-1）两者之一。
那么下一点只能取正右方的点E（xiiii
中点画线算法假设M是E和SE的中点，即，则：
1、当F（M）<0时，M在圆内（圆弧A），这说明点E距离圆更近，应取点E作为下一象素点；2、当F（M）>0时，M在圆外（圆弧B），表明SE点离圆更近，应取SE点；3、当F（M）=0时，在E点与SE点之中随便取一个即可，我们约定取SE点。
二、中点画圆算法思想因此，我们用中点M的圆函数作为决策变量d，同时用增量法来迭代计算下一个中点Mi的决策变量d。
i+1（2－21）下面分两种情况来讨论在迭代计算中决策变量d的推导。
i+1<0，则选择E点，接着下一个中点就是，这时1、见图（a），若di新的决策变量为：
（2－22）
<0）中点画线算法（a）（di式（2－22）减去（2－21）得：
（2－23）d=d+2x+3i+1ii≥0，则选择SE点，接着下一个中点就是，这2、见图（b），若di时新的决策变量为：
（2－24）≥0）中点画线算法（b）（di式（2－24）减去（2－21）得：
（2－25）d=d+2（x-y+5i+1iii）我们利用递推迭代计算这八分之一圆弧上的每个点，每次迭代需要两步处理：
（1）用前一次迭代算出的决策变量的符号来决定本次选择的点。
（2）对本次选择的点，重新递推计算得出新的决策变量的值。
剩下的问题是计算初始决策变量d，如下图所示。
对于初始点（0，R），顺时针生成八分0之一圆，下一个中点M的坐标是，所以：
（2－26
生成圆的初始条件和圆的生成方向三、中点画圆算法实现）；1、输入：
圆半径r、圆心（x，y002、确定初值：
x=0，y=r、d=5/4-r；3、While（x<=y）{·利用八分对称性，用规定的颜色color画八个象素点（x，y）；·若d≥0{y=y-1；d=d+2（x-y）+5）；}否则d=d+2x+3；·x=x+1；}五、中点画圆算法完善在上述算法中，使用了浮点数来表示决策变量d。
为了简化算法，摆脱浮点数，在算法中全部使用整数，我们使用e=d-1/4代替d。
显然，初值d=5/4-r对应于e=1-r。
决策变量d<0对应于e<-1/4。
算法中其它与d有关的式子可把d直接换成e。
又由于e的初值为整数，且在运算过程中的迭代值也是整数，故e始终是整数，所以e<-1/4等价于e<0。
因此，可以写出完全用整数实现的中点画圆算法。
要求：
写出用整数实现的中点画圆算法程序，并上机调试，观看运行结果。
六、中点画圆算法程序voidMidpointCircle（intx0,inty0,intr,intcolor）
{intx,y;floatd;x=0;y=r;d=5.0/4-r;while（x<=y）{putdot（x0,y0,x,y,color）;if（d<0）d+=x*2.0+3;else{d+=2.0*（x-y）+5;y--;}x++;}}putdot（x0,y0,x,y,color）{putpixel（x0+x,y0+y,color）;putpixel（x0+x,y0-y,color）;putpixel（x0-x,y0+y,color）;putpixel（x0-x,y0-y,color）;putpixel（x0+y,y0+x,color）;putpixel（x0+y,y0-x,color）;putpixel（x0-y,y0+x,color）;putpixel（x0-y,y0-x,color）;}2.2.3正负算法生成圆正负法是利用平面曲线将平面划分成正负区域，对当前点产生的圆函数进行符号判别，利用负反馈调整以决定下一个点的产生来直接生成圆弧。
一、正负画圆算法描述设要显示圆的圆心在原点（0，0），半径为R，初始点的坐标为（0，R），顺时针生成八分222+y-R之一圆，令：
F（x，y）=x
则圆的方程为：
F（x，y）=0（2-27）当点（x，y）在圆内时，则F（x，y）<0；当点（x，y）在圆外时，则F（x，y）>0；当点（x，y）在圆上时，则F（x，y）=0；二、正负画圆算法思想现以下图的AB弧为例，来说明正负画圆法（顺时针生成圆）。
（x），取下一个点P（x）的原则是：
假设当前点为P，y，yiiii+1i+1i+1）≤0时：
取x=x+1，y=y1、当F（x，y。
即向右走一步，从圆内走向圆外。
对应iii+1ii+1i图（a）中的从P到P。
ii+1）>0时：
取x=x=y-1。
即向下走一步，从圆外走向圆内。
对应图2、当F（x，y，yiii+1ii+1i（b）中的从P到P。
ii+1）的正负，因此称为正负法。
由于向圆内或向圆外走取决于F（x，yii）的递推公式：
下面分两种情况求出F（x，yii）≤0时，向右走，取x=x+1，y=y
（1）当F（x，y，则iii+1ii+1i）=F（x+1，y）F（x，yi+1i+1ii222=（x+1）+y-Rii（2-28）222=（x+y-R）+2x+1iii=F（x）+2x+1，yiii）>0时，向下走，取x=x=y-1，则
（2）当F（x，y，yiii+1ii+1i）=F（x-1）F（x，y，yi+1i+1ii222=x+（y-1）-Rii（2-9）222=（x+y-R）-2y+1iii=F（x）-2y+1，yiii初始时，x=0，y=R，故
222+R）-R=0（2-30）F（0，R）=（0公式（2-28）、（2-29）和（2-30）就构成正负画圆算法的核心。
给象素坐标（x，y）及F赋初始值后，进入循环画点；画点后，根据F的符号进行F值的递推和下一个点的获取，直到x>y为止。
同前面介绍的一样，利用圆的八分对称性，循环一次，画八个点。
三、正负画圆算法实现注意：
初值不同、圆的生成方向不同时，当前点和下一个点的获取原则是不同的，见下图。
例如，初始点（R，0），逆时针生成圆，从图（b）可知：
（x+1），即向上走一步；若当前点P在圆内，则下一点P，yii+1ii（x-1，y），即向左走一步；若当前点P在圆外，则下一点Pii+1ii（a）顺时针生成圆（b）逆时针生成圆五、正负画圆算法特点物理意义清楚，程序中只含整数运算，因此算法速度快。
六、正负画圆算法程序//顺时针生成圆voidPNARC（intx0,inty0,intr,intcolor）{intx=0,y=r,f=0;while（x<=y）{putdot（x0,y0,x,y,color）;if（f<=0）
{f=f+2*x+1;x++;}else{f=f-2*y+1;y--;}}}2.3区域填充前面介绍的直线和圆都属于线划图，然而，光栅显示的一个重要特点是能进行面着色，区域填充就是在一个闭合区域内填充某种颜色或图案。
区域填充一般分两类：
多边形填充和种子填充。
一、多边形填充1、填充条件多边形的顶点序列（P，i=0，1，…，n）、填充色。
i2、多边形内点的判别准则对多边形进行填充，关键是找出多边形内的象素。
在顺序给定多边形顶点坐标的情况下，如何判明一个象素点是处于多边形的内部还是外部呢？
从测试点引出一条伸向无穷远处的射线（假设是水平向右的射线），因为多边形是闭合的，那么：
若射线与多边形边界的交点个数为奇数时，则该点为内点（例：
图中测试点4引出的射线）；反之，交点个数为偶数时，则该点为外点。
（例：
测试点2引出的射线）。
多边形内点的判别准则和奇异点3、奇异点的处理：
上述的判别准则，在大多数情况下是正确的，但当水平扫描线正好通过多边形顶点时，要特别注意。
例如，图中过顶点的射线1、射线6，它们与多边形的交点个数为奇数，按照判别准则它们应该是内点，但实际上却是外点。
而图中过顶点的射线3、射线5，对于判别准则的使用又是正确的。
多边形内点的判别准则和奇异点综合以上情况，我们将多边形的顶点分为两大类：
（1）局部极值点：
如图中的点P、P、P和P。
对于这些点来说，进入该点的边线和离开1246该点的边线位于过该点扫描线的同一侧。
（2）非极值点：
如图中的点P、P。
对于这些点来说，进入该点的边线和离开该点的边线35位于过该点扫描线的两侧。
处理奇异点规则：
（1）对于局部极值点，应看成两个点；
（2）对于非极值点，应看成一个点。
4、逐点判别算法步骤：
（x）中求极值，x
（1）求出多边形的最小包围盒：
从P，y、y、x、y。
iiiminminmaxmax
（2）对包围盒中的每个象素引水平射线进行测试。
（3）求出该射线与多边形每条边的有效交点个数。
（4）如果个数为奇数：
该点置为填充色。
（5）否则：
该点置为背景色。
逐点判别算法虽然简单，但不可取，原因是速度慢。
它割断了各象素之间的联系，孤立地考虑问题，由于要对每个象素进行多次求交运算，求交时要做大量的乘除运算，从而影响了填
充速度。
二、种子填充种子填充是将区域内的一点（种子）赋予给定的颜色，然后将这种颜色扩展到整个区域内的过程。
1、填充条件区域内一点的坐标即种子坐标、边界色、填充色。
2、连通方式区域是互相连通着的象素的集合，连通方式可分为四连通和八连通。
四连通：
从区域内一点出发，可通过四个方向：
上、下、左、右到达该区域内部的任意象素。
八连通：
区域内部从一个象素到达另一个象素的移动路径，除了上、下、左、右四个方向外，还允许沿着对角线方向。
注意：
（1）八连通区域中，既然区域内的两个象素可以通过对角线相通，那么，区域边界上的象素则不能通过对角线相连，否则填充就会溢出到区域外，因此，八连通区域的边界线必须是四连通的，见下图（a）；
（2）而四连通区域，其边界象素是四连通和八连通的都可以，见下图（b）。
（a）八连通区域四连通边界（b）四连通区域八连通（或四连通）边界3、内点（x,y）的检测条件
（1）if（getpixel（x,y）!
=边界色&&getpixel（x,y）!
=填充色）
（2）if（getpixel（x,y）!
=背景色）这两个条件任何一个都可以用来检测象素点（x,y）是不是尚未填充。
推荐使用条件
（1）进行象素点检测。
2.3.1边相关扫描线多边形填充算法2.3.2扫描线种子填充算法2.3.3边标志填充算法2.3.4图案填充2.3.1边相关扫描线多边形填充算法边相关扫描线填充算法属于多边形填充类。
它比逐点判别算法速度提高很多，是一种较经典的多边形填充算法。
该算法利用了扫描线的相关性和多边形边的相关性，而不是逐点进行处理。
一、边相关扫描线填充算法描述扫描线的相关性：
某条扫描线上相邻的象素，几乎都具有同样的内外性质，这种性质只有遇到多边形边线与该扫描线的交点时才会发生改变。
见下图（a）。
边的相关性：
由于相邻扫描线上的交点是与多边形的边线相关的。
对同一条边，前一条=y+1与该边的交点则为x=x+1/m，利扫描线y与该边的交点为x，而后一条扫描线yiii+1ii+1i用这种相关性可以省去大量的求交运算。
见下图（b）所示。
（a）扫描线的相关性（b）边的相关性边相关扫描线填充算法的实现需要建立两个表：
边表（ET）和活动边表（AET）。
1、边表（ET：
EdgeTable）
用来对除水平边外的所有边进行登记，来建立边的记录。
边的记录定义为：
扫描线y对应的ET表=y-1。
第一项：
某边的最大y值（y）。
注意要进行奇异点处理：
对于非极值点应该ymaxmaxmax第二项：
某边的最小的y对应的x值。
第三项：
某边斜率的倒数:
1/m。
第四项：
指针。
用来指向同一条扫描线相交的其它边，如果其它边不存在，则该项置空。
2、活动边表（AET：
ActiveEdgeTable）ET表建立以后，就可以开始扫描转换了。
对不同的扫描线，与之相交的边线也是不同的，当对某一条扫描线进行扫描转换时，我们只需要考虑与它相交的那些边线，为此需要建立一个只与当前扫描线相交的边记录链表，称之为活动边表。
二、边相关扫描线填充算法思想1、根据给出的多边形顶点坐标，建立ET表；求出顶点坐标中最大y值y和最小y值y。
maxmin2、初始化AET表指针，使它为空。
3、使用扫描线的y值作为循环变量，使其初值为y。
jmin对于循环变量y的每一整数值，重复作以下事情，直到y大于y，或ET表与AETjjmax表都为空为止：
（1）如果ET表中y桶非空，则将y桶中的全部记录合并到AET表中。
jj
（2）对AET表链中的记录按x的大小从小到大排序。
（3）依次取出AET表各记录中的x坐标值，两两配对填充，即将每对x之间的象素ii填上所要求的颜色。
=y（4）如果AET表中某记录的y，则删除该记录。
maxj+1/m代替x（5）对于仍留在AET表中的每个记录，用x进行修改，这就是该记录ii+1的交点。
的边线与下一条扫描线yj
（6）使y加1，以便进入下一轮循环。
j三、边相关扫描线填充算法举例对下图（a）的多边形利用边相关扫描线填充算法进行处理：
1、首先建立ET表。
注意：
在做奇异点处理时，当该边最大y值对应的顶点为非极值点时，边记录的第一项：
y=y-1。
例如：
PPPP边、P边、P边，见下图（b）。
maxmax3432452、接着建立AET表。
AET表的建立过程就是有效地进行填充的操作，在这个期间不断地做以下工作：
（1）合并ET表
升级会员 