精华内容
下载资源
问答
  • 多边形扫描填充算法

    2011-11-24 12:08:35
    多边形扫描填充算法,填充图案为自己的学号
  • 编写C++MFC程序,要求在MFC的视图中利用鼠标画多边形,并按要求利用横线或竖线进行填充。利用对话框控制线的数量或密度,以及横线或竖线,并可以重复画线或填充
  • python实现扫描线填充算法,使用matplotlib模块将绘制的图形保存并画出来,可以画凹多边形
  • C语言实现多边形扫描转换算法源码。 C语言实现多边形扫描转换算法,绝对原创! C语言 多边形扫描转换 源代码 水平扫描线 扫描线
  • 计算机图形学的大实验,直线、圆、多边形画法,多边形填充算法,包括扫描线填充、四方向种子填充和种子栈填充,方法是,先画好多边形,点击多边形填充方法,选择好颜色后,点击多边形,就可自动填充。注意,种子填充...
  • 用java编写的多边形扫描填充算法,有文档和在jbuilder下打包的exe文件
  • 多边形扫描填充算法 1、顶点按右图形状自定整数坐标; 2、计算新边表; 3、用活化边填充内部线段; 1、顶点按右图形状自定整数坐标; P0(12,0)、P1(10,12)、P2(6,6)、P3(4,10)、P4(2,2) 2、计算新边表; 3、用...

    多边形扫描填充算法

    1、顶点按右图形状自定整数坐标;
    2、计算新边表;
    3、用活化边填充内部线段;

    1、顶点按右图形状自定整数坐标;
    P0(12,0)、P1(10,12)、P2(6,6)、P3(4,10)、P4(2,2)
    在这里插入图片描述

    2、计算新边表;
    在这里插入图片描述
    在这里插入图片描述
    3、用活化边填充内部线段
    在这里插入图片描述

    展开全文
  • vs2008下 opengl实现,多边形扫描线填充算法。 用到glut库 鼠标左右键实现选点和填充
  •  扫描线算法适合对矢量图形进行区域填充,只需要直到多边形区域的几何位置,不需要指定种子点,适合计算机自动进行图形处理的场合使用,比如电脑游戏和三维CAD软件的渲染等等。  对矢量多边形区域填充算法核心...

    二、扫描线算法(Scan-Line Filling)

            扫描线算法适合对矢量图形进行区域填充,只需要直到多边形区域的几何位置,不需要指定种子点,适合计算机自动进行图形处理的场合使用,比如电脑游戏和三维CAD软件的渲染等等。

            对矢量多边形区域填充,算法核心还是求交。《计算几何与图形学有关的几种常用算法》一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法,利用此算法可以判断一个点是否在多边形内,也就是是否需要填充,但是实际工程中使用的填充算法都是只使用求交的思想,并不直接使用这种求交算法。究其原因,除了算法效率问题之外,还存在一个光栅图形设备和矢量之间的转换问题。比如某个点位于非常靠近边界的临界位置,用矢量算法判断这个点应该是在多边形内,但是光栅化后,这个点在光栅图形设备上看就有可能是在多边形外边(矢量点没有大小概念,光栅图形设备的点有大小概念),因此,适用于矢量图形的填充算法必须适应光栅图形设备。

     

    2.1扫描线算法的基本思想

            扫描线填充算法的基本思想是:用水平扫描线从上到下(或从下到上)扫描由多条首尾相连的线段构成的多边形,每根扫描线与多边形的某些边产生一系列交点。将这些交点按照x坐标排序,将排序后的点两两成对,作为线段的两个端点,以所填的颜色画水平直线。多边形被扫描完毕后,颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤:

     

    (1)       求交,计算扫描线与多边形的交点

    (2)       交点排序,对第2步得到的交点按照x值从小到大进行排序;

    (3)       颜色填充,对排序后的交点两两组成一个水平线段,以画线段的方式进行颜色填充;

    (4)       是否完成多边形扫描?如果是就结束算法,如果不是就改变扫描线,然后转第1步继续处理;

     

            整个算法的关键是第1步,需要用尽量少的计算量求出交点,还要考虑交点是线段端点的特殊情况,最后,交点的步进计算最好是整数,便于光栅设备输出显示。

            对于每一条扫描线,如果每次都按照正常的线段求交算法进行计算,则计算量大,而且效率底下,如图(6)所示:

    观察多边形与扫描线的交点情况,可以得到以下两个特点:

     

    (1)       每次只有相关的几条边可能与扫描线有交点,不必对所有的边进行求交计算;

    (2)       相邻的扫描线与同一直线段的交点存在步进关系,这个关系与直线段所在直线的斜率有关;

     

            第一个特点是显而易见的,为了减少计算量,扫描线算法需要维护一张由“活动边”组成的表,称为“活动边表(AET)”。例如扫描线4的“活动边表”由P1P2和P3P4两条边组成,而扫描线7的“活动边表”由P1P2、P6P1、P5P6和P4P5四条边组成。

            第二个特点可以进一步证明,假设当前扫描线与多边形的某一条边的交点已经通过直线段求交算法计算出来,得到交点的坐标为(x, y),则下一条扫描线与这条边的交点不需要再求交计算,通过步进关系可以直接得到新交点坐标为(x + △x, y + 1)。前面提到过,步进关系△x是个常量,与直线的斜率有关,下面就来推导这个△x。

            假设多边形某条边所在的直线方程是:ax + by + c = 0,扫描线yi和下一条扫描线yi+1与该边的两个交点分别是(xi,yi)和(xi+1,yi+1),则可得到以下两个等式:

     

    axi + byi + c = 0                        (等式 1)

    axi+1 + byi+1 + c = 0                     (等式 2)

     

    由等式1可以得到等式3:

     

    xi = -(byi + c) / a                           (等式 3)

     

    同样,由等式2可以得到等式4:

     

    xi+1 = -(byi+1 + c) / a                      (等式 4)

     

    由等式 4 – 等式3可得到

     

    xi+1 – xi = -b (yi+1 - yi) / a

     

    由于扫描线存在yi+1 = yi + 1的关系,将代入上式即可得到:

     

    xi+1 – xi = -b / a

     

    即△x = -b / a,是个常量(直线斜率的倒数)。

     

            “活动边表”是扫描线填充算法的核心,整个算法都是围绕者这张表进行处理的。要完整的定义“活动边表”,需要先定义边的数据结构。每条边都和扫描线有个交点,扫描线填充算法只关注交点的x坐标。每当处理下一条扫描线时,根据△x直接计算出新扫描线与边的交点x坐标,可以避免复杂的求交计算。一条边不会一直待在“活动边表”中,当扫描线与之没有交点时,要将其从“活动边表”中删除,判断是否有交点的依据就是看扫描线y是否大于这条边两个端点的y坐标值,为此,需要记录边的y坐标的最大值。根据以上分析,边的数据结构可以定义如下:

    typedef struct tagEDGE
    {
    	int ymax;
    	float xi;
    	float dx;
    	tagEDGE(float my, float mx, float mdx) :ymax(my), xi(mx), dx(mdx) {}
    	bool operator<(tagEDGE &e);
    }EDGE;
    bool tagEDGE::operator<(tagEDGE &e)
    {
    	if(xi!=e.xi)
    		return xi < e.xi;
    	if (dx == 0)	return e.dx > 0;
    	if (e.dx == 0)	return dx < 0;
    	if (dx < 0 && e.dx>0)	return true;
    	if (dx > 0 && e.dx < 0)	return false;
    	return dx * ymax < e.dx*e.ymax;
    }

    根据EDGE的定义,扫描线4和扫描线7的“活动边表”就分别如图(7)和图(8)所示:

                                                                                 图(7) 扫描线4的活动边表

     

                                                                               图(8) 扫描线7的活动边表

    前面提到过,扫描线算法的核心就是围绕“活动边表(AET)”展开的,为了方便活性边表的建立与更新,我们为每一条扫描线建立一个“新边表(NET)”,存放该扫描线第一次出现的边。当算法处理到某条扫描线时,就将这条扫描线的“新边表”中的所有边逐一插入到“活动边表”中。“新边表”通常在算法开始时建立,建立“新边表”的规则就是:如果某条边的较低端点(y坐标较小的那个点)的y坐标与扫描线y相等,则该边就是扫描线y的新边,应该加入扫描线y的“新边表”。上例中各扫描线的“新边表”如下图所示:

                                                                           图(9) 各扫描线的新边表

    讨论完“活动边表(AET)”和“新边表(NET)”,就可以开始算法的具体实现了,但是在进一步详细介绍实现算法之前,还有以下几个关键的细节问题需要明确:

    (1)      多边形顶点处理

            在对多边形的边进行求交的过程中,在两条边相连的顶点处会出现一些特殊情况,因为此时两条边会和扫描线各求的一个交点,也就是说,在顶点位置会出现两个交点。当出现这种情况的时候,会对填充产生影响,因为填充的过程是成对选择交点的过程,错误的计算交点个数,会造成填充异常。

            假设多边形按照顶点P1、P2和P3的顺序产生两条相邻的边,P2就是所说的顶点。多边形的顶点一般有四种情况,如图(10)所展示的那样,分别被称为左顶点、右顶点、上顶点和下顶点:

    除了下顶点在活动边表(AET)上存在两条边,其余的顶点在AET上只存在一条边,对于另外三种顶点,我们称为局部非极限点,如果不对局部非极限点做特殊处理会导致奇偶奇数错误,常采用的修正方法是修改以顶点为终点的那条边的区间,将顶点排除在区间之外,也就是删除这条边的终点,这样在计算交点时,就可以少计算一个交点,平衡和交点奇偶个数。结合前文定义的“边”数据结构:EDGE,只要将该边的ymax修改为ymax + 1就可以了。

    (2)      水平边的处理

        水平边与扫描线重合,会产生很多交点,通常的做法是将水平边直接画出(填充),然后在后面的处理中就忽略水平边,不对其进行求交计算。

    (3)      如何避免填充越过边界线

            边界像素的取舍问题也需要特别注意。多边形的边界与扫描线会产生两个交点,填充时如果对两个交点以及之间的区域都填充,容易造成填充范围扩大,影响最终光栅图形化显示的填充效果。为此,人们提出了“左闭右开”的原则,简单解释就是,如果扫描线交点是1和9,则实际填充的区间是[1,9),即不包括x坐标是9的那个点。

    2.2扫描线算法实现

    扫描线算法的整个过程都是围绕“活动边表(AET)”展开的,为了正确初始化“活动边表”,需要初始化每条扫描线的“边表(ET)”,首先定义“边表”的数据结构。定义“边表”为一个红黑树,map的每个元素存放对应的y值最小的扫描线的所有“边”。因此定义“边表”如下:

    std::map<int, std::list<EDGE> > ET;

    接下来我们要以多边形的顶点计算所有的边,并且初始化ET表:

    ​for (unsigned i = 0; i < v.size() - 1; i++)
    {
    	if (v[i + 1].x == v[i].x)
    			continue;
    	float dx = v[i + 1].y - v[i].y == 0 ? 0 : (v[i + 1].x - v[i].x) / (v[i + 1].y - v[i].y);
    	float ymax, xi, ymin;//xi低端点的x值,x高端点的x值
    	if (v[i + 1].y > v[i].y){
    		ymax = v[i + 1].y;
    		ymin = v[i].y;
    		xi = v[i].x;
    	}
    	else {
    		ymax = v[i].y;
    		ymin = v[i + 1].y;
    		xi = v[i + 1].x;
    	}
    	EDGE e(ymax, xi, dx);
    	ET[ymin].push_back(e);
    }
    

    接下来要对ET表进行更新,将特殊点进行特殊处理:

    //更新边表,将非极值点边表向y轴方向沿线段缩短一个单位
    	for (auto it = ET.begin(); it != ET.end();)
    	{
    		if (it->second.size() == 1) {
    			EDGE e = *(it->second.begin());
    			e.xi += e.dx;
    			int ymin = it->first + 1;
    			ET.erase(it++);
    			ET[ymin].push_back(e);
    		}
    		it++;
    	}

    最后,我们需要定义一个AET表,对AET表的操作:

    (1)画一条与x轴水平的扫描线,扫描线的初始y值与ET表中key键对应的最小y值相等,将ET表中对应的边放入AET表中,对AET表排序

    循环:

      (2)在AET表中遍历所有元素,将此时扫描线与所有边表的交点两两对应,画出交点区间内的所有点,将扫描线往y轴方向移动一个单位

      (3)遍历AET表中所有元素,若扫描线的y值大于边的y值(即扫描线在边上方)则删除该边

    (4)搜索ET表中是否存在该扫描线对应的边,若存在,将该扫描线对应的所有边放入AET表中

    (5)对AET表排序

    循环直到AET表空 :结束

    //创建活动边表并填充
    	std::list<EDGE>AET;
    	int y = 0;
    	
    	//获取首元素
    	y = ET.begin()->first;
    	AET.insert(AET.begin(),ET.begin()->second.begin(),ET.begin()->second.end());
    	AET.sort();
    	glBegin(GL_POINTS);
    	do {
    		auto node = AET.begin();
    		while (node != AET.end())
    		{
    			float x1 = node->xi;
    			node->xi += node->dx;
    			node++;
    			float x2 = node->xi;
    			node->xi += node->dx;
    			node++;
    			while (x1 < x2)
    			{
    				glVertex2f(x1, y);
    				x1++;
    			}
    		}
    		y++; 
    		std::list<EDGE>::reverse_iterator it = AET.rbegin();
    		for (; it != AET.rend();) {
    			if (y > it->ymax)
    				it = std::list<EDGE>::reverse_iterator(AET.erase((++it).base()));
    			else it++;
    		}
    		if (ET.find(y) != ET.end())
    			AET.insert(AET.end(), ET[y].begin(), ET[y].end());
    		AET.sort();
    	}while (!AET.empty());
    	glEnd(); 

    所有代码如下:

    typedef struct tagEDGE
    {
    	int ymax;
    	float xi;
    	float dx;
    	tagEDGE(float my, float mx, float mdx) :ymax(my), xi(mx), dx(mdx) {}
    	bool operator<(tagEDGE &e);
    }EDGE;
    bool tagEDGE::operator<(tagEDGE &e)
    {
    	if(xi!=e.xi)
    		return xi < e.xi;
    	if (dx == 0)	return e.dx > 0;
    	if (e.dx == 0)	return dx < 0;
    	if (dx < 0 && e.dx>0)	return true;
    	if (dx > 0 && e.dx < 0)	return false;
    	return dx * ymax < e.dx*e.ymax;
    }
    void fill(gl::Polygon &py)
    {
    	//初始化边表
    	std::vector<gl::Vertex>v = py.getVertexs();
    	std::map<int, std::list<EDGE> > ET;
    	for (unsigned i = 0; i < v.size() - 1; i++)
    	{
    		if (v[i + 1].x == v[i].x)
    			continue;
    		float dx = v[i + 1].y - v[i].y == 0 ? 0 : (v[i + 1].x - v[i].x) / (v[i + 1].y - v[i].y);
    		float ymax, xi, ymin;//xi低端点的x值,x高端点的x值
    		if (v[i + 1].y > v[i].y){
    			ymax = v[i + 1].y;
    			ymin = v[i].y;
    			xi = v[i].x;
    		}
    		else {
    			ymax = v[i].y;
    			ymin = v[i + 1].y;
    			xi = v[i + 1].x;
    		}
    		EDGE e(ymax, xi, dx);
    		ET[ymin].push_back(e);
    	}
    	//更新边表,将非极值点边表向y轴方向沿线段缩短一个单位
    	for (auto it = ET.begin(); it != ET.end();)
    	{
    		if (it->second.size() == 1) {
    			EDGE e = *(it->second.begin());
    			e.xi += e.dx;
    			int ymin = it->first + 1;
    			ET.erase(it++);
    			ET[ymin].push_back(e);
    		}
    		else {
    			it++;
    		}
    	}
    	//创建活动边表并填充
    	std::list<EDGE>AET;
    	int y = 0;
    	
    	//获取首元素
    	y = ET.begin()->first;
    	AET.insert(AET.begin(),ET.begin()->second.begin(),ET.begin()->second.end());
    	AET.sort();
    
    	glBegin(GL_POINTS);
    	do {
    		auto node = AET.begin();
    		while (node != AET.end())
    		{
    			float x1 = node->xi;
    			node->xi += node->dx;
    			node++;
    			float x2 = node->xi;
    			node->xi += node->dx;
    			node++;
    			while (x1 < x2)
    			{
    				glVertex2f(x1, y);
    				x1++;
    			}
    		}
    		y++; 
    		std::list<EDGE>::reverse_iterator it = AET.rbegin();
    		for (; it != AET.rend();) {
    			if (y > it->ymax)
    				it = std::list<EDGE>::reverse_iterator(AET.erase((++it).base()));
    			else it++;
    		}
    		if (ET.find(y) != ET.end())
    			AET.insert(AET.end(), ET[y].begin(), ET[y].end());
    		AET.sort();
    	}while (!AET.empty());
    	glEnd(); 
    }

    3.实现缺陷

    1.EDG中的ymax为int,实际应为浮点数,整形会有较大的误差

    2.实际上扫描线不应该是均匀采样

    最后总的来说上述实现的代码没什么实际用处=,= 若是读者有兴趣可以完善下。

    展开全文
  • 扫描线法填充多边形,头一次写图形学相关的习题。代码有点啰嗦,而且完全没注意效率。没什么注释。但是保证可以运行。环境:QT5.0
  • 资源内容:通过键盘按键,实现正方体的移动,伸缩,旋转等变换 语言:C++ 运行环境:Visual Studio 2013/更高版本
  • 本文实例为大家分享了python扫描线填充算法,供大家参考,具体内容如下 介绍 1.用水平扫描线从上到下扫描由点线段构成的多段构成的多边形。 2.每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类,...
  • 用c++进行编写,用鼠标左击描绘顶点,右击把最后一个点和第一个点进行连接构造多边形,双击进行多边形颜色填充。这程序把屏幕坐标系转为GL坐标系,用OpenGL进行填充填充时间根据多边形大小而定,最多50个顶点。
  • 多边形扫描线填充算法(vs2010 c++)

    千次阅读 2019-04-26 21:02:47
    扫描线填充算法的基本原理: 用水平扫描线从上到下(或从下到上)扫描由多条首尾相连的线段构成的多边形,每根扫描线与多边形的某些边产生一系列交点。将这些交点按照x坐标排序,将排序后的点两两成对,作为线段的...

     

    扫描线填充算法的基本原理:

    用水平扫描线从上到下(或从下到上)扫描由多条首尾相连的线段构成的多边形,每根扫描线与多边形的某些边产生一系列交点。将这些交点按照x坐标排序,将排序后的点两两成对,作为线段的两个端点,以所填的颜色画水平直线。多边形被扫描完毕后,颜色填充也就完成了。

    几个重要的概念:

    边的数据结构 :

    typedef struct EDGE{
    	int ymax;	/*边所交的最高扫描线号(顶点的最大y值)*/
    	double x;/*当前扫描线与边的交点x值*/
    	double dx; /*从当前扫描线到下一扫描线之间的x增量*/
    	struct EDGE *next;/*下一条边*/
    }Edge;

     

     

    边的分类表:

    为了方便活性边表的建立与更新,我们为每一条扫描线建立一个“新边表(NET)”,存放该扫描线第一次出现的边。

    活性边:把与当前扫描线相交的边称为活性边。

    活性边表:把它们按与扫描线交点x坐标递增的顺序存放在一个链表中,称此链表为活性边表。

    扫描线6的活性边表如下:P6P1 P6P5 P5P4 P4P3
    扫描线4的活性边表如下:P6P1P4P3 
    扫描线3的活性边表如下:P6P1P4P3 
    扫描线2的活性边表如下:P1P6P3P2

    下面说下算法实现:

     

     

    展开全文
  • 采用VC++语言编程实现多边形扫描转换的扫描线填充算法,可以画任意多边形。 多边形为任意多边形,如:凸多边形、凹多边形、含内环多边形。 上传的资源中没有采用通过鼠标画来实现多边形顶点的输入,而是在代码中人...
  •  扫描线多边形区域填充算法是按扫描线顺序(由下到上),计算扫描线与多边形的相交区间,再用要求的颜色显示这些区间的象素,即完成填充工作。    区间的端点可以通过计算扫描线与多边形边界线的交点获得。  ...

    一.基本原理

               扫描线多边形区域填充算法是按扫描线顺序(由下到上),计算扫描线与多边形的相交区间,再用要求的颜色显示这些区间的象素,即完成填充工作。

                                           

               区间的端点可以通过计算扫描线与多边形边界线的交点获得。

               对于一条扫描线,多边形的填充过程可以分为四个步骤:

    (1)求交:计算扫描线与多边形各边的交点;

    (2)排序:把所有交点按x值递增顺序排序;

    (3)配对:第一个与第二个,第三个与第四个等等;每对交点代表扫描线与多边形的一个相交区间;

    (4)填色:把相交区间内的象素置成多边形颜色;

    如图所示,扫描线 6 与多边形的边界 线交于四点A、B、C、D。
    这四点把扫描线分 为五个区间 [0, 2],[2, 3.5],[3.5, 7],[7, 11], [11, 2]。
    其中, [2, 3.5], [7, 11] 两个区间落在 多边形内,该区间内的象素应取多边形色。
    其它区间内的象素取背景色。
    这里的四个交点在计算时未必是按从左到 右的顺序获得。
    例如,当多边形采用顶点序列 P1P2P3P4P5P6 表示时,把扫描线 6 分别与边 P1P2,P2P3,P3P4,P4P5,P5P6,P6P1 相 交,
    得到交点序列D、C、B、A,必须经过排 序,才能得到从左到右,按 x 递增顺序排列的
    交点 x 坐标序列。

    二.问题

    (1)当扫描线与多边形顶点相交时,交点 的取舍问题(保证交点正确配对):

         检查相交顶点的两条边的另外两个顶点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定是取零个、一个、还是两个。

    当扫描线与多边形顶点相交 时,会出现异常情况。例如图所示,扫描线 2 与 P1 相交。
    按前述方法求得交点 ( x 坐标)序列:2,2,8。这将导致 [2, 8] 区间内的 象素取背景色,
    而这个区间的象素正是属于多 边形内部,需要填充的。
    所以,我们拟考虑当 扫描线与多边形的顶点相交时,相同的交点只 取一个。
    这样,扫描线 2 与多边形的交点序列就成为 2,8。正是我们所希望的结果。
    然而,按新的规定,扫描线 7 与多边形的 交点序列为 2,9,11。
    这将导致错把[2,9]区间作为多边形内部来填充。
    为了正确地进行交点取舍,必须对上述两种 情况区别对待。
    在第一种情况,扫描线交于一顶 点,而共享顶点的两条边分别落在扫描线的两边 。
    这时,交点只算一个。在第二种情况,共享交 点的两条边在扫描线的同一边,这时交点作为零个或两个,
    取决于该点是多边形的局部最高点还是局部最低点。
    具体实现时,只需检查顶点的两条边的另 外两个端点的 y 值。按这两个 y 值中大于交点 y 值的个数是 0,1,2 来决定是取零个、一 个、还是二个。
    例如,扫描线 1 交于顶点 P2,由于共享该顶点的两条边的另外二个顶点 均高于扫描线,故取交点 P2 两次。
    这使得 P2 象素用多边形颜色设置。
    再考虑扫描线 2。在 P1 处,由于 P6 高于扫描线,而 P2 低于扫描 线,所以该交点只算一个。
    而在 P6 处,由于 P1和P5均在下方,所以扫描线 7 与之相交时,交点算零个,该点不予填充。
    //
    (如果某一条边,平行于某一条扫描线;那这一条边,不予记录)///

    (2)多边形边界上象素的取舍问题(避免填充扩大化):

    对扫描线与多边形的相交区间取左闭右开。

    例如,对左下角为 (1,1),右上角为(3,3)的正方形填充 时,若对边界上所有象素均进行填充,
    被填充的象素覆盖的面积为 3×3 单位,而方形实际面积只有 2×2 单 位。显然,
    这个扩大化问题是由于对边界上的所有象素进行填充引起的。
    为了克服这个问 题,规定落在右/上边界的象素不予填充,而落在左/下边界的象素予以填充。
    在具体实现时,只要对扫描线与多边形的 相交区间取*左闭右开*。
    容易看出,我们在前面 一个问题所采用的方法,即扫描线与多边形顶
    点相交时,交点的取舍方法,保证了多边形的 “下闭上开”——丢弃上方水平边以及上方非
    水平边上作为局部最高点的顶点。
    重合点的处理:当扫描线和边界相交于边界顶点时,同时产生两个交点,通常采用 “起闭终开”或“起开终闭” 。
    水平边处理:水平边不参加求交计算,跳过。
    

    三. 解决步骤

     为了计算每条扫描线与多边形各边的交点, 最简单的方法是把多边形的所有边放在一个表中。

    这样处理效率很低。这是因为一条扫描线 往往只与少数几条边相交,甚至与整个多边形 都不相交。若在处理每条扫描线时,不分青红 皂白地把所有边都拿来与扫描线求交,则其中 决大多数计算都是徒劳无用的。

    为了提高效率,在处理一条扫描线时,仅 对与它相交的多边形的边进行求交运算。我们 把与当前扫描线相交的边称为活性边,并把它 们按与扫描线交点 x 坐标递增的顺序存放在一个链表中,称此链表为活性边表(AET)。

     假定当前扫描线与多边形某一条边的交点的x坐标为x,则下一条扫描线与该边的交点不要重计算,只要加一个增量△x。(连贯性)

            设该边的直线方程为:ax+by+c=0;

            若y=yi,x=xi;则当y = yi+1时,

             xi+1=xi-b/a

           其中ΔX= -b/a为常数,

           另外使用增量法计算时,我们需要知道一条边何时不再与下一条扫描线相交,以便及时把它从活性边表中删除出去。

    x i+1 = ( - by i+1 –c)/a = x i –b/a 其中△x = -b/a 为常量。△x 可以存放在对应 边的活性边表结点中。另外,使用增量法计算 时,我们需要知道一条边何时与下一条扫描线 相交,以便及时把它从活性边表中删除出去, 避免下一步进行无谓的计算。综上所述,活性边表的结点中至少应为对应边保存如下内容:

    第1项存当前扫描线与边的交点坐标x值;

    第2项存从当前扫描线到下一条扫描线间x的增量D x;

    第3项存该边所交的最高扫描线号ymax;

    第4项存指向下一条边的指针(Λ代表一条边的退出,即结束或抛弃);

                                       

    扫描线6的活性边表  :

     扫描线7的活性边表:

     

     为了方便活性边表的建立与更新,我们为每一条扫描线建立一个新边表(NET,存放在该扫描线第一次出现的边。也就是说,若某边的较低端点为ymin,则该边就放在扫描线ymin的新边表中。

                                

    1.这个结构实际上是一个指针数组,数组的每个变量是个指针,
    这个指针指向所有的以这个y值作为起点的边。
    2.把多边形所有的边全部填成这样的结构,插到这个指针数组里面来。
    3.从上面这个指针数组里面就知道多边形是从哪里开始的。
    在这个指针数组里只有1、2、3、5处有边,因此当从下往上进行扫描转换的时候,
    从y=1开始做,而在1这条线上有两条边进来了,然后就把这两条边放进活性边表来处理。
    4.当处理y=2这条扫描线时(活性边里有2条边),先看活性边表里是否有边要退出和加入,
    实际上p1p2边要退出了(y=ymax),p1p6边要加入了。
    退出的边要从活性边表里去掉,不退出的边要进行处理,即把x值加上一个增量。
    (这时p1p2变后边需要加一个Λ)
    5.后面持续步骤3,4,只到y=5这扫描线结束。
    6.即每做一次新的扫描线时,要对已有的边进行三个处理:
    一是否被去除掉;如果不被去除;
    第二就要对它的数据进行更新,所谓更新数据就是要更新它的x值,即x+△x;
    最后,就是有没有新的边进来,新的边在NET里,可以插入排序插进来。
    

    四.算法描述

         这个算法过程从来没有求交,这套数据结构使得你不用求交点!避免了求交运算。

         扫描线多边形填充算法的主要步骤:

    1. 建立NET(NewEdgeList)
    2. 从最低扫描线开始到最高扫描线循环
    3. 建立或调整AET(ActiveEdgeList)
    4.  按照AET中的接点顺序填充
    void polyfill (多边形  polygon, 颜色 color)
    { for (各条扫描线i )
      { 初始化新边表头指针NET [i];把ymin = i 的边放进边表NET [i];   }
       y = 最低扫描线号;
       初始化活性边表AET为空;
       for (各条扫描线i )
        { 把新边表NET[i]中的边结点用插入排序法插入AET表,使之按x坐标递增顺序排列;
          遍历AET表,把y max= i 的结点从AET表中删除,并把y max > i结点的x值递增D x;
          若允许多边形的边自相交,则用冒泡排序法对AET表重新排序;
          遍历AET表,把配对交点区间(左闭右开)上的象素(x, y),用drawpixel (x, y, color) 改写象素颜色值;
         }
    }

     

    展开全文
  • 适用于图形学的课程设计类代码,实用性较高,对广大同学有帮助的
  • 应用多边形扫描填充算法,将多边形用数字填充
  • 利用QT实现多边形填充算法,在网格下坐标系下,双击两下鼠标显示起点,之后点击依次连线,一共七条线,首尾要在同一个坐标才能实现功能。
  • 填充算法是计算机算法的一种分类,是一个将指定不规则区域内部像素填充为填充色的过程,在计算机辅助设计和图像处理等领域有广泛应用。包括了注入填充区域算法、种子填充算法扫描线填充算法、边填充算法等。
  • 主要为大家详细介绍了OpenGL实现扫描线填充算法,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 计算机图形学中的区域填充扫描线算法的程序实现.
  • 采用VC++语言编程实现多边形扫描转换的扫描线填充算法,可以画任意多边形。 多边形为任意多边形,如:凸多边形、凹多边形、含内环多边形。 上传的资源中没有采用通过鼠标画来实现多边形顶点的输入,而是在代码...
  • 扫描线算法是针对计算机中多边形的显示。多边形三条或三条以上的线段首位顺次连接所组成的封闭图形,有凸多边形(任意两顶点间的连线均在多边形内)和凹多边形(任意两顶点间的连线有不在多边形内的部分)。 ...
  • 多边形扫描线填充算法 未橡皮筋实现 类实现的算法 为多边形扫描线算法 未用橡皮筋多边形扫描线填充源代码实现 整个算法由类实现 包含详细的算法描述 开放源代码
  • 使用VS 2017实现多边形填充中的种子填充算法,此资源包括完整的项目文件,可以直接使用。此代码仅供学习交流使用。
  • 扫描线算法填充多边形源代码

    热门讨论 2011-12-20 11:21:27
    这是我在图形学课上自己写的一个扫描线算法的程序 注意使用了glut库 所以在建立工程的时候要引入这个库才行 具体请下载我的安装说明GlutLib 此算法效率较高 而且数据结构清晰 经过我测试了各种情况均没问题 分享给...
  • 用种子填充算法扫描线填充算法等任意两种算法实现指定多边形的区域填充。 实验步骤 1. 复习有关算法,明确实验目的和要求; 2. 依据算法思想,绘制程序流程图(指定填充多边形); 3. 设计程序界面,要求操作方便...
  • 扫描线填充算法的OpenGL实现

    热门讨论 2011-12-16 11:36:40
    基于AEL(活化边表)的扫描线填充算法的OpenGL实现。该算法包含一个基于GLUT的事件捕获框架用于绘制多边形
  • OPENGL扫描线填充算法

    2018-12-04 09:53:45
    完整的OPENGL的扫描线算法,基于VS2017开发。文件已经打好,自己找个路径放就行

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,582
精华内容 1,032
关键字:

多边形扫描填充算法