计算机图形学课程设计有效边表填充算法的实现

实验三计算机图形学多边形填充算法课程名称计算机图形学实验日期 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-扫描线算法的基本思想是，按照扫描线的顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。

实验一：改进的有效边表算法一.实验目的用鼠标描绘几个顶点，画出多边形，用边表桶的填充算法实现多边形的填充。

二.算法思想在处理一条扫描线时，仅对与它相交的多边形的边（有效边）求交，其次利用扫描线的连贯性，考虑到当前扫描线与各边的交点顺序与下一条扫描线各边的交点顺序很可能相同或者相似，因此在当前扫描线处理完毕之后，不必为下一条扫描线从头开始构造交点信息；最后利用多边形边的连贯性，认为若某条边与当前扫描线相交，则它很可能也与下一条扫描线相交且其交点与上一次的交点相交。

三.实现过程1.边表的构造1.首先构造一个纵向链表，链表长度为多边形所占有的最大扫描线数，链表的每个结点，称为，称为一个桶，对应多边形覆盖的每一条扫描线。

2.将每条边的信息装入与该边最小Y坐标（Ymin）相对应的桶中，也就是说，若某条边的较低端点为Ymin,则该边就放在相应的Y=Ymin的扫描线桶中。

3.每条边的数据形成一个结点，内容包括该扫描线与该边的初始交点X（即较低端点的X坐标），该边的最大Y 坐标值Ymax,以及边斜率的倒数1/k.4.同一桶中若干条边按x|ymin 由小到大排序，若x|ymin相等，则按照1/k由小到大排序。

2.扫描线的填充算法1.初始化。

构造边表，AET表设置为空。

2.将第一个不空的ET表中的边与AET表合并。

3.由AET表中取出的交点并进行填充，填充时候设置一个布尔量b（初值为假），令指针有效边表中的第一个结点（交点）到最后一个结点遍历一次，每访问一个结点，把b取反一次，若b为真，则把从当前结点的x值开始到下一个结点的x值结束的区间用多边形色填充，填充之后删除y=ymax的边（需注意，填充时同样为避免多边形区域的扩大化，需要多交点进行与x-扫面线算法相同的处理）。

4.y i+1=y i+1,根据x i+1=x i+1/k计算并修改AET表，同时合并ET表中y=y i+1桶中的边，按次序插入到AET 表中形成新的AET表。

实验三计算机图形学多边形填充算法课程名称计算机图形学实验日期 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.实验目的：设计有效边表结点和边表结点数据结构设计有效边表填充算法编程实现有效边表填充算法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{。

实验四区域填充算法的实现班级 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();}。

实验四区域填充算法的实现班级 08信计学号 67姓名张洪伟分数一、实验目的和要求：1. 理解区域的表示和类型；2．实现区域填充的扫描线算法；3．WIN-TC 图形编程模板实现编程结果并保存。

二、实验内容：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。

1. 确定种子区段：从种子点出发，沿当前扫描线向左右两个方向填充直到边界。

用三元组(y,xLeft,xRight)记录此区段。

2．初始化：将堆栈设为空，将种子区段压入堆栈。

3．出栈：若堆栈为空，算法结束;否则取栈顶元素，以纵坐标为y的扫描线为当前扫描线，[xLeft,xRight]为搜索区间。

4．进栈：分别确定与当前扫描线相邻的上下两条扫描线与区段(y,xLeft,xRight)连通的位于给定区域内的区段。

如果有这样的区段，填充并将它们的信息压入堆栈，返回步骤3。

三、实验结果分析1该实验先用fillellipse(100,100,60,40) 画出实心椭圆，然后用如上算法填充，代码如下：setcolor(5);fillellipse(300,250,60,40);ScanLineFill(300,250,15,5);此算法还能填充带边框的多边形，如下代码填充一个矩形区域，oldColor 为背景色0：rectangle(100,20,200,50);ScanLineFill(125,30,0,5);如下代码填充带孔的四连通区域：bar(100,80,150,180);bar(150,80,200,90);bar(200,80,250,180);bar(150,130,200,180);ScanLineFill(110,150,15,2);对于每一个待填充的区段，只需压栈一次，因此扫描线算法的效率提高了很多。