区域填充

计算机术语

区域填充在矢量数据结构中，通常以不规则多边形来表示区域，对于多边形内填充的晕线成符号，只是图形输出的表示方法，它并不作为空间数据参加运算。矢量数据转成概格数据是通过矢量边界轮席的转换实现的。在栅格数据结构中，概格元家值直接表示属性值。因此，当矢量边界线段转换成幅格数据后，还需进行面域填充。

释义

CAD语言

要求

所谓区域填充,指的是在输出平面的闭合区域内完整地填充某种颜色或图案。以下所述及的区域填充算法或相关程序,主要针对显示平面内的区域而言。

区域填充的问题一般分两大类,一是多边形填充；一是种子填充。多边形填充有一定难度；种子填充在学生掌握了“栈”这一抽象数据类型的实现方法的前提下,比较容易完成。而边标志填充算法却是介于这两类之间,部分地具有它们的痕迹,算法思想巧妙,实现起来更容易。

在编程时可能需要在屏幕上画线段,建议学生使用自己在上次实习中实现的画线程序,也允许学生使用Turbo C的画线函数,包括：line( )、lineto( )、linerel( )、moveto( )等；另外,在编写种子填充程序时除了可能用到函数putpixel( )外,还要用到取屏幕上某象素颜色的函数getpixel( ),上述这些函数的具体使用方法可参考Turbo C使用手册,也可查看Turbo C的联机帮助。请注意,在Turbo C图形模式下,设备坐标系原点在屏幕左上角,X轴正方向向右,Y轴正方向向下。

内容

将闭合的多边形内填充某种颜色或图案。

基本要求

1、用扫描线种子填充算法实现多边形内实面积填充。

2、用边标志填充算法实现多边形内实面积填充。

提高要求

1、实现多边形内图案填充。

2、实现多边形内剖线填充。

3、用边相关多边形扫描线填充算法实现多边形内实面积填充。

主要思想方法

扫描线种子填充算法

扫描线种子填充算法思想

首先填充种子所在的尚未填充的一区段,然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段,如果存在,则依次把每个新区段最右端的象素作为种子放入堆栈。反复这个过程,直到堆栈为空。

扫描线种子填充算法步骤　1、初始化堆栈。　2、种子压入堆栈。　3、While（堆栈非空）从堆栈弹出种子象素。

(1)如果种子象素尚未填充,则：　　① 求出种子区段：xleft、xright。

② 填充整个区段。　　 (2)检查相邻的上扫描线的xleft≤x≤xright区间内,是否存在需要填充的新区段,如果存在,则把每个新区段在xleft≤x≤xright范围内的最右边的象素,作为新的种子象素依次压入堆栈。　 (3)检查相邻的下扫描线的xleft≤x≤xright区间内,是否存在需要填充的新区段,如果存在,则把每个新区段在xleft≤x≤xright范围内的最右边的象素,作为新的种子象素依次压入堆栈。　

有关堆栈操作的辅助代码

1、定义栈结构：

2、初始化堆栈

3、进栈操作

4、出栈操作

5、堆栈非空

扫描线种子填充算法伪代码

边相关多边形扫描线填充算法

边相关多边形扫描线填充思想

边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。

ET用来对除水平边外的所有边进行登记,即建立边的记录。

AET则是在ET建立的基础上进行扫描转换。对不同的扫描线,与之相交的边线也是不同的,当对某一条扫描线进行扫描转换时,我们只需要考虑与它相交的那些边线,为此AET建立了只与当前扫描线相交的边记录链表,以提供对当前扫描线上的区段进行填充。