区域填充

时间:2024-03-15 16:08:29

                                        区域填充

               区域填充是指将区域内的一点(常称种子点)赋予给定颜色,然后将这种颜色扩展到整个区域内的过程。

1.区域及其表示

       区域---指已经表示成点阵形式的填充图形,是象素的集合。
       区域可以采用内点表示和边界表示:

                 区域填充

内点表示 枚举出区域内部的所有像素,内部的所有像素着同一个颜色,边界像素着与内部像素不同的颜色
边界表示 枚举出边界上的所有像素,边界上的所有像素着同一个颜色,内部像素着与边界像素不同的颜色

2.区域的连通(注意是区域内还是区域上)

  区域填充算法要求区域是连通的,因为只有在连通区域中,才可能将种子点的颜色扩展到区域内的其它点。
  

连通区域的分类
4向连通区域 从区域上一点出发,可通过四个方向,即上、下、左、右移动的组合,在不越出区域的前提下,到达区域的任意象素
8向连通区域 从区域内每一象素出发,可通过八个方向,即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达区域的任意象素
 

                        区域填充              

3.区域填充递归算法

1)算法原理:假设在多边形区域内部有一像素已知,由此出发找到区域内的所有像素,用一定的颜色或灰度来填充。

2)算法依据(边界与区域内部的像素值不同):

         即假设区域采用边界定义,即区域边界上所有像素均具有某个特定值,区域内部所有像素均不取这一特定值,而边界外的像素则可具有与边界相同的值。
3)算法实现

使用栈结构来实现简单的种子填充算法,算法原理如下:
   种子像素入栈(任选一个未填充颜色的),当栈非空时重复执行如下三步操作:
(1)栈顶像素出栈
(2)将出栈像素置成要填充色
(3)按左、上、右、下顺序检查与栈像素相邻的四个像素,若其中像素不在边界且未置成填充色的,一个一个的把他们入栈

区域填充
4)算法的不足与改进

a.有些像素会入栈多次,降低算法效率;栈结构占空间

b.递归执行,算法简单,但效率不高。区域内每一像素都引进一次递归,进/出栈,费时费内存
c.改进算法,减少递归次数,提高效率

5)多边形的扫描转换与区域填充算法

①基本思想不同:

             多边形扫描转换是指将多边形的顶点表示转化为点阵表示,而区域填充只改变区域的填充颜色,不改变区域表示方法。②基本条件不同
             在区域填充算法中,要求给定区域内一点作为种子点,然后从这一点根据连通性将新的颜色扩散到整个区域。故其不但知道边界,而且还知道区域内的一点,进而可以利用四连通或八连通区域不断往外扩展
             扫描转换多边形是从多边形的边界(顶点)信息出发,利用多种形式的连贯性进行填充的。