区域填充扫描线算法实验报告

1、期中作业一实验内容区域填充扫描线算法：按照扫描线的顺序，计算扫描线与多 边形的相交区间，再用要求的颜色显示这些区间的像素，完成填充工 作。二算法描述扫描线填充算法的基本思想是:用水平扫描线从上到下（或从下到上） 扫描由多条首尾相连的线段构成的多边形，每根扫描线与多边形的某 些边产生一系列交点。将这些交点按照x坐标排序，将排序后的点两 两成对，作为线段的两个端点，以所填的颜色画水平直线。多边形被 扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以 下4个步骤：（1）求交，计算扫描线与多边形的交点（2）交点排序，对第2步得到的交点按照x值从小到大进行排序；（3）颜色填充，对排序后的交点两

2、两组成一个水平线段，以画线段 的方式进行颜色填充；（4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫 描线，然后转第1步继续处理；整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考 虑交点是线段端点的特殊情况，最后，交点的步进计算最好是整数， 便于光栅设备输出显示。Stepl:将ET表中各元素置空，建立ET表Step2：为多边形P的每一条边建立边结构按该边的上端点的y值y 上插入ET表中的第y上类（组），即插入ETy上.Step3 :（初始化）AEL置空/AEL=Nully:ET表中非空元素的区域号最大值。Step4 :扫描转化while （AEL or ET 非空）doN

3、o.1 （边插入）如果ETy非空，则将ETy中各边插入AEL。No.2 （排序）将AEL中的各边按照x （若x相等按Ax的递增顺序排 序。No.3 （如果AEL非空填色）将AEL中各边依次组成对，在横坐标为y 的扫描线上，将以每对边的x坐标为端点的区间上填上多边形所需要 的颜色.No.4 （下一条扫描线）y 。No.5 （边删除）将AEL中满足y=ymin的边删除。No.6 （边更新）将AEL中的各边x值更新，x=x+ Ax 三源代码#include stdafx.h#include demo.h#include ChildView.h#include #define Round(d) int

4、(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(CREATE

5、STRUCT& 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(COLOR_WINDOW+1), NULL);return TRUE;void CChildView:OnPaint()CPaintDC dc(this);

6、 /用于绘制的设备上下文/ TODO:在此处添加消息处理程序代码DrawGraph();/不要为绘制消息而调用CWnd:OnPaint()void CChildView:ReadPoint()/点表P0.x = 50; P0.y = 100;P1.x = -150;P1.y = 300;P2.x = -250;P2.y = 50;P3.x = -150;P3.y = -250;P4.x = 0;P4.y=-50;P5.x = 100; P5.y = -250;P6.x = 300; P6.y = 150;void CChildView:DrawPolygon(CDC *pDC)/绘制多边形边界

7、CLine *line = new CLine;CP2 t;for(int i = 0; i MoveTo(pDC, Pi);t = Pi;elseline-LineTo(pDC, Pi);line-LineTo(pDC, t);/闭合多边形delete line;void CChildView:DrawGraph()/绘制图形 TOC o 1-5 h z CRect rect;/定义客户区GetClientRect(&rect);/获得客户区的大小CDC *pDC = GetDC();/定义设备上下文指针pDC-SetMapMode(MM_ANISOTROPIC);/自定义坐标系pDC-Se

8、tWindowExt(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(pD

9、C);/填充多边形ReleaseDC(pDC);/释放DCvoid CChildView:FillPolygon(CDC *pDC) /填充多边形for(int i = 0; i SetPoint(P1, 7);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();