扫描线种子填充算法
扫描线种子填充算法的基本过程如下：当给定种子点(x, y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围[xLeft, xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。
扫描线种子填充算法可由下列四个步骤实现：
(1) 初始化一个空的栈用于存放种子点，将种子点(x, y)入栈；
(2) 判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线；
(3) 从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight；
(4) 分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素，从xLeft开始向xRight方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中最右边的一个，并将其作为种子点压入栈中，然后返回第（2）步；
这个算法中最关键的是第（4）步，就是从当前扫描线的上一条扫描线和下一条扫描线中寻找新的种子点。如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大，而且是连续的情况下，算法的第（3）步就处理了这种情况。如图所示：
新扫描线区间增大且连续的情况
假设当前处理的扫描线是黄色点所在的第7行，则经过第3步处理后可以得到一个区间[6,10]。然后第4步操作，从相邻的第6行和第8行两条扫描线的第6列开始向右搜索，确定红色的两个点分别是第6行和第8行的种子点，于是按照顺序将（6, 10）和（8, 10）两个种子点入栈。接下来的循环会处理（8, 10）这个种子点，根据算法第3步说明，会从（8, 10）开始向左和向右填充，由于中间没有边界点，因此填充会直到遇到边界为止，所以尽管第8行实际区域比第7行的区间[6,10]大，但是仍然得到了正确的填充。
如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大，而且中间有边界点的情况，算法又是怎么处理呢？算法描述中虽然没有明确对这种情况的处理方法，但是第4步确定上、下相邻扫描线的种子点的方法，以及靠右取点的原则，实际上暗含了从相邻扫描线绕过障碍点的方法。如下图所示：
新扫描线区间增大且不连续的情况
算法第3步处理完第5行后，确定了区间[7, 9]，相邻的第4行虽然实际范围比区间[7, 9]大，但是因为被（4, 6）这个边界点阻碍，使得在确定种子点（4, 9）后向左填充只能填充右边的第7列到第10列之间的区域，而左边的第3列到第5列之间的区域没有填充。虽然作为第5行的相邻行，第一次对第4行的扫描根据靠右原则只确定了（4, 9）一个种子点。但是对第3行处理完后，第4行的左边部分作为第3行下边的相邻行，再次得到扫描的机会。第3行的区间是[3, 9]，向左跨过了第6列这个障碍点，第2次扫描第4行的时候就从第3列开始，向右找，可以确定种子点（4, 5）。这样第4行就有了两个种子点，就可以被完整地填充了。
由此可见，对于有障碍点的行，通过相邻边的关系，可以跨越障碍点，通过多次扫描得到完整的填充，算法已经隐含了对这种情况的处理。扫描线种子填充算法的实现如下：
263 void ScanLineSeedFill(int x, int y, int new_color, int boundary_color)
264 {
265 std::stack
266
267 stk.push(Point(x, y)); //第1步，种子点入站
268 while(!stk.empty())
269 {
270 Point seed = stk.top(); //第2步，取当前种子点
271 stk.pop();
272
273 //第3步，向左右填充
274 int count = FillLineRight(seed.x, seed.y, new_color, boundary_color);//向'cf?右'd3?填'cc?充'b3?
275 int xRight = seed.x + count - 1;
276 count = FillLineLeft(seed.x - 1, seed.y, new_color, boundary_color);//向'cf?左'd7?填'cc?充'b3?
277 int xLeft = seed.x - count;
278
279 //第4步，处理相邻两条扫描线
280 SearchLineNewSeed(stk, xLeft, xRight, seed.y - 1,
new_color,boundary_color);
281 SearchLineNewSeed(stk, xLeft, xRight, seed.y + 1,
new_color,boundary_color);
282 }
283 }
FillLineRight()和FillLineLeft()两个函数就是从种子点分别向右和向左填充颜色，直到遇到边界点，同时返回填充的点的个数。这两个函数返回填充点的个数是为了正确调整当前种子点所在的扫描线的区间[xLeft, xRight]。SearchLineNewSeed()函数完成算法第4步所描述的操作，就是在新扫描线上寻找种子点，并将种子点入栈，新扫描线的区间是xLeft和xRight参数确定的：
234 void SearchLineNewSeed(std::stack
235 int y, int new_color, int boundary_color)
236 {
237 int xt = xLeft;
238 bool findNewSeed = false;
239
240 while(xt <= xRight)
241 {
242 findNewSeed = false;
243 while(IsPixelValid(xt, y, new_color, boundary_color) && (xt < xRight))
244 {
245 findNewSeed = true;
246 xt++;
247 }
248 if(findNewSeed)
249 {
250 if(IsPixelValid(xt, y, new_color, boundary_color) && (xt == xRight))
251 stk.push(Point(xt, y));
252 else
253 stk.push(Point(xt - 1, y));
254 }
255
256 /*向右跳过内部的无效点（处理区间右端有障碍点的情况）*/
257 int xspan = SkipInvalidInLine(xt, y, xRight, new_color, boundary_color);
258 xt += (xspan == 0) ? 1 : xspan;
259 /*处理特殊情况,以退出while(x<=xright)循环*/
260 }
261 }
最外层的while循环是为了保证区间[xLeft, xRight]右端被障碍点分隔成多段的
情况能够得到正确处理，通过外层while循环，可以确保为每一段都找到一个种子点。内层的while循环只是为了找到每一段最右端的一个可填充点作为种子点。SkipInvalidInLine()函数的作用就是跳过区间内的障碍点，确定下一个分隔段的开始位置。
13. 设五边形的五个顶点坐标为(10, 10)，(15, 5)，(12, 5)，(8, 2)和(4, 5)，利用多边形区域填充算法，编一程序生成一个实心图。 解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表： 6-10 5 4 3 2 1 该多边形的AET指针的内容为： 1 AET为空 2 3 4 1 2 3 4 5 6 7 8 9 10 01234567891011121314 1516
5 6 7 8 9 10 具体编程实现如下： 第1步：(1) 根据输入的五个顶点坐标找到y 值最小的点(例如点D ，此时y=2)，并找到与D 有边关系的两个顶点(此时为E 和C)，在y=2处建立ET 边表记录(ymax 、xi 和m 值均可通过顶点坐标间的计算得到，例如DE 边的建立，特别注意：当D 点和E 点y 坐标值相同时，也即是DE 与x 轴平行，该边不能计入ET 边表)，之后标记D 点被访问过；(2) 排除访问过的点以及和该点相关联的边，重复(1)直至将ET 表建立完善。 [注]边关系的建立可通过邻接矩阵的数据结构实现，权值可以为该矩阵行编号对应点的y 坐标值，ET 边表采用邻接表的数据结构 第2步：根据ET 表构建AET 表，并逐行完成多边形填充，具体的C++代码如下： (1) 建立头文件base_class.h ，主要是边表结点结构体和ET 边表类的实现 enum ResultCode{Success, Failure}; template
扫描线算法（S c a n-L i n e F i l l i n g） 扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指 定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏和三维CAD软件的渲染等等。 对矢量多边形区域填充，算法核心还是求交。《计算几何与图形学有关的几种常用算法》 一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法，利用此算法可以 判断一个点是否在多边形内，也就是是否需要填充，但是实际工程中使用的填充算法都是 只使用求交的思想，并不直接使用这种求交算法。究其原因，除了算法效率问题之外，还 存在一个光栅图形设备和矢量之间的转换问题。比如某个点位于非常靠近边界的临界位置，用矢量算法判断这个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就 有可能是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此， 适用于矢量图形的填充算法必须适应光栅图形设备。 2.1扫描线算法的基本思想 扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首尾相 连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些交点按照 x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。 多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤：（1）求交，计算扫描线与多边形的交点 （2）交点排序，对第2步得到的交点按照x值从小到大进行排序； （3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充； （4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步 继续处理； 整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端点的 特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。 对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算，则计算量大，而且效 率底下，如图（6）所示： 图（6）多边形与扫描线示意图
实验四区域填充算法的实现 一、实验目的和要求： 1、掌握区域填充算法基本知识 2、理解区域的表示和类型，能正确区分四连通和八连通的区域 3、了解区域填充的实现原理，利用Microsoft Visual C++ 6.0（及EasyX_2011版） 实现区域种子填充的递归算法。 二、实验内容： 1、编程完成区域填色 2、利用画线函数，在屏幕上定义一个封闭区域。 3、利用以下两种种子填充算法，填充上述步骤中定义的区域 (1)边界表示的四连通区域种子填充的实现 (2)内点表示的四连通区域种子填充的实现 4、将上述算法作部分改动应用于八连通区域，构成八连通区域种子填充算法， 并编程实现。 三、实验结果分析 1、以上各种算法相应代码及运行结果如下： 程序代码： #include
/种子填充算法 void CZhztchView::boundaryfill4(int x, int y, int boundarycolor, int newcolor) { int color; CClientDC dc(this); //获取客户区设备描述表 color=dc.GetPixel(x,y); if(color!=newcolor&&color!=boundarycolor) { dc.SetPixel(x,y,newcolor); boundaryfill4(x,y+1,boundarycolor,newcolor); boundaryfill4(x,y-1,boundarycolor,newcolor); boundaryfill4(x-1,y,boundarycolor,newcolor); boundaryfill4(x+1,y,boundarycolor,newcolor); } } ///////////////////////////////////////////////////////////////// /////////////// //扫描线填充算法 void CZhztchView::OnScanfill() {
RedrawWindow(); CDC* pDC=GetDC(); CPen newpen(PS_SOLID,3,RGB(255,0,0)); CPen *old=pDC->SelectObject(&newpen); spt[0]=CPoint(100,100); //绘制多边形区域 spt[1]=CPoint(300,100); spt[2]=CPoint(250,250); spt[3]=CPoint(100,250); spt[4]=CPoint(150,200); spt[5]=CPoint(90,180); spt[6]=CPoint(150,150); spt[7]=CPoint(100,100); pDC->Polyline(spt,8); //pDC->SelectObject(old); //ReleaseDC(pDC); // TODO: Add your command handler code here //CDC* pDC=GetDC(); CPen newpen2(PS_SOLID,1,RGB(0,255,0)); CPen *old2=pDC->SelectObject(&newpen2); int j,k,s = 0;
任意封闭多边形的扫描线填充算法类收藏 这个代码不是我写的，但是我肯定这代码是一个牛人写的，放在这里供大家学习和使用啦！感谢原作者！ 我在这里做了些改进： 1 去除了绘制多边形的函数，使其成为了一个纯的填充算法模块 2 改进了其成员变量，使其更容易让大多数人所使用 3 改进了填充，使其“看”（代码上）起来更像用扫描线在填充 改进后的扫描线算法类如下： //扫描线填充算法类 class CPFill { public: CPoint *Point; //指向点坐标的指针 int Count; //多边形点的个数 public: CPFill(int,int[],int[]);//构造函数 bool FillPolygon(CDC*);//填充多边形 bool CrossJudge(CPoint,CPoint,CPoint,CPoint,CPoint&);//判断两条线段是否相交 int GetAi(int);//获取下一个点的索引号 int GetBi(int);//获取前一个点的索引号 bool Sort(int*,int);//冒泡排序 ~CPFill();//析构函数 }; //构造函数（模块入口，koradji 注，合理的设计这个地方，就可以完全不用改动其他的地方就可以使用这个类） CPFill::CPFill(){ } //获取前一个点的索引号 int CPFill::GetBi(int i) { return (i==0)? Count-1:i-1; } //获取下一个点的索引号
int CPFill::GetAi(int i) { return (i==Count-1)?0:i+1; } //在指定的pDC设备中，填充多边形 bool CPFill::FillPolygon(CDC* pDC) { //获取多边形中所有坐标点的最大值和最小值，作为扫描线循环的范围 int minX=Point[0].x , minY=Point[0].y; int maxX=Point[0].x , maxY=Point[0].y; for(int i=1;i
计算机图形学四连通区域种子填充算法实 验
《计算机图形学实验》报告 任课教师：钱文华 2016年春季学期 实验:四连通区域种子填充算法 实验时间：2016年12月8日 实验地点：信息学院2204 实验目的：掌握种子填充算法的原理，并会用种子填充算法和opengl并结合使用c++语言编写程序绘制多边形。
实验原理：种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。内点的检测条件： if(interiorColor!=borderColor&&interiorColor!=fillColor)。 种子填充算法常用四连通域和八连通域技术进行填充操作。从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。 四向连通填充算法： a）种子像素压入栈中； b）如果栈为空，则转e)；否则转c)； c）弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈； d）转b）； e）结束。 四连通填充算法利用到了递归的思想。
本实验只包括四连通填充算法 程序代码：#include
课程设计报告 课程名称计算机图形学 课题名称多边形裁剪与填充 专业计算机科学与技术 班级计算机0902 学号 姓名 指导教师刘长松曹燚 2012年10 月9 日
湖南工程学院 课程设计任务书 课程名称计算机图形学课题多边形裁剪与填充 专业班级计算机0902 学生姓名 学号 指导老师刘长松曹燚 审批 任务书下达日期2012年9月15 日 任务完成日期2012 年10月9 日
一、设计内容与设计要求 1．设计内容： 交互式地实现多边形的裁剪和填充。。 2．设计要求： 1）窗口功能设计。 2）实现鼠标画多边形与数据存储功能。 3）实现鼠标剪裁窗口选择功能。 4）实现多边形裁剪和填充功能。 3.算法提示： 多边形裁剪算法分析： 基本思想是一次用窗口的一条边裁剪多边形，窗口的一条边以及延长线构成裁剪线，该线把平面分成两个部分：可见一侧，不可见一侧。用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入点。 对于每一条裁剪边，只是判断点在窗口的哪一测以及求线段与裁剪边的交点算法应随之改变。 多边形填充算法分析： 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin 和ymax），从y=ymin 到 y=ymax, 每次用一条扫描进行填充。对一条扫描线填充的过程可分为四个步骤: a.求交b.排序c.交点配对d.区间填色。 二、进度安排 第 3 周星期一8：00——12：00 星期二8：00——12：00 星期三8：00——12：00 星期四8：00——12：00 星期五8：00——12：00 第 4 周星期一8：00——12：00 附： 课程设计报告装订顺序：封面、任务书、目录、正文、附件（A4大小的图纸及程序清单）、评分。正文的格式：一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。 正文的内容：一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。 正文总字数要求在5000字以上（不含程序原代码）。
扫描线算法（Scan-Line F illing） 扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏 和三维CAD软件的渲染等等。 对矢量多边形区域填充，算法核心还是求交。《计算几何与图形学有关的几种 常用算法》一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断 算法，利用此算法可以判断一个点是否在多边形内，也就是是否需要填充，但 是实际工程中使用的填充算法都是只使用求交的思想，并不直接使用这种求交 算法。究其原因，除了算法效率问题之外，还存在一个光栅图形设备和矢量之 间的转换问题。比如某个点位于非常靠近边界的临界位置，用矢量算法判断这 个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能 是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此，适用于矢量图形的填充算法必须适应光栅图形设备。 2.1扫描线算法的基本思想 扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由 多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列 交点。将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个 端点，以所填的颜色画水平直线。多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤： （1）求交，计算扫描线与多边形的交点 （2）交点排序，对第2步得到的交点按照x值从小到大进行排序； （3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进 行颜色填充； （4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然 后转第1步继续处理； 整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是 线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出 显示。
计算机图形学 ——区域填充的扫描线算法 NORTHWESTUNIVER SITY
一、实验目的 1.通过实验，进一步理解和掌握几种常用多边形填充算法的基本原理 2.掌握多边形区域填充算法的基本过程 3.掌握在C/C++环境下用多边形填充算法编程实现指定多边形的填充。 4.利用TC2.0编写区域填充的扫描线算法。 二、实验内容 算法基本思想：首先填充种子点所在扫描线上位于区域内的区段，然后确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存, 这些区段分别被用区域边界色显示的像素点所包围。随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。 算法描述：扫描线填充算法一般包括四个步骤：求交、排序、交点配对、区域填充。正确求得扫描线与区域填内外轮廓线的交点是算法成败的关键问题。另一方面，采用合适的数据结构又可以简化操作、提高算法的效率。本论文由于采用链表结构记录轮廓线和交点，无需焦点排序的过程，因而提高了算法效率。扫描线来源于光栅显示器的显示原理：对于屏幕上所有待显示像素的信息，将这些信息按从上到下、自左至右的方式显示。 扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; （4）填色：把相交区间内的象素置成多边形颜色; 三、实验原理 扫描线填充算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。 区域填充的扫描线算法可由下列四个步骤实现： (1)初始化：堆栈置空。将种子点(x,y)入栈。 (2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。 (4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条
实验报告 一、实验目的 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为空。 ●将新边表ET中对应y值的新边节点插入到AET表。 ●遍历AET表，将两两配对的交点之间填充给定颜色值。 ●遍历AET表，将 ymax= y的边节点从AET表中删除，并将ymax> y的各边节点 的x值递增Δx；并重新排序。 ●y增加1。 三、程序源代码 #include "graphics.h" #define WINDOW_HEIGHT 480 #define NULL 0 #include "alloc.h" #include "stdio.h" #include "dos.h" #include "conio.h" typedef struct tEdge /*typedef是将结构定义成数据类型*/ { int ymax; /* 边所交的最高扫描线号 */
实验三多边形的有效边表填充算法 一、实验目的与要求 1、理解多边形的扫描转换原理、方法； 2、掌握有效边表填充算法； 3、掌握链表的建立、添加结点、删除节点的基本方法； 3、掌握基于链表的排序操作。 二、实验内容 在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类 CMyGL 中。 1、C++实现有效边表算法进行多边形扫描转换 2、利用1进行多边形扫描转换和区域填充的实现； 三、实验原理 请同学们根据教材及上课的PPT独立完成。 四、实验步骤（程序实现）。 1、建立并选择工程项目。打开VC6.0->菜单File 的New 项,在projects 属性页选择MFC AppWizard(exe)项，在Project name 中输入一个工程名,如“Sample”。单文档。 2、新建一个图形类。选择菜单Insert New class，Class type 选择“Generic Class”，Name 输入类名，如“CMyCG。 3、向新建的图形类中添加成员函数（实际就是加入实验要求实现的图形生成算法的实现代码）。在工作区中直接鼠标右键单击，选择“Add Member Function…”项，添加绘制圆的成员函数。 void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC) 添加其他成员函数： CreatBucket(); CreatET(); AddEdge(); EdgeOrder(); 4、成员函数的实现。实现有效边表填充算法。这一部分需要同学们去实现。 参考实现： 多边形的有效边表填充算法的基本过程为： 1、定义多边形： 2、初始化桶 3、建立边表 4、多边形填充 1)对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE. 2)对临时AET表排序，按照x递增的顺序存放。 3)根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanline 4)扫描AET表，填充扫描线和多边形相交的区间。
实验六扫描线填充算法 一、实验目的 编写多边形的扫描线填充算法程序，加深对扫描线算法的理解，验证算法的正确性。 二、实验任务（2学时） 编写多边形的扫描线填充算法程序，利用数组实现AET，考虑与链表实现程序的不同。 三、实验内容 1、算法 对一条扫描线的填充一般分为以下4个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把扫描线上所有交点按递增顺序进行排序； （3）配对：将第一个交点与第二个交点，第三个交点与第四个交点等等进行配对，每对交点代表扫描线与多边形的一个相交区间。 （4）着色：把区间内的像素置为填充色。 2、成员函数的关系 主程序名为fill_area(count, x, y)，其中参数x, y是两个一维数组，存放多边形顶点（共c ount个）的x和y坐标。它调用8个子程序，彼此之间的调用关系图1所示为： 图1 fill_area的程序结构 3、算法的程序设计
步骤1：创建“S_L_Fill”工程文件； 步骤2：创建类class：“EACH_ENTRY”。 在工作区“S_L_Fill classes”单击右键-→“new class”-→选择类型“Generic Class”名称为“EACH_ENTRY”，添加成员变量（添加至“class EACH_ENTRY { public:”之内）：int y_top; float x_int; int delta_y; float x_change_per_scan; 步骤3：包含头文件，同时初始化定义多边形顶点数目。在“class CS_L_FillView : public Cview……”之前添加代码“#include EACH_ENTRY.h”及“#define MAX_POINT 9”。 #define MAX_POINT 9 #include "EACH_ENTRY.h" 步骤4：在类“class CS_L_FillView”中添加成员变量（鼠标双击工作区“CS_L_FillView”，代码添加至“class CS_L_FillView : public Cview {protected: ……public:之后”）：EACH_ENTRY sides[MAX_POINT]; int x[MAX_POINT],y[MAX_POINT]; int side_count,first_s,last_s,scan,bottomscan,x_int_count; 步骤5：利用构造函数“CS_L_FillView::CS_L_FillView()”初始化顶点坐标（鼠标双击工作区“CS_L_FillView”，代码添加至“CS_L_FillView（）之内”）： x[0]=200;y[0]=100; x[1]=240;y[1]=160; x[2]=220;y[2]=340; x[3]=330;y[3]=100; x[4]=400;y[4]=180; x[5]=300;y[5]=400; x[6]=170;y[6]=380; x[7]=120;y[7]=440; x[8]=100;y[8]=220; 步骤6：在“class CS_L_FillView”下添加实现不同功能的成员函数。在工作区“CS_L_FillView”上单击鼠标右键，选择“Add Member Function”，分别完成以下成员函数的添加： （1）void put_in_sides_list(int entry,int x1,int y1,int x2,int y2,int next_y) 函数说明：put_in_sides_list子程序的主要功能是将一条边存入活性边表之内。操作步骤是：对该边判别是否左顶点或右顶点，如果将入边之终点删去，按照y_top的大小在活性边表中找到该点的合适位置，y值较大者，排在活性边表的靠前位置。 void put_in_sides_list(int entry,int x1,int y1,int x2,int y2,int next_y)// entry为剔除水平边之后的第entry条边，x1, y1,为起点，x2, y2为终点，next_y为终点相邻的下一个顶点y坐标{ int maxy; float x2_temp,x_change_temp; x_change_temp=(float)(x2-x1)/(float)(y2-y1);//计算1/k x2_temp=float(x2); if((y2>y1)&&(y2 实验三区域填充种子算法实现 实验目的： 1、熟练在Visual C＋＋中程序实现及调试的能力。 2、通过程序的设计熟练区域填充种子算法过程； 3、掌握堆栈在数据结构中的应用 实验内容： 1、visual c＋＋中菜单的修改，点的输入及鼠标函数的控制； 2、复习数据结构中堆栈的建立，入栈，出栈等函数； 3、实现整个多边形的区域填充种子算法，与扫描转换算法进行区分； 实验步骤： 预处理：多边形点列的输入，存储于数组中P[100]，种子点的输入，确定为point（x，y） 确定多边形的边界色（旧画笔色），初始色（背景色），填充色（新画笔色）； 数据结构的建立：建立堆栈，包括数组stack[100],及一个指标top，用来指向当前堆栈的最外面的栈口的元素。 步骤：1、堆栈置为空，top=0; 2、将初始的种子点point进栈，push(x,y); 3、填色堆栈非空即top>0时，一直循环下列步骤 取栈顶的元素，出栈pop(x,y)，savex=x; 从当前点开始沿当前扫描线往右检验，若有未填新色的，则填色。 然后同样往左检验。 当前扫描线俩个方向都检查完后，检验上一条扫描线y=y+1; 若有未填新色的，则把所有未填新色区间的右端点压入堆栈。 同理检验下一条扫描线y=y-2; 实验指导： 一、 在实验二的基础上进行编程 ； （1） 引入实验二代码 scanline.dsw 二、 编辑菜单资源 选中窗口左边栏的“ResourceView ”，其中的“Menu ”，双击“IDR_MAINFRAME ”，右边即为菜单，在菜单上空处双击，出项如图所示窗口，其中弹出不选中； 如上，同样创建其余菜单项。(如下表)； 三、 添加消息处理函数 由菜单的“查看”，“建立类向导”，打开ClassWizard （也可CTRL+W ）为应用程序添加与菜单项相关的消息处理函数，ClassName 栏选中CScanLineView 类，根据表建立。 输入菜单项名称，（如显示多边形） 双击，出现如下窗口 扫描线Z-Buffer算法作业说明 学号20821055 姓名邹松 联系方式zousong@https://www.doczj.com/doc/645903293.html, 1、SRC目录 src目录为算法源代码，编译环境为microsoft visual c++ 2005 express edition，源码中有主要步骤的注释说明。绘制时用到了OpenGL的glDrawPixels函数，需用到OpenGL库文件和头文件及glut库 2、BIN目录 bin目录为编译好的可执行程序，批处理运行程序，多个测试obj文件。 各个obj文件说明： cube.obj 为立方体模型，8个点，12个面，36条边。 cone.obj为圆台模型，146个点，288个多边形，864条边； sphere.obj为球模型，482个点，960个多边形，2880条边; teapot.obj为茶壶模型，530个点，992个多边形，2976条边; torus.obj为圆环模型，288个点，576个多边形，1728条边; torusknot.obj为环形结模型，1440个点，2880个多边形，8640条边; venusm.obj 为维纳斯像模型，19755个点，43357个多边形，130071个条边。 test.obj为我自己手工建立的obj文件，包含一个五角星和两个三角形，主要测试(凹)多边形(上面几个模型都只有三角形)，及多边形互相贯穿的情况。 可执行程序运行方式: SL_Z_buffer [file] 参数分别为obj文件名 默认分别为test.obj 直接运行run.bat文件即可对以上obj文件分别绘制出对应的图像。 使用的可执行程序为每个面片产生随机颜色 运行SL_Z_buffer可绘制test.obj 对应的图像 计算机图形学——区域填充的扫描线算法 一．实验名称： 区域填充的扫描线算法 二．实验目的： 1、理解区域填充扫描线算法的原理； 2、实现区域填充的扫描线算法并测试； 三．算法原理： 算法基本思想: 首先填充种子点所在扫描线上位于区域内的区段，然后确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存, 这些区段分别被用区域边界色显示的像素点所包围。随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。 借助于栈结构，区域填充的扫描线算法之步骤如下： Step 1. 初始化种子点栈：置种子点栈为空栈，并将给定的种子点入栈； Step 2. 出栈：若种子点栈为空，算法结束；否则，取栈顶元素(x，y)为种子点； Step 3. 区段填充：从种子点(x, y) 开始沿纵坐标为y 的当前扫描线向左右两个方向逐像素点进行填色，其颜色值置为newcolor 直至到达区域边界。分别以xl 和xr 表示该填充区段两端点的横坐标； Step 4. 新种子点入栈: 分别确定当前扫描线上、下相邻的两条 扫描线上位于区段[xl, xr] 内的区域内的区段。若这些区段内的像素点颜色值为newolor ,则转至Step 2；否则以区段的右端点为种子点入种子点栈，再转至Step 2。 四．原程序代码： /*****************************************/ /*4-ScanLineFill 区域填充的扫描线算法实现*/ /*****************************************/ #include [最新]扫描线算法代码 #include /* Inserts edge into list in order of increasing xIntersect field. */ void insertEdge (Edge * list, Edge * edge) { Edge * p, * q = list; p = q->next; while (p != NULL) { if (edge->xIntersect < p->xIntersect) p = NULL; else { q = p; p = p->next; } } edge->next = q->next; q->next = edge; } /* For an index, return y-coordinate of next nonhorizontal line */ int yNext (int k, int cnt, dcPt * pts) { int j; if ((k+1) > (cnt-1)) j = 0; else j = k + 1; while (pts[k].y == pts[j].y) 多边形的偏移填充算法 多边形偏移（polygon offset）算法可能我们印象不深，不过用过autoCAD的同学也印象autoCAD 上面也还是有这个功能的。我们可以用autoCAD上的“正多边形”功能画一个多边形，然后用修改工具中“偏移”按钮，对多边形进行偏移，见图1，从外面的一个大的5边形按照边偏移至里面小的5边形，其中相应边偏移的距离定义为offset值。 图1 AutoCAD中的多边形偏移效果图 当然，这只是简单的情况，复杂的情况可能是有多个多边形，其中1个outer多边形，多个inner 多边形，然后offset的时候应该是outer多边形向内offset，inner多边形向外offset。当一个多边形（特别是凹多边形）初步offset时，可能会发生自交；然后多边形之间也可能会发生相交。大概思路：这里就需要首先将自交的多边形分裂出来，并选择正确的多边形；然后将选择出来的多边形进行求交计算，再一次将有相交的多边形合并分裂出来，并且选择正确的多边形，这个时候得到的全部多边形就是一次offset出来的结果。 1、为了保证outer多边形能向内offset，inner多边形能向外offset，这里需要保证outer多边形是逆时针方向旋转的，inner多边形是顺时针方向旋转的。 1.1 这里就稍稍讲下多边形的顺逆判断。 在多边形是简单多边形的前提下，其实还是挺简单的，只要找出多边形左下角的一个顶点，然后判断与这个顶点相连的两条边的叉积是否大于0就行了；如果多边形不是简单多边形，比如有自相交，有顶点夹角为0的情况等等，这个时候多边形就不应该有顺逆这种属性吧 2、对单个多边形，根据角平分线初步偏移得到角点 对于一个角点，可以设这个顶点为curPoint，相连的前一个点为prePoint，下一个点为nexPoint，于是可以得到两个向量a = prePoint – curPoint，b=nexPoint – curPoint。将向量a和b设置为单位向量之后，相加就能得到角平分线的方向向量c。然后对单位向量a和b做点乘和叉乘，就能得到这个角度的cos和sin值了，我们假设这个角度的一般为Θ，则cos=cos2Θ，sin=sin2Θ。根据三角函数，就能得到sinΘ值，之后将就能得到该顶点的角平分线方向的偏移向量d=c/|c|×offset÷sinΘ。 3、考虑到有些边在偏移的过程中会消失，即一些边有退化的offset值，见图3。如果初步偏移的值大于它的退化offset值，则该边就会反向出现，见图3中的边【4,5】，会给后面的程序带来很大的麻烦。 图2区域填充种子算法实现
扫描线Z-Buffer算法作业说明-Read
计算机图形学-区域填充的扫描线算法
[最新]扫描线算法代码
多边形的偏移填充算法
相关主题
文本预览