计算机图形学 有效边表填充算法实验报告

实验题目：实验二有效边表填充算法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.算法设计：（1）建立AET和BUCKET类；（2）初始化桶，并在建立桶结点时为其表示的扫描线初始化为带头结点的链表；（3）对每个桶结点进行循环，将桶内每个结点的边表合并为有效边表，并进行有效边表循环；（4）按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按X值递增的顺序进行排序，配对，以确定填充区间；（5）用指定颜色点亮填充区间内的所有像素，即完成填充工作。

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

计算机图形学课程设计设计题目改进的有效边表算法对多边形的填充学院名称信息科学与技术学院专业名称计算机科学与技术学生姓名刘柯学生学号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);}四、实验结果五、实验总结分析做这个实验要借助数组链表和指针的用法，通过研究，更熟练了用指针进行扫描来绘制圆，通过做这实验，也提升了我对这门课的兴趣。

《计算机图形学》有序边表填充算法(总9页)-CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除实验报告一、实验目的1、掌握有序边表算法填充多边形区域；2、理解多边形填充算法的意义；3、增强C语言编程能力。

二、算法原理介绍根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。

所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。

判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可以分为四个步骤：（1）求交：计算扫描线与多边形各边的交点；（2）排序：把所有交点按x值递增顺序排序；（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;（4）着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。

p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。

如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。

p2，p6为非极值点，则不用如上处理。

为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。

把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。

对每一条扫描线都建立一个与它相交的多边形的活性边表（AET）。

每个AET的一个节点代表一条活性边，它包含三项内容1.x -当前扫描线与这条边交点的x坐标；2.Δx -该边与当前扫描线交点到下一条扫描线交点的x增量；3.ymax -该边最高顶点相交的扫描线号。

每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。

当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。

实验二有效边表填充算法实验题目：有效边表填充算法学号：姓名：班级：指导老师：完成日期：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);}四、实验截图。

有效边表填充算法基本思想：⽤⽔平扫描线从上到下（或从下到上）扫描由多条⾸尾相连的线段构成的多边形，每根扫描线与多边形的某些边产⽣⼀系列的交点。

将这些交点按照x坐标排序，将排序后的点两两配对，作为线段的两个端点，以所填的颜⾊画⽔平直线。

步骤1.求交，计算扫描线与多边形的交点。

2.交点排序，对第1步得到的交点按照x从⼩到⼤排序3.颜⾊填充，对排序后的交点两两组成⼀个⽔平线段，以画线段的⽅式进⾏颜⾊填充。

4.完成多边形扫描，就结束算法，否则，继续1有效边多边形与当前扫描线相交的边成为有效边(active edge)。

在处理⼀条扫描线时仅对有效边进⾏求交运算，避免与多边形所有边求交，提⾼效率。

x y max1/k next桶表与边表有效边给出了扫描线与有效边交点的计算⽅法，但没有给出新边出现的位置坐标。

为了确定在哪条扫描线上加⼊了新边，就需要构造⼀个边表（edge table ET),⽤以存放扫描线上多边形各条边出现的信息。

⽔平边本⾝就是扫描线在建⽴边表时可以不予考虑。

桶表与边表的表⽰法桶表是按照扫描线顺序管理边出现的⼀个数据结构。

⾸先，构造⼀个纵向扫描线链表，链表的长度为多边形所占有的最⼤扫描线数，链表的每个节点称为桶(bucket）,对应多边形覆盖的每⼀条扫描线。

将每条边的信息链加⼊该边最⼩y坐标对应的桶处。

对每⼀条扫描线，如果新增多条边，按照x|y min 坐标递增的顺序存放在⼀个链表中，若x|y min 相等，则按照1/k递增，就形成边表。

x|ymin ymax1/k next。

实验报告（第9周）
班级：姓名：学号：
实验名称：实现边缘填充算法和区域填充算法
报告内容：
1、任务描述
(1)生成一个MFC单文档应用程序，添加必要的菜单和功能
(2)仿照上个实验，使用画线函数绘制一个线框多边形
(3)完成边缘填充算法的程序，实现多边形填充
(4)多边形一个顶点为圆心绘制一个圆，与多边形交集形成一块自定义区
域；使用边界定义的四连通种子填充算法，填充这个区域
2、试验环境
(1)Visual Studio 6.0 （或以上）标准版
3、试验目标
(1)掌握边缘填充算法
(2)掌握区域的种子填充算法
4、实验步骤
（运行结果抓图，有用的程序代码，并辅助文字说明）。

西安工程大学实验报告课程实验名称区第 1 页共 6 页系别组别_____________ 实验报告日期年月日姓名学号报告退发 ( 订正、重做 )E_mail:_________________________________ 教师审批评分___________________区域填充算法一、实验目的和任务1. 学习多边形填充的基于扫描线的区域填充算法2. 编程实现区域填充算法二、实验环境和设备windows系统下 vs2012 c++三、实验步骤和过程在MFC框架中通过菜单与对话框实现多边形顶点参量的输入，选择各种填充算法中的两种进行展示，其中栅栏填充和边填充算法不能同时选择，多边形的表示根据所选择的算法，以内点表示或边界表示均可四、实验故障与排除五、总结附录#include <glut.h>#include<Windows.h>const int POINTNUM = 7; //多边形点数./******定义结构体用于活性边表AET和新边表NET***********************************/ typedef struct XET{float x;float dx, ymax;XET* next;}AET, NET;/******定义点结构体point******************************************************/struct point{float x;float y;}polypoint[POINTNUM] = { 250, 50, 550, 150, 550, 400, 250, 250, 100, 350, 100, 100, 120, 30 };//多边形顶点void PolyScan(){/******计算最高点的y坐标(扫描到此结束)****************************************/int MaxY = 0;int i;for (i = 0; i<POINTNUM; i++)if (polypoint[i].y>MaxY)MaxY = polypoint[i].y;/*******初始化AET表***********************************************************/ AET *pAET = new AET;pAET->next = NULL;/******初始化NET表************************************************************/ NET *pNET[1024];for (i = 0; i <= MaxY; i++){pNET[i] = new NET;pNET[i]->next = NULL;}glClear(GL_COLOR_BUFFER_BIT); //赋值的窗体显示.glColor3f(0.0, 0.0, 0.0); //设置直线的颜色红色glBegin(GL_POINTS);/******扫描并建立NET表*********************************************************/ for (i = 0; i <= MaxY; i++){for (int j = 0; j<POINTNUM; j++)if (polypoint[j].y == i){ //一个点跟前面的一个点形成一条线段。

实验题目: 实验二有效边表填充算法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.算法设计:（1）建立AET和BUCKET类；（2）初始化桶, 并在建立桶结点时为其表示的扫描线初始化为带头结点的链表；（3）对每个桶结点进行循环, 将桶内每个结点的边表合并为有效边表, 并进行有效边表循环；（4）按照扫描线从小到大的移动顺序, 计算当前扫描线与多边形各边的交点, 然后把这些交点按X值递增的顺序进行排序, 配对, 以确定填充区间；（5）用指定颜色点亮填充区间内的所有像素, 即完成填充工作。

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

填充算法实验报告实验报告：填充算法研究与实验1. 实验目的填充算法在计算机图形学中有着广泛的应用，并且对于计算机图形学的发展有着重要意义。

本次实验旨在通过对填充算法的研究与实验，了解填充算法的原理和应用，掌握填充算法的基本实现方法，实现简单的填充效果。

2. 实验背景填充算法是计算机图形学中的一种常用算法，用于将指定区域进行填充。

填充算法可以应用于图像的编辑、区域选择、图像渲染等方面。

常见的填充算法包括区域种子填充算法、扫描线填充算法等。

3. 实验内容本次实验主要研究和实现了区域种子填充算法和扫描线填充算法。

区域种子填充算法是指通过指定一个待填充的种子点，在其周围的区域进行填充。

扫描线填充算法是指通过扫描图像的每一行，在特定条件下对像素进行填充。

在实验中，我们首先实现了区域种子填充算法。

通过在待填充的区域中选择一个点作为种子点，然后从指定点出发，通过递归或栈的方式对相邻的像素进行着色，直到遇到与起始点像素颜色不同的像素为止，从而完成填充效果。

其次，我们实现了扫描线填充算法。

这种算法的核心是扫描图像的每一行，在每一行上找到待填充区域的边界并将其记录下来，然后根据边界的位置对每一个像素进行填充。

我们采用了活性边表和扫描线转换算法来实现扫描线填充算法。

4. 实验结果通过实验我们成功实现了区域种子填充算法和扫描线填充算法，在输入指定的区域和种子点后，程序能够快速地对指定区域进行填充，生成了良好的填充效果。

5. 实验分析区域种子填充算法是一种简单且直观的填充算法，但对于复杂区域的填充效果并不理想。

它的主要缺点是可能导致栈溢出或填充效果不均匀，因此在实际应用中不太常用。

相比之下，扫描线填充算法具有更好的填充效果和效率。

其使用了活性边表和扫描线转换算法，可以在进行每一行的扫描时快速地找到边界并进行填充。

但该算法无法很好地处理较复杂的几何形状，例如存在凹陷和自相交的区域。

6. 实验总结通过本次实验，我们深入学习了填充算法的基本原理和实现方法，并成功实现了区域种子填充算法和扫描线填充算法。

《计算机图形学》有序边表填充算法实验报告一、实验目的1、掌握有序边表算法填充多边形区域；2、理解多边形填充算法的意义；3、增强C语言编程能力。

二、算法原理介绍根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。

所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。

判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可以分为四个步骤：（1）求交：计算扫描线与多边形各边的交点；（2）排序：把所有交点按x值递增顺序排序；（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;（4）着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。

p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。

如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。

p2，p6为非极值点，则不用如上处理。

为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。

把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。

对每一条扫描线都建立一个与它相交的多边形的活性边表（AET）。

每个AET的一个节点代表一条活性边，它包含三项内容1.x -当前扫描线与这条边交点的x坐标；2.Δx -该边与当前扫描线交点到下一条扫描线交点的x增量；3.ymax -该边最高顶点相交的扫描线号。

每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。

当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。

当多边形新边表ET构成后，按下列步骤进行：①对每一条扫描线i，初始化ET表的表头指针ET[i]；②将ymax = i的边放入ET[i]中；③使y =多边形最低的扫描线号；④初始化活性边表AET为空；⑤循环，直到AET和ET为空。