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

期中作业 一 实验内容 区域填充扫描线算法：按照扫描线的顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，完成填充工作。 二 算法描述 扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤： （1） 求交，计算扫描线与多边形的交点 （2） 交点排序，对第2步得到的交点按照x值从小到大进行排序； （3） 颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充； （4） 是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步继续处理； 整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。 Step1：将ET表中各元素置空，建立ET表 Step2：为多边形P的每一条边建立边结构按该边的上端点的y值y上插入ET表中的第y上类（组），即插入ET[y上]. Step3 ：（初始化） AEL置空//AEL=Null y:ET表中非空元素的区域号最大值。 Step4：扫描转化 while（AEL or ET 非空） do {No.1 （边插入）如果ET[y]非空，则将ET[y]中各边插入AEL。 No.2 （排序）将AEL中的各边按照x（若x相等按Δx的递增顺序排序。 No.3（如果AEL非空填色）将AEL中各边依次组成对，在横坐标为y的扫描线上，将以每对边的x坐标为端点的区间上填上多边形所需要的颜色. No.4（下一条扫描线）y－－。 No.5（边删除）将AEL中满足y=ymin的边删除。 No.6（边更新）将AEL中的各边x值更新，x=x+ Δx } 三 源代码 #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 // CChildView CChildView::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_castHBRUSH(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 CChi