[计算机图形学经典算法] 区域填充_简述4-连通和8-连通边界填充算法,图示其填充过程

刚学习了计算机图形学这门课程，为奠定根基的算法所倾倒，特此记录一二。

• 区域填充是指从区域内的某一个象素点（种子点）开始，由内向外将填充色扩展到整个区域内的过程。
• 区域是指已经表示成点阵形式的填充图形，它是相互连通的一组像素的集合。（前面描述的 X - 扫描线算法适用于顶点表达的多边形）
• 区域填充算法（边界填充算法和泛填充算法）是根据区域内的一个已知象素点（种子点）出发，找到区域内其他象素点的过程，所以把这一类算法也成为种子填充算法。

边界填充算法—4 - 连通区域与 8 - 连通区域

• 4-连通区域：从区域上的一点出发，通过访问已知点的4-邻接点，在不越出区域的前提下，遍历区域内的所有象素点。
• 8-连通区域：从区域上的一点出发，通过访问已知点的8-邻接点，在不越出区域的前提下，遍历区域内的所有象素点。
  

边界填充算法

• 算法的输入：种子点坐标(x,y)，填充色以及边界颜色。
• 利用堆栈实现简单的种子填充算法：
  算法从种子点开始检测相邻位置是否是边界颜色，若不是就用填充色着色，并检测该像素点的相邻位置，直到检测完区域边界颜色范围内的所有像素为止。

算法步骤

• 栈结构实现4-(8-)连通边界填充算法的算法步骤为：
  种子象素入栈；当栈非空时重复执行如下三步操作：
  
  • (a) 栈顶象素出栈；
  • (b) 将出栈象素置成填充色；
  • (c) 检查出栈象素的4-(8-)邻接点，若其中某个象素点不是边界色且未置成多边形色，则把该象素入栈。

图示

扫描线种子填充算法

内外测试

奇-偶规则

• 奇-偶规则（Odd-even Rule）
  从任意位置p作一条射线，若与该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点。

非零环绕数规则

非零环绕数规则（Nonzero Winding Number Rule）

• 首先使多边形的边变为矢量。
• 将环绕数初始化为零。
• 再从任意位置p作一条射线。当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形的边从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1。
• 处理完多边形的所有相关边之后，若环绕数为非零，则p为内部点，否则，p是外部点。

两种规则的比较