区域填充算法

没有简介又怎么了😏

概述

区域: 👉已经表示成点阵形式的填充图形,是像素的集合

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

区域可以采用内点表示和边界表示两种形式

00.png

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

边界表示: 枚举出边界上的所有像素,边界上的所有像素填充同一个颜色,内部像素填充与边界像素不同的颜色

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

区域又分为 4 向连通区域和 8 向连通区域

01.png

  • 4 向连通区域:从区域上一点出发,可以通过四个方向,即:👆、👇、👈、👉移动的组合,在不越出区域的前提下,到达区域内任意像素
  • 8 向连通区域:同理

简单 4 连通种子填充算法

又称:区域填充递归算法

假设区域采用边界定义,即:区域边界上所有像素均具有某一特定值,区域内部所有像素均不采用这一特定值,而边界外的像素可以具有与边界相同的值

使用栈结构来实现简单的种子填充算法

队列:先进先出
栈:后进先出

算法原理:

种子像素入栈,当栈非空时,重复执行:

  1. 栈顶像素出栈
  2. 将出栈像素填充成要求的颜色
  3. 按照👈、👆、👉、👇的顺序(顺序不是固定的)检查与栈像素相邻的四个像素,若其中某个像素不在边界且颜色不是要求的颜色,则将其入栈

不足之处:

  1. 有些像素会入栈多次,降低算法效率
  2. 栈结构占空间
  3. 递归执行,算法简单,但是效率不高
  4. 区域内每一像素都要引进一次递归,进栈出栈,费时费内存

改进算法:

减少递归次数,提高效率

可以采用区域填充的扫描线算法

多边形扫描转换:

  • 将多边形的顶点表示转化为点阵表示
  • 从多边形的边界(顶点)信息出发,利用多种形式的连贯性进行填充

区域填充:

  • 只改变区域颜色,不改变区域表示方法
  • 要求给定区域内一点作为种子点,然后从种子点根据连通性将新的颜色扩散到整个区域

区域填充的核心是要知道多边形的边界,得到内部的像素集,所以条件性更强