polyfill.cpp

关于多边形填充的C++实现

#include "stdafx.h"
#include "polyfill.h"

//定义构造函数和析构函数
CPfill::CPfill()
{
	AET=0;//初始化活化边表的指针为空
	maxy=0;
	miny=500;
}
CPfill::~CPfill()
{
	edge *p;
	while(AET)
	{
		p=AET;
		AET=AET->next;
		delete p;
	}
	if(edges)
		delete []edges;
}

//建立边表
void CPfill::creatET(CPoint *point,int num)
{
    int m,k;//存放该多边形经过的扫描线条数
	edge *p,*q;//存放edge结点的指针
	CPoint lowpoint,highpoint;
	m=maxy-miny+1;
	edges=new edge*[m];//按多边形经过的扫描线条数申请存放指向edge类型的空间
	for(int i=0;i<m;i++)
		edges[i]=0;
	//根据顶点的坐标建立边表
	for(i=0;i<num;i++)//在所有顶点循环
	{
		//判断边的两个顶点y值大小，并作相应处理
		if(point[i].y<point[(i+1)%num].y)
		{
			lowpoint=point[i];
			highpoint=point[(i+1)%num];
			k=point[i].y-miny;
		}
		else
		{
			lowpoint=point[(i+1)%num];
			highpoint=point[i];
			k=point[(i+1)%num].y-miny;
		}
		q=edges[k]; //把当前扫描线的头接点指针赋给变量q
		if (q) //若当前扫描线已经有表结点
			while(q->next)
				q=q->next;
		//建立一个边结点，并连接到相应扫描线的边表中
		p=new edge;
		p->y_max=highpoint.y;
		p->x=lowpoint.x;
		p->deltx=(highpoint.x-lowpoint.x)*1.0/(highpoint.y-lowpoint.y);
		p->next=NULL;
		if(q)
			q->next=p;
		else
			edges[k]=p;
	}
}
//建立活化边表,参数y为当前扫描线
void CPfill::creatAET(int y)
{
	edge *p,*q;
	p=AET;//让p指向当前活化边表
	//重新计算与当前扫描线相交的边坐标，并计入活化边表
	while(p)
	{
		p->x=p->x+p->deltx;	
		p=p->next;
	}
	//检查是否有边已经与当前扫描线没有交点，若有，则删除之
	p=q=AET;
	edge *t;
	while(p)
	{
		if(y>=p->y_max)
		{
			if(p==AET)//若头结点超出范围,则删除头结点
			{
				AET=AET->next;
				delete p;
				p=q=AET;
			}
			else 
			{
				q->next=p->next;
				t=p;
				p=p->next;
				delete t;
			}
		}
		else
		{
			q=p;
			p=p->next;
		}
	}
	//检查当前扫描线的边表中有无新的边加入，若有，则进入活化边表
	q=edges[y-miny];
	if(AET==NULL)
		AET=q;
	else
	{
		p=AET;
		while(p->next)
			p=p->next;
		p->next=q;
	}
	//对新的活化边表进行按x值递增的顺序排讯
	p=AET;
	AET=NULL;
	while(p)
	{
		q=p;
		p=p->next;
		AET=insert(AET,q);
	}
}
edge* CPfill::insert(edge *head,edge *p)
{
	edge *p1,*p2;
	if(head == 0 )
	{   
		head = p;
		p->next = 0;
        return head;
	}
	if(head->x >= p->x)
	{
	        p->next = head; 
			head = p;
	        return head;
	}
	p2 = p1 = head;
	while(p2->next && p2->x <p->x) 
	{
	        p1 = p2;  
			p2 = p2->next;
	}
	if(p2->x < p->x)   
	{
		p2->next = p;
		p->next = 0;
	}
	else
	{
		p->next = p2; 
		p1->next = p;
	}
	return head;
}
void CPfill::polyfill(CPoint *point,int num,CDC *pdc,long color)
{
	edge *p;
	int j;
	//设置绘图对象
	CPen newpen(PS_SOLID,1,color),*oldpen;
	oldpen=pdc->SelectObject(&newpen);
	//计算最小扫描线和最大扫描线
    for(int i=0;i<num;i++)
	{
		if(point[i].y>maxy)
			maxy=point[i].y;
		if(point[i].y<miny)
			miny=point[i].y;
	}
	//建立边表
	creatET(point,num);
	//扫描线填充
	for(i=miny;i<=maxy;i++)
	{
		//建立活化边表
		creatAET(i);
		p=AET;
		j=0;
		while(p)
		{
			if(j%2==0)
				pdc->MoveTo(int(p->x+0.5),i);
			if(j%2==1)
				pdc->LineTo(int(p->x+0.5),i);
			p=p->next;
			j++;
		}
	}
	pdc->SelectObject(oldpen);
}