区域填充在矢量数据结构中，通常以不规则多边形来表示区域，对于多边形内填充的晕线成符号，只是图形输出的表示方法，它并不作为空间数据参加运算。矢量数据转成概格数据是通过矢量边界轮席的转换实现的。在栅格数据结构中，概格元家值直接表示属性值。因此，当矢量边界线段转换成幅格数据后，还需进行面域填充。
CAD语言
所谓区域填充,指的是在输出平面的闭合区域内完整地填充某种颜色或图案。以下所述及的区域填充算法或相关程序,主要针对显示平面内的区域而言。
区域填充的问题一般分两大类,一是多边形填充；一是种子填充。多边形填充有一定难度；种子填充在学生掌握了“栈”这一抽象数据类型的实现方法的前提下,比较容易完成。而边标志填充算法却是介于这两类之间,部分地具有它们的痕迹,算法思想巧妙,实现起来更容易。
在编程时可能需要在屏幕上画线段,建议学生使用自己在上次实习中实现的画线程序,也允许学生使用Turbo C的画线函数,包括：line( )、lineto( )、linerel( )、moveto( )等；另外,在编写种子填充程序时除了可能用到函数putpixel( )外,还要用到取屏幕上某象素颜色的函数getpixel( ),上述这些函数的具体使用方法可参考Turbo C使用手册,也可查看Turbo C的联机帮助。请注意,在Turbo C图形模式下,设备坐标系原点在屏幕左上角,X轴正方向向右,Y轴正方向向下。
将闭合的多边形内填充某种颜色或图案。
基本要求
1、用扫描线种子填充算法实现多边形内实面积填充。
2、用边标志填充算法实现多边形内实面积填充。
提高要求
1、实现多边形内图案填充。
2、实现多边形内剖线填充。
3、用边相关多边形扫描线填充算法实现多边形内实面积填充。
扫描线种子填充算法
扫描线种子填充算法思想
首先填充种子所在的尚未填充的一区段,然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段,如果存在,则依次把每个新区段最右端的象素作为种子放入堆栈。反复这个过程,直到堆栈为空。
扫描线种子填充算法步骤 1、初始化堆栈。 2、种子压入堆栈。 3、While（堆栈非空）从堆栈弹出种子象素。
(1)如果种子象素尚未填充,则：
① 求出种子区段：xleft、xright。
② 填充整个区段。 (2)检查相邻的上扫描线的xleft≤x≤xright区间内,是否存在需要填充的新区段,如果存在,则把每个新区段在xleft≤x≤xright范围内的最右边的象素,作为新的种子象素依次压入堆栈。 (3)检查相邻的下扫描线的xleft≤x≤xright区间内,是否存在需要填充的新区段,如果存在,则把每个新区段在xleft≤x≤xright范围内的最右边的象素,作为新的种子象素依次压入堆栈。 }
有关堆栈操作的辅助代码
1、定义栈结构：
# define MAX 100 struct stack { int top; int xy; }s; |
2、初始化堆栈
s.top=－1; |
3、进栈操作
pushxy(int x,int y) { if(s.top= =MAX－1) { printf(“Overflow!”); exit(1); } else { s.top=s.top+1; s.xy=x; s.xy=y; } } |
4、出栈操作
popxy(int *x,int *y) { if(s.top<0) { printf(“underflow!”); exit(1); } else { *x=s.xy; *y=s.xy; s.top=s.top－1; } } |
5、堆栈非空
s.top!=－1 或者 s.top>=0 |
扫描线种子填充算法伪代码
scanline_seed_fill(int x,int y,int boundarycolor,int newcolor) { int savex,xleft,xright,pflag,xenter; //初始化堆栈； pushxy(x,y); while(堆栈非空) { popxy(&x,&y); savex=x; while(getpixel(x,y)!=boundarycolor) { putpixel(x,y, newcolor ); x++; } xright=x－1; x=savex－1; while(getpixel(x,y)!=boundarycolor) { putpixel(x,y, newcolor ); x--; } xleft=x+1; x=xleft; y=y+1; while(x<=xright) { pflag=0; while(getpixel(x,y)!=boundarycolor && getpixel(x,y)!=newcolor&& x<xright) { if(pflag= =0) pflag=1; x++; } if(pflag= =1) { if((x= =xright)&&(getpixel(x,y)!=boundarycolor)&&(getpixel(x,y)!=newcolor)) pushxy(x,y); else pushxy(x－1,y); pflag=0; } xenter=x; while((getpixel(x,y)==boundarycolor||getpixel(x,y)==newcolor)&&x<xright) { x++; } if(xenter==x) x++; } x=xleft; y=y－2; } } |
边相关多边形扫描线填充算法
边相关多边形扫描线填充思想
边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。
ET用来对除水平边外的所有边进行登记,即建立边的记录。
AET则是在ET建立的基础上进行扫描转换。对不同的扫描线,与之相交的边线也是不同的,当对某一条扫描线进行扫描转换时,我们只需要考虑与它相交的那些边线,为此AET建立了只与当前扫描线相交的边记录链表,以提供对当前扫描线上的区段进行填充。
边相关多边形扫描线填充算法步骤
1、根据给出的顶点坐标建ET表；并求出顶点坐标中最大y值ymax和最小y值ymin。
2、定义AET指针,并使它为空。
3、使用扫描线的yj值作为循环变量,使其初值为ymin。
4、对于循环变量yj的每一整数值,重复作以下事情,直到yj大于ymax,或ET与AET表都为空为止：
① 如果ET中yj桶非空,则将yj桶中的全部记录合并到AET中。
② 对AET链中的记录按x的大小从小到大排序。
③ 依次取出AET各记录中的xi坐标值,两两配对,对每对xi之间的象素填上所要求的颜色。
④ 如果AET中某记录的ymax=yj,则删除该记录。
⑤ 对于仍留在AET中的每个记录,用xi+1/m代替xi,这就是该记录边线与下一条扫描线yj+1的交点。
⑥ 使yj加1,以便进入下一轮循环。
边相关多边形扫描线填充为伪代码
#include <stdlib.h> #include <graphics.h> #include <stdio.h> #define round(x) ((x>0)?(int)(x+0.5):(int)(x-0.5)) struct edge{ int ymax; float xi; float m; struct edge *next; }; void poly_fill(int,int *,int); void main() { int polypoints={ 100,300, 200,200, 300,200, 300,350, 400,250, 450,300, 300,50, 100,150}; int gdriver=DETECT,gmode; initgraph(&gdriver,&gmode,""); poly_fill(8,polypoints,4); getch(); closegraph(); } void insert_et(struct edge *anedge,struct edge **p_edges) { struct edge *p; p=*p_edges; *p_edges=anedge; anedge->next=p; } short insert_aet(struct edge *p,struct edge **p_aet) { struct edge *q,*k,*l; if(!(q=(struct edge *)malloc(sizeof(struct edge)))) { printf("nOUT MEMORY IN INSERTING EDGE RECORD TO AETn"); return(0); } q->ymax=p->ymax; q->xi=p->xi; q->m=p->m; q->next=NULL; if(!(*p_aet)||((*p_aet)->xi>q->xi)||(((*p_aet)->xi==q->xi)&&((*p_aet)->m>q->m))) { l=*p_aet; *p_aet=q; q->next=l; } else { l=*p_aet; k=l->next; while(k&&(k->xi<q->xi)) { l=k; k=k->next; } if(k&&(k->xi==q->xi)&&(k->m<q->m)) { l=k; k=k->next; } l->next=q; q->next=k; } return(1); } void draw_line(int x1,int x2,int y,int color) { int i; y=getmaxy()-y; for(i=x1;i<=x2;i++)putpixel(i,y,color); } void poly_fill(int numpoint,int *points,int color) { struct edge **et=NULL,*aet,*anedge,*p,*q; int i,j,maxy,miny,x1,y1,x2,y2,yi,znum; maxy=miny=points; znum=2*numpoint; for(i=3;i<znum;i++) { if(maxy<points) maxy=points; else if(miny>points)miny=points; i++; } if(!(et=(struct edge **)malloc((maxy-miny+1)*sizeof(struct edge *)))) { printf("nOUT MEMORY IN ConSTRUCTING ETn"); return; } for(i=0;i<maxy-miny+1;i++) et=NULL; x1=points; y1=points; for(i=0;i<znum;i+=2) { x2=points; y2=points; if(y1!=y2) { if(!(anedge=(struct edge *)malloc(sizeof(struct edge)))) { printf("nOUT MEMORY IN ConSTRUCTING EDGE RECORD.n"); goto quit; } anedge->m=(float)(x2-x1)/(y2-y1); anedge->next=NULL; if(y2>y1) { j=i+1; do{ if((j+=2)>=znum)j-=znum; }while(points==y2); if(points>y2) anedge->ymax=y2-1; else anedge->ymax=y2; anedge->xi=x1; insert_et(anedge,&et); } else { j=i+1; do{ if((j-=2)<0)j+=znum; }while(points==y1); if(points>y1) anedge->ymax=y1-1; else anedge->ymax=y1; anedge->xi=x2; insert_et(anedge,&et); } } x1=x2; y1=y2; } aet=NULL; for(yi=miny;yi<=maxy;yi++) { while(p) { if(!insert_aet(p,&aet)) goto quit; p=p->next; } p=aet; while(p) { draw_line(round(p->xi),round(p->next->xi),yi,color); p=p->next->next; } p=aet; while(p&&(p->ymax==yi)) { aet=p->next; free(p); p=aet; } while(p) { if(p->ymax==yi) { q->next=p->next; free(p); p=q->next; } else { p->xi+=p->m; q=p; p=p->next; } } } quit: if(et) { for(yi=miny;yi<=maxy;yi++) { q=p=et; while(p) { q=p->next; free(p); p=q; } } free(et); } } |
边标志填充算法
边标志填充算法思想
扫描线具有连贯性,这种连贯性只有在扫描线与多边形相交处才会发生变化,而每次的变化结果：无非是在前景色和背景色之间相互“切换”。
边标志填充算法正是基于这一发现,先在屏幕上生成多边形轮廓线,然后逐条扫描线处理。处理中：逐点读取象素值,若为边界色,则对该象素值进行颜色切换。
边标志填充算法步骤 1、用边界色画出多边形轮廓线,也就是将多边形边界所经过的象素打上边标志。
2、为了缩小范围,加快填充速度,须找出多边形的最小包围盒：xmin、ymin、xmax、ymax。
3、逐条扫描线进行处理,初始时标志为假,对每条扫描线依从左往右的顺序,逐个访问该扫描线上的象素。每遇到边界象素,标志取反。然后,按照标志是否为真决定象素是否为填充色。
边标志填充算法伪代码
EdgeMarkFill(int p,int n,int boundarycolor,int newcolor) { int i,x,y,flag,xmin,xmax,ymin,ymax; setcolor(boundarycolor); for(i=0 ;i<n;i++) line(p, p, p, p); for(y=ymin;y<=ymax;y++) { flag=－1; for(x=xmin;x<=xmax;x++) { if(getpixel(x,y)= = boundarycolor) flag=－flag; if(flag= =1)putpixel(x,y, newcolor); } } } |
温馨提示：
