合並填充演算法

① 區域填充的主要思想和方法

掃描線種子填充演算法思想
首先填充種子所在的尚未填充的一區段,然後確定與這一區段相鄰的上下兩條掃描線上位於該區段內是否存在需要填充的新區段,如果存在,則依次把每個新區段最右端的象素作為種子放入堆棧。反復這個過程,直到堆棧為空。
掃描線種子填充演算法步驟 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[MAX][2]; /*種子點（二維）*/
}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[s.top][0]=x;
s.xy[s.top][1]=y;
}
} 4、出棧操作 popxy(int *x,int *y)
{
if(s.top<0)
{
printf(「underflow!」);
exit(1);
}
else
{
*x=s.xy[s.top][0];
*y=s.xy[s.top][1];
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; /*保存種子坐標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; /*找到新種子的標志：0為假；1為真*/
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); /*新區間超過xright,將代表該區段的象素進棧*/
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++;/*處理特殊情況,以退出while(x<=xright)循環*/
}
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[]={ /*多邊形頂點坐標: x0,y0,x1,y1,... */
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( OUT MEMORY IN INSERTING EDGE RECORD TO AET );
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);
}
/*從（x1,y）到（x2,y）用color色繪水平直線*/
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);
}
/*多邊形掃描線填充:
numpoint是多邊形頂點個數；
points存放多邊形頂點坐標（x0,y0,x1,y1,...);
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[1];
znum=2*numpoint;
for(i=3;i<znum;i++)
{
if(maxy<points[i]) maxy=points[i];
else if(miny>points[i])miny=points[i];
i++;
}
if(!(et=(struct edge **)malloc((maxy-miny+1)*sizeof(struct edge *))))
{ /*建立邊表ET */
printf( OUT MEMORY IN CONSTRUCTING ET );
return;
}
for(i=0;i<maxy-miny+1;i++) et[i]=NULL;
x1=points[znum-2]; y1=points[znum-1];
for(i=0;i<znum;i+=2)
{ /*處理多邊形所有邊,為每條非水平邊建立一個邊記錄,並將其插到ET表中的合適位置 */
x2=points[i]; y2=points[i+1];
if(y1!=y2) /*只考慮非水平邊*/
{
if(!(anedge=(struct edge *)malloc(sizeof(struct edge))))
{
printf( OUT MEMORY IN CONSTRUCTING EDGE RECORD. );
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[j]==y2);
if(points[j]>y2) anedge->ymax=y2-1;
/*若(x2,y2)不是局部極值點,邊記錄的ymax域為y2-1,這樣處理
掃描線y=y2時此邊記錄將不在AET中,從而不會產生交點 */
else anedge->ymax=y2; /*若(x2,y2)是局部極值點,邊記錄的ymax域為y2,
這樣處理掃描線y=y2時此邊記錄將在AET中,從而會產生一個交點 */
anedge->xi=x1;
insert_et(anedge,&et[y1-miny]);
}
else
{
j=i+1; /*向前劃過所有水平邊*/
do{
if((j-=2)<0)j+=znum;
}while(points[j]==y1);
if(points[j]>y1) anedge->ymax=y1-1;
/*若(x1,y1)不是局部極值點,邊記錄的ymax域為y1-1,這樣處理
掃描線y=y1時此邊記錄將不在AET中,從而不會產生交點 */
else anedge->ymax=y1; /*若(x1,y1)是局部極值點,邊記錄的ymax
域為y1,這樣處理掃描線y=y1時此邊記
錄將在AET中,從而會產生一個交點 */
anedge->xi=x2;
insert_et(anedge,&et[y2-miny]);
}
}
x1=x2;
y1=y2;
}
aet=NULL; /*初始化有效邊表AET*/
for(yi=miny;yi<=maxy;yi++) /*從低到高逐條處理掃描線*/
{ /*將ET表中與yi對應的邊記錄鏈表中的全部邊記錄
p=et[yi-miny]; 都按序並入AET中*/
while(p)
{
if(!insert_aet(p,&aet)) goto quit;
p=p->next;
}
p=aet;
while(p) /*依次取出AET各記錄中的xi坐標值,兩兩配對,*/
{/*對每對xi之間的象素填上所要求的顏色*/
draw_line(round(p->xi),round(p->next->xi),yi,color);
p=p->next->next;
}
p=aet;
while(p&&(p->ymax==yi)) /*對AET中的每個記錄,若它的ymax==yi, */
{/*則刪除該記錄,否則用xi+1/m代替xi,這就是該記錄所對應的*/
aet=p->next; /*邊線與下一條掃描線y=yi+1的交點 */
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[yi-miny];
while(p)
{
q=p->next;
free(p);
p=q;
}
}
free(et);
}
} 邊標志填充演算法思想
掃描線具有連貫性,這種連貫性只有在掃描線與多邊形相交處才會發生變化,而每次的變化結果：無非是在前景色和背景色之間相互「切換」。
邊標志填充演算法正是基於這一發現,先在屏幕上生成多邊形輪廓線,然後逐條掃描線處理。處理中：逐點讀取象素值,若為邊界色,則對該象素值進行顏色切換。
邊標志填充演算法步驟 1、用邊界色畫出多邊形輪廓線,也就是將多邊形邊界所經過的象素打上邊標志。
2、為了縮小范圍,加快填充速度,須找出多邊形的最小包圍盒：xmin、ymin、xmax、ymax。
3、逐條掃描線進行處理,初始時標志為假,對每條掃描線依從左往右的順序,逐個訪問該掃描線上的象素。每遇到邊界象素,標志取反。然後,按照標志是否為真決定象素是否為填充色。
邊標志填充演算法偽代碼 EdgeMarkFill(int p[][2],int n,int boundarycolor,int newcolor)
{
int i,x,y,flag,xmin,xmax,ymin,ymax;
setcolor(boundarycolor); /*設置畫筆色*/
for(i=0 ;i<n;i++)/*畫出多邊形的n條邊*/
line(p[i][0], p[i][1], p[(i+1)%n][0], p[(i+1)%n][1]);
/*用求極值的演算法,從多邊形頂點數組p中,求出xmin,xmax,ymin,ymax*/
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);
}
}
}