第3章2多边形的转换与区域填充2011.ppt

P5 P4 P3 P1 P2 P2 P3 P4 P5 P3 P4 P5 P1 图 栅栏填充算法示意图 缺点：栅栏填充算法只是减少了被重复访问的像素的数目，但仍有一些像素会被重复访问 * * 边标志算法基本思想： 对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的像素打上边标志； 填充。对每条与多边形相交的扫描线，依从左到右顺序，逐个访问该扫描线上像素。使用一个布尔量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。 inside的初始值为假，每当当前访问像素为被打上边标志的点，就把inside取反。对未打标志的像素，inside不变。若访问当前像素时，对inside作必要操作之后，inside为真，则把该像素置为多边形色。 * * 与上两个算法相比，边标志算法避免了对帧缓存中大量元素的多次赋值，但需逐条扫描线地对帧缓存中的元素进行搜索和比较。 当用软件实现本算法时，速度与改进的有效边表算法相当，但本算法用硬件实现后速度会有很大提高。 * * void edge_mark_fill (polydef, color) 多边形定义 polydef; int color; { 对多边形polydef每条边进行直线扫描转换; inside = FALSE; for(每条与多边形polydef相交的扫描线y) { if(像素x被打上边标志) inside = !(inside); if(inside !=FALSE) drawpixel(x,y,color); else drawpixel(x,y,background); } } * * 3.3.3种子填充 区域填充:一个封闭区域确定以后，在指定的区域内填充上某种颜色或图案. 基本思想：假设在区域内部有一像素已知，由此出发找到区域内的所有像素。 * * 填充方式 4-连通和8-连通 (b)p的8-邻接点 (a)p的4-邻接点 问题：4连通有时不能完整填充 * * 算法原理：种子像素入栈；当栈非空时重复执行如下三步操作： （1） 找顶像素出栈； （2） 将出栈像素置成填充色； （3） 按某一个顺序如右、上、左、下检查与出栈像素相邻的四个像素，若其中某个像素不为填充也不为边界色，则把该像素入栈。 算法的输入：种子点坐标(x,y)，填充色和边界颜色。 * * S 2 4 6 8 1 3 9 4 6 8 3 9 4 6 8 4 9 4 6 8 5 9 4 6 8 6 9 4 6 8 9 4 6 8 4 6 8 6 8 8 * * 递归算法 void boundaryfill4 (int seedx, int seedy, int fcolor, int bcolor) { int current = getpixel (seedx, seedy); if ((current != bcolor) (current != fcolor)) { putpixel (seedx, seedy, fcolor); boundaryfill4 (seedx +1, seedy, fcolor, bcolor); boundaryfill4 (seedx –1, seedy, fcolor, bcolor); boundaryfill4 (seedx, seedy +1, fcolor, bcolor); boundaryfill4 (seedx, seedy –1, fcolor, bcolor); } } * * 特点： 可以用于填充带有内孔的平面区域。 把太多的象素压入堆栈 算法改进 沿扫描线填充水平象素段 仅将水平扫描像素区段的起始位置放入堆栈 * * 基于扫描线的种子填充算法 4-连通扫描线填充算法步骤： 种子象素入栈；当栈非空时作如下三步操作： 1) 栈顶像素出栈； 2) 沿扫描线对出栈像素的左右像素进行填充，直至遇到边界像素为止，即每出栈一个像素，就对包含该像素的整个区间进行填充；上述区间内最左、右的像素分别记为xl 和xr ； 3)在区间[xl,xr]检查与当前扫描线相邻的上下两条扫描线的有关像素是否全为边界像素或已填充的像素，若存在非边界，未填充的像素，则把每一区间的最左像素取作种子(横坐标xr或xr-1)像素入栈。 * * 2 1 3 1 2 6 5 4 1 3 7 5 4 1 6 7 基于扫描线的种子填充算法 * * 3.2.6 多边形扫描转换与区域填充