实验四、多边形填充算法

一．区域填充算法

区域填充– 对区域重新着色的过程

–将指定的颜色从种子点扩展到整个区域的过程

–区域填充算法要求区域是连通的

连通性： 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)]

Image.png