扫描线多边形填充算法讲解.ppt

73 2. 种子填充算法 基本思想：假设在多边形区域内部至少有一个像素是已知的（此像素称为种子像素），由此出发找到区域内所有其他像素，并对其进行填充。 由于区域可采用边界定义和内点定义两种方式，区域按连通性又可分为四连通区域和八连通区域两类，所以常用的种子填充算法有： 边界表示的四连通区域种子填充算法 内点表示的四连通区域种子填充算法 边界表示的八连通区域种子填充算法 内点表示的八连通区域种子填充算法 (1)边界表示的四连通区域种子填充算法 基本思想：从多边形内部任一点（像素）出发，依“左上右下”顺序判断相邻像素，若其不是边界像素且没有被填充过，对其填充，并重复上述过程，直到所有像素填充完毕。 可以使用栈结构来实现该算法，算法的执行步骤如下： 种子像素入栈，当栈非空时，重复执行如下三步操作： 1）栈顶像素出栈； 2）将出栈像素置成多边形填充的颜色； 3）按左、上、右、下的顺序检查与出栈像素相邻的四个像素，若其中某个像素不在边界上且未置成多边形色，则把该像素入栈。 以边界表示的四连通区域种子填充算法 (基于递归) 例：填充如下区域：堆栈的变化如图所示。 (2)内点表示的四连通区域种子填充算法 基本思想：从多边形内部任一点（像素）出发，依“左上右下”顺序判断相邻像素，如果是区域内的像素，则对其填充，并重复上述过程，直到所有像素填充完毕。它也常称为漫水法。 可以使用栈结构来实现该算法，算法的执行步骤如下： 种子像素入栈，当栈非空时，重复执行如下三步操作： 1）栈顶像素出栈； 2）将出栈像素置成多边形填充的颜色； 3）按左、上、右、下的顺序检查与出栈像素相邻的四个像素，若其中某个像素是区域内的像素，则把该像素入栈。 * * 我们知道多边形是常用基本图形，它是由一组边围成，封闭区域，多边形也可以是凸、凹或是带空洞。多边形区域填充就是将区域内的像素置成新的颜色值或图案。由于任何一个封闭曲线都可以用多边形来逼近，所以多边形填充实用面广。 一、多边形区域填充 3.4.2 扫描线多边形填充算法 演示 1．区域内部点判断准则 区域填充首先判断一个像素点是否处于多边形区域内,其判断准则如下： 从该点向无穷远处引出一条射线（也称扫描线），若射线与区域边界交点目标数目为奇数，则此点在区域内。若射线与区域边界交点目标数目为偶数，则此点为区域外点。 例如： A点向右引射线与区域边界共3个交点，为内点 B点向右引射线与区域边界共2个交点，为外点 A B 此时应注意两点： （1）当扫描线与多边形相交如下情况时: Y X A I B E D C F ①若两相邻边与扫描线相交于同一点，且两边位于扫描线同侧，则视为两个交点。 如yb：1点向右交点为3个（奇数）是内点 3点向右交点为4个（偶数）是外点 ②若两相邻边与扫描线相交于同一点，且两边位于扫描线异侧，则视为一个交点。 如ya yb 3 1 ya （2）当扫描线重合多边形某条边界水平线时，如该水平边线前后两条边线是一上一下的，则该水平边线两个端点作为一个交点，即扫描线与该水平边界线相交了一次。 如下图yCB X Y D C B A E 如该水平边线前后两条边线是同为上或同为下的，则将该水平边线两个端点作为交点，即扫描线与该水平边界线相交了两次。如yDE yCB yDE 2．边相关性及边记录 很显然，不能利用区域内部点判别准则对显示平面上每个点逐个判别，这样计算量太大。 事实上，相对于一个给定多边形区域来说，显示平面上每个像素点内外特性是互相关联的。相邻像素间具有相关属性。在实施多边形填充时，利用扫描线相关性，就无需对扫描线上所有像素点逐个地进行内外特性判断，只需对一条扫描线从左到右求出该扫描线与区域边界交点，这些交点必将扫描线分成内外交替线段，这些交点x值大小依次排列。 X Y A B C D 如上图，按x从小到大排列为A B C D 交点AB间线段上像素点必在区域内。 所以关键是求交点。 （1）交点计算 多边形填充首先需要求出扫描线与边界的交点，利用边的相关性可以简单有效地解决这个问题。当一条扫描线yi 与多边形的某一边线有交点时，其相邻扫描线yi+1一般也与该边线相交（除非yi+1超出了该边线所在区间），而且扫描线yi+1与该边线的交点，很容易从前一条扫描线yi与该边的交点递推求得。 设某条直线边的方程为 y=mx+b 该边两个端点坐标为（x1,y1)、（x2,y2) 且x1≠x2 则该边斜率为m=(y2-y1)/(x2-x1) 令扫描线yi与该边交点为（xi，yi）