首页 > 代码库 > 计算机图形学 有效边表填充算法（6）
计算机图形学 有效边表填充算法（6）
作者：卿笃军
原文地址：http://blog.csdn.net/qingdujun/article/details/40154077
本文通过一个完整的实例，展示多边形有效边表填充算法。
1）创建CAET类
头文件：AET.h
// AET.h: interface for the CAET class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_AET_H__A7CAD03F_C111_4B1F_90F2_88E39668C107__INCLUDED_)
#define AFX_AET_H__A7CAD03F_C111_4B1F_90F2_88E39668C107__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
//有效边表数据结构定义如下:
class CAET
{
public:
CAET();
virtual ~CAET();
double x;
int yMax;
double k; //代替1/k
CAET *pNext;
};
#endif // !defined(AFX_AET_H__A7CAD03F_C111_4B1F_90F2_88E39668C107__INCLUDED_)
实现文件：AET.cpp// AET.cpp: implementation of the CAET class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "FillPolygon.h"
#include "AET.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CAET::CAET()
{
}
CAET::~CAET()
{
}
2）创建CBucket类头文件：Bucket.h
// Bucket.h: interface for the CBucket class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_BUCKET_H__F1ED22A9_3004_4C3A_8710_AD025BEC063C__INCLUDED_)
#define AFX_BUCKET_H__F1ED22A9_3004_4C3A_8710_AD025BEC063C__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "aet.h"
//桶的数据结构定义如下:
class CBucket
{
public:
CBucket();
virtual ~CBucket();
int ScanLine; //扫描线
CAET *p; //桶上的边表指针
CBucket *pNext;
};
#endif // !defined(AFX_BUCKET_H__F1ED22A9_3004_4C3A_8710_AD025BEC063C__INCLUDED_)
实现文件：Bucket.cpp// Bucket.cpp: implementation of the CBucket class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "FillPolygon.h"
#include "Bucket.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CBucket::CBucket()
{
}
CBucket::~CBucket()
{
}
3）创建CFillPolygon类头文件：FillPolygon.h
// FillPolygon.h: interface for the CFillPolygon class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_FILLPOLYGON_H__18C16134_AA95_46FE_B223_DD5CF4ECAEC0__INCLUDED_)
#define AFX_FILLPOLYGON_H__18C16134_AA95_46FE_B223_DD5CF4ECAEC0__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#define Number 7 //闭合多边形顶点个数，顶点存放在二维数组Point[Number]中
#include "AET.h"
#include "Bucket.h"
//有效边表法多边形填充
class CFillPolygon
{
public:
CFillPolygon();
virtual ~CFillPolygon();
void CreatBucket(); //建立桶结点
void CreatEdge(); //构造边表
void InsertEdge(CAET *edge); //插入临时边表
CAET* EdgeSort(); //对边表进行排序
void PolygonFill(CClientDC *dc, COLORREF rgb); //多边形填充
void ShowPolygon(CDC *pDC); //将7个顶点连接起来
protected:
CPoint Point[Number]; //多边形顶点
COLORREF GetColor; //调色板
CBucket *HeadB, *CurrentB; //桶的头结点和当前结点
CAET Edge[Number], *HeadE, *CurrentE, *T1, *T2;//有效边表的结点
};
#endif // !defined(AFX_FILLPOLYGON_H__18C16134_AA95_46FE_B223_DD5CF4ECAEC0__INCLUDED_)
实现文件：FillPolygon.cpp// FillPolygon.cpp: implementation of the CFillPolygon class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "EdgeTable.h"
#include "FillPolygon.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
#define ROUND(a) int(a+0.5)//四舍五入
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CFillPolygon::CFillPolygon()
{
//设置多边形的7个顶点
Point[0]=CPoint(550,400);//P0
Point[1]=CPoint(350,600);//P1
Point[2]=CPoint(250,350);//P2
Point[3]=CPoint(350,50); //P3
Point[4]=CPoint(500,250);//P4
Point[5]=CPoint(600,50); //P5
Point[6]=CPoint(800,450);//P6
}
CFillPolygon::~CFillPolygon()
{
}
void CFillPolygon::CreatBucket()//建立空桶结点，尚未连接边表
{
int i,ScanMin,ScanMax;
ScanMax=ScanMin=Point[0].y;
for(i=1;i<Number;i++) //确定扫描线的最小值和最大值
{
if(Point[i].y<ScanMin)
{
ScanMin=Point[i].y; //扫描线的最小值
}
if(Point[i].y>ScanMax)
{
ScanMax=Point[i].y; //扫描线的最大值
}
}
for(i=ScanMin;i<=ScanMax;i++) //建立桶结点(和创建单链表类似)
{
if(ScanMin==i) //桶头结点
{
HeadB=new CBucket; //建立桶的头结点
CurrentB=HeadB; //CurrentB为Bucket当前结点指针
CurrentB->ScanLine=ScanMin;
}
else //建立桶的其它结点
{
CurrentB->pNext=new CBucket;//新建一个桶结点
CurrentB=CurrentB->pNext;//使CurrentB指向新建的桶结点
CurrentB->ScanLine=i;
}
CurrentB->p=NULL; //没有连接边链表
CurrentB->pNext=NULL;
}
}
void CFillPolygon::CreatEdge()//如[P121图4-28]，构造边表（边表，相当于该边“最低处”的有效边表）,同时连接桶表
{
for(int i=0;i<Number;i++) //访问每个顶点
{
CurrentB=HeadB; //从桶链表的头结点开始循环
int j=i+1; //边的第二个顶点，Point[i]和Point[j]构成边
if(j==Number) j=0; //保证多边形的闭合
if(Point[j].y>Point[i].y) //终点比起点高
{
while(CurrentB->ScanLine!=Point[i].y)//在桶内寻找该边的yMin
{
CurrentB=CurrentB->pNext;//移到下一个桶结点
}
Edge[i].x=Point[i].x; //扫描线与边的x交点
Edge[i].yMax=Point[j].y; //线段最高点y值
Edge[i].k=double((Point[j].x-Point[i].x))/(Point[j].y-Point[i].y);//代表1/k
Edge[i].pNext=NULL;
}
if(Point[j].y<Point[i].y)//终点比起点低
{
while(CurrentB->ScanLine!=Point[j].y)
{
CurrentB=CurrentB->pNext;
}
Edge[i].x=Point[j].x;
Edge[i].yMax=Point[i].y;
Edge[i].k=double((Point[i].x-Point[j].x))/(Point[i].y-Point[j].y);
Edge[i].pNext=NULL;
}
CurrentE=CurrentB->p; //获得桶上链接边表的地址
if(CurrentB->p==NULL) //当前桶结点上没有链接边结点
{
CurrentE=&Edge[i]; //赋边的起始地址
CurrentB->p=CurrentE;//第一个边结点直接连接到对应的桶中
}
else
{
while(CurrentE->pNext!=NULL)//如果当前边已连有边结点
{
CurrentE=CurrentE->pNext;//移动指针到当前边的最后一个边结点
}
CurrentE->pNext=&Edge[i];//把当前边接上去
}
}
CurrentB=NULL;
CurrentE=NULL;
}
void CFillPolygon::InsertEdge(CAET *edge)//插入临时边表
{
T1=HeadE;
if(T1==NULL) //边表为空,将边表置为TempEdge
{
T1=edge;
HeadE=T1;
}
else
{
while(T1->pNext!=NULL) //边表不为空,将TempEdge连在该边之后
{
T1=T1->pNext;
}
T1->pNext=edge;
}
}
CAET* CFillPolygon::EdgeSort()//对边表进行排序，（x|Ymin，表示Ymin处的x值）
{
T1=HeadE;
if(T1==NULL)
{
return NULL;
}
if(T1->pNext==NULL) //如果该边表没有再连边表
{
return NULL; //桶结点只有一条边，不需要排序
}
else
{
if(T1->pNext->x<T1->x || (T1->pNext->x==T1->x && T1->pNext->k<T1->k)) //边表按x，1/k值排序
{
T2=T1->pNext;
T1->pNext=T2->pNext;
T2->pNext=T1;
HeadE=T2;
}
T2=HeadE;
T1=HeadE->pNext;
while(T1->pNext!=NULL) //继续两两比较相连的边表的x,1/k值,进行排序
{
if(T1->pNext->x<T1->x || (T1->pNext->x==T1->x && T1->pNext->k<T1->k))
{
T2->pNext=T1->pNext;
T1->pNext=T1->pNext->pNext;
T2->pNext->pNext=T1;
T2=T2->pNext;
}
else
{
T2=T1;
T1=T1->pNext;
}
}
}
return HeadE;
}
void CFillPolygon::ShowPolygon(CDC *pDC) //将7个顶点连接起来
{
pDC->Polygon(Point,7);//绘制多边形
//输出多边形的顶点编号
pDC->TextOut(550,410,"P0");
pDC->TextOut(350,600,"P1");
pDC->TextOut(230,340,"P2");
pDC->TextOut(350,30,"P3");
pDC->TextOut(490,220,"P4");
pDC->TextOut(600,30,"P5");
pDC->TextOut(805,450,"P6");
}
void CFillPolygon::PolygonFill(CClientDC *dc, COLORREF rgb)//多边形填充
{
CAET *DelE=NULL;
CBucket *DelB=NULL;
HeadE=NULL;
for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->pNext)//访问所有桶结点
{
for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->pNext)//访问桶中排序前的边结点
{
//创建一个临时边结点
CAET *TempEdge=new CAET;
TempEdge->x=CurrentE->x;
TempEdge->yMax=CurrentE->yMax;
TempEdge->k=CurrentE->k;
TempEdge->pNext=NULL;
InsertEdge(TempEdge); //将该边插入临时CAET表
}
T1=EdgeSort(); //使得边表按照x，1/k递增的顺序存放（由于CreatEdge创建时是无序的）
if(T1==NULL)
{
return;
}
//根据ymax抛弃扫描完的边结点（局部最高点和扫描线重合，则抛弃）
while(CurrentB->ScanLine>=T1->yMax)//放弃该结点，CAET表指针后移（下闭上开）
{
DelE=T1;
T1=T1->pNext;
HeadE=T1;
delete DelE; //释放空间
DelE=NULL;
if(HeadE==NULL) //T1==NULL
{
return;
}
}
if(T1->pNext!=NULL)
{
T2=T1;
T1=T2->pNext;
}
while(T1!=NULL)
{
if(CurrentB->ScanLine>=T1->yMax)//跳过一个结点
{
T2->pNext=T1->pNext;
T1->pNext=NULL;
T1=T2->pNext;
}
else
{
T2=T1;
T1=T2->pNext;
}
}
BOOL isfill=false; //设置一个BOOL变量isfill，初始值为假
double xb,xe; //扫描线的起点和终点
for(T1=HeadE;T1!=NULL;T1=T1->pNext)//填充扫描线和多边形相交的区间
{
if(isfill==false)
{
xb=T1->x;
isfill=true; //每访问一个结点,把isfill值取反一次
}
else //如果isfill值为真，则填充从当前结点的x值开始到下一结点的x值结束的区间
{
xe=T1->x-1; //左闭右开
for(double x=xb;x<=xe;x++)
dc->SetPixel(ROUND(x),CurrentB->ScanLine,rgb);//填充语句
//Sleep(1); //延时1ms,提高填充过程的可视性
isfill=false;
}
}
for(T1=HeadE;T1!=NULL;T1=T1->pNext)//边连贯性
{
T1->x=T1->x+T1->k; //x=x+1/k
}
}
//释放边表空间
while (HeadE!=NULL)
{
DelE=HeadE;
HeadE=HeadE->pNext;
delete DelE;
}
DelE=NULL;
//释放桶表空间
while (HeadB!=NULL)
{
DelB=HeadB;
HeadB=HeadB->pNext;
delete DelB;
}
DelB=NULL;
}4）工程CEdgeTableView类头文件：EdgeTableView.h
// EdgeTableView.h : interface of the CEdgeTableView class
//
/////////////////////////////////////////////////////////////////////////////
#if !defined(AFX_EDGETABLEVIEW_H__6908D229_1F3E_40E1_BB66_41E93BA625D9__INCLUDED_)
#define AFX_EDGETABLEVIEW_H__6908D229_1F3E_40E1_BB66_41E93BA625D9__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "FillPolygon.h"
class CEdgeTableView : public CView
{
protected: // create from serialization only
CEdgeTableView();
DECLARE_DYNCREATE(CEdgeTableView)
// Attributes
public:
CEdgeTableDoc* GetDocument();
// Operations
public:
private:
CFillPolygon *pFill; //有效边表法多边形填充
COLORREF rgb; //填充颜色
// Overrides
// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CEdgeTableView)
public:
virtual void OnDraw(CDC* pDC); // overridden to draw this view
virtual BOOL PreCreateWindow(CREATESTRUCT& cs);
protected:
//}}AFX_VIRTUAL
// Implementation
public:
virtual ~CEdgeTableView();
#ifdef _DEBUG
virtual void AssertValid() const;
virtual void Dump(CDumpContext& dc) const;
#endif
protected:
// Generated message map functions
protected:
//{{AFX_MSG(CEdgeTableView)
afx_msg void OnMenuFill();
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};
#ifndef _DEBUG // debug version in EdgeTableView.cpp
inline CEdgeTableDoc* CEdgeTableView::GetDocument()
{ return (CEdgeTableDoc*)m_pDocument; }
#endif
/////////////////////////////////////////////////////////////////////////////
//{{AFX_INSERT_LOCATION}}
// Microsoft Visual C++ will insert additional declarations immediately before the previous line.
#endif // !defined(AFX_EDGETABLEVIEW_H__6908D229_1F3E_40E1_BB66_41E93BA625D9__INCLUDED_)
实现文件：EdgeTableView.cpp// EdgeTableView.cpp : implementation of the CEdgeTableView class
//
#include "stdafx.h"
#include "EdgeTable.h"
#include "EdgeTableDoc.h"
#include "EdgeTableView.h"
#include "FillPolygon.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CEdgeTableView
IMPLEMENT_DYNCREATE(CEdgeTableView, CView)
BEGIN_MESSAGE_MAP(CEdgeTableView, CView)
//{{AFX_MSG_MAP(CEdgeTableView)
ON_COMMAND(IDM_MENU_FILL, OnMenuFill)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CEdgeTableView construction/destruction
CEdgeTableView::CEdgeTableView()
{
pFill = new CFillPolygon; //初始化一个对象
}
CEdgeTableView::~CEdgeTableView()
{
delete pFill;
}
BOOL CEdgeTableView::PreCreateWindow(CREATESTRUCT& cs)
{
// TODO: Modify the Window class or styles here by modifying
// the CREATESTRUCT cs
return CView::PreCreateWindow(cs);
}
/////////////////////////////////////////////////////////////////////////////
// CEdgeTableView drawing
void CEdgeTableView::OnDraw(CDC* pDC)
{
CEdgeTableDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
//将7个顶点连接起来
pFill->ShowPolygon(pDC);
}
/////////////////////////////////////////////////////////////////////////////
// CEdgeTableView diagnostics
#ifdef _DEBUG
void CEdgeTableView::AssertValid() const
{
CView::AssertValid();
}
void CEdgeTableView::Dump(CDumpContext& dc) const
{
CView::Dump(dc);
}
CEdgeTableDoc* CEdgeTableView::GetDocument() // non-debug version is inline
{
ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CEdgeTableDoc)));
return (CEdgeTableDoc*)m_pDocument;
}
#endif //_DEBUG
/////////////////////////////////////////////////////////////////////////////
// CEdgeTableView message handlers
void CEdgeTableView::OnMenuFill()
{
CClientDC dc(this);
CColorDialog ccd(rgb);
if(ccd.DoModal()==IDOK) //调用调色板选取前景色
{
rgb=ccd.GetColor();
}
RedrawWindow(); //刷新屏幕
pFill->CreatBucket(); //初始化桶
pFill->CreatEdge(); //用于建立边表
pFill->PolygonFill(&dc, rgb); //多边形填充
}
5）运行效果
原文地址：http://blog.csdn.net/qingdujun/article/details/40154077
参考文献：1）计算机图形学基础教程（Visual C++版）（第2版） 孔令德 编著
2）tmljs1988，CSDN博客，多边形有效边表填充算法，http://blog.csdn.net/tmljs1988/article/details/5985914
计算机图形学 有效边表填充算法（6）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。