边相关扫描线算法实现多边形填充(VC)



很久没有更新计算机图形学的东西了,这几天遇到一些问题,各种问题,也懒得去说什么了。废话不多说什么了,今天给出的是边相关扫描线算法的实现。算法原理也不多说了,其实说我也说不清楚,下面直接给出边相关算法的实现代码,所有的代码在VS2008中编译通过。我把代码打包了一个函数,需要用到的人可以直接复制,详细使用方法请见后面的说明。

代码如下:

typedef struct tEdge

{

int yUpper;                        //y坐标

float xIntersect,dxPerScan;        //xIntersect为点的x坐标,dxPerScan为为直线斜率的倒数

struct tEdge *next;                //

}Edge;

void insertEdge(Edge *list, Edge *edge)  //将扫描的边以X的升序排序(插入边且进行排序)

{

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, CPoint *pts)//计算下一条非水平线的Y值

{

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);

}

&nbsp;

void makeEdgeRec(CPoint lower, CPoint 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);

}

&nbsp;

void buildEdgeList(int cnt, CPoint *pts, Edge *edges[])//建立有序边表

{

Edge *edge;

CPoint v1,v2;

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

v1.x=pts[cnt-1].x;

v1.y=pts[cnt-1].y;

for(i=0;i<cnt;i++)

{

v2=pts[i];

if(v1.y!=v2.y)

{

edge=(Edge*)new(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;

}

}

&nbsp;

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,COLORREF color,CDC *pDC)//对当前扫描线进行填充

{

Edge *p1,*p2;

int i;int dell=1000000;

p1=active->next;

//CDC *pDC = GetDC();                               //tianjia

while(p1){

p2=p1->next;

for(i=p1->xIntersect;i<p2->xIntersect;i++)

pDC->SetPixel((int) i,scan,color);

while(dell!=0){dell--;}

p1=p2->next;

}

}

&nbsp;

void deleteAfter(Edge *q)//删除不再相交的边

{

Edge *p=q->next;

q->next=p->next;

delete(p);

}

&nbsp;

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;

}

}

&nbsp;

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,CPoint *pts,COLORREF color,CDC *pDC)//循环重复填空

{

// TODO: Add your command handler code here

Edge *edges[WINDOW_HEIGHT],* active;

int i,scan;

&nbsp;

for(i=0;i<WINDOW_HEIGHT;i++){

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

edges[i]->next = NULL;

}

buildEdgeList(cnt,pts,edges);

active = (Edge *)new(Edge);

active->next=NULL;

&nbsp;

for(scan=0;scan<WINDOW_HEIGHT;scan++){

buildActiveList(scan,active,edges);

if(active->next){

fillScan(scan,active,color,pDC);

updateActiveList(scan,active);

resortActiveList(active);

}

}

}

使用方法:

1.复制上面的函数,放在需要调用之前

2.调用的时候直接 scanFill()函数,四个参数的意思分别是:点的个数,点的数组,颜色

3.本代码并非百分百原创,这里共享之,希望能够帮到有用的人
 标签: C++, 图形学, 边相关

作者  :  sailor

仅仅看明白了还不够,能把别人给讲明白了才算及格。



最新文章