边标志算法分为两个步骤: 第一步,对多边形的每条边进行直线扫描转换,即 对多边形边界所经过的像素打上边标志。 第二步,填充。对每条与多边形相交的扫描线,依 从左到右顺序,逐个访问该扫描线上像素。使用一个布 尔量 inside来指示当前点的状态,若点在多边形内,则 inside为真。若点在多边形外,则 inside为假。 Inside的初值为假,每当当前访问像素为被打上边标 志的点,就把 inside取反。对未打标志的像素, inside不变。若访问当前像素时,对 inside作必要操 作之后, inside为真,则把该像素置为多边形色。 边标志算法描述如下 define FALSE o edge_mark_fill(polydef, color) 多边形定义 polytef; int colori
边标志算法分为两个步骤： 第一步，对多边形的每条边进行直线扫描转换，即 对多边形边界所经过的像素打上边标志。 第二步，填充。对每条与多边形相交的扫描线，依 从左到右顺序，逐个访问该扫描线上像素。使用一个布 尔量inside来指示当前点的状态，若点在多边形内，则 inside为真。若点在多边形外，则inside为假。 Inside的初值为假，每当当前访问像素为被打上边标 志的点，就把inside取反。对未打标志的像素， inside不变。若访问当前像素时，对inside作必要操 作之后，inside为真，则把该像素置为多边形色。 边标志算法描述如下： #define FALSE 0 edge_mark_fill (polydef,color) 多边形定义 polydef; int color;
对多边形 polytef每条边进行直线扫描转换; inside: FALSEr for(每条与多边形 polytef相交的扫描线y) for(扫描线上每个像素x) if(像素x被打上边标志) inside=!(inside)i if (inside !=FALSE) drawpixel(x,y, color); else drawpixel (x, y, background) 用软件实现时,有序边表算法与边标志算法执行速度 几乎相同,但由于在帧缓冲器中应用边标志算法时,不必 建立和维护边表以及对它进行排序,所以边标志算法更适 合硬件实现
{ 对多边形polydef每条边进行直线扫描转换； inside=FALSE; for (每条与多边形polydef相交的扫描线y) for (扫描线上每个像素x) { if (像素x被打上边标志) inside= !(inside); if (inside !=FALSE) drawpixel(x,y,color); else drawpixel(x,y,background); } } 用软件实现时，有序边表算法与边标志算法执行速度 几乎相同，但由于在帧缓冲器中应用边标志算法时，不必 建立和维护边表以及对它进行排序，所以边标志算法更适 合硬件实现
5.13种子填充算法 原理和方法 种子填充算法是假设在多边形区域内部取一点(像 素),由此岀发找到区域内所有像素。该算法要求区域采 用边界定义,即区域边界上所有像素均具有某个特定值, 而区域内部所有像素均不取这一特定值。 区域可以分为四向连通和八向连通两种。四向连通区 域指的是从区域上一点出发,可通过四个方向,即上、下 左、右移动的组合,在不越出区域的前提下,到达区域内 的任意像素。八向连通区域指的是区域内每一个像素,可 以通过左、右 左上、右上、左下、右下这八 方向的移动组合来达到 种子填充算法中允许从四个方向寻找下一个像素者, 称为四向算法;允许从八个方向搜索下一像素者,称为八 向算法。八向算法既可以填充八向连通区域,也可以填充 四向连通区域。但是,四向算法只能填充四向连通区域, 而不能填充八向填充区域
5.1.3 种子填充算法 1．原理和方法 种子填充算法是假设在多边形区域内部取一点（像 素），由此出发找到区域内所有像素。该算法要求区域采 用边界定义，即区域边界上所有像素均具有某个特定值， 而区域内部所有像素均不取这一特定值。 区域可以分为四向连通和八向连通两种。四向连通区 域指的是从区域上一点出发，可通过四个方向，即上、下、 左、右移动的组合，在不越出区域的前提下，到达区域内 的任意像素。八向连通区域指的是区域内每一个像素，可 以通过左、右、上、下、左上、右上、左下、右下这八个 方向的移动组合来达到。 种子填充算法中允许从四个方向寻找下一个像素者， 称为四向算法；允许从八个方向搜索下一像素者，称为八 向算法。八向算法既可以填充八向连通区域，也可以填充 四向连通区域。但是，四向算法只能填充四向连通区域， 而不能填充八向填充区域
下面只考虑四向算法。 可以使用栈结构来实现简单的种子填充算法, 其原理如下:种子像素如栈,当栈非空时,重复 如下三步操作: 栈顶像素出栈 2.将出栈像素置成多边形色,即填充色 3.按左、上、右、下的顺序检查与出栈像素相邻的 四个像素,若其中某个像素不在边界且未被置成 多边形色,则把该像素入栈。 举例,如图5.1.9所示,为一个用边界表示 的区域,其中s1(2,3)为种子像素,用简单的种 子填充算法对该区域进行填充,各像素的出栈顺 序分析如下
下面只考虑四向算法。 可以使用栈结构来实现简单的种子填充算法， 其原理如下：种子像素如栈，当栈非空时，重复 如下三步操作： 1. 栈顶像素出栈； 2. 将出栈像素置成多边形色，即填充色； 3. 按左、上、右、下的顺序检查与出栈像素相邻的 四个像素，若其中某个像素不在边界且未被置成 多边形色，则把该像素入栈。 举例，如图5.1.9所示，为一个用边界表示 的区域，其中s1(2,3)为种子像素，用简单的种 子填充算法对该区域进行填充，各像素的出栈顺 序分析如下：
步骤: (1)S1入栈, 栈:s1 2)出栈:S1,即(2,3) 入栈:4,7,9,2 栈:4,7,9,2 (3)出栈:2,即(1,3) 入栈:3,8 栈:4,7,9,3,8 (4)出栈:8,即(1,4) 入栈:没有 栈:4,7,9,3 (5)出栈:3,即(1,2) 入栈:没有 栈:4,7,9
步骤： （1） s1入栈， 栈：s1; （2） 出栈：s1，即（2，3） 入栈：4，7，9，2； 栈：4，7，9，2； （3） 出栈：2，即（1，3） 入栈：3，8 栈：4，7，9，3，8 （4） 出栈：8，即（1，4） 入栈：没有 栈：4，7，9，3 （5） 出栈：3，即（1，2） 入栈：没有 栈：4，7，9