fill.cpp

实现了区域填充已经其他画线功能

// Fill.cpp: implementation of the CFill class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "GraphExp.h"
#include "Fill.h"

#include "stack"
//////////////////////////
using namespace std ;
typedef stack<CPoint> STACK_Point;
////////////////////////////

#define round(x) ((x>0)?(int)(x+0.5):(int)(x-0.5))

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CFill::CFill()
{
	
}
CFill::CFill(CDC*pDoc)
{
//	pDC=pDoc;
}
CFill::~CFill()
{
	
}

/*将一条边记录插入边记录构成的链表的表头*/
void CFill::insert_et(struct edge *anedge, struct edge **p_edges)
{
	struct edge  *p;
	p=*p_edges;
	*p_edges=anedge;
	anedge->next=p;
}

/*复制一条边记录插入有效边表，维持有效边表的有序性*/

short CFill::insert_aet(struct edge *p, struct edge **p_aet)
{
	struct edge *q,*k,*l;
	if(!(q=(struct edge*)malloc(sizeof(struct edge))))
	{
		printf("\nKDIEOPE\n");
		return 0;
	}
	q->xmin=p->xmin;   q->yi=p->yi;
	q->m=p->m;     q->next=NULL;
	if(!(*p_aet)
		||((*p_aet)->yi>q->yi)||(((*p_aet)->yi==q->yi)&&((*p_aet)->m>q->m)))
	{
		l=*p_aet;   *p_aet=q;    q->next=l;
	}
	else
	{
		l=*p_aet;
		k=l->next;
		while(k&&(k->yi<q->yi))
		{
			l=k;
			k=k->next;
		}
		if(k&&(k->yi==q->yi)&&(k->m<q->m))
		{
			l=k;
			k=k->next;
		}
		l->next=q;
		q->next=k;
	}
	return (1);
}

/*从（x1,y）到（x2,y）用color色绘水平直线*/
void CFill::draw_line(CDC *pDC,int y1, int y2, int x, int color)
{
	int i;
	for(i=y1+1;i<=y2-1;i++)
		pDC->SetPixel(x,i,color);
}

/* 多边形扫描线填充：
 numpoint 是多边形顶点个数；
 points存放多边形顶点坐标（x0,y0,x1,y1......）；
 color是填充色*/

void CFill::poly_fill(CDC *pDC,int numpoint, int *points, int color)
{
	struct edge**et=NULL,*aet,*anedge,*p,*q;
	int i,j,maxx,minx,x1,y1,x2,y2,xi,znum;
	maxx=minx=points[0];
	znum=2*numpoint;
	////找出多边形各个点中的X坐标值中的最大值和最小值
	for(i=2;i<znum;i++)
	{
		if(maxx<points[i])        maxx=points[i];
		else if(minx>points[i])minx=points[i];
		i++;
	}
	if(!(et=(struct edge**)malloc((maxx-minx+1)*sizeof(struct edge*))))
	{
		printf("\nODKEIDJL\n");
		return;
	}
	for(i=0;i<maxx-minx+1;i++)   et[i]=NULL;
	x1=points[znum-2];      y1=points[znum-1];
	
	for(i=0;i<znum;i+=2)
	{
		x2=points[i];  y2=points[i+1];
		if(x1!=x2)
		{
			if(!(anedge=(struct edge*)malloc(sizeof(struct edge))))
			{
				printf("\nODKEIDJL\n");
				return;
			}
			anedge->m=(float)(y2-y1)/(x1-x2);//求出相关边的斜率
			anedge->next=NULL;
			if(x2<x1)
			{
				j=i;
				do{
					if((j+=2)>=znum) j-=znum;
				}while(points[j]==x2);
				if(points[j]<x2)  anedge->xmin=x2+1;
				else anedge->xmin=x2;
				anedge->yi=y1;
				insert_et(anedge,&et[maxx-x1]);
			}
			else 
			{
				j=i;
				do{
					if((j-=2)<0)  j+=znum;
				}while(points[j]==x1);
				if(points[j]<x1) anedge->xmin=x1+1;
				else anedge->xmin=x1;
				anedge->yi=y2;
				insert_et(anedge,&et[maxx-x2]); ///将点加入相关的边链表中 
			}
		}
		x1=x2;
		y1=y2;
	}
	aet=NULL;
	//从右往左处理各个边链表////////
	for(xi=maxx;xi>=minx;xi--)
	{
		p=et[maxx-xi];
		while(p)
		{
			if(!insert_aet(p,&aet))   goto quit;
			p=p->next;
		}
		p=aet;
		if(xi%5==0)       //控制线宽
			////填充相应的一列//////////
			while(p)
			{
				draw_line(pDC,int(p->yi),int(p->next->yi),xi,color);
				p=p->next->next;
			}
			p=aet;
			while(p&&(p->xmin==xi))
			{
				aet=p->next;
				delete p;
				p=aet;
			}
			while(p)
			{
				if(p->xmin==xi)
				{
					q->next=p->next;
					delete p;
					p=q->next;
				}
				else
				{
					p->yi+=p->m;  
					q=p;
					p=p->next;
				}
			}
	}
	///删除已经处理过的点/////
quit:
	if(et)
	{
		for(xi=maxx;xi>=minx;xi--)
		{
			q=p=et[maxx-xi];
			while(p)
			{
				q=p->next;
				free(p);
				p=q;
			}
		}
		free(et);
	}
}

////////////////扫描线填充/////////////////////
void CFill::Scan_Fill(CDC *pDC,CPoint Pseed, unsigned int boundary_color, unsigned int fill_color)
{

	int x,y,xtemp,xleft,xright;
	int span_need_fill;
	CPoint P;
	///////限制扫描线填充的屏幕范围///////////
	int m_nMaxX=GetSystemMetrics(SM_CXSCREEN);
	int m_nMaxY=GetSystemMetrics(SM_CYSCREEN);
	
	STACK_Point	station;
	station.push(Pseed);///////////扫描线种子入栈
	while(!(station.empty()))
	{
		P=station.top();
		station.pop();
		x=P.x;
		y=P.y;
		pDC->SetPixel(x,y,fill_color);
		/*向右填充*/
		//&&(xtemp<m_nMaxX)	&&(y<m_nMaxY)
		for(xtemp=x+1;(pDC->GetPixel(xtemp,y)!=boundary_color);xtemp++)
		{
			if(xtemp>=m_nMaxX)
				return;
			pDC->SetPixel(xtemp,y,fill_color);
		}
		xright=xtemp-1;//最右端像素的横坐标
		/*向左填充*/
		//&&(xtemp>0)&&(y>0)
		for(xtemp=x-1;pDC->GetPixel(xtemp,y)!=boundary_color;xtemp--)
		{
			if(xtemp<0)
				return;
			pDC->SetPixel(xtemp,y,fill_color);
		}
		xleft=xtemp+1;//最左端像素的横坐标
		/////////////////////////////
		//检查上一条扫描线
		xtemp=xleft;
		y=y+1;
		if(pDC->GetPixel(xtemp,y)==boundary_color)
			xtemp++;
		while(xtemp<=xright)
		{
			span_need_fill=0;
			//寻找待填充的区段
			//&&(xtemp<m_nMaxX)	&&(y<m_nMaxY)
			while((pDC->GetPixel(xtemp,y)!=boundary_color)&&(pDC->GetPixel(xtemp,y)!=fill_color)&&(xtemp<=xright))
			{
				span_need_fill=1;
				xtemp++;
			}
			
			if(span_need_fill==1)
			{	
				P.x=xtemp-1;
				P.y=y;
				station.push(P);
			}/*最右端像素作为种子点入栈*/
			/*继续向右检查，跳过边界像素或已填充像素*/
			//&&(xtemp<m_nMaxX)&&(y<m_nMaxY)
			xtemp++;
			while((pDC->GetPixel(xtemp,y)==boundary_color||
				pDC->GetPixel(xtemp,y)==fill_color)&&xtemp<=xright)
				xtemp++;		
		}//上一条扫描线检查完毕；
		///////////////////////////////
		//检查下一条扫描线
		xtemp=xleft;
		y=y-2;
		while(xtemp<=xright)
		{
			span_need_fill=0;
			//寻找待填充的区段&&(xtemp<m_nMaxX)&&(y<m_nMaxY)
			while(pDC->GetPixel(xtemp,y)!=boundary_color&&
				pDC->GetPixel(xtemp,y)!=fill_color&&xtemp<=xright)
			{
				span_need_fill=1;
				xtemp++;
			}
			if(span_need_fill==1)
			{	
				P.x=xtemp-1;
				P.y=y;
				station.push(P);
			}/*最右端像素作为种子点入栈*/
			/*继续向右检查，跳过边界像素或已填充像素*/
			//(xtemp<m_nMaxX)&&(y<m_nMaxY)
			xtemp++;
			while((pDC->GetPixel(xtemp,y)==boundary_color||
				pDC->GetPixel(xtemp,y)==fill_color)&&xtemp<=xright)
				xtemp++;
		}//下一条扫描线检查完毕；
		
	}
}

void CFill::Flood_Fill_8(CDC *pDC,CPoint Pseed, unsigned int old_color, unsigned int fill_color)
{
	int current;
	int x=Pseed.x;
	int y=Pseed.y;
	current=pDC->GetPixel(x,y);
	STACK_Point	station;;
	int xright,xleft,search,savex;
	CPoint P;
	station.push(Pseed);
	while(!(station.empty()))
	{
		P=station.top();
		station.pop();
		x=P.x;
		y=P.y;
		pDC->SetPixel(x,y,fill_color);
		savex=x;
		x=x+1;
		while((pDC->GetPixel(x,y)==old_color))
		{ 
			pDC->SetPixel(x,y,fill_color);  /* fill all right points */
		    x++;
		}
		xright=x-1;
		x=savex-1;
		while ((pDC->GetPixel(x,y)==old_color))
		{ 
			pDC->SetPixel(x,y,fill_color);  /* fill all left points */
		    x--;
		}
		x++;
		xleft=x;
		y=y-1;
		search=1;
		while(x<=xright)  /* search seed from left */
		{
			if(search==1)
			{
				if((pDC->GetPixel(x,y)==old_color))
				{ 
					P.x=x;
					P.y=y;
					station.push(P);      /* have searched */
					search=0;
				}
			}
			else
				if((pDC->GetPixel(x,y)==fill_color)||(pDC->GetPixel(x,y)!=old_color))
					search=1;   /* ignore other points */
				x++;
		}
		x=xleft;
		y=y+2;
		search=1;
		while(x<=xright) 
		{         /* search seed in the higher row */
			if(search==1)
			{
				if((pDC->GetPixel(x,y)==old_color))
				{ 
					P.x=x;
					P.y=y;
					station.push(P);      /* have searched */
					search=0;
				}
			}
			else
				if((pDC->GetPixel(x,y)==fill_color)||(pDC->GetPixel(x,y)!=old_color))
					search=1;   /* ignore other points */
				x++;
		}
	}
}