当前位置:   article > 正文

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

简述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是外部点。

两种规则的比较

这里写图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/407239
推荐阅读
相关标签
  

闽ICP备14008679号