x3
x2 x0 x1
(a)从x3向右求余
边标志算法
边标志算法进一步改进了栅栏算法,使得算法 对每个象素仅访问一次. 边标志算法分两步进行:
对多边形边界上的象素打上边标志; 填充.
Filling Ellipse Arcs
扫描线算法：对每条扫描线，首先 计算它与扇形区域边界的交点，再把配 对交点之间的像素用指定颜色填充。
栅栏填充算法
将当前扫描线上的所有象素着上指定颜色的补色
x3
x2 x0 x1
(a)从x0向左求余
栅栏填充算法
x3
x2 x0 x1
(a)从x1向左求余
栅栏填充算法
将当前扫描线上的所有象素着上指定颜色的补色
x3
x2 x0 x1
(a)从x2向左求余
栅栏填充算法
将当前扫描线上的所有象素着上指定颜色的补色
基本思想:对于每一条扫描线和每条多边形边的交 点(x1,y1),将该扫描线上交点右方的所 有象素取补.对多边形的每条边做此处理, 多边形的顺序随意.
以扫描线为中心的边缘填充算法
将当前扫描线上的所有象素着上指定颜色的补色
x3 x0 x1
x2
(a)从x0向右求余
以扫描线为中心的边缘填充算法
x3 x0 x1
以边为中心的边缘填充算法
对非水平边上的每个象素点向右求余
以边为中心的边缘填充算法
以边为中心的边缘填充算法
以边为中心的边缘填充算法
边缘填充算法特点
该算法的优点是简单,缺点是对复杂图形,每一象 素可能被访问多次,输入输出的量比较大.
栅栏填充算法
基本思想:对于每个扫描线与多边形边的交 点,仅将交点与栅栏之间的象素取补.
递归填充算法
初始化：种子象素入栈 第一步：栈顶象素出栈，作为种子点； 第二步：种子点被置为填充色； 第三步：按照上、下、左、右顺序检查
与种子点相邻的象素：若非边界且未被 填充，则入栈（8向连通区域需考虑更 多相邻象素）。 若栈不空，则重复第一步。
Algorithm
void FloodFill4(int x, int y, int oldColor, int newColor)
}
Example：
5 6 9 10 4 7 8 11
3 2 •1 21 22
12 13 16 17 20 14 15 18 19
(2)扫描线算法
算法: (1)填充并确定种子点所在的区段； (2)将种子区段压栈; (3)若堆栈非空,栈顶区段出栈;否则算法 结束; (4)填充并确定新的区段, 将其区段信息 压栈.
区域连通性（3）
允许从4个方向搜索下一个象 素的填充算法称为是四向填 充算法
允许从8个方向搜索下一个象 素的填充算法称为是8向填充 算法
(1)递归算法
算法思想：
设G为一内点表示的区域，(x,y)是G内一点，以(x,y)为 种子点，先将(x,y)置为newcolor，然后对(x,y)的4(或 8)领域进行递归处理，逐步将整个区域G置为 newcolor.
x2
(a)从x1向右求余
以扫描线为中心的边缘填充算法
x3 x0 x1
x2
(b)从x1向右求余
以扫描线为中心的边缘填充算法
x3 x余
以扫描线为中心的边缘填充算法
x3 x0 x1
x2
(c )从x2向右求余
以扫描线为中心的边缘填充算法
x3 x0 x1
x2
(d)从x3向右求余
{if (GetPixel(x,y)==oldColor) { PutPixel(x,y,newColor); FloodFill4(x,y+1,oldColor,newColor); FloodFill4(x,y-1,oldColor,newColor); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); }
此处加标题
计算机图形学边缘填 充算法
眼镜小生制作
边缘填充算法
基本思想:对于每一条扫描线和每条多边形边的交点 (x1,y1),将该扫描线上交点右方的所有象素取补. 对多边形的每条边做此处理,多边形的顺序随意.
该算法的优点是简单,缺点是对复杂图形,每一象素 可能被访问多次,输入输出的量比较大.
•
•
以扫描线为中心的边缘填充算法
(c)从x2向右求余
以扫描线为中心的边缘填充算法
x3
x2 x0 x1
(d)从x3向右求余
以扫描线为中心的边缘填充算法
x3
x2 x0 x1
(d)从x3向右求余
以扫描线为中心的边缘填充算法
对各条扫描线循环上述处理过程。
以边为中心的边缘填充算法
原始多边形
以边为中心的边缘填充算法
初始化：将绘图窗口的背景色置为多边形颜色的补色
扫描线种子填充算法流程（1）
初始化：由指定的种子象素点(x,y)生成种子(y,xl,xr),填 充并入栈。
x3
x2 x0 x1
(a)从x0向右求余
以扫描线为中心的边缘填充算法
x3
x2 x0 x1
(b)从x1向右求余
以扫描线为中心的边缘填充算法
x3
x2 x0 x1
(b)从x1向右求余
以扫描线为中心的边缘填充算法
x3
x2 x0 x1
(c)从x2向右求余
以扫描线为中心的边缘填充算法
x3
x2 x0 x1
(特征值),边界上pixel不着色.
区域连通性（1）
▪ 要求:
区域具有一定的连通性:4连通或8连通
4连通区域:取区域内任意两点,在该区域内(不能 通过区域外的点),若从其中一点出发,通过上、 下、左、右 四种运动可到达另一点时,则称该 区域为4连通区域.
区域连通性（2）
4连通运动方向
8连通运动方向
区域填充(种子填充算法)
区域（种子）填充是指先将区域内的一点 (种子点)赋予给定颜色,然后将颜色扩充到整个 区域内的过程(染色过程). 区域:已经表示成点阵形式的象素集合,具有相 同颜色.
区域的表示
区域的两种表示:内点表示、边界表示. ❖ 边界表示:给位于边界上的所有象素着色,而区
域内不着色. ❖ 内点表示:给区域内所有象素都着上同一种颜色
以扫描线为中心的边缘填充算法
x3 x0 x1
x2
(d)从x3向右求余
以扫描线为中心的边缘填充算法
x3 x0 x1
x2
(d)从x3向右求余
以扫描线为中心的边缘填充算法
将当前扫描线上的所有象素着上指定颜色的补色
x3
x2 x0 x1
(a)从x0向右求余
以扫描线为中心的边缘填充算法
将当前扫描线上的所有象素着上指定颜色的补色