邊填充演算法

『壹』 邊緣填充演算法屬於()演算法一種。

邊緣填充演算法屬於A 多邊形掃描轉換

『貳』 剩餘矩形填充演算法是優化演算法嗎

是，針對矩形件排樣問題提出的一種新的空白矩形填充優化演算法.
首先,設計空白矩形填充演算法時,提出了消除多餘空白矩形的方法,以減小計算時間復雜度.其次,利用鄰域搜索演算法優化矩形件排放順序,通過挖掘矩形件排樣的問題特徵,設計了受限距離的交叉和插入兩種鄰域運算元,並提出了特殊運算元執行點選擇策略.然後,設計了基於兩種鄰域運算元交替迭代的鄰域搜索演算法.最後,對文獻中的21個經典案例進行試驗計算,4個案例的排樣利用率達到了100％,絕大多數案例的排樣利用率超過了99％,最小排樣利用率超過了98％.將其他常用演算法和文獻中演算法進行比較,驗證了本文演算法的有效性

『叄』 區域填充的主要思想和方法

掃描線種子填充演算法思想
首先填充種子所在的尚未填充的一區段,然後確定與這一區段相鄰的上下兩條掃描線上位於該區段內是否存在需要填充的新區段,如果存在,則依次把每個新區段最右端的象素作為種子放入堆棧。反復這個過程,直到堆棧為空。
掃描線種子填充演算法步驟 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);
}
}
}

『肆』 比較邊界填充演算法和泛填充演算法的異同

如果是用線填充，程序如下。如果是用點填充需要用到堆棧和系統底層庫函數或者用畫點函數putpixel()。
下面實例是用掃描線填充長方形，開始要輸入長方形的左上頂點坐標和右下頂點坐標以及填充掃描線的間距(>=1)，如果間距等於1，就是完全填充(實填充)。
一個完整的c程序如下,程序在win-tc和tc2.0下都調試通過。
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<graphics.h>

void draw(int x1,int y1,int x2,int y2,int delta)
{int nx1,ny1,nx2,ny2; <br/>nx1=x1,ny1=y2-delta,nx2=x1+delta,ny2=y2; <br/>while((ny1>=y1)&&(nx2<=x2)) <br/>{line(nx1,ny1,nx2,ny2); <br/>ny1-=delta; <br/>nx2+=delta; <br/>}
if(nx2>x2)
{ny2-=nx2-x2; <br/>nx2=x2; <br/>while(ny1>y1) <br/>{line(nx1,ny1,nx2,ny2); <br/>ny1-=delta; <br/>ny2-=delta; <br/>}
nx1+=y1-ny1;
ny1=y1;
while(nx1<x2)
{line(nx1,ny1,nx2,ny2); <br/>nx1+=delta; <br/>ny2-=delta; <br/>}
}
else
{nx1+=y1-ny1; <br/>ny1=y1; <br/>while(nx2<x2) <br/>{line(nx1,ny1,nx2,ny2); <br/>nx2+=delta; <br/>nx1+=delta; <br/>}
ny2-=nx2-x2;
nx2=x2;
while(ny2>y1)
{line(nx1,ny1,nx2,ny2); <br/>ny2-=delta; <br/>nx1+=delta; <br/>}
}
}

int main(void)
{int x1,y1,y2,x2,delta; <br/>int driver=DETECT,mode; <br/>printf("Please input lefttop(x1,y1) and rightbottom(x2,y2) of rectangle and delta:\n"); <br/>scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&delta); <br/>initgraph (&driver,&mode,"C:\\TC"); /*這里*/<br/>rectangle(x1,y1,x2,y2); <br/>draw(x1,y1,x2,y2,delta); <br/>gotoxy(1,1); <br/>printf("Press any key to exit!"); <br/>getch()(); <br/>closegraph(); <br/>return 0; <br/>}

說明：將main()函數中的initgraph(&gdriver,&gmode,"");中的""更改為你的TC安裝目錄,一般tc必須安裝在c盤根目錄下，所以就是initgraph(&gdriver,&gmode,"C:\\TC");如你的TC安裝目錄為D盤的Tools目錄下的TC目錄，那麼上述語句改為：
initgraph(&gdriver,&gmode,"D:\\Tools\\TC");
同時保證在D:\\Tools\\TC目錄里有文件EGAVGA.BGI,萬一不行，將本程序復制到你的TC安裝目錄下再運行。

『伍』 簡單掃描線性填充和與邊相關掃描線填充演算法的區別

1. 對多邊形的每一條邊進行掃描轉換，即對 多邊形邊界所經過的象素作一個邊界標志。 2.填充。對每條與多邊形相交的掃描線，按 從左到右的順序，逐個訪問該掃描線上的象 素。 取一個布爾變數inside來指示當前點的狀態， 若點在多邊形內，則inside為真。若點在多 邊形外，則inside為假。 Inside 的初始值為假，每當當前訪問象素為 被打上標志的點，就把inside取反。對未打 標志的點，inside不變。

『陸』 區域填充的要求

所謂區域填充,指的是在輸出平面的閉合區域內完整地填充某種顏色或圖案。以下所述及的區域填充演算法或相關程序,主要針對顯示平面內的區域而言。
區域填充的問題一般分兩大類,一是多邊形填充；一是種子填充。多邊形填充有一定難度；種子填充在學生掌握了「棧」這一抽象數據類型的實現方法的前提下,比較容易完成。而邊標志填充演算法卻是介於這兩類之間,部分地具有它們的痕跡,演算法思想巧妙,實現起來更容易。
在編程時可能需要在屏幕上畫線段,建議學生使用自己在上次實習中實現的畫線程序,也允許學生使用Turbo C的畫線函數,包括：line( )、lineto( )、linerel( )、moveto( )等；另外,在編寫種子填充程序時除了可能用到函數putpixel( )外,還要用到取屏幕上某象素顏色的函數getpixel( ),上述這些函數的具體使用方法可參考Turbo C使用手冊,也可查看Turbo C的聯機幫助。請注意,在Turbo C圖形模式下,設備坐標系原點在屏幕左上角,X軸正方向向右,Y軸正方向向下。