发布时间 : 星期一 文章用扫描线算法实现多边形的填充更新完毕开始阅读
用扫描线算法实现多边形的填充
电信001李理 0052011
一 算法分析。
1. 基本原理：每一条扫描线与不自交多边形有偶数个交点， 如果将交点的横坐标按
升序排列，则第一二，三四…个交点之间的点为多边形内的点。所以一条扫描线上的填充过程可分为下面三个步骤： （1） 求扫描线与多边形的交点； （2） 对所求交点排序；
（3） 将交点两两配对，并填充每一段区域。
2．下面先解决第一个步骤，即求交：为了减少求交次数，我们可以利用边的连贯性（coherence）。
3．对交点的排序可在建立Edge Table 中实现，具体见程序清单。
4．数据结构：除了上《逐点判断法》中的Polygon，Point结构外，还要用到边结构 定义如下： typedef struct tEdge {
int yUpper; /* 边的上端点的y坐标值 */ float xIntersect,dxPerScan; struct tEdge * next;
}Edge;
由于程序是参考” Computer Graphics,C Version 2nd Ed “中的程序，因此先列出程序清单如下。
二 程序清单。
/********************************************************************************** Scan-Line Polygon Fill Algorithm. Referenced Program Is In
\ CopyRights 2002 By LiLi.
**********************************************************************************/ #include \#include \#define MAX 10
#define WINDOW_HEIGHT 480 typedef struct {
int x; int y;
}Point; typedef struct {
int PolygonNum; Point verteces[MAX];
}Polygon; typedef struct tEdge{
int yUpper;
float xIntersect,dxPerScan; struct tEdge * next; }Edge;
int Color; main() {int i; Polygon *P;
void ScanFill(Polygon *);
printf(\ scanf(\ for(i=0;i
{printf(\ scanf(\
printf(\ scanf(\ }
printf(\ scanf(\
P->verteces[i].x=P->verteces[0].x; P->verteces[i].y=P->verteces[0].y; ScanFill(P); getch(); }
/* Insert edge into list in order of increasing xIntersect field If the xIntersect is the same then sorting by dxPerScan */ void insertEdge(Edge *list,Edge *edge) {
Edge *p,*p1,*q=list; p=q->next; while(p!=NULL)
{if(edge->xIntersect
{p1=q;q=p;p=p->next; } }
if(q->xIntersect==edge->xIntersect&&q->dxPerScan>edge->dxPerScan) {p1->next=edge;edge->next=q; } else
{edge->next=q->next;
q->next=edge; } }
/* For an index, return y-coordinates of nonhorizontal line */ int yNext(int k,int cnt,Point *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); }
/* restore lower-y coordinate and inverse slope for each edges. Adjust and store upper-y coordinate for edges that are the lower member of a monotonically increasing or decreasing pair of edge */
void makeEdgeRec(int x1,int y1,int x2,int y2,int yComp,Edge *edge,Edge *edges[]) {
edge->dxPerScan= (float)(x2-x1)/(y2-y1); edge->xIntersect=x1; if(y2
edge->yUpper=y2; insertEdge(edges[y1],edge); }
void buildEdgeList(int cnt,Point *pts,Edge *edges[]) {
Edge *edge; int x1,y1,x2,y2; int i,yPrev=pts[cnt-2].y; x1=pts[cnt-1].x; y1=pts[cnt-1].y; for(i=0;i if(y1!=y2) /* nonhorizontal line */ {edge=(Edge*)malloc(sizeof(Edge)); if(y1 makeEdgeRec(x1,y1,x2,y2,yNext(i,cnt,pts),edge,edges); else /* down-going edge */ makeEdgeRec(x2,y2,x1,y1,yPrev,edge,edges); } yPrev=y1; x1=x2;y1=y2; } } 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->xIntersect;i putpixel((int)i,WINDOW_HEIGHT-1-scan,Color); p1=p2->next; } } void deleteAfter(Edge *q) { Edge *p=q->next; q->next=p->next; free(q); } /* Delete completed edges, Update 'xIntersect' field for others */ void updateActiveList(int scan,Edge *active) {