區域填充

區域填充在矢量數據結構中，通常以不規則多邊形來表示區域，對於多邊形內填充的暈線成符號，只是圖形輸出的表示方法，它並不作為空間數據參加運算。矢量數據轉成概格數據是通過矢量邊界輪席的轉換實現的。在柵格數據結構中，概格元家值直接表示屬性值。因此，當矢量邊界線段轉換成幅格數據後，還需進行面域填充。

基本介紹

• 中文名：區域填充
• 外文名：Region filling
• 屬於：CAD語言
• 主要針對：顯示平面內的區域而言
• 填充算法：掃描線種子填充算法思想

釋義

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[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("\nOUT MEMORY IN INSERTING EDGE RECORD TO AET\n"); 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("\nOUT MEMORY IN CONSTRUCTING ET\n"); 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("\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[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); }; }; }