版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
第3章基本光栅图形算法本章内容3.1用Java语言绘图13.2直线的扫描转换23.3圆的扫描转换33.4多边形的扫描转换43.5区域填充53.6字符的生成63.7光栅图形的反走样算法73.1用Java语言绘图3.1.1用Java小程序绘图关键方法init()
——由浏览器或applet浏览器来调用，通知小程序即将被装入系统，即初始化。绘图函数
——paint(Graphics)：绘制构件，当调整小程序浏览窗口大小，缩放浏览窗口，移动窗口或重载等需要重绘窗口时都会调用该方法。 ——update()：刷新屏幕，并调用paint()方法。 ——repaint()：调用update()方法。简单的绘图操作
Graphics.drawLine(int
startX,int
startY,int
endX,int
endY)：画一条起点为(startX,startY)，终点为(endX,endY)的直线段。
Graphics.clearRect(int
x,int
y,int
width,intheight)：将左上角为(x,y)，宽为width，高为height的区域用背景色填充。
Graphics.setColor(Color)：设置当前的绘图颜色
Graphics.getColor()：返回当前的绘图颜色
setBackground(Color)和setForeground(Color)：设置诸如面板和框架等组件的背景色
getBackground（）和getForeground（）：获得当前组件的颜色3.1.1用Java小程序绘图创建Color对象的构造函数
——Color（int，int，int） 使用三个表示所需颜色的RGB值的整数值。 ——Color（float，float，float） 使用三个表示所需颜色的RGB值的浮点数值。3.1.1用Java小程序绘图black(0,0,0)gray(128,128,128)red(255,0,0)blue(0,0,255)green(0,255,0)white(255,255,255)cyan(0,255,255)lightGray(255,200,0)yellow(255,255,0)darkGray(64,64,64)magenta(255,0,255)Color类中的标准颜色表importjava.awt.*;//引入图形软件包awtimportjava.applet.Applet;//使用java.applet.Applet类publicclasslineextendsApplet{int
startX,startY,endX,endY;Colorcolor;publicvoidinit()//初始化
{ startX=50;//设置直线的起点和终点位置
startY=50;
endX=100;
endY=150; color=Color.blue;//初始化颜色为蓝色
} 3.1.1用Java小程序绘图例：画一条起点为（50，50），终点为（150，150）的直线。publicvoidpaint(Graphicsg){g.setColor(color);//设置颜色
drawLine(g,startX,startY,endX,endY);//调用绘制直线的函数
}voiddrawLine(Graphics
g,intx1,inty1,intx2,inty2)//绘制直线的函数
{ g.drawLine(x1,y1,x2,y2);//画一条起点为（x1,y1）终点为（x2,y2）的直线
}}3.1.1用Java小程序绘图将以上代码保存为名为line.java的文件，该文件编译生成名为line.class的类文件。该类文件必须嵌入到Web页中才可运行。通过下面的代码将line.class的类文件放到Web页中：<HTML><appletcode="line.class"width=500height=400></applet></HTML>将代码保存为名为line的html文件。该文件可用Java自带的appletviewer浏览器运行，也可直接在浏览器中运行line.htm。3.1.1用Java小程序绘图3.1.2用Java应用程序绘图应用程序（application）能独立运行,由一个或多个类构成。其中包含main（）函数的类为程序的入口类。Java应用程序中，可把图形绘制在面板中，然后将该面板加入到窗口程序中显示图形。面板是继承JPanel类而来，其中与绘图相关的是paintComponent(Graphics)函数。可通过覆盖面板的paintComponent()函数，将所有的图形操作代码放在该函数中实现图形的绘制。窗口是继承JFrame类而来，其中的show（）函数使整个窗口可见。3.1.2用Java应用程序绘图例：画一条起点为（50，50），终点为（150，150）的直线。importjavax.swing.*;//引入swing包importjava.awt.*;//引入图形软件包awtclassSetPixelextendsJPanel{Colorcolor;
int
startX,startY,endX,endY;publicSetPixel()//构造函数（初始化）
{color=Color.blue;//蓝色
startX=50;//设置直线的起点和终点位置
startY=50;先用下面的SetPixel类将生成一个面板，并在上面画一条起点为（50，50），终点为（150，150）的直线，直线的颜色为蓝色。
endX=150;
endY=150;} publicvoidpaintComponent(Graphicsg){ g.setColor(color);//设置颜色
drawLine(g,startX,startY,endX,endY);//调用绘制直线的函数
}voiddrawLine(Graphics
g,intx1,inty1,intx2,inty2)//绘制直线的函数
{g.drawLine(x1,y1,x2,y2);//画一条起点为(x1,y1)终点为(x2,y2)的直线
}}3.1.2用Java应用程序绘图3.1.2用Java应用程序绘图publicclassPixelWindowextendsJFrame{publicPixelWindow(){super("PixelColor"); //设置窗口标题
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
//设置窗口关闭模式
setBounds(newRectangle(100,100,300,300));
//设置窗口在屏幕上的显示位置和大小
SetPixelset=newSetPixel();//生成SetPixel类对象（一个面板对象）
add(set);//将面板加入到窗口中
} publicstaticvoidmain(String[]args){PixelWindow
setPixel=newPixelWindow();//生成PixelWindow对象
setPixel.show();//设置JFrame窗口可见
}}再用PixelWindow类生成运行窗口显示SetPixel类对象，主函数在此类中。3.2直线的扫描转换对直线进行光栅化时，只能在显示器所给定的有限个像素组成的点阵中，选择能最好地逼近于该直线的一组像素，并对这些像素进行写操作。这就是通常所说的用显示器绘制直线，即直线的扫描转换。直线扫描转换的主要工作：快速找出像素点阵中距直线最近的网格点，用这些网格点对应的像素表示该直线。数学上的理想直线没有宽度，是由无数个点构成的集合。3.2直线的扫描转换像素和坐标的对应关系(a)(b)3.2.1基本增量算法基本思想设直线满足，由于直线的斜率小于等于1，所以，该直线的扫描转换可从最左端开始，每次递增一个单位，对每个，相应的有，则所以，每增加一个单位，只需加上一个，这样就去掉了乘法运算，提高了算法效率。在该算法中，直线上的所有点的和值可由前一点的值加一个基本增量得到，所以该算法称为基本增量算法。3.2.1基本增量算法注：上述讨论只适合的情况，当时，只需将和的角色互换，即每次增加一个单位，每次增加。基本增量算法也叫数字微分分析器算法（DigitalDifferentialAnalyzer，DDA）。DDA是用数值方法求解微分方程的一种设备，即根据和的一阶导数，在和方向上渐进地以小步长移动，由此产生连续的像素坐标。3.2.1基本增量算法参数直线段的情况
设起点和终点坐标分别为（，）和（，），令， ,则直线的参数方程是–
令，将参数区间[0，1]分为等份，即每次的增量为。3.2.1基本增量算法第步时于是有(3.1)(3.2)公式（3.2）是一个迭代公式，第步的坐标是由第步的结果加上一个增量得到。该算法在或变化比较大的方向增量为,而另一方向上的增量的绝对值小于等于1。3.2.1基本增量算法下图中，用公式（3.2）求得的直线上的点用空心圆表示，但显示时要用像素来表示，即采用舍入的办法得到最靠近空心圆点的像素，用这些像素（下图中的实心圆点）来表示直线。图中实心圆点表示用DDA方法生成的直线3.2.1基本增量算法DDA算法的程序实现voiddda(Graphicsg,intx1,intx2,inty1,inty2){intk;floatx,y,dx,dy;k=Math.abs(x2-x1);if(Math.abs(y2-y1)>k)k=Math.abs(y2-y1);
dx=(float)(x2-x1)/k;
dy=(float)(y2-y1)/k;x=(float)x1;y=(float)y1;for(inti=0;i<k;i++){g.drawLine((int)(x+.5f),(int)(y+.5f),(int)(x+.5f),(int)(y+.5f)); x=x+dx; y=y+dy;}}3.2.1基本增量算法实例设给定直线的起点坐标为(0，0)，终点坐标为(9，6)，则上述DDA算法画出的直线如下图所示。DDA方法所画直线图DDA算法缺点：需要进行浮点数运算，产生一个像素要做两次加法和两次取整运算，运行效率低且取整运算不利于硬件实现。3.2.2Bresenham算法基本思想设直线的起点坐标为，斜率为。下面就的情况来说明该算法。取为像素所在点的横坐标（整数），令，直线上相邻两点的坐标满足关系(3.3)一般来说，不一定是整数，所以也不一定是整数，因此要用靠近该点最近的网格点来近似。由于取整计算量较大，为了提高效率，Bresenham算法用下面的方法来避免使用取整运算。3.2.2Bresenham算法设图3.4中已得到第个显示的点，B点是直线与第列网格线的交点，则第个显示的点只能从C或D点中去选。设A为CD边的中点，令误差项(3.4)当B在A的下面时，，此时应取C点作为；当B在A的上面时，，则应取D点作为。BACD图3.4的几何意义3.2.2Bresenham算法通过递推的方式，高效地计算点序列和，由图3.4可得
(3.5)由式（3.3）～（3.5）可得=(3.6)注：3.2.2Bresenham算法式（3.5）和（3.6）是根据图3.4所示的情况推出的，容易验证，式（3.5）和（3.6）对图3.5所示的两种情况也成立。CBADBACD图3.5的几何意义的其他两种情况3.2.2Bresenham算法算法的程序实现由式（3.3）和（3.4）可得假设直线段起始点的坐标分量和均为整数，则有m=(double)dy/(double)dx；e=m–0.5；for(i=0;i<dx;i++){
g.drawLine(x,y,x,y);
if(e>=0){y=y+1；e=e–1;}x=x+1；e=e+m;}该算法在计算直线斜率和误差项时用到了小数与除法，可改用整数来避免除法，以提高算法的效率和减少算法的复杂性。由于算法中只用到误差项的符号，因此可进行如下替换：。改进后的算法程序3.2.2Bresenham算法voidbresenham(Graphicsg,int
xs,int
ys,int
xe,intye) {int
dx=xe-xs;
int
dy=ye-ys;
inte=2*dy-dx;
intx=xs;
inty=ys;
for(inti=0;i<dx;i++){
g.drawLine(x,y,x,y);//画点（x,y）
if(e>=0){y=y+1;e=e-2*dx;}x=x+1;e=e+2*dy;} }3.3圆的扫描转换3.3.1正负法基本思想设圆的半径为R，则圆的方程为对于圆上的点，；对于圆内的点，；对于圆外的点，。以顺时针绘制左图中第一象限内四分之一圆弧AB为例说明该方法。假定圆心和起点均精确地落在像素上。设起点A为，则有。(0,0)ABPiPi+1Pi-1弧AB上点的取法3.3.1正负法确定当前点后，可通过的值来决定下一个点：若，说明点在圆内，则下一步应向圆外走，即取若，说明点在圆外，则下一步应向圆内走，即取若，说明点在圆上，则下一步可以向圆内走，也可以向圆外走，这里规定取。这样用于表示圆弧的点均在理想圆弧附近且时正时负，因此称为正负法。由于这种方法每走完一步，都要比较当前位置的函数值，以决定下一步的走向，因而也称为逐点比较法。3.3.1正负法的递推公式。由上可知。如果的值已算出，计算时可分为两种情况：当时，(3.9)当时，(3.10)由式（3.9）和式(3.10)知，3.3.1正负法算法的程序实现voidpnarc(Graphics
g,intradius){int
x,y,f;x=0;y=0+radius;f=0;while(y>0){
g.drawLine(x,y,x,y); if(f>0){ f=f-2*y+1; y--; }else{ f=f+2*x+1;x++; }}
if(y==0)g.drawLine(x,y,x,y);}3.3.2Bresenham算法xy45°AB(-x,-y)(-y,-x)(-x,y)(x,y)(x,-y)(-y,x)(y,x)(y,-x)图3.87个对称点图3.9Pi-1的两个侯选点xHiLiPi-1yD(Hi)>0D(Li)<0AB仅讨论图3.8中弧AB的画法，而要显示一个整圆，只需在显示AB上任一点的同时显示圆上该点的其它七个对称点即可。从A点开始向右下方逐点寻找显示弧AB要用的点，若图3.9中的点是已选中的一个表示圆弧上的点，则下一个点应为 或，选还是选取决于哪一个点更接近于弧AB。3.3.2Bresenham算法设R为弧AB的半径，记点P到原点的距离的平方与圆的半径的平方之差为D(P)，即
假定为圆弧上的点，则，。令当时，，比距圆弧近，应取来显示弧AB
；当时，，应取来显示弧AB
；当时，可在两者中任取一点，这里规定取。Bresenham算法在候选的两个像素中，总是选离圆弧最近的像素为圆弧的一个近似点，因此，它比正负法决定的像素更合理。3.3.2Bresenham算法设点坐标为，则和点的坐标分别为和,和的坐标分别为和。已知，，，。则(3.12)(3.13)(3.14)的递推公式3.3.2Bresenham算法当时，点被选中，这时，由式（3.13）和（3.14）可得当时，点被选中，这时，由式（3.13）和（3.14）可得(3.15)(3.16)式（3.12），（3.15）和（3.16）组成计算的递推公式。3.3.2Bresenham算法算法的程序实现voidbresenham_arc(Graphics
g,intradius){int
x,y,d;x=0;y=radius;d=3-2*radius;while(x<y){
g.drawLine(x,y,x,y);
if(d<0)d=d+4*x+6; else{d=d+4*(x-y)+10;y--;}x++;}
if(x==y)g.drawLine(x,y,x,y);}3.3.3圆的多边形迫近法基本思想按一定方式计算给定圆弧轨迹上的一系列顶点，然后用连接相邻点的一系列直线段来逼近圆弧。用正多边形迫近圆弧法设圆弧所在圆的半径为R，圆弧的起始角和终止角分别为和，把圆弧分割成份，则相邻两个顶点之间的夹角为。设顶点序列的第个点为，为该点的幅角。则下一个顶点的坐标为或表示为矩阵形式3.3.3圆的多边形迫近法椭圆弧的生成设椭圆的中心在原点，长短轴分别为a和b，且平行于坐标柚，则该椭圆的参数方程为，设顶点序列的第i个顶点为,则下一个顶点的坐标应满足
,
由此可得其中3.4多边形的扫描转换3.4.1多边形的扫描转换多边形的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来描述多边形，如可用P0P1P2P3P4P0的点序列来表示图3.11中的多边形。该表示几何意义强、占内存少、几何变换方便；但不能直观地说明哪些像素在多边形内，故不能直接用于面着色。图3.11多边形的顶点表示P1P0P2P3P4图3.12多边形的点阵表示3.4.1多边形的扫描转换点阵表示用位于多边形内的像素的集合来描述多边形。如图3.11的多边形可表示成图3.12的标有·号的像素的集合，该方法虽然没有多边形的几何信息，但便于用帧缓存表示图形，可直接用于面着色。多边形的扫描转换就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，并为帧缓存内的各个对应元素设置相应的灰度或颜色。3.4.2扫描线算法基本思想扫描线算法按扫描线的顺序计算出扫描线与多边形的相交区间，然后用要求的颜色填充这些区间内的像素。该算法利用了扫描线的连续性和边的连续性，避免对像素的逐点判断和反复求交运算，减少了计算量，提高了算法速度。先求出扫描线与多边形边的交点，利用扫描线的连续性求出多边形与扫描线相交的连续区域，然后利用多边形边的连续性，求出下一条扫描线与多边形的交点，对所有扫描线由上到下依次处理。3.4.2扫描线算法1扫描线的连续性设多边形P的顶点，将各顶点的纵坐标按递减顺序排列,即设当前扫描线，，与多边形P的边的交点记为。设为与P的边界各交点横坐标的递增序列，该序列称为交点序列。(3.21)3.4.2扫描线算法交点序列具有以下性质：交点个数l是偶数；扫描线上的区间 l–1位于多边形P内（图3.13中的实线段部分），其余区间都在P外（图3.13中的虚线段部分），两类区间沿扫描线相间排列。这些性质就称为扫描线的连续性。P0P1P2P3P4P5P6P7P8xe0xe2xe3xe7xe6xe4图3.13扫描线的连续性图中----表示在多边形外的区间──表示在多边形内的区间根据扫描线的连续性，只需求出扫描线与多边形P的边界的所有交点，就可确定扫描线位于多边形P内的区间。3.4.2扫描线算法2边的连续性设当前扫描线的下一条扫描线为，，且,设位于扫描线上的交点序列为
（3.22）若,
成立，则扫描线与扫描线和多边形P相同的边相交，由扫描线的连续性知，两序列（3.21）和（3.22）的点满足以下关系：（1）两序列元素的个数相等，即。（2）点（）与（）位于多边形P的同一边上（见图3.14），所以可由下式计算
(3.23)以上性质称为边的连续性。3.4.2扫描线算法图3.14边的连续性P0P1P2P3P4P5P6P7P8xe0xe2xe3xe7xe6xe4xd0xd6xd43.4.2扫描线算法3奇点的处理上述三种形式的连续性都基于一个几何事实：每一条扫描线与多边形P的边界的交点个数都是偶数（包括零）。但是当扫描线与多边形P的边界的交点恰好是P的顶点时（该交点称为奇点）：如果把每一奇点简单地计为一个交点，则交点个数可能出现奇数（如图3.15中的扫描线的情况）；若将每一奇点都简单地计为两个交点，同样会导致反常的结果（如图3.15中扫描线的情况）。因此，必须按不同的情况区别对待奇点。3.4.2扫描线算法设多边形P的顶点为这些顶点可分为两类：极值点和非极值点。如果，则称顶点为极值点（如图3.15中的）；否则称为非极值点（如图3.15中的）。P0P1P2P3P4P5P6P7图3.15一个多边形与若干条扫描线P83.4.2扫描线算法为使每一条扫描线与多边形P的边界的交点个数始终为偶数，规定当奇点是多边形P的极值点时，该点按两个交点计算，否则按一个交点计算。图3.16非极值点的处理（a）（b）实际计算中，可如下处理非极值点：若是非极值点，则将,两边中位于扫描线上方的那条边在处截去一个单位长，这样就能保证扫描线只和，中的一边相交，只有一个交点。3.4.2扫描线算法4算法的实现步骤与数据结构对于每一条扫描线，多边形的填充过程可分为以下4步：计算扫描线与多边形各边的交点，设交点个数为n。把所有的交点按x值递增的顺序进行排列。将排序后的第1个与第2个交点，第3个与第4个交点，……第n-1个与第n个交点配对，每对交点就代表扫描线与多边形的一个相交区间。把相交区间内的像素置成多边形的颜色，相交区间外的像素置成背景色。12343.4.2扫描线算法活性边表与当前扫描线相交的边称为活性边。把活性边与扫描线的交点按x坐标递增的顺序放在一个链表中，该链表就称为活性边表（ActiveEdgeList,AEL
）。设多边形某一条边的方程为，当前扫描线与该边的交点坐标为，则下一条扫描线与该边的交点不需要重新计算，只要加一个增量即可。因为此时有其中为常数，并规定时，。3.4.2扫描线算法使用增量计算时，还要知道一条边何时不再与下一条扫描线相交，以及时地把该边从活性边表中删除，因此需要记录下与该边相交的最高扫描线号。综上，AEL中的节点应由如下四个域组成：
:边的上端点的y坐标，即与该边相交的最高扫描线号。x:边与扫描线的交点的x坐标。
:从当前扫描线到下一条扫描线间的x坐标的增量，即边的斜率的倒数。Next:指向下一条边的指针。3.4.2扫描线算法新边表为方便活性边表的建立与更新，还要为每一条扫描线建立一个新边表（NewEdgeList,
NEL
），存放在该扫描线上第一次出现的边。也就是说，如果某边的较低端点为，则该边就放在扫描线的新边表中。注意：水平边不放到任何扫描线的NEL中，即水平边不参加分类。NEL中的节点结构与AEL相同，只是x在这里不再表示边与扫描线的交点，而是表示该边较低端点的x坐标值。3.4.2扫描线算法具体例子图3.18和3.19是图3.17中多边形的新边表NEL和活性边表AEL。在图3.17中表示边，各顶点为[P0P1…P6]=[(2,5)(2,10)(9,6)(16,9)(16,4)(12,2)(7,2)]
其中，是非极值点，在分类前已对边作了预处理，即分别在处把它们截去一个单位长，这样保证扫描线只和两边中的一边相交，求得一个交点，是水平边，不参加分类。3.4.2扫描线算法图3.17多边形P0P1…P6P051015P1P2P3P4P5P6P0e0e2e3e5e1e4e63.4.2扫描线算法图3.18新边表NEL123456e5e0e11002e3e2△xxymaxnext109e4901699574212e6AELAELe0e4e1e3e2xymax△xnexte5图3.19活性边表AEL55421410021059149016AEL在y=3扫描线上的状态AEL在y=8扫描线上的状态3.4.2扫描线算法3.4.3边缘填充算法基本思想假设某像素的颜色是，对该像素做偶数次求补运算后，其颜色还是；做奇数次求补运算后，其颜色变为。在光栅图形中，如某区域已着上值为M的某种颜色，则上述求补运算的结果是：对区域作偶数次求补运算后，该区域的颜色不变；作奇数次求补运算后，该区域的颜色则变成值为的颜色。3.4.3边缘填充算法具体步骤对多边形P的每一非水平边（i=0,1,…,n）上的各像素进行向右求补运算，当相对于所有边的求补运算都完成后，多边形的扫描转换也随之完成。图3.20a为给定的多边形；b为对区域赋初值；c、d、e和f表示逐边向右求补。(a)(b)(c)(d)(f)(e)图3.20边缘填充算法的过程3.4.4边界标志算法基本思想首先用一种特殊的颜色在帧缓存中将多边形的边界（水平边的部分边界除外）勾画出来，然后再把位于多边形内的各个区段着上所需的颜色。具体步骤步骤1：以值为boundary_color
的特殊颜色勾画多边形P的边界。设多边形的顶点为均为整数，置。下面的算法可保证每一条扫描线上着上这种特殊颜色的点的个数是偶数（包括零）。3.4.4边界标志算法intred=Color.red.getRGB();publicImageboundary(){Imageimage;//定义Image对象for(i=0;i<7;i++){dy=p[i+1].y-p[i].y;
dx=(p[i+1].x-p[i].x)/dy;
if(dy>0)x=p[i].x;elsex=p[i+1].x;
ymax=(Math.max(p[i].y,p[i+1].y));
ymin=(Math.min(p[i].y,p[i+1].y));for(y=ymin+1;y<=ymax;y++){x=(int)(x+dx+.5);
if(pixels[y*w+x]==red)pixels[y*w+x+1]=red;elsepixels[y*w+x]=red;}}
ImageProducer
ip=newMemoryImageSource(w,h,pixels,0,w);image=createImage(ip);returnimage;}3.4.4边界标志算法步骤2：逐条处理扫描线对多边形着色。设in_flag是一布尔变量。对每一条扫描线从左到右进行搜索，若当前像素位于多边形P内，则in_flag=true，需填上值为polygon_color的颜色；若该像素在多边形P外，则需填上值为background_color的颜色：//maxx、maxy、minx、miny是获得的多边形最小矩形包围盒边界值publicImageinterior(){Imageimage;
int
maxx=150,minx=20,maxy=120,miny=20,l;
int
in_flag；//多边形内部标志变量for(y=miny-1;y<=maxy;y++){in_flag=0;for(x=minx-1;x<maxx;x++){l=pixels2[y*w+x];if(l==red){if(in_flag==0)in_flag=1;elsein_flag=0;}
if(in_flag==1)pixels2[y*w+x]=red;}}
ImageProducer
ip=newMemoryImageSource(w,h,pixels,0,w);image=createImage(ip);returnimage;}3.4.4边界标志算法3.4.4边界标志算法具体例子
边界标志算法的过程(a)
勾画边界(b)
在y=1的扫描线上转换(c)
在y=2的扫描线上转换(d)
扫描转换完毕3.5区域填充区域填充是指先将区域内的一点（常称种子点）赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。3.5.1区域的表示和类型1内点表示把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。它将区域内的所有像素填充成同一种颜色（常称为原色），而区域边界上的像素则不能填这种颜色。如图3.22，有·的方格表示内点，在内点处像素填原色。图3.22内点表示的区域图3.23边界表示的区域2边界表示法3.5.1区域的表示和类型把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。它将区域边界上的像素都着上同一种颜色（常称为边界色），而区域内的像素则不能着这种颜色。如图3.23，有×的方格表示边界点，在边界点处像素填边界色。3.5.1区域的表示和类型3区域的连通性四连通的区域是指从该区域内一点出发，通过上、下、左、右四种运动（如图3.24）的组合，在不越出区域的前提下，可到达区域内的任一点。八连通的区域是指从该区域内一点出发，通过沿水平方向、垂直方向和对角线方向的八种运动（如图3.25）的组合，在不越出区域的前提下，可到达区域内的任一点。图3.24四个方向的运动图3.25八个方向的运动3.5.1区域的表示和类型图3.26内点表示的八连通区域图3.27边界表示的八连通区域3.5.1区域的表示和类型用于八连通区域的填充算法可用于四连通区域的填充，但用于四连通区域的填充算法并不适用于八连通区域的填充。四连通区域也可理解成八连通区域，但两者的边界不尽相同。若将图3.28中标有·号的像素组成的区域作为四连通区域，则其边界由图中标有△号的像素组成。若将该区域作为八连通区域，则其边界由图中标有△号和×号的两种像素组成。图3.28四连通区域与八连通区域的不同边界3.5.2递归算法基本思想设（x,y）是内点表示的一区域G内的一点，old_color是G的原色。先取（x,y）点为种子点，测试其颜色，若等于old_color，说明是区域内一点，则将其置为新的颜色new_color，否则说明该点不在区域G内，则停止填充；然后将该点周围的四个点（四连通）或八个点（八连通）作为新的种子点进行同样的处理，通过这种扩散完成对整个区域的填充。显然，这一过程是用递归实现的。3.5.2递归算法publicvoidflood_fill_8(int[]pixels,int
x,int
y,int
old_color,int
new_color){if(x<w&&x>0&&y<h&&y>0){if(pixels[w*y+x]==old_color){
pixels[w*y+x]=new_color; flood_fill_8(pixels,x,y+1,old_color,new_color); flood_fill_8(pixels,x,y-1,old_color,new_color); flood_fill_8(pixels,x-1,y,old_color,new_color); flood_fill_8(pixels,x+1,y,old_color,new_color); flood_fill_8(pixels,x+1,y+1,old_color,new_color); flood_fill_8(pixels,x+1,y-1,old_color,new_color); flood_fill_8(pixels,x-1,y+1,old_color,new_color); flood_fill_8(pixels,x-1,y-1,old_color,new_color);}}}算法实现3.5.3扫描线种子填充算法基本思想从给定的种子点开始，先填充种子点所在扫描线上的位于给定区域内的一个区间，然后确定与这一区间相邻的上下两条扫描线上需要填充的区间，从这些区间上各取一个种子点并依次保存下来，作为下次填充的种子点，反复进行这个过程，直到所保存的各区间都填充完毕。3.5.3扫描线种子填充算法算法实现①将堆栈置空，并将给定的种子点（x,y）压入堆栈。②若堆栈为空，算法结束；否则取栈顶元素（x,y）作为种子点。③从种子点（x,y）出发，沿纵坐标为y的当前扫描线向左右两个方向用新的颜色逐个像素地填充，直到边界。设区间两边界的横坐标分别为和。④以区间为搜索范围，检查与当前扫描线相邻的上下两条扫描线上的像素，若存在非边界、未填充的像素，则把相应小区间中最右边的点作为种子点压入堆栈，转入②。3.5.3扫描线种子填充算法程序publicvoidscan(int[]pixels,Point
point,int
old_color,int
new_color){int
x,y,savex,xright,xleft;Pointp;Stackstack=newStack();//设置堆栈对象
stack.push(point);//压栈
boolean
span_need_fill;while(!stack.empty()){p=(Point)(stack.pop());//出栈，从堆栈中取一像素作为种子像素
x=p.x;y=p.y;
savex=x;//保存横坐标x的值
while(pixels[y*w+x]!=boundary_color){
pixels[y*w+x]=new_color;x++;}//从种子像素开始向右填充到边界 xright=x-1;//保存线段的右端点x=savex-1;while(pixels[y*w+x]!=boundary_color){
pixels[y*w+x]=new_color;x--;}//从种子像素开始向左填充到边界，以上两步完成区间填充xleft=x+1;//保存线段的左端点x=xleft;y=y+1;while(x<=xright){//在上一条扫描线上检查是否需要填充
span_need_fill=false;while(pixels[w*y+x]==old_color&&x<=xright){//待填充的线段
span_need_fill=true;x++;}//待填充的线段处理完3.5.3扫描线种子填充算法if(span_need_fill){//如果区间需要填充，则将其右端点作为 //种子点压进堆栈p=newPoint(x-1,y);
stack.push(p);//进栈
span_need_fill=false;}//继续向右检查以防有遗漏
while(pixels[y*w+x]!=old_color&&x<=xright)x++;}//在上一条扫描线上检查完x=xleft;y=y-2;//形成下一条扫描线的y值
//在下一条扫描线上从左向右地检查位于区间[xleft,xright]上的像素
3.5.3扫描线种子填充算法while(x<=xright){
span_need_fill=false;while(pixels[w*y+x]==old_color){
span_need_fill=true; x++;} if(span_need_fill){ p=newPoint(x-1,y);
stack.push(p);
span_need_fill=false; }
while(pixels[y*w+x]!=old_color&&x<=xright)x++;}}}3.5.3扫描线种子填充算法3.5.3扫描线种子填充算法(a)
1212(b)12123(c)(d)算法执行过程示例3.6字符的生成3.6.1点阵式字符点阵式字符是将字符形状表示为一个矩形点阵，由点阵中点的不同值来表达字符的形状。常用的点阵大小有7×9、8×8
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 北师大初中信息技术八年级全册教案
- 人教版小学五年级下册数学教案 全册
- 2024-2025学年度秋季第一学期六年级上册劳动教育教学计划
- 家长如何正确培养孩子的良好品格
- 创伤性颅脑损伤患者的神经功能恢复护理课件
- 大学美育 课件 第一篇第一章第三节 田园村庄
- 高二上学期英语人教版（2019）选择性必修第一册单词背诵课件
- 寒假英语教师读书心得体会
- 教师数字素养心得体会
- 关于教师职业规划范文（30篇）
- 产品选型方案设计
- 律师职业介绍
- 直播运营测试题附有答案
- 小鱼研究员：中国研学产业发展趋势报告2024
- 海洋低碳生态
- 组织内部沟通和协作
- 2024年西藏自治区专升本考试法学基础测试题含解析
- 2024年上海市第二十七届初中物理竞赛初赛试题及答案
- 单管塔地脚锚栓计算
- 广告策划实训教程 课件 项目八 广告策划实务之策划书撰写
- 2024年四川成都市兴蓉集团有限公司招聘笔试参考题库含答案解析
评论
0/150
提交评论