多边形填充算法实验报告【图形学实验报告四多边形填充算法】
时间:2020-07-29 00:42:28 来源:天一资源网 本文已影响 人
贵州大学实验报告
学院:计算机科学与信息学院专业
学院:计算机科学与信息学院
专业:计算机科学与技术 班级:101
姓名
学号
实验组
4
实验时间
2013425
指导教师
口. 一
吴厶
成绩
实验项目名称 多边形填充算法 实
验
使学生掌握光栅显示系统中多边形的扫描转换和区域填充算法。掌握 4连通区域的扩展性。
目
实
验
要
求实现多边形的扫描转换算法和区域填充算法
实
验
要
求
实现多边形的扫描转换算法和区域填充算法
实 验 原 理
实 验 原 理
扫描线算法算法原理:
利用相邻像素之间的连贯性, 提高算法效率。
根据多边形内部点的连续性知:一条扫描线与多 边形的交点中,入点和出点之间所有点都是多边 形的内部点。所以,对所有的扫描线填充入点到 岀点之间所有的点就可填充多边形。
处理对象:非自交多边形(边与边之间除了 顶点外无其它交点)判断扫描线上的点是否在多 边形之内,根据多边形区域连续性,分为3个步骤:
求出扫描线与多边形所有边的交点;
把这些交点的x坐标值以升序排列;
对每一对交点间的区域进行填充。
第三个步骤是从奇数个交点岀发到偶数 个交点。如右图,对 y = 8的扫描线排序x坐标得到的表是(2,4,9,13),然后对交点2与4之间、9与13之间 的所有象素点进行填充。
边界上的象素 :“左闭右开”,“下闭上开” (将左边界和下边界的点算为内部,而将右边界和
算为外部)
顶点:“上开下闭”
几种特殊情况:
1 ?扫描线交于一顶点,共享的两条边分另处于扫描线的两边,这时交点只取一个,如扫描线 y=3,该点被填
充一次。2.共享交点的两条边处于扫描线的上方,这时交点取二个,如扫描线 y=1 ,该点被填充一次。
?共享交点的两条边处于扫描线的下方,这时交点取 0个,如扫描线y=9,无交点,不填充。
?水平边在算法中不起任何作用,可不考虑。
活性边表(提高效率):
为了减少求交的计算量,要利用一条边与相继的两条扫描线的交点的连贯性。 在处理一条扫描线时只对活
性边(与它相交的多边形的边)进行求交运算。把交点按 x增加方向存在一个链表(活性边表)中。活性边:
与当前扫描线相交的边。
活性边表(AEL):按交点x的增量顺序存放在一个链表中,该链表称作活性边表( AEL)。
种子填充算法算法原理
种子填充算法首先假定区域由封闭轮廓线围成,且轮廓线内某点是已知的,然后开始搜索与种子点相邻且
位于轮廓线内的点。如果这相邻 点不在轮廓线内,则已达到轮廓线的边界; 如果相邻点在轮廓线之内, 则这相
邻点成为新的种子点,继续搜索下去。只适用于光栅扫描设备。
区域分类(区域采用边界定义,即区域边界上与边界外的象素取相同值,区域内部的点取不同值)
1、 四向连通区域:各象素在水平垂直四个方向是边通的。即从区域内任一点岀发,可水平/垂直移动到达区 域内任一点。
2、 八向连通区域:各象素在水平、垂直、及四个对角线方向都是是边通的。 即从区域内任一点岀发, 可水平、 垂直、及四个对角线方向移动到达区域内任一点。
扫描线种子算法
测试对象为象素段 ,对区域内的每一象素段,只保留其最右边(或左边)的象素作为种子象素?区域填充(扫描
线算法):
-目标:减少递归层次
-适用于内点表示的4连通区域
基本过程:
当给定种子点时,首先填充种子点所在的扫描线上的位于给定区域的一个区段,然后确定与这一区段相通的上 下两条扫描线上位于给定区域内的区段,并依次保存下来。反复这个过程,直到填充结束。
算法步骤:
1、 填充并确定种子区段;
2、 初始化:将种子区段压入堆栈;
3、 出栈:如果堆栈为空,则算法结束;否则取栈顶元素 y,xLeft,xRight ),以纵坐标为y的扫描线为当前扫描 线,[xLeft, xRight]为搜索区间;
4、 填充并确定新的区段 。
扫描线种子填充:
public void FillField( int x, int y, Color newColor, uint oldColor, Graphics g)
{
if ("".Equals(txtx.Text) || "".Equals(txty.Text)) {
return;
}
else
{
x = Con vert.ToI nt32(txtx.Text);
y = Con vert.ToI nt32(txty.Text);
}
int xl, xr;
bool spa nN eedFill;
myStack.Clear();
int ptx = x;
int pty = y;
myStack.Push(ptx);
myStack.Push(pty);
while (myStack.Count != 0)
{
pty = ( int )myStack.Pop();
ptx = ( int )myStack.Pop();
x = ptx;
y = pty;
while (bitmap .GetPixel(g, x, y) == oldColor)
{
bitmap .SetPixel? x, y, ColorTranslator .ToWin32(newColor)); x++;
}
xr = x - 1;
x = ptx - 1;
while (bitmap .GetPixel(g, x, y) == oldColor)
{
bitmap .SetPixel(g, x, y, ColorTranslator .ToWin32(newColor)); x--;
}
xl = x + 1;
x = xl;
y = y + 1;
while (x <= xr)
{
spa nN eedFill = false ;
while (bitmap .GetPixel(g, x, y) == oldColor)
{
spa nN eedFill = true ;
x++;
}
if (spa nNeedFill)
{
ptx = x - 1;
pty = y;
myStack.Push(ptx);
myStack.Push(pty);
spa nN eedFill = false ;
}
while (bitmap .GetPixel? x, y) != oldColor && x <= xr)
{
x++;
}
}
x = xl;
y = y - 2;
while (x <= xr)
{
spa nN eedFill = false ;
while (bitmap.GetPixel? x, y) == oldColor)
{
spa nN eedFill = true ;
x++;
}
if (spa nNeedFill)
{
ptx = x - 1;
pty = y;
myStack.Push(ptx);
myStack.Push(pty);
spa nN eedFill = false ;
}
while (bitmap .GetPixel? x, y) != oldColor && x <= xr)
{
x++;
}
}
}
四连通种子填充:
public void BoundaryFill4( int x, int y, uint oldColor, Graphics g)
{
if ("".Equals(txtx.Text) || "".Equals(txty.Text))
{
return;
}
else
{
x = Con vert.ToI nt32(txtx.Text);
y = Con vert.ToI nt32(txty.Text);
}
if (bitmap .GetPixel? x, y) != oldColor && bitmap .GetPixel? x, y)==
ColorTranslator .ToWin32( Color .Yellow))
{
bitmap .SetPixel? x, y, ColorTranslator .ToWin32( Color .Red));
BoundaryFill4(x, y + 1, oldColor, g);
BoundaryFill4(x - 1, y, oldColor, g);
BoundaryFill4(x, y - 1, oldColor, g);
Bou ndaryFill4(x + 1, y, oldColor, g);
实 验 环 境
VS2010(C#)
实 验 步 骤
1、 添加一个C#F的Windows窗体应用程序,实现对于算法的选择。
2、 根据不同算法添加不同窗体,接受圆初始化数据,编写核心函数。代码见实验原理中代码 部分。
3、 调试运行。
实 验 内 容
在VS2010环境下利用C#编程实现多边形填充算法,并给出实验报告。
实 验 结 果
实 验 总 结
一、 对四连通的递归区域填充算法的分析:
该算法也可以填充有孔区域。
优点:算法简单
缺点:递归执行,效率不高,要求很大的存储空间来实现堆栈。费时费内存。
改进:减少递归次数,提咼效率。
二、 扫描线种子填充算法
该算法对于每一个待填充区段,只需压栈一次;因此,扫描线种子填充算法提咼了区域填充的 效率。
指
导 教 师
意
见
签名: 年 月 日
相关关键词: 多边形的面积教学设计 多边形的面积教学反思 多边形的面积教学视频 数学教案-多边形面积的计算 幼儿园数学教案多边形