实验四、多边形填充算法
一．区域填充算法
区域填充– 对区域重新着色的过程
–将指定的颜色从种子点扩展到整个区域的过程
–区域填充算法要求区域是连通的
连通性： 4连通、8连通
堆栈结构实现种子算法,四向算法:
1、种子象素压入堆栈
2、若堆栈非空，即有区域中象素在堆栈中，做如下循环：
A.栈顶象素出栈；
B.将出栈象素置为多边开颜色。
C.按左、上、右、下四个方向左右顺序检查与出栈象素相邻 的四个象素，若其中某象素不在边界置为多边形颜色，则将该象素推入堆栈。
算法特点：简单。
问题：算法是深度递归的，效益低。要求很大的存储空间来实现堆栈。
二．****算法实现
// 区域填充算法View.cpp : implementation of the CMyView class
//
include "stdafx.h"
include "区域填充算法.h"
include "区域填充算法Doc.h"
include "区域填充算法View.h"
ifdef _DEBUG
define new DEBUG_NEW
undef THIS_FILE
static char THIS_FILE[] = FILE;
endif
/////////////////////////////////////////////////////////////////////////////
// CMyView
IMPLEMENT_DYNCREATE(CMyView, CView)
BEGIN_MESSAGE_MAP(CMyView, CView)
//{{AFX_MSG_MAP(CMyView)
// NOTE - the ClassWizard will add and remove mapping macros here.
// DO NOT EDIT what you see in these blocks of generated code!
//}}AFX_MSG_MAP
// Standard printing commands
ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CMyView construction/destruction
CMyView::CMyView()
{
stack_top=0;
}
CMyView::~CMyView()
{
}
BOOL CMyView::PreCreateWindow(CREATESTRUCT& cs)
{
// TODO: Modify the Window class or styles here by modifying
// the CREATESTRUCT cs
return CView::PreCreateWindow(cs);
}
/////////////////////////////////////////////////////////////////////////////
// CMyView drawing
void CMyView::OnDraw(CDC* pDC)
{
CMyDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
//定义画笔颜色
CPen PenRed(PS_SOLID,1,RGB(255,0,0));//定义红色笔
CPen PenBlue(PS_SOLID,1,RGB(0,0,255));//定义蓝色笔
int x,y;
//用蓝色笔画出多变形的边界
pDC->SelectObject(&PenBlue);
POINT polygon[5]={{300,120},{390,160},{430,320},{180,300},{150,240}};
pDC->Polygon(polygon,5);
//定义种子位置，背景色oldcolor和填充色newcolor
x=300;y=121;
COLORREF newcolor=RGB(255,0,0);
COLORREF oldcolor=RGB(255,255,255);
//调用扫描线填充算法程序
floodfill4(x,y, oldcolor,newcolor);
}
/////////////////////////////////////////////////////////////////////////////
// CMyView printing
BOOL CMyView::OnPreparePrinting(CPrintInfo* pInfo)
{
// default preparation
return DoPreparePrinting(pInfo);
}
void CMyView::OnBeginPrinting(CDC* /pDC/, CPrintInfo* /pInfo/)
{
// TODO: add extra initialization before printing
}
void CMyView::OnEndPrinting(CDC* /pDC/, CPrintInfo* /pInfo/)
{
// TODO: add cleanup after printing
}
/////////////////////////////////////////////////////////////////////////////
// CMyView diagnostics
ifdef _DEBUG
void CMyView::AssertValid() const
{
CView::AssertValid();
}
void CMyView::Dump(CDumpContext& dc) const
{
CView::Dump(dc);
}
CMyDoc* CMyView::GetDocument() // non-debug version is inline
{
ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMyDoc)));
return (CMyDoc*)m_pDocument;
}
endif //_DEBUG
/////////////////////////////////////////////////////////////////////////////
// CMyView message handlers
int CMyView::stackpop()
{
int val;
val=stack[stack_top];
stack_top=stack_top-1;
return val;
}
void CMyView::stackpush(int p_xy)
{
stack_top+=1;
stack[stack_top]=p_xy;
}
int CMyView::isstackempty()
{
if (stack_top>0)
return 1;
else
return 0;
}
void CMyView::setstackempty()
{
int i;
for(i=0;i<=stack_top;i++)
stack[i]=0;
stack_top=0;
}
void CMyView::floodfill4(int x, int y, COLORREF oldcolor, COLORREF newcolor)
{
CDC * pDC=GetDC();
int xl,xr,x0,xnextspan;
bool spanNeedFill;
//将栈清空
setstackempty();
//种子入栈
stackpush(x);
stackpush(y);
while(isstackempty()!=0)
{
//栈顶出栈，注意出栈顺序
y= stackpop();
x= stackpop();
pDC->SetPixel(x,y,newcolor);
x0=x+1;
while(pDC->GetPixel(x0,y)==oldcolor) //向右填充
{
pDC->SetPixel(x0,y,newcolor);
x0++;
}
xr = x0-1; //最右元素
x0 = x-1;
while(pDC->GetPixel(x0,y)==oldcolor) //向左填充
{
pDC->SetPixel(x0,y,newcolor);
x0--;
}
xl = x0+1; //最左元素
//处理上面一条扫描线
x0 = xl;
y = y+1;
while (x0<=xr)
{
spanNeedFill=FALSE; //while((pDC->GetPixel(x0,y)!=RGB(0,0,255))&&(pDC->GetPixel(x0,y)!=newcolor)&&(x0<xr))
while (pDC->GetPixel(x0,y)==oldcolor)
{ if (spanNeedFill==FALSE) spanNeedFill=TRUE;
x0++;
}
if(spanNeedFill)
{
//if ((x0==xr)&&(pDC->GetPixel(x0,y)!=RGB(0,0,255))&&(pDC->GetPixel(x0,y)!=newcolor))
if (x0==xr)
{ stackpush(x0);
stackpush(y);}
else
{stackpush(x0-1);
stackpush(y);}
spanNeedFill=FALSE;
} //end if
xnextspan=x0;
while(pDC->GetPixel(x,y)!=oldcolor && x0<xr) x0++;
if (xnextspan==x0) x0++;
}//End of while(x0<=xr)
}//End of while(!isstackempty())
}
三．****截图效果
[图片上传失败...(image-16aaee-1533085074373)]
