边相关扫描线算法实现多边形填充(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);
}
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);
}
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;
}
}
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;
}
}
void deleteAfter(Edge *q)//删除不再相交的边
{
Edge *p=q->next;
q->next=p->next;
delete(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,CPoint *pts,COLORREF color,CDC *pDC)//循环重复填空
{
// TODO: Add your command handler code here
Edge edges[WINDOW_HEIGHT], active;
int i,scan;
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;
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.本代码并非百分百原创，这里共享之，希望能够帮到有用的人