[VIP专享]计算机图形学 有效边表填充算法实验报告

实验三计算机图形学多边形填充算法课程名称计算机图形学实验日期 2013-11-7 实验名称多边形填充算法编程成绩实验目的:熟悉多边形填充算法，掌握MFC图形编程的基本方法和调试技巧。

实验条件: 计算机;VS2008;OpenGL实验内容:1(使用MFC技术实现多边形有效边表填充算法，参考界面效果如下:// ChildView.cpp : CChildView 类的实现#include "stdafx.h"#include "demo.h"#include "ChildView.h"#include <math.h>#define Round(d) int(floor(d+0.5))//四舍五入宏定义#ifdef _DEBUG#define new DEBUG_NEW#endif// CChildViewCChildView::CChildView(){}CChildView::~CChildView(){}BEGIN_MESSAGE_MAP(CChildView, CWnd)ON_WM_PAINT()ON_WM_CREATE()ON_COMMAND(ID_DRAW_PIC, &CChildView::OnDrawPic)END_MESSAGE_MAP()// CChildView 消息处理程序BOOL CChildView::PreCreateWindow(CREATESTRUCT& cs) {if (!CWnd::PreCreateWindow(cs))return FALSE;cs.dwExStyle |= WS_EX_CLIENTEDGE;cs.style &= ~WS_BORDER;cs.lpszClass = AfxRegisterWndClass(CS_HREDRAW|CS_VREDRAW|CS_DBLCLKS,::LoadCursor(NULL, IDC_ARROW),reinterpret_cast<HBRUSH>(COLOR_WINDOW+1), NULL);return TRUE;}void CChildView::OnPaint(){CPaintDC dc(this); // 用于绘制的设备上下文// TODO: 在此处添加消息处理程序代码DrawGraph();// 不要为绘制消息而调用CWnd::OnPaint() }void CChildView::ReadPoint() //点表{P[0].x = 50; P[0].y = 100;P[1].x = -150;P[1].y = 300;P[2].x = -250;P[2].y = 50;P[3].x = -150;P[3].y = -250;P[4].x = 0; P[4].y = -50;P[5].x = 100; P[5].y = -250;P[6].x = 300; P[6].y = 150;}void CChildView::DrawPolygon(CDC *pDC) //绘制多边形边界{CLine *line = new CLine;CP2 t;for(int i = 0; i < 7; i++) //绘制多边形{if(i == 0){line->MoveTo(pDC, P[i]);t = P[i];}else{line->LineTo(pDC, P[i]);}}line->LineTo(pDC, t); //闭合多边形delete line;}void CChildView::DrawGraph() //绘制图形 {CRect rect; //定义客户区GetClientRect(&rect); //获得客户区的大小CDC *pDC = GetDC(); //定义设备上下文指针pDC->SetMapMode(MM_ANISOTROPIC); //自定义坐标系pDC->SetWindowExt(rect.Width(), rect.Height()); //设置窗口比例pDC->SetViewportExt(rect.Width(), -rect.Height()); //设置视区比例，且x轴水平向右，y轴垂直向上pDC->SetViewportOrg(rect.Width() / 2, rect.Height() / 2); //设置客户区中心为坐标系原点rect.OffsetRect(-rect.Width() / 2, -rect.Height() / 2); //矩形与客户区重合if(!bFill)DrawPolygon(pDC); //绘制多边形elseFillPolygon(pDC); //填充多边形ReleaseDC(pDC); //释放DC}void CChildView::FillPolygon(CDC *pDC) //填充多边形 {for(int i = 0; i < 7; i++) //转储顶点坐标，y坐标取为整数{P1[i].x = P[i].x;P1[i].y = Round(P[i].y);P1[i].c = CRGB(bRed / 255.0, bGreen / 255.0, bBlue / 255.0);}CFill *fill = new CFill; //动态分配内存fill->SetPoint(P1, 7); //初始化Fill对象fill->CreateBucket(); //建立桶表fill->CreateEdge(); //建立边表fill->Gouraud(pDC); //填充多边形delete fill; //撤销内存 }int CChildView::OnCreate(LPCREATESTRUCT lpCreateStruct) {if (CWnd::OnCreate(lpCreateStruct) == -1)return -1;// TODO: 在此添加您专用的创建代码bFill = FALSE;ReadPoint();return 0;}void CChildView::OnDrawPic(){// TODO: 在此添加命令处理程序代码COLORREF GetClr = RGB(0, 0, 0); //调色板颜色CColorDialog ccd(GetClr, CC_SOLIDCOLOR);if(IDOK == ccd.DoModal()) //调用颜色对话框选取填充色GetClr = ccd.GetColor();elsereturn;bRed = GetRValue(GetClr); //获取红色分量bGreen = GetGValue(GetClr); //获取绿色分量bBlue = GetBValue(GetClr); //获取蓝色分量bFill = TRUE;Invalidate();}2(使用MFC技术实现多边形边缘填充算法，参考界面效果如下:// demoView.cpp : CdemoView 类的实现#include "stdafx.h"#include "demo.h"#include "demoDoc.h"#include "demoView.h"#include <math.h>#define Round(d) int(floor(d+0.5))//四舍五入宏定义 #ifdef _DEBUG #define new DEBUG_NEW#endif// CdemoViewIMPLEMENT_DYNCREATE(CdemoView, CView)BEGIN_MESSAGE_MAP(CdemoView, CView)// 标准打印命令ON_COMMAND(ID_FILE_PRINT, &CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT, &CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_PREVIEW, &CdemoView::OnFilePrintPreview) ON_COMMAND(ID_DRAW_PIC, &CdemoView::OnDrawPic) END_MESSAGE_MAP() // CdemoView 构造/析构CdemoView::CdemoView(){// TODO: 在此处添加构造代码}CdemoView::~CdemoView(){}BOOL CdemoView::PreCreateWindow(CREATESTRUCT& cs) {// TODO: 在此处通过修改// CREATESTRUCT cs 来修改窗口类或样式return CView::PreCreateWindow(cs); }// CdemoView 绘制void CdemoView::OnDraw(CDC* /*pDC*/) {CdemoDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);if (!pDoc)return;// TODO: 在此处为本机数据添加绘制代码DrawGraph();}// CdemoView 打印void CdemoView::OnFilePrintPreview() {AFXPrintPreview(this);}BOOL CdemoView::OnPreparePrinting(CPrintInfo* pInfo){// 默认准备return DoPreparePrinting(pInfo); }void CdemoView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) {// TODO: 添加额外的打印前进行的初始化过程 }void CdemoView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) {// TODO: 添加打印后进行的清理过程 }void CdemoView::OnRButtonUp(UINT nFlags, CPoint point){ClientToScreen(&point);OnContextMenu(this, point);}void CdemoView::OnContextMenu(CWnd* pWnd, CPoint point){theApp.GetContextMenuManager()->ShowPopupMenu(IDR_POPUP_EDIT,point.x, point.y, this, TRUE);}void CdemoView::ReadPoint() //点表 {P[0].x = 50; P[0].y = 100;P[1].x = -150;P[1].y = 300;P[2].x = -250;P[2].y = 50;P[3].x = -150;P[3].y = -250;P[4].x = 0; P[4].y = -50;P[5].x = 100; P[5].y = -250;P[6].x = 300; P[6].y = 150; }void CdemoView::DrawPolygon(CDC *pDC) { for(int i = 0; i < 7; i++) //计算多边形边界{if(P[i].x > MaxX)MaxX = P[i].x;if(P[i].x < MinX)MinX = P[i].x;if(P[i].y > MaxY)MaxY = P[i].y;if(P[i].y < MinY)MinY = P[i].y;}CLine *line = new CLine;CP2 t;for(int i = 0; i < 7; i++) //绘制多边形{if(i == 0){line->MoveTo(pDC, P[i]);t = P[i];}else{line->LineTo(pDC, P[i]);}}line->LineTo(pDC, t); //闭合多边形line->MoveTo(pDC, CP2(MinX, MinY)); //绘制包围盒line->LineTo(pDC, CP2(MinX, MaxY));line->LineTo(pDC, CP2(MaxX, MaxY));line->LineTo(pDC, CP2(MaxX, MinY));line->LineTo(pDC, CP2(MinX, MinY));delete line;}void CdemoView::FillPolygon(CDC *pDC){COLORREF BClr = RGB(255, 255, 255); //背景色COLORREF FClr = GetClr; //填充色int ymin, ymax; //边的最小y值与最大y值double x, y, k; //x,y当前点，k斜率的倒数for(int i = 0; i < 7; i++) //循环多边形所有边{int j = (i + 1) % 7;k = (P[i].x - P[j].x) / (P[i].y - P[j].y); //计算/kif(P[i].y < P[j].y) //得到每条边y的最大值与最小值{ymin = Round(P[i].y);ymax = Round(P[j].y);x = P[i].x; //得到x|ymin}else{ymin = Round(P[j].y);ymax = Round(P[i].y);x = P[j].x;}for(y = ymin; y < ymax; y++) //沿每一条边循环扫描线{for(int m = Round(x); m < MaxX; m++) //对每一条扫描线与边的交点的右侧像素循环{if(FClr == pDC->GetPixel(m, Round(y))) //如果是填充色pDC->SetPixelV(m, Round(y), BClr); //置为背景色elsepDC->SetPixelV(m, Round(y), FClr); //置为填充色}x += k; //计算下一条扫描线的x起点坐标}}}void CdemoView::DrawGraph() //绘制图形 {CRect rect; //定义客户区GetClientRect(&rect); //获得客户区的大小CDC *pDC = GetDC(); //定义设备上下文指针pDC->SetMapMode(MM_ANISOTROPIC); //自定义坐标系pDC->SetWindowExt(rect.Width(), rect.Height()); //设置窗口比例pDC->SetViewportExt(rect.Width(), -rect.Height()); //设置视区比例，且x轴水平向右，y轴垂直向上pDC->SetViewportOrg(rect.Width() / 2, rect.Height() / 2); //设置客户区中心为坐标系原点rect.OffsetRect(-rect.Width() / 2, -rect.Height() / 2); //矩形与客户区重合if(!bFill)DrawPolygon(pDC); //绘制多边形elseFillPolygon(pDC); //填充多边形ReleaseDC(pDC); //释放DC }// CdemoView 诊断#ifdef _DEBUGvoid CdemoView::AssertValid() const{CView::AssertValid();}void CdemoView::Dump(CDumpContext& dc) const{CView::Dump(dc);}CdemoDoc* CdemoView::GetDocument() const // 非调试版本是内联的 { ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CdemoDoc)));return (CdemoDoc*)m_pDocument;}#endif //_DEBUG// CdemoView 消息处理程序void CdemoView::OnInitialUpdate(){CView::OnInitialUpdate();// TODO: 在此添加专用代码和/或调用基类bFill = FALSE;ReadPoint();GetClr = RGB(0,0,0);MinX = MaxX = P[0].x;MinY = MaxY = P[0].y;}void CdemoView::OnDrawPic(){// TODO: 在此添加命令处理程序代码CColorDialog ccd(GetClr, CC_SOLIDCOLOR);if(IDOK == ccd.DoModal()) //调用颜色对话框选取填充色GetClr = ccd.GetColor();elsereturn;bFill = TRUE;Invalidate(FALSE);}3.使用MFC技术实现种子填充算法，参考界面效果如下:// demoView.cpp : CdemoView 类的实现 #include "stdafx.h"#include "demo.h"#include "demoDoc.h"#include "demoView.h"#include <math.h>#define Round(d) int(floor(d+0.5))//四舍五入宏定义 #ifdef _DEBUG #define new DEBUG_NEW#endif// CdemoViewIMPLEMENT_DYNCREATE(CdemoView, CView) BEGIN_MESSAGE_MAP(CdemoView, CView)// 标准打印命令ON_COMMAND(ID_FILE_PRINT, &CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT, &CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_PREVIEW, &CdemoView::OnFilePrintPreview) ON_WM_LBUTTONDOWN()ON_COMMAND(ID_DRAW_PIC, &CdemoView::OnDrawPic)END_MESSAGE_MAP()// CdemoView 构造/析构CdemoView::CdemoView(){// TODO: 在此处添加构造代码bFill = FALSE;SeedClr = RGB(255, 0, 0);}CdemoView::~CdemoView(){}BOOL CdemoView::PreCreateWindow(CREATESTRUCT& cs) { // TODO: 在此处通过修改// CREATESTRUCT cs 来修改窗口类或样式return CView::PreCreateWindow(cs); }// CdemoView 绘制void CdemoView::OnDraw(CDC* /*pDC*/) {CdemoDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);if (!pDoc)return;// TODO: 在此处为本机数据添加绘制代码DrawGraph();}// CdemoView 打印void CdemoView::OnFilePrintPreview() { AFXPrintPreview(this);}BOOL CdemoView::OnPreparePrinting(CPrintInfo* pInfo) {// 默认准备return DoPreparePrinting(pInfo);}void CdemoView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) {// TODO: 添加额外的打印前进行的初始化过程}void CdemoView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) { // TODO: 添加打印后进行的清理过程}void CdemoView::OnRButtonUp(UINT nFlags, CPoint point){ClientToScreen(&point);OnContextMenu(this, point);}void CdemoView::OnContextMenu(CWnd* pWnd, CPoint point) {theApp.GetContextMenuManager()->ShowPopupMenu(IDR_POPUP_EDIT,point.x, point.y, this, TRUE);}// CdemoView 诊断#ifdef _DEBUGvoid CdemoView::AssertValid() const{CView::AssertValid();}void CdemoView::Dump(CDumpContext& dc) const{CView::Dump(dc);}CdemoDoc* CdemoView::GetDocument() const // 非调试版本是内联的 { ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CdemoDoc)));return (CdemoDoc*)m_pDocument;}#endif //_DEBUGvoid CdemoView::DrawGraph()//绘制图形{CDC *pDC = GetDC(); //定义设备上下文指针GetClientRect(&rect); //获得客户区的大小pDC->SetMapMode(MM_ANISOTROPIC); //自定义坐标系pDC->SetWindowExt(rect.Width(), rect.Height()); //设置窗口比例pDC->SetViewportExt(rect.Width(), -rect.Height()); //设置视区比例，且x轴水平向右，y轴垂直向上pDC->SetViewportOrg(rect.Width() / 2, rect.Height() / 2); //设置客户区中心为坐标系原点rect.OffsetRect(-rect.Width() / 2, -rect.Height() / 2); //矩形与客户区重合CDC MemDC;//内存DCCBitmap NewBitmap, *pOldBitmap; //内存中承载图像的位图MemDC.CreateCompatibleDC(pDC); //建立与屏幕pDC兼容的MemDCNewBitmap.LoadBitmap(IDB_BITMAP1); //导入空心汉字位图pOldBitmap = MemDC.SelectObject(&NewBitmap);//将兼容位图选入MemDC MemDC.SetMapMode(MM_ANISOTROPIC); //MemDC自定义坐标系MemDC.SetWindowExt(rect.Width(), rect.Height());MemDC.SetViewportExt(rect.Width(), -rect.Height());MemDC.SetViewportOrg(rect.Width() / 2, rect.Height() / 2);pDC->BitBlt(-rect.Width() / 2, -rect.Height() / 2, rect.Width(), rect.Height(), &MemDC,-rect.Width() / 2, -rect.Height() / 2, SRCCOPY);//将内存位图拷贝到屏幕if(bFill)CharFill(pDC); //填充空心汉字MemDC.SelectObject(pOldBitmap); //恢复位图NewBitmap.DeleteObject(); //删除位图MemDC.DeleteDC(); //删除MemDCReleaseDC(pDC); //释放DC }void CdemoView::CharFill(CDC *pDC) //文字填充函数 {COLORREF BoundaryClr = RGB(0,0,0); //边界色BOOL bSpanFill;pHead = new CStackNode; //建立栈结点pHead->pNext = NULL; //栈头结点的指针域总为空Push(Seed); //种子像素入栈int x, y, x0 = Round(Seed.x), y0 = Round(Seed.y);//x，y用于判断种子与图形的位置关系x = x0 - 1;while(pDC->GetPixel(x, y0) != BoundaryClr && pDC->GetPixel(x, y0) != SeedClr )//左方判断{x--;if(x <= -rect.Width() / 2){MessageBox(L"种子不在图形之内", L"警告");//到达客户区最左端return;}}y = y0 + 1;while(pDC->GetPixel(x0, y) != BoundaryClr && pDC->GetPixel(x0, y) != SeedClr)//上方判断{y++;if(y >= rect.Height() / 2)//到达客户区最上端{MessageBox(L"种子不在图形之内", L"警告");return;}}x = x0 + 1;while(pDC->GetPixel(x, y0) != BoundaryClr && pDC->GetPixel(x, y0) != SeedClr)//右方判断{x++;if(x >= rect.Width() / 2)//到达客户区最右端{MessageBox(L"种子不在图形之内", L"警告");return;}}y = y0 - 1;while(pDC->GetPixel(x0, y) != BoundaryClr && pDC->GetPixel(x0, y) != SeedClr)//下方判断{y--;if(y <= -rect.Height() / 2)//到达客户区最下端{MessageBox(L"种子不在图形之内", L"警告");return;}}double xleft, xright;//区间最左端与最右端像素CP2 PopPoint, PointTemp;while(pHead->pNext != NULL)//如果栈不为空{Pop(PopPoint);if(pDC->GetPixel(Round(PopPoint.x), Round(PopPoint.y)) == SeedClr) continue;// 分别向左和向右填充扫描线PointTemp = PopPoint;while(pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != BoundaryClr &&pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) {pDC->SetPixelV(Round(PointTemp.x), Round(PointTemp.y), SeedClr);PointTemp.x++;}xright = PointTemp.x - 1;PointTemp.x = PopPoint.x - 1;while(pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != BoundaryClr &&pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) {pDC->SetPixelV(Round(PointTemp.x), Round(PointTemp.y), SeedClr);PointTemp.x--;}xleft=PointTemp.x + 1;//处理上一条扫描线PointTemp.x = xleft;PointTemp.y = PointTemp.y + 1;while(PointTemp.x < xright){bSpanFill = FALSE;while(pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != BoundaryClr &&pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) {bSpanFill = TRUE;PointTemp.x++;}if(bSpanFill){if(PointTemp.x == xright && pDC->GetPixel(Round(PointTemp.x),Round(PointTemp.y)) != BoundaryClr && pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) PopPoint = PointTemp;elsePopPoint.x = PointTemp.x - 1; PopPoint.y = PointTemp.y;Push(PopPoint);bSpanFill = FALSE;}while((pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) == BoundaryClr &&PointTemp.x < xright) || (pDC->GetPixel(Round(PointTemp.x),Round(PointTemp.y)) == SeedClr &&PointTemp.x < xright))PointTemp.x++;}//处理下一条扫描线PointTemp.x = xleft;PointTemp.y = PointTemp.y - 2;while(PointTemp.x < xright){bSpanFill = FALSE;while(pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != BoundaryClr &&pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) {bSpanFill = TRUE;PointTemp.x++;}if(bSpanFill){if(PointTemp.x == xright && pDC->GetPixel(Round(PointTemp.x),Round(PointTemp.y)) != BoundaryClr && pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) PopPoint = PointTemp;elsePopPoint.x = PointTemp.x - 1; PopPoint.y = PointTemp.y;Push(PopPoint);bSpanFill=FALSE;}while((pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) == BoundaryClr &&PointTemp.x < xright) || (pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) == SeedClr &&PointTemp.x < xright))PointTemp.x++;}}delete pHead;pHead = NULL;}void CdemoView::Push(CP2 point)//入栈函数{pTop = new CStackNode;pTop->PixelPoint = point;pTop->pNext = pHead->pNext;pHead->pNext = pTop;}void CdemoView::Pop(CP2 &point) //出栈函数{if(pHead->pNext != NULL){pTop = pHead->pNext;pHead->pNext = pTop->pNext;point = pTop->PixelPoint;delete pTop;}}// CdemoView 消息处理程序void CdemoView::OnLButtonDown(UINT nFlags, CPoint point) {// TODO: 在此添加消息处理程序代码和/或调用默认值Seed = CP2(point.x - rect.Width() / 2, rect.Height() / 2 - point.y); //选择种子位置Invalidate(FALSE);CView::OnLButtonDown(nFlags, point);}void CdemoView::OnDrawPic(){// TODO: 在此添加命令处理程序代码CColorDialog ccd(SeedClr, CC_SOLIDCOLOR);if(IDOK == ccd.DoModal())//调用颜色对话框选取填充色SeedClr = ccd.GetColor();elsereturn;if(IDOK == MessageBox(L"请在空心字体内单击鼠标左键!", L"提示",MB_OKCANCEL))bFill = TRUE;elsereturn;}实验总结:上机做实验主要是看明白程序，现在来说，自己还不会自己编程，还是下载老师的实例程序看代码，然后运行看结果，自己再去琢磨理解程序。

计算机图形学课程设计设计题目改进的有效边表算法对多边形的填充学院名称信息科学与技术学院专业名称计算机科学与技术学生姓名刘柯学生学号201213030112任课教师梅占勇设计（论文）成绩教务处制2015年9 月28 日目录一、设计内容与要求 (3)1.1设计题目 (3)1.2 设计内容 (3)1.3 设计目标 (3)二、总体设计 (3)2.1 多边形的表示 (3)2.2 x-扫描线算法 (4)2.3 改进的有效边表算法 (4)2.3.1 改进的有效边表算法 (4)2.3.2 有效边表 (5)2.3.3 边表 (6)三、详细设计 (8)3.1 改进的有效边表算法的实现 (8)3.2 有效边表算法程序流程图 (9)四、测试结果 (9)五、总结 (15)六、源代码 (15)参考文献 (26)一、设计内容与要求1.1设计题目用改进的有效边表算法实现多边形的填充1.2 设计内容使用OpenGL实现用改进的有效边表算法填充多边形1.3 设计目标参照课本上改进的有效边表算法的思想，实现该算法的C语言代码，并用该算法搭配OpenGL以像素点的方式绘制出给定顶点坐标的多边形。

二、总体设计2.1 多边形的表示在计算机图形学中，多边形有2种重要的表示方法：顶点表示和点阵表示。

顶点表示用多边形的顶点序列来刻画多边形，这种方法直观、几何意义强，占用内存少，应用普遍，但它没有明确指出哪些像素在多边形内，故不能直接用于面着色。

点阵表示用位于多边形内的像素的集合来刻画多边形。

这种表示法虽然失去了许多重要的几何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。

大多数图形应用系统采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转换或多边形的填充。

即从多边形的顶点信息出发，求出位于其内部的各个像素，并将其颜色值写入帧缓存的相应单元中。

2.2 x-扫描线算法x-扫描线算法的基本思想是，按照扫描线的顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。

实验三计算机图形学多边形填充算法课程名称计算机图形学实验日期 2013-11-7 实验名称多边形填充算法编程成绩实验目的:熟悉多边形填充算法，掌握MFC图形编程的基本方法和调试技巧。

实验条件: 计算机;VS2008;OpenGL实验内容:1(使用MFC技术实现多边形有效边表填充算法，参考界面效果如下:// ChildView.cpp : CChildView 类的实现#include "stdafx.h"#include "demo.h"#include "ChildView.h"#include <math.h>#define Round(d) int(floor(d+0.5))//四舍五入宏定义#ifdef _DEBUG#define new DEBUG_NEW#endif// CChildViewCChildView::CChildView(){}CChildView::~CChildView(){}BEGIN_MESSAGE_MAP(CChildView, CWnd)ON_WM_PAINT()ON_WM_CREATE()ON_COMMAND(ID_DRAW_PIC, &CChildView::OnDrawPic)END_MESSAGE_MAP()// CChildView 消息处理程序BOOL CChildView::PreCreateWindow(CREATESTRUCT& cs) {if (!CWnd::PreCreateWindow(cs))return FALSE;cs.dwExStyle |= WS_EX_CLIENTEDGE;cs.style &= ~WS_BORDER;cs.lpszClass = AfxRegisterWndClass(CS_HREDRAW|CS_VREDRAW|CS_DBLCLKS,::LoadCursor(NULL, IDC_ARROW),reinterpret_cast<HBRUSH>(COLOR_WINDOW+1), NULL);return TRUE;}void CChildView::OnPaint(){CPaintDC dc(this); // 用于绘制的设备上下文// TODO: 在此处添加消息处理程序代码DrawGraph();// 不要为绘制消息而调用CWnd::OnPaint() }void CChildView::ReadPoint() //点表{P[0].x = 50; P[0].y = 100;P[1].x = -150;P[1].y = 300;P[2].x = -250;P[2].y = 50;P[3].x = -150;P[3].y = -250;P[4].x = 0; P[4].y = -50;P[5].x = 100; P[5].y = -250;P[6].x = 300; P[6].y = 150;}void CChildView::DrawPolygon(CDC *pDC) //绘制多边形边界{CLine *line = new CLine;CP2 t;for(int i = 0; i < 7; i++) //绘制多边形{if(i == 0){line->MoveTo(pDC, P[i]);t = P[i];}else{line->LineTo(pDC, P[i]);}}line->LineTo(pDC, t); //闭合多边形delete line;}void CChildView::DrawGraph() //绘制图形 {CRect rect; //定义客户区GetClientRect(&rect); //获得客户区的大小CDC *pDC = GetDC(); //定义设备上下文指针pDC->SetMapMode(MM_ANISOTROPIC); //自定义坐标系pDC->SetWindowExt(rect.Width(), rect.Height()); //设置窗口比例pDC->SetViewportExt(rect.Width(), -rect.Height()); //设置视区比例，且x轴水平向右，y轴垂直向上pDC->SetViewportOrg(rect.Width() / 2, rect.Height() / 2); //设置客户区中心为坐标系原点rect.OffsetRect(-rect.Width() / 2, -rect.Height() / 2); //矩形与客户区重合if(!bFill)DrawPolygon(pDC); //绘制多边形elseFillPolygon(pDC); //填充多边形ReleaseDC(pDC); //释放DC}void CChildView::FillPolygon(CDC *pDC) //填充多边形 {for(int i = 0; i < 7; i++) //转储顶点坐标，y坐标取为整数{P1[i].x = P[i].x;P1[i].y = Round(P[i].y);P1[i].c = CRGB(bRed / 255.0, bGreen / 255.0, bBlue / 255.0);}CFill *fill = new CFill; //动态分配内存fill->SetPoint(P1, 7); //初始化Fill对象fill->CreateBucket(); //建立桶表fill->CreateEdge(); //建立边表fill->Gouraud(pDC); //填充多边形delete fill; //撤销内存 }int CChildView::OnCreate(LPCREATESTRUCT lpCreateStruct) {if (CWnd::OnCreate(lpCreateStruct) == -1)return -1;// TODO: 在此添加您专用的创建代码bFill = FALSE;ReadPoint();return 0;}void CChildView::OnDrawPic(){// TODO: 在此添加命令处理程序代码COLORREF GetClr = RGB(0, 0, 0); //调色板颜色CColorDialog ccd(GetClr, CC_SOLIDCOLOR);if(IDOK == ccd.DoModal()) //调用颜色对话框选取填充色GetClr = ccd.GetColor();elsereturn;bRed = GetRValue(GetClr); //获取红色分量bGreen = GetGValue(GetClr); //获取绿色分量bBlue = GetBValue(GetClr); //获取蓝色分量bFill = TRUE;Invalidate();}2(使用MFC技术实现多边形边缘填充算法，参考界面效果如下:// demoView.cpp : CdemoView 类的实现#include "stdafx.h"#include "demo.h"#include "demoDoc.h"#include "demoView.h"#include <math.h>#define Round(d) int(floor(d+0.5))//四舍五入宏定义 #ifdef _DEBUG #define new DEBUG_NEW#endif// CdemoViewIMPLEMENT_DYNCREATE(CdemoView, CView)BEGIN_MESSAGE_MAP(CdemoView, CView)// 标准打印命令ON_COMMAND(ID_FILE_PRINT, &CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT, &CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_PREVIEW, &CdemoView::OnFilePrintPreview) ON_COMMAND(ID_DRAW_PIC, &CdemoView::OnDrawPic) END_MESSAGE_MAP() // CdemoView 构造/析构CdemoView::CdemoView(){// TODO: 在此处添加构造代码}CdemoView::~CdemoView(){}BOOL CdemoView::PreCreateWindow(CREATESTRUCT& cs) {// TODO: 在此处通过修改// CREATESTRUCT cs 来修改窗口类或样式return CView::PreCreateWindow(cs); }// CdemoView 绘制void CdemoView::OnDraw(CDC* /*pDC*/) {CdemoDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);if (!pDoc)return;// TODO: 在此处为本机数据添加绘制代码DrawGraph();}// CdemoView 打印void CdemoView::OnFilePrintPreview() {AFXPrintPreview(this);}BOOL CdemoView::OnPreparePrinting(CPrintInfo* pInfo){// 默认准备return DoPreparePrinting(pInfo); }void CdemoView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) {// TODO: 添加额外的打印前进行的初始化过程 }void CdemoView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) {// TODO: 添加打印后进行的清理过程 }void CdemoView::OnRButtonUp(UINT nFlags, CPoint point){ClientToScreen(&point);OnContextMenu(this, point);}void CdemoView::OnContextMenu(CWnd* pWnd, CPoint point){theApp.GetContextMenuManager()->ShowPopupMenu(IDR_POPUP_EDIT,point.x, point.y, this, TRUE);}void CdemoView::ReadPoint() //点表 {P[0].x = 50; P[0].y = 100;P[1].x = -150;P[1].y = 300;P[2].x = -250;P[2].y = 50;P[3].x = -150;P[3].y = -250;P[4].x = 0; P[4].y = -50;P[5].x = 100; P[5].y = -250;P[6].x = 300; P[6].y = 150; }void CdemoView::DrawPolygon(CDC *pDC) { for(int i = 0; i < 7; i++) //计算多边形边界{if(P[i].x > MaxX)MaxX = P[i].x;if(P[i].x < MinX)MinX = P[i].x;if(P[i].y > MaxY)MaxY = P[i].y;if(P[i].y < MinY)MinY = P[i].y;}CLine *line = new CLine;CP2 t;for(int i = 0; i < 7; i++) //绘制多边形{if(i == 0){line->MoveTo(pDC, P[i]);t = P[i];}else{line->LineTo(pDC, P[i]);}}line->LineTo(pDC, t); //闭合多边形line->MoveTo(pDC, CP2(MinX, MinY)); //绘制包围盒line->LineTo(pDC, CP2(MinX, MaxY));line->LineTo(pDC, CP2(MaxX, MaxY));line->LineTo(pDC, CP2(MaxX, MinY));line->LineTo(pDC, CP2(MinX, MinY));delete line;}void CdemoView::FillPolygon(CDC *pDC){COLORREF BClr = RGB(255, 255, 255); //背景色COLORREF FClr = GetClr; //填充色int ymin, ymax; //边的最小y值与最大y值double x, y, k; //x,y当前点，k斜率的倒数for(int i = 0; i < 7; i++) //循环多边形所有边{int j = (i + 1) % 7;k = (P[i].x - P[j].x) / (P[i].y - P[j].y); //计算/kif(P[i].y < P[j].y) //得到每条边y的最大值与最小值{ymin = Round(P[i].y);ymax = Round(P[j].y);x = P[i].x; //得到x|ymin}else{ymin = Round(P[j].y);ymax = Round(P[i].y);x = P[j].x;}for(y = ymin; y < ymax; y++) //沿每一条边循环扫描线{for(int m = Round(x); m < MaxX; m++) //对每一条扫描线与边的交点的右侧像素循环{if(FClr == pDC->GetPixel(m, Round(y))) //如果是填充色pDC->SetPixelV(m, Round(y), BClr); //置为背景色elsepDC->SetPixelV(m, Round(y), FClr); //置为填充色}x += k; //计算下一条扫描线的x起点坐标}}}void CdemoView::DrawGraph() //绘制图形 {CRect rect; //定义客户区GetClientRect(&rect); //获得客户区的大小CDC *pDC = GetDC(); //定义设备上下文指针pDC->SetMapMode(MM_ANISOTROPIC); //自定义坐标系pDC->SetWindowExt(rect.Width(), rect.Height()); //设置窗口比例pDC->SetViewportExt(rect.Width(), -rect.Height()); //设置视区比例，且x轴水平向右，y轴垂直向上pDC->SetViewportOrg(rect.Width() / 2, rect.Height() / 2); //设置客户区中心为坐标系原点rect.OffsetRect(-rect.Width() / 2, -rect.Height() / 2); //矩形与客户区重合if(!bFill)DrawPolygon(pDC); //绘制多边形elseFillPolygon(pDC); //填充多边形ReleaseDC(pDC); //释放DC }// CdemoView 诊断#ifdef _DEBUGvoid CdemoView::AssertValid() const{CView::AssertValid();}void CdemoView::Dump(CDumpContext& dc) const{CView::Dump(dc);}CdemoDoc* CdemoView::GetDocument() const // 非调试版本是内联的 { ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CdemoDoc)));return (CdemoDoc*)m_pDocument;}#endif //_DEBUG// CdemoView 消息处理程序void CdemoView::OnInitialUpdate(){CView::OnInitialUpdate();// TODO: 在此添加专用代码和/或调用基类bFill = FALSE;ReadPoint();GetClr = RGB(0,0,0);MinX = MaxX = P[0].x;MinY = MaxY = P[0].y;}void CdemoView::OnDrawPic(){// TODO: 在此添加命令处理程序代码CColorDialog ccd(GetClr, CC_SOLIDCOLOR);if(IDOK == ccd.DoModal()) //调用颜色对话框选取填充色GetClr = ccd.GetColor();elsereturn;bFill = TRUE;Invalidate(FALSE);}3.使用MFC技术实现种子填充算法，参考界面效果如下:// demoView.cpp : CdemoView 类的实现 #include "stdafx.h"#include "demo.h"#include "demoDoc.h"#include "demoView.h"#include <math.h>#define Round(d) int(floor(d+0.5))//四舍五入宏定义 #ifdef _DEBUG #define new DEBUG_NEW#endif// CdemoViewIMPLEMENT_DYNCREATE(CdemoView, CView) BEGIN_MESSAGE_MAP(CdemoView, CView)// 标准打印命令ON_COMMAND(ID_FILE_PRINT, &CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT, &CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_PREVIEW, &CdemoView::OnFilePrintPreview) ON_WM_LBUTTONDOWN()ON_COMMAND(ID_DRAW_PIC, &CdemoView::OnDrawPic)END_MESSAGE_MAP()// CdemoView 构造/析构CdemoView::CdemoView(){// TODO: 在此处添加构造代码bFill = FALSE;SeedClr = RGB(255, 0, 0);}CdemoView::~CdemoView(){}BOOL CdemoView::PreCreateWindow(CREATESTRUCT& cs) { // TODO: 在此处通过修改// CREATESTRUCT cs 来修改窗口类或样式return CView::PreCreateWindow(cs); }// CdemoView 绘制void CdemoView::OnDraw(CDC* /*pDC*/) {CdemoDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);if (!pDoc)return;// TODO: 在此处为本机数据添加绘制代码DrawGraph();}// CdemoView 打印void CdemoView::OnFilePrintPreview() { AFXPrintPreview(this);}BOOL CdemoView::OnPreparePrinting(CPrintInfo* pInfo) {// 默认准备return DoPreparePrinting(pInfo);}void CdemoView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) {// TODO: 添加额外的打印前进行的初始化过程}void CdemoView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) { // TODO: 添加打印后进行的清理过程}void CdemoView::OnRButtonUp(UINT nFlags, CPoint point){ClientToScreen(&point);OnContextMenu(this, point);}void CdemoView::OnContextMenu(CWnd* pWnd, CPoint point) {theApp.GetContextMenuManager()->ShowPopupMenu(IDR_POPUP_EDIT,point.x, point.y, this, TRUE);}// CdemoView 诊断#ifdef _DEBUGvoid CdemoView::AssertValid() const{CView::AssertValid();}void CdemoView::Dump(CDumpContext& dc) const{CView::Dump(dc);}CdemoDoc* CdemoView::GetDocument() const // 非调试版本是内联的 { ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CdemoDoc)));return (CdemoDoc*)m_pDocument;}#endif //_DEBUGvoid CdemoView::DrawGraph()//绘制图形{CDC *pDC = GetDC(); //定义设备上下文指针GetClientRect(&rect); //获得客户区的大小pDC->SetMapMode(MM_ANISOTROPIC); //自定义坐标系pDC->SetWindowExt(rect.Width(), rect.Height()); //设置窗口比例pDC->SetViewportExt(rect.Width(), -rect.Height()); //设置视区比例，且x轴水平向右，y轴垂直向上pDC->SetViewportOrg(rect.Width() / 2, rect.Height() / 2); //设置客户区中心为坐标系原点rect.OffsetRect(-rect.Width() / 2, -rect.Height() / 2); //矩形与客户区重合CDC MemDC;//内存DCCBitmap NewBitmap, *pOldBitmap; //内存中承载图像的位图MemDC.CreateCompatibleDC(pDC); //建立与屏幕pDC兼容的MemDCNewBitmap.LoadBitmap(IDB_BITMAP1); //导入空心汉字位图pOldBitmap = MemDC.SelectObject(&NewBitmap);//将兼容位图选入MemDC MemDC.SetMapMode(MM_ANISOTROPIC); //MemDC自定义坐标系MemDC.SetWindowExt(rect.Width(), rect.Height());MemDC.SetViewportExt(rect.Width(), -rect.Height());MemDC.SetViewportOrg(rect.Width() / 2, rect.Height() / 2);pDC->BitBlt(-rect.Width() / 2, -rect.Height() / 2, rect.Width(), rect.Height(), &MemDC,-rect.Width() / 2, -rect.Height() / 2, SRCCOPY);//将内存位图拷贝到屏幕if(bFill)CharFill(pDC); //填充空心汉字MemDC.SelectObject(pOldBitmap); //恢复位图NewBitmap.DeleteObject(); //删除位图MemDC.DeleteDC(); //删除MemDCReleaseDC(pDC); //释放DC }void CdemoView::CharFill(CDC *pDC) //文字填充函数 {COLORREF BoundaryClr = RGB(0,0,0); //边界色BOOL bSpanFill;pHead = new CStackNode; //建立栈结点pHead->pNext = NULL; //栈头结点的指针域总为空Push(Seed); //种子像素入栈int x, y, x0 = Round(Seed.x), y0 = Round(Seed.y);//x，y用于判断种子与图形的位置关系x = x0 - 1;while(pDC->GetPixel(x, y0) != BoundaryClr && pDC->GetPixel(x, y0) != SeedClr )//左方判断{x--;if(x <= -rect.Width() / 2){MessageBox(L"种子不在图形之内", L"警告");//到达客户区最左端return;}}y = y0 + 1;while(pDC->GetPixel(x0, y) != BoundaryClr && pDC->GetPixel(x0, y) != SeedClr)//上方判断{y++;if(y >= rect.Height() / 2)//到达客户区最上端{MessageBox(L"种子不在图形之内", L"警告");return;}}x = x0 + 1;while(pDC->GetPixel(x, y0) != BoundaryClr && pDC->GetPixel(x, y0) != SeedClr)//右方判断{x++;if(x >= rect.Width() / 2)//到达客户区最右端{MessageBox(L"种子不在图形之内", L"警告");return;}}y = y0 - 1;while(pDC->GetPixel(x0, y) != BoundaryClr && pDC->GetPixel(x0, y) != SeedClr)//下方判断{y--;if(y <= -rect.Height() / 2)//到达客户区最下端{MessageBox(L"种子不在图形之内", L"警告");return;}}double xleft, xright;//区间最左端与最右端像素CP2 PopPoint, PointTemp;while(pHead->pNext != NULL)//如果栈不为空{Pop(PopPoint);if(pDC->GetPixel(Round(PopPoint.x), Round(PopPoint.y)) == SeedClr) continue;// 分别向左和向右填充扫描线PointTemp = PopPoint;while(pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != BoundaryClr &&pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) {pDC->SetPixelV(Round(PointTemp.x), Round(PointTemp.y), SeedClr);PointTemp.x++;}xright = PointTemp.x - 1;PointTemp.x = PopPoint.x - 1;while(pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != BoundaryClr &&pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) {pDC->SetPixelV(Round(PointTemp.x), Round(PointTemp.y), SeedClr);PointTemp.x--;}xleft=PointTemp.x + 1;//处理上一条扫描线PointTemp.x = xleft;PointTemp.y = PointTemp.y + 1;while(PointTemp.x < xright){bSpanFill = FALSE;while(pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != BoundaryClr &&pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) {bSpanFill = TRUE;PointTemp.x++;}if(bSpanFill){if(PointTemp.x == xright && pDC->GetPixel(Round(PointTemp.x),Round(PointTemp.y)) != BoundaryClr && pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) PopPoint = PointTemp;elsePopPoint.x = PointTemp.x - 1; PopPoint.y = PointTemp.y;Push(PopPoint);bSpanFill = FALSE;}while((pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) == BoundaryClr &&PointTemp.x < xright) || (pDC->GetPixel(Round(PointTemp.x),Round(PointTemp.y)) == SeedClr &&PointTemp.x < xright))PointTemp.x++;}//处理下一条扫描线PointTemp.x = xleft;PointTemp.y = PointTemp.y - 2;while(PointTemp.x < xright){bSpanFill = FALSE;while(pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != BoundaryClr &&pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) {bSpanFill = TRUE;PointTemp.x++;}if(bSpanFill){if(PointTemp.x == xright && pDC->GetPixel(Round(PointTemp.x),Round(PointTemp.y)) != BoundaryClr && pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) != SeedClr) PopPoint = PointTemp;elsePopPoint.x = PointTemp.x - 1; PopPoint.y = PointTemp.y;Push(PopPoint);bSpanFill=FALSE;}while((pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) == BoundaryClr &&PointTemp.x < xright) || (pDC->GetPixel(Round(PointTemp.x), Round(PointTemp.y)) == SeedClr &&PointTemp.x < xright))PointTemp.x++;}}delete pHead;pHead = NULL;}void CdemoView::Push(CP2 point)//入栈函数{pTop = new CStackNode;pTop->PixelPoint = point;pTop->pNext = pHead->pNext;pHead->pNext = pTop;}void CdemoView::Pop(CP2 &point) //出栈函数{if(pHead->pNext != NULL){pTop = pHead->pNext;pHead->pNext = pTop->pNext;point = pTop->PixelPoint;delete pTop;}}// CdemoView 消息处理程序void CdemoView::OnLButtonDown(UINT nFlags, CPoint point) {// TODO: 在此添加消息处理程序代码和/或调用默认值Seed = CP2(point.x - rect.Width() / 2, rect.Height() / 2 - point.y); //选择种子位置Invalidate(FALSE);CView::OnLButtonDown(nFlags, point);}void CdemoView::OnDrawPic(){// TODO: 在此添加命令处理程序代码CColorDialog ccd(SeedClr, CC_SOLIDCOLOR);if(IDOK == ccd.DoModal())//调用颜色对话框选取填充色SeedClr = ccd.GetColor();elsereturn;if(IDOK == MessageBox(L"请在空心字体内单击鼠标左键!", L"提示",MB_OKCANCEL))bFill = TRUE;elsereturn;}实验总结:上机做实验主要是看明白程序，现在来说，自己还不会自己编程，还是下载老师的实例程序看代码，然后运行看结果，自己再去琢磨理解程序。

《计算机图形学》实验报告(实验二：图形填充算法)一、实验目的及要求用两种方法做图形的填充算法！二、理论基础1.边填充算法对于每一条扫描线和每条多边形的交点（x1,y1），将该扫描线上的交点右方的所有像素取补。

2.种子填充算法利用栈来实现种子填充算法。

种子像素入栈，当栈非空时重复执行如下步骤：将栈顶像素出栈，将出栈像素置成多边形色，按左，上，右，下顺序检查与出栈像素相邻的四个像素，若其中某个像素不再边界且未置成多边形，则把该像素入栈！三、算法设计与分析1、边填充算法void CEdge_mark_fillView::OnDraw(CDC* pDC){CEdge_mark_fillDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);int d[500][500]={0};int inside;int x,y;Bresenham(80,101,100,400,d);Bresenham(100,300,290,400,d);Bresenham(292,400,382,50,d);Bresenham(380,50,202,150,d);Bresenham(200,150,82,101,d);for(y=0;y<500;y++){inside=0;for(x=0;x<500;x++){if(d[x][y]==1)if(d[x+1][y]!=1){inside=!(inside);}if(inside!=0)pDC->SetPixel(x,y,12);}}}2、种子填充int x=299,y=51;COLORREF oldcolor;COLORREF newcolor;oldcolor=RGB(256,256,256);newcolor=RGB(123,123,123);pDC->MoveTo (40,40);pDC->LineTo (80,40);pDC->LineTo (70,80);pDC->LineTo (40,40);FloodFill(51,51,RGB(255,255,255),RGB(0,0,255));pDC->LineTo (40,40);void CMyView::FloodFill(int x,int y,COLORREF oldcolor,COLORREF newcolor) {CDC* pDC;pDC=GetDC();if(pDC->GetPixel(x,y)==oldcolor){pDC->SetPixel(x,y,newcolor);FloodFill(x,y-1,oldcolor,newcolor);FloodFill(x,y+1,oldcolor,newcolor);FloodFill(x-1,y,oldcolor,newcolor);FloodFill(x+1,y,oldcolor,newcolor);}四、程序调试及结果的分析1、2、四、实验心得及建议由于很多不会，所以这次没能按时当堂完成，下来花了不少时间才弄出来，第二种尤其比较麻烦，在同学的帮助下才做出来了。

计算机图形学课程名称多边形填充实验名称一、实验目的及要求软件环境：Microsoft studio visual C++ 6.0 MFC硬件：计算机（1）理解窗口到视区的变换（2）学习使用MFC的图形编程（3）实现五角多边形的填充二、实验内容仿照Windows的附件程序“画图”, 用C++语言编制一个具有交互式绘制和编辑多种图元功能的程序“Mini-Painter”，实现以下功能对应的设计内容：(1) 能够以交互方式在图形绘制区绘制填充多边形(2) 设置线条的颜色、线型和线条宽度，对绘制的图元进行线条和填充属性的修改；三、实验步骤1．新建MFC应用程序（a）新建工程。

运行VC++6.0，新建一个MFC AppWizard[exe]工程，并命名为“多边形”，选择保存路径，确定。

(b)详细步骤不再细述，接下来如图（c）在view.cpp中输入代码并编译运行无误得到结果三、实验内容// 多边形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_FILEstatic char THIS_FILE[] = __FILE__;#endif/////////////////////////////////////////////////////////////////////////////// CMyViewIMPLEMENT_DYNCREATE(CMyView, CView)BEGIN_MESSAGE_MAP(CMyView, CView)//{{AFX_MSG_MAP(CMyView)ON_COMMAND(ID_DUOBIANXING, OnDuobianxing)//}}AFX_MSG_MAP// Standard printing commandsON_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/destructionCMyView::CMyView(){// TODO: add construction code here}CMyView::~CMyView(){}BOOL CMyView::PreCreateWindow(CREATESTRUCT& cs){// TODO: Modify the Window class or styles here by modifying// the CREATESTRUCT csreturn CView::PreCreateWindow(cs);}///////////////////////////////////////////////////////////////////////////// // CMyView drawingvoid CMyView::OnDraw(CDC* pDC){CMyDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);// Circle(100,RGB(0,168,168),pDC) ;// TODO: add draw code for native data here}///////////////////////////////////////////////////////////////////////////// // CMyView printingBOOL CMyView::OnPreparePrinting(CPrintInfo* pInfo){// default preparationreturn 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 _DEBUGvoid 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 handlersvoid CMyView::OnDuobianxing(){// TODO: Add your command handler code here//CMyDoc* pDoc = GetDocument();//ASSERT_VALID(pDoc);CDC *pDC=GetDC();const int POINTNUM=10; //多边形点数.typedef struct XET{float x;float dx,ymax;XET* next;}AET,NET;struct point{float x;float y;}polypoint[POINTNUM]={200,150,350,50,350,400,250,250,100,350,200,200,300,200,400,200};//多边形顶点int MaxY=0;int i;for(i=0;i<POINTNUM;i++)if(polypoint[i].y>MaxY)MaxY=polypoint[i].y;AET *pAET=new AET;pAET->next=NULL;NET *pNET[1024];for(i=0;i<=MaxY;i++){pNET[i]=new NET;pNET[i]->next=NULL;}for(i=0;i<=MaxY;i++){for(int j=0;j<POINTNUM;j++)if(polypoint[j].y==i){if(polypoint[(j-1+POINTNUM)%POINTNUM].y>polypoint[j].y){NET *p=new NET;p->x=polypoint[j].x;p->ymax=polypoint[(j-1+POINTNUM)%POINTNUM].y;p->dx=(polypoint[(j-1+POINTNUM)%POINTNUM].x-polypoint[j].x)/(polypoint[(j-1+POINTNUM)%POINTN UM].y-polypoint[j].y);p->next=pNET[i]->next;pNET[i]->next=p;}if(polypoint[(j+1+POINTNUM)%POINTNUM].y>polypoint[j].y){NET *p=new NET;p->x=polypoint[j].x;p->ymax=polypoint[(j+1+POINTNUM)%POINTNUM].y;p->dx=(polypoint[(j+1+POINTNUM)%POINTNUM].x-polypoint[j].x)/(polypoint[(j+1+POINTNUM)%POINTN UM].y-polypoint[j].y);p->next=pNET[i]->next;pNET[i]->next=p;}}}for(i=0;i<=MaxY;i++){NET *p=pAET->next;while(p){p->x=p->x + p->dx;p=p->next;}//断表排序,不再开辟空间AET *tq=pAET;p=pAET->next;tq->next=NULL;while(p){while(tq->next && p->x >= tq->next->x)tq=tq->next;NET *s=p->next;p->next=tq->next;tq->next=p;p=s;tq=pAET;}//(改进算法)先从AET表中删除ymax==i的结点AET *q=pAET;p=q->next;while(p){if(p->ymax==i){q->next=p->next;delete p;p=q->next;}else{q=q->next;p=q->next;}}//将NET中的新点加入AET,并用插入法按X值递增排序p=pNET[i]->next;q=pAET;while(p){while(q->next && p->x >= q->next->x)q=q->next;NET *s=p->next;p->next=q->next;q->next=p;p=s;q=pAET;}//配对填充颜色p=pAET->next;while(p && p->next){for(float j=p->x;j<=p->next->x;j++)pDC->SetPixel(static_cast<int>(j),i,RGB(168,255,55));p=p->next->next;//考虑端点情况}}ReleaseDC(pDC);}四、实验结果五、实验总结分析做这个实验要借助数组链表和指针的用法，通过研究，更熟练了用指针进行扫描来绘制圆，通过做这实验，也提升了我对这门课的兴趣。

实验二有效边表填充算法实验题目：有效边表填充算法学号：姓名：班级：指导老师：完成日期：1.实验目的：设计有效边表结点和边表结点数据结构设计有效边表填充算法编程实现有效边表填充算法2.实验描述：下图1 所示多边形覆盖了12 条扫描线，共有7 个顶点和7 条边。

7 个顶点分别为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）, P4（6，5）, P5（8，1）, P6（12，9）。

在1024×768 的显示分辩率下，将多边形顶点放大为P0（500,400），P1（350，600），P2（250，350），P3（350，50）, P4（500，250）, P5（600，50）, P6（800，450）。

图1示例多边形图2屏幕显示多边形3.算法设计：多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间的所有像素，即完成填充工作。

有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。

4.源程序：1）//AET.h和AET..cppclass AET{public:AET();virtual ~AET();double x;int yMax;double k; //代替1/kAET *next;}2）//Bucket.h和Bucket.cppclass Bucket{public:Bucket();virtual ~Bucket();int ScanLine;AET *p;//桶上的边表指针Bucket *next;}3) // TestView.h#include "AET.h"//包含有效边表类#include "Bucket.h"//包含桶类#define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中class CTestView : public CView{。

实验二2-2一、实验题目给定四个点绘制图4-44所示的不同转角的两个正方形，使用有效边表算法进行填充，填充效果如图4-45所示，注意采用“左闭右开”和“上闭下开”的原则，使得每个正方形的右边界和下边界没有填充。

二、实验思想有效边表填充算法通过维护边表和有效边表，避开了扫描线与多边形所有边求交的复杂运算。

填充原理是按照扫描线从小到大的移动顺序，计算当前扫描线与有效边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，最后用指定颜色填充区间内的所有像素，即完成填充工作。

三、实验代码void CTestView::GetMaxX()//获得屏幕宽度{CRect Rect;GetClientRect(&Rect);MaxX=Rect.right;}void CTestView::GetMaxY()//获得屏幕高度{CRect Rect;GetClientRect(&Rect);MaxY=Rect.bottom;}void CTestView::ReadPoint()//读入点表函数{//设置第一个正方形的4个顶点int a=160;P1[0]=CP2(MaxX/4-a,MaxY/2+a);//P0P1[1]=CP2(MaxX/4+a,MaxY/2+a);//P1P1[2]=CP2(MaxX/4+a,MaxY/2-a);//P2P1[3]=CP2(MaxX/4-a,MaxY/2-a);//P3//设置第二个正方形的4个顶点int b=ROUND(sqrt(2)*a);P2[0]=CP2(3*MaxX/4,MaxY/2+b);//P0P2[1]=CP2(3*MaxX/4+b,MaxY/2);//P1P2[2]=CP2(3*MaxX/4,MaxY/2-b);//P2P2[3]=CP2(3*MaxX/4-b,MaxY/2);//P3}void CTestView::DrawRect(CDC *pDC,CP2 *P)//绘制正方形函数{CP2 T;CLine line;for(int i=0;i<4;i++)//边循环{if(i==0){line.MoveTo(pDC,P[i]);T=P[0];}else{line.LineTo(pDC,P[i]);;}}line.LineTo(pDC,T);//闭合}void CTestView::OnMENUIFill(){// TODO: Add your command handler code hereCOLORREF FColor;CColorDialog ccd(RGB(255,0,0));if(ccd.DoModal()==IDOK)//调用调色板选取色{FColor=ccd.GetColor();m_Red=GetRValue(FColor);//获得颜色的红色分量m_Green=GetGValue(FColor);//获得颜色的绿色分量m_Blue=GetBValue(FColor);//获得颜色的蓝色分量}RedrawWindow();//刷新屏幕FillRect(P1);//填充正方形1FillRect(P2);//填充正方形2}void CTestView::FillRect(CP2 *P)//填充正方形函数{CFill fill;CPi2 Point[4];for(int i=0;i<4;i++){Point[i].x=P[i].x;Point[i].y=ROUND(P[i].y);Point[i].c=CRGB(double(m_Red)/255.0,double(m_Green)/255.0,double(m_Blue)/255.0);}CDC *pDC=GetDC();fill.SetPoint(Point,4);//填充正方形fill.CreateBucket();fill.CreateEdge();fill.Gouraud(pDC);ReleaseDC(pDC);}四、实验截图。

实验四区域填充算法的实现班级 08信计2班学号 20080502082 姓名分数一、实验目的和要求：1、理解区域的表示和类型。

2、能正确区分四连通和八连通的区域3、了解区域填充的实验原理。

4、利用C++实现区域填充的递归算法。

二、实验内容：1假设在多边形内有一像素已知，由此出发利用连通性找到区域内所有像素。

2 取（x，y）为种子点将整个区域填充为新的颜色。

3 进行递归填充。

三、实验结果分析区域填充属性包括填充样式，填充颜色和填充图案的类型。

C语言中定义了某种图形后，即可调用-floodfill函数，对指定区域进行填充. 程序代码#define pi 3.141592#define MAX(a,b) (a>b)? a:b#define MIN(a,b) (a<b)? a:b#include "graphics.h"#include "math.h"struct edge {int ymax;float x;float delat;struct edge * pedge; };struct point{int x;int y;} ;struct et { struct edge * pedge;int n;};struct edge g_aet[10];struct edge dge[10];struct et g_et[10];struct point point1,point2;int ZUO(float x){ if((int)x==x)return (int)x;return (int)x+1;}int YOU(float x){ if((int)x==x)return (int)x-1;return (int)x;}int k=400,l=0;void draw1(){int i,t,j,a,c,p,z; float b;struct edge temp;for(i=k;i<=l;i++){a=0;for(t=0;t<=9;t++){ if(g_et[t].n==i) break;}for(j=0;j<=9;j++){ if(g_aet[j].ymax==0) break;}if(t!=10){ g_aet[j].ymax=g_et[t].pedge->ymax;g_aet[j].x=g_et[t].pedge->x;g_aet[j].delat=g_et[t].pedge->delat;if(g_et[t].pedge->pedge!=0){g_aet[j+1].ymax=g_et[t].pedge->pedge->ymax;g_aet[j+1].x=g_et[t].pedge->pedge->x;g_aet[j+1].delat=g_et[t].pedge->pedge->delat; }}for(j=0;j<=9;j++){ if(g_aet[j].ymax==0) break; }j--;for(t=0;t<=j;t++){ for(z=0;z<=j-1;z++){if(g_aet[z].x>g_aet[z+1].x){ temp.ymax=g_aet[z].ymax;temp.x=g_aet[z].x;temp.delat=g_aet[z].delat;g_aet[z].ymax=g_aet[z+1].ymax;g_aet[z].x=g_aet[z+1].x;g_aet[z].delat=g_aet[z+1].delat;g_aet[z+1].ymax=temp.ymax;g_aet[z+1].x=temp.x;g_aet[z+1].delat=temp.delat;}}}for(j=0;j<=9;j++){ if(g_aet[j].ymax==0) break; }j--;for(p=0;p<=j;p++){ a++;if(a%2!=0)b=g_aet[p].x;else{for(c=ZUO(b);c<=YOU(g_aet[p].x);c++)putpixel(c,i,2);}}for(t=0;t<=j;t++){ if(g_aet[t].ymax==(i+1)){ g_aet[t].ymax=0;g_aet[t].x=0;g_aet[t].delat=0;}g_aet[t].x+=g_aet[t].delat;}for(t=0;t<=j;t++){ for(z=0;z<=j-1;z++){if(g_aet[z].x<g_aet[z+1].x){ temp.ymax=g_aet[z].ymax;temp.x=g_aet[z].x;temp.delat=g_aet[z].delat;g_aet[z].ymax=g_aet[z+1].ymax;g_aet[z].x=g_aet[z+1].x;g_aet[z].delat=g_aet[z+1].delat;g_aet[z+1].ymax=temp.ymax;g_aet[z+1].x=temp.x;g_aet[z+1].delat=temp.delat;}}}}}void generate(){int i,y,n=1,m,q,p;float x;for(i=0;i<=9;i++){if(n==1){ point2.x=point1.x=300;point2.y=point1.y=200;n++;}else{ if(n%2==0){ x=40*cos(i*pi/5)+200;y=40*sin(i*pi/5)+200;}else{ x=100*cos(i*pi/5)+200;y=100*sin(i*pi/5)+200;}if(point1.y==y) { n++; continue;}m=MIN(point1.y,y);if(x==point1.x){ dge[i-1].delat=0;dge[i-1].ymax=MAX(point1.y,y);dge[i-1].x=x;dge[i-1].pedge=0;for(q=0;q<=9;q++){ if(g_et[q].n==m) break;}if(q==10){g_et[i-1].pedge=&dge[i-1];g_et[i-1].n=m;}else{g_et[q].pedge->pedge=&dge[i-1];g_et[i-1].n=0;}}else{dge[i-1].delat=(float)(x-point1.x)/(y-point1.y);dge[i-1].ymax=MAX(point1.y,y);if(point1.y>y) dge[i-1].x=x;else {dge[i-1].x=point1.x; }dge[i-1].pedge=0;for(q=0;q<=9;q++){ if(g_et[q].n==m) break;}if(q==10){ g_et[i-1].pedge=&dge[i-1];g_et[i-1].n=m;}else{g_et[q].pedge->pedge=&dge[i-1];g_et[i-1].n=0;}}p=MAX(point1.y,y);k=MIN(k,m);l=MAX(l,p);point1.x=x;point1.y=y;n++;}}if(point1.y==point2.y) return;else{if(point2.x==point1.x){dge[i-1].delat=0;dge[i-1].ymax=MAX(point1.y,point2.y);dge[i-1].x=point2.x;}else{ dge[i-1].ymax=MAX(point1.y,point2.y);if(point1.y>point2.y) dge[i-1].x=point2.x;else {dge[i-1].x=point1.x;}dge[i-1].delat=(float)(point2.x-point1.x)/(point2.y-point1.y);}}m=MIN(point1.y,point2.y);k=MIN(k,m);l=MAX(l,dge[i-1].ymax);g_et[i-1].n=m;g_et[i-1].pedge=&dge[i-1];}void main(){ int driver=DETECT,mode; int i; registerbgidriver(EGA VGA_driver);initgraph(&driver,&mode,"\\tc");initgraph(&driver,&mode,"\\tc");for(i=0;i<=9;i++){ g_aet[i].ymax=0; g_aet[i].x=0; g_aet[i].delat=0;g_et[i].pedge=0;}generate();draw1();circle(200,200,100); circle(200,200,40);getch();closegraph();}。