多边形扫描线填充算法

如果是用线填充，程序如下。如果是用点填充需要用到堆栈和系统底层库函数或者用画点函数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安装目录下再运行。

typedef struct tEdge

{ int yUpper

float xIntersect,dxPerScan

struct tEdge *next

}Edge

void insertEdge(Edge *list Edge *edge)//将结点插入边表

{

Edge *p,*q=list

p=q->next

while (p!=NULL)

{ if (edge->xIntersect<p->xIntersect) p=NULL

else { q=p p=p->next}

}

edge->next=q->next

q->next=edge

}

int yNext(int k,int cnt, dcPt *pts)//求奇异点

{

int j

if ((k+1)>(cnt-1)) j=0

else j=k+1

while (pts[k].y==pts[j].y)

if((j+1)>粗颤(cnt-1)) j=0

else j++

return (pts[j].y)

}

void makeEdgeRec(dcPt lower,dcPt upper,int yComp, Edge *edge, Edge *edges[]) //生成边表结点，并插入到边表中

{

edge->dxPerScan=(float)(upper.x-lower.x)/(upper.y-lower.y)

edge->xIntersect=lower.x

if (upper.y<yComp)

edge->yUpper=upper.y-1

else

edge->yUpper=upper.y

insertEdge(edges[lower.y],edge)

}

void buildEdgeList(int cnt,dcPt *pts, Edge *edges[])//创建边表的主体函岩察败数

{

Edge *edge

dcPt v1,v2

int i,yPrev=pts[cnt-2].y

v1.x=pts[cnt-1].xv1.y=pts[cnt-1].y

for (i=0i<cnti++)

{ v2=pts[i]

if (v1.y!=v2.y)

{ edge=(Edge *)malloc(sizeof(Edge))

if (v1.y<v2.y)

makeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges)

else makeEdgeRec(v2,v1,yPrev,edge,edges)

}

yPrev=v1.y

v1=v2

}

}

void buildActiveList(int scan,Edge * active,Edge *edges[])//建立活动边表的主题函数

{ Edge *p,*q

p=edges[scan]->next

while (p)

{ q=p->next

insertEdge(active,p)

p=q

}

}

void fillScan(int scan,Edge *active)//填充一对交点

{

Edge *p1,*p2

int i

p1=active->next

while(p1)

{

p2=p1->next

for (i=p1->xIntersecti<p2->xIntersecti++)

setPixel((int)i,scan)

p1=p2->next

}

}

void delectAfter(Edge *q)//删除链表中结点

{

Edge *p=q->next

q->next=p->next

free(p)

}

void updateActiveList(int scan,Edge *active)//填没宏充完后，更新活动边表

{

Edge *q=active,*p=active->next

while (p)

if (scan>=p->yUpper)

{

p=p->next

deleteAfter(q)

}

else

{ p->xIntersect=p->xIntersect+p->dxPerScan

q=p

p=p->next

}

}

void resortActiveList(Edge *active)//对活动边表结点重新排序

{

Edge *q,*p=active->next

active->next=NULL

while(p)

{ q=p->next

insertEdge(active,p)

p=q

}

}

void scanFill(int cnt,dcPt *pts)//多边形填充主体程序

{

Edge *edge[WINDOW_HEIGHT],*active

int i,scan

for (i=0i<WINDOW_HEIGHTi++)

{

edges[i]=(Edge *)malloc(sizeof(Edge))

edges[i]->next=NULL

}

buildEdgeList(cnt,pts,edges)

active=(Edge *)malloc (sizeof(Edge))

active->next=NULL

for(scan=0scan<WINDOW_HEIGHTscan++)

{

buildActiveList(scan,active,edges)

if (active->next)

{fillScan(sacn,active)<br/> updateActiveList(scan,active)<br/>resortActiveList(active)<br/>}

}

}

}

}

}

这是袜含从书上第99页节录下来的，试试吧！

#define SET_BIT_MACRO( a , b ) if( image[a][b] == HIGH){ \

image[a][b] = colorcnt++}

/**

* image: 影像阵列

* xs, ys: 开始位告派笑置

* color: 比对的颜色

*/

void pixelset(unsigned char image[Y_SIZE][X_SIZE], int xs, int ys, int color){

int i, j, cnt, im, ip, jm, jp

image[ys][xs] = color

while( cnt != 0 ){

cnt = 0

for(i = 0i <Y_SIZEi++){

for(j = 0j <X_SIZEj++){

if(image[i][j]==color){

im=i-1ip=i+1jm=j-1jp=j+1

if(im <0) im=0if(ip>Y_SIZE-1) ip=Y_SIZE-1

if(jm <羡巧 0) jm=0if(jp>X_SIZE-1) jp=X_SIZE-1

// 周围八个方向都找一遍

SET_BIT_MACRO( image[i][jp] )

SET_BIT_MACRO( image[im][jp] )

SET_BIT_MACRO( image[im][j] )

SET_BIT_MACRO( image[im][jm] )

SET_BIT_MACRO( image[i][jm] )

SET_BIT_MACRO( image[ip][jm] )

SET_BIT_MACRO( image[ip][j] )

SET_BIT_MACRO( image[ip][jp] )

}

}

}

}

}

---