贵州大学实验报告
学院：计算机科学与信息学院专业
学院：计算机科学与信息学院
专业：计算机科学与技术 班级：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#编程实现多边形填充算法，并给出实验报告。
实 验 结 果
实 验 总 结
一、 对四连通的递归区域填充算法的分析：
该算法也可以填充有孔区域。
优点：算法简单
缺点：递归执行，效率不高，要求很大的存储空间来实现堆栈。费时费内存。
改进：减少递归次数，提咼效率。
二、 扫描线种子填充算法
该算法对于每一个待填充区段，只需压栈一次；因此，扫描线种子填充算法提咼了区域填充的 效率。
指
导 教 师
意
见
签名： 年 月 日