当前位置：文档之家 › 第2章 基本图形的生成与计算_区域填充算法_new

第2章 基本图形的生成与计算_区域填充算法_new

  • 格式：ppt
  • 大小：658.50 KB
  • 文档页数：29

下载文档原格式

  / 29

合集下载

计算机图形学ppt课件 第二章基本图形的生成与计算

计算机图形学ppt课件 第二章基本图形的生成与计算

for (x=x0; xx1, x++) drawpixel (x, int(y+0.5), color); y=y+k;



例：画直线段P0(0,0)--P1(5,2)
int(y+0.5) 0 0 1 1 2 2 y+0.5 0+0.5 0.4+0.5 0.8+0.5 1.2+0.5 1.6+0.5 2.0+0.5
角度DDA法
显然，确定x,y的初值及d值后，即可以增量方 式获得圆周上的坐标，然后取整可得象素坐标。 但要采用浮点运算、乘法运算、取整运算。
中点画圆法
利用圆的对称性，只须讨论1/8圆。第二个8分 圆 P（Xp ，Yp ）
P1
M P2
P为当前点亮象素，那么，下一个点亮的象素可 能是P1（Xp+1，Yp）或P2（Xp +1，Yp +1)。
pi 2 xi dy 2 yi dx 2dy (2b 1)dx
（2.4）
在1a象限内，dx总大于0，所以pi可以判断d1d2的符号。Pi+1为
pi 1 2 xi 1dy (2 yi 1 2 yi 2 yi )dx 2dy (2b 1)dx
2( xi 1)dy (2 yi 1 2 yi 2 yi )dx 2dy (2b 1)dx
本算法是Bresenham在1965年提出。
设直线起点（x1，y1）终点（x2，y2），直 线可表示为 y mx b
y2 y1 dy b y1 m x1 , m x2 x1 dx
此处讨论先将直线方向限于1a象限，当
xi 1 xi 1

第2章基本图形生成算法

第2章基本图形生成算法
)
if (Flag) { //X方向单位增量
for (n=0; n<= Length; n++) {//X方向插补过程
WritePixel(ix, Round(y), value); ix+=idx; y+=dy; } //End of for } //End of if else { //Y方向斜率增量
第 2 章 基本图形生成算法(Ⅰ)
1) Bresenham的基本原理
假定直线斜率 k在 0~1之间 。 此时 ， 只需考
虑 x方向每次递增 1个单位 ， 决定 y方向每次 递增 0或 1。
设直线的
当前点为 (xi,y) 当前光栅点为 (xi,yi)
下一个
直线的点应为 (xi+1,y+k) 直线的光栅点
y
y 2
y1
k
x x2 x1
第 2 章 基本图形生成算法(Ⅰ)
1)David F. Rogers 描述描述
如果已知第 i点的坐标 ， 可用步长 StepX 和 StepY得到
第 i+1点的坐标为 ： – xi+1=xi+ StepX – yi+1=yi+ StepY 或 yi+1=yi+ k * StepX
Bresenham算法
– 基本原理 – Bresenham算法 – 整数 Bresenham算法 – 一般整数 Bresenham算法
第 2 章 基本图形生成算法(Ⅰ)
2.1.1 DDA算法算法
1)David F. Rogers 描述描述
直线的基本微分方程是 ：
dy dx ＝ 常数 (k)
设直线通过点 P1(x1,y1)和P2(x2,y2) , 则直线方程可表示为 ：

计算机图形学扫描线种子填充算法

计算机图形学扫描线种子填充算法

2.1 深度递归的种子填充算法
2.2 扫描线种子填充算法
2.1 深度递归的种子填充算法
种子填色又称边界填色(Boundary Filling)。 它的功能是，给出多边形光栅化后的边界位置及边 界色代码oundary_color，以及多边形内的一点(x, y)位置，要求将颜色fill_color填满多边形。
动画演示
扫描线种子填充算法特点
1. 该算法考虑了扫描线上象素的相关性，种子象 素不再代表一个孤立的象素，而是代表一个尚 未填充的区段。 2. 进栈时，只将每个区段选一个象素进栈（每个 区段最右边或最左边的象素），这样解决了堆 栈溢出的问题。 3. 种子出栈时，则填充整个区段。 4. 这样有机的结合：一边对尚未填充象素的登记 （象素进栈），一边进行填充（象素出栈）， 既可以节省堆栈空间，又可以实施快速填充。

3. 已知有一个5边形如下。建立新边表 NET，并写出每一条扫描线经过时活性边 表AET中的数据状态。
X ΔX Ymax
第1项存当前扫描线与边的交点坐标x值； 第2项存从当前扫描线到下一条扫描线间x的增量Dx; 第3项存该边所交的最高扫描线号ymax； 第4项存指向下一条边的指针。
假定当前扫描线与多边形某一条边的交点的x 坐标为x，则下一条扫描线与该边的交点不要重计 算，只要加一个增量△x。(连贯性) 设该边的直线方程为：ax+by+c=0； 若y＝yi，x=x i；则当y = y i+1时， x i+1=xi-b/a 其中ΔX= -b/a为常数， 另外使用增量法计算时，我们需要知道一条边 何时不再与下一条扫描线相交，以便及时把它从 活性边表中删除出去。
建立或调整AET(ActiveEdgeList)；

区域填充算法

区域填充算法

区域填充算法填充原理种⼦填充算法是从区域内任⼀个种⼦像素位置开始，由内向外将填充⾊扩散到整个多边形区域的填充过程。

种⼦填充算法突出的优点是能对具有任意复杂闭合边界的区域进⾏填充。

四邻接点与⼋邻接点四连通域与⼋连通域种⼦填充算法算法定义从种⼦像素点开始，使⽤四邻接点⽅式搜索下⼀像素点的填充算法称为四邻接点填充算法。

从种⼦像素点开始，使⽤⼋邻接点⽅式搜索下⼀像素点的填充算法称为⼋邻接点填充算法。

⼋邻接点填充算法的设计和四邻接点填充算法基本相似，只要把搜索⽅式由四邻接点修改为⼋邻接点即可。

算法原理种⼦填充算法⼀般要求区域边界⾊和填充⾊不同，输⼊参数只有种⼦坐标位置和填充颜⾊。

种⼦填充算法⼀般需要使⽤堆栈数据结构来实现。

先将种⼦像素⼊栈，种⼦像素为栈底像素，如果栈不为空，执⾏如下3步操作：1. 栈顶像素出栈；2. 按填充颜⾊绘制出栈像素。

3. 按左、右、下、上（或左、左上、上、右上、右、右下、下、左下）顺序搜索与出栈像素相邻的四（⼋）个像素，若该像素的颜⾊不是边界⾊并且未置成填充⾊，则把该像素⼊栈；否则丢弃该像素。

该算法也可以填充有孔区域。

缺点：递归执⾏，算法简单，但效率不⾼，区域内每⼀象素都引起⼀次递归，进/出栈，费时费内存。

改进算法，减少递归次数，提⾼效率。

解决⽅法是⽤扫描线填充算法。

扫描线算法⽬标：减少递归层次算法思想：在任意不间断区间中只取⼀个种⼦像素（不间断区间指在⼀条扫描线上⼀组相邻元素），填充当前扫描线上的该段区间；然后确定与这⼀区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进⾏这个过程，直到所保存的个区段都填充完毕。

扫描线种⼦填充算法算法原理为：先将种⼦像素⼊栈，种⼦像素为栈底像素，如果栈不为空，执⾏如下4步操作。

1. 栈顶像素出栈。

2. 沿扫描线对出栈像素的左右像素进⾏填充，直⾄遇到边界像素为⽌。

即每出栈⼀个像素，就对区域内包含该像素的整个连续区间进⾏填充。

3. 同时记录该区间，将区间最左端像素记为xleft，最右端像素记为xright。

第二章 基本图元的显示1

第二章 基本图元的显示1

图 形 学
第二章 基本图形元素的生成算法
(0,6)
(6,6)
(6,0)
(0,0) 计 算 机 图 形 学 (5,3)
(0,0)
第二章 基本图形元素的生成算法
扫描转换:通常把图像中的点、线、圆、区域和字符等图 形基本指令组成的显示文件转换成为显示缓冲器中图像的 位映像图的过程，成为扫描转换。 位图：是与屏幕图像每个像素点一一对应的图像矩阵， 矩阵中的每个元素就是像素的值（表示灰度级别与色 彩）。 选择扫描转换算法，速度与图像质量两者之间权衡折 衷。由于在建立一幅图形过程中，基本的图形扫描转 换算法将被调用成百上千此，因此，速度快一些是比 较可取的。
1 xi 1 x i x x i x x i 1 | x | 1 y i 1 y i y y i y y i k | y |
x=x-1;y=y-k; for(x=x1;x>=x2;x--) {putpixel(x,round(y));y=y-k;}
（X1,Y1)的像素点，对应的显示缓冲器地址为： 字节地址= S + ( H / 8 ) * Y1 + ( X1 / 8 ) 的整数部分 字节内的位地址= X1 / 8 的余数 计 算 机 图 形 学
第二章 基本图形元素的生成算法
2.1.2 直线段的生成
数学上的直线是由无数个点构成的集合，显 然，光栅显示器只能近地似显示直线。对 于水平、垂直和45°斜线是可以达到较为 满意的效果的。当我们对直线进行光栅化 时，需要确定最佳逼近该直线的一组象素。 扫描转换直线段就是计算出落在直线段上 或充分靠近它的一串像素，并以此像素近 似代替原连续直线段在屏幕上显示的过程。
计 算 机 图 形 学

计算机基本图形生成算法

计算机基本图形生成算法
给定圆心在原点，半径为整数R的圆，其方程为
x2 y2 R2
构造函数F(x,y)=x2+y2-R2。 对于圆上的点，有F(x,y)=0； 对于圆外的点，F(x,y)>0； 而对于圆内的点，F(x,y)<0。
31
y
Pu
PM
Pd
x
图5.13 中点Bresenham画圆的原理
中点Bresenham画圆
y
yi
k
19
改进的Bresenham算法
kd
k d
kd
k kd
图5.10 改进的Brensemham算法绘制直线的原理
改进的Bresenham算法——原理
xi1 yi1
xi
yi yi
1
1
(d 0.5) (d 0.5)
误差项的计算
d初=0， 每走一步：d=d+k
一旦y方向上走了一步，d=d-1
中点Bresenham画圆
判别式的初始值
d0 F ( x0 1, y0 0.5) F (1, R 0.5) 1 (R 0.5)2 R2 1.25 R
36
改进：用d-0.25代替d 此时有：
d d 2xi 3
d 0.25
d d 2(xi yi ) 5 d 0.25
yi-2
(xi 2)2 ( yi 0.5)2 R2
xi xi+1 xi+2
d2 ( xi 1 1)2 ( yi 0.5)2 R2 图5.14 d≤0的情况
( xi 1)2 2xi 3 ( yi 0.5)2 R2
d1 2xi 3
误差项的递推（d>0）
yi
P
yi-1
构造判别式：

计算机图形学——区域填充算法（基本光栅图形算法）

计算机图形学——区域填充算法（基本光栅图形算法）⼀、区域填充概念区域：指已经表⽰成点阵形式的填充图形，是象素的集合。

区域填充：将区域内的⼀点（常称【种⼦点】）赋予给定颜⾊，然后将这种颜⾊扩展到整个区域内的过程。

区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种⼦点的颜⾊扩展到区域内的其它点。

1、区域有两种表⽰形式1）内点表⽰：枚举出区域内部的所有象素，内部所有象素着同⼀个颜⾊，边界像素着与内部象素不同的颜⾊。

2）边界表⽰：枚举出区域外部的所有象素，边界上的所有象素着同⼀个颜⾊，内部像素着与边界象素不同的颜⾊。

21）四向连通区域：从区域上⼀点出发可通过【上、下、左、右】四个⽅向移动的组合，在不越出区域的前提下，到达区域内的任意象素。

2）⼋向连通区域：从区域上⼀点出发可通过【上、下、左、右、左上、右上、左下、右下】⼋个⽅向移动的组合，在不越出区域的前提下，到达区域内的任意象素。

⼆、简单种⼦填充算法给定区域G⼀种⼦点（x, y）,⾸先判断该点是否是区域内的⼀点，如果是，则将该点填充为新的颜⾊，然后将该点周围的四个点（四连通）或⼋个点（⼋连通）作为新的种⼦点进⾏同样的处理，通过这种扩散完成对整个区域的填充。

这⾥给出⼀个四连通的种⼦填充算法（区域填充递归算法），使⽤【栈结构】来实现原理算法原理如下：种⼦像素⼊栈，当【栈⾮空】时重复如下三步：这⾥给出⼋连通的种⼦填充算法的代码：void flood_fill_8(int[] pixels, int x, int y, int old_color, int new_color){if(x<w&&x>0&&y<h&&y>0){if (pixels[y*w+x]==old_color){pixels[y*w+x]== new_color);flood_fill_8(pixels, x,y+1,old_color,new_color);flood_fill_8(pixels, x,y-1,old_color,new_color);flood_fill_8(pixels, x-1,y,old_color,new_color);flood_fill_8(pixels, x+1,y,old_color,new_color);flood_fill_8(pixels, x+1,y+1,old_color,new_color);flood_fill_8(pixels, x+1,y-1,old_color,new_color);flood_fill_8(pixels, x-1,y+1,old_color,new_color);flood_fill_8(pixels, x-1,y-1,old_color,new_color);}}}简单种⼦填充算法的不⾜a)有些像素会多次⼊栈，降低算法效率，栈结构占空间b)递归执⾏，算法简单，但效率不⾼，区域内每⼀像素都要进/出栈，费时费内存c)改进算法，减少递归次数，提⾼效率三、扫描线种⼦填充算法基本思想从给定的种⼦点开始，填充当前扫描线上种⼦点所在的⼀区段，然后确定与这⼀段相邻的上下两条扫描线上位于区域内的区段（需要填充的区间），从这些区间上各取⼀个种⼦点依次把它们存起来，作为下次填充的种⼦点。

第二章二维基本图形的生成与二维区域的填充课件


2019y/12i+/41)作为下一个象素点。
23
2.1.2 生成直线的Bresenham算法
• 因此只要利用(d1-d2)的符号就可以决定下 一个象素点的选择。为此，我们进一步定义一 个新的判别式：
• pi=△x×(d1-d2)=2△y·xi-2△x·yi+c (2－11) 式(2-11)中的△x=(x2-x1)>0，因此pi与(d1-
三、直线Bresenham算法思想之二
•
由于象素坐标的整数性，数学点(xi，yi)与所
取象素点(xi，yir)间会引起误差(εi)，当xi列上已用
象素坐标(xi，yir)表示直线上的点(xi，yi)，下一直
线点B(xi+1，yi+1)，是取象素点C(xi+1，yir )，还是
2019D/12(/4xi＋1，y(i+1)r)呢？
(2－12)
将式(2-12)减去(2-11)，并利用xi+1=xi+1，
可得：
• pi+1= pi+2△y-2△x·(yi+1-yi) (2－13)
• 再假设直线的初始端点恰好是其象素点的 坐标，即满足：
• y1=mx1+b
(2－14)
2019/12/4
25
2.1.2 生成直线的Bresenham算法
我们知道，一幅图是由点、直线、曲线、多 边形填充区域以及字符串等组成。下面将讨论这 些基本图元的生成技术和算法。
2019/12/4
4
2.1 直线的扫描转换
一、数学直线 在数学上，理想的直线是一条由无穷多个无
限小的连续的点组成。
数学直线
2019/12/4

计算机图形学--第四讲 区域填充算法

任课教师：李陶深教授tshli@12直线生成算法圆与椭圆的绘制算法5图元的概念436区域填充算法裁剪反走样技术4.4 区域填充算法4.4 区域填充算法—基础知识（3）线框多边形物体:只需扫描转换线段填充多边形物体:要扫描转换多边形本质：点阵表示。

特点：面着色，画面明暗自然、色彩丰富。

4.4 区域填充算法4.4 区域填充算法—基础知识（4）图形学中多边形的两种表示方式顶点表示：用多边形的有序顶点序列表示多边形点阵表示：用位于多边形内部的像素集合来表示多边形4.4 区域填充算法多边形边界的矢量形式数据之上，可用于程序填色，也可用于交互填色。

形边界的图像形式数据之上，并还需提供多边形边界内一点的坐标。

概括地说，该算法先画边界，然后对内定义区域填充。

所以，它一般只能用于人机交互填色，而难以用于程序填色。

4.4 区域填充算法—多边形填色算法的问题多边形填色算法面临的一个首要问题，是判断一个像素是在多边形内还是多边形外。

Question1: How to Judge…?Question2: How to improve …?图4.14 射线法图4.15 转角法4.4 区域填充算法4.4 区域填充算法4.4 区域填充算法4.4 区域填充算法4.4 区域填充算法大量的求交、乘除运算4.4 区域填充算法—扫描线填色算法（1）基本思路：扫描线算法按扫描线的顺序计算出扫描线与多边形的相交区间，然后用要求的颜色填充这些区间内的像素。

该算法利用了扫描线的连续性和边的连续性，避免对像素的逐点判断和反复求交运算，减少了计算量，提高了算法速度。

具体处理过程：先求出扫描线与多边形边的交点，利用扫描线的连续性求出多边形与扫描线相交的连续区域，然后利用多边形边的连续性，求出下一条扫描线与多边形的交点，对所有扫描线由上到下依次处理。

4.4 区域填充算法—扫描线填色算法（2） 算法实现的步骤：对每一条扫描线执行如下四步:(1) 求交：求扫描线与多边形各边的交点;(2) 排序：将求得的交点按递增顺序进行排序;(3) 交点配对：确定相交区间;(4) 区间填色：将相交区间内的像素置成多边形色, 相交区间外的像素置成背景色。

计算机图形学基本图形生成算法


y= k· x+b
k=0.571429
b=0.428571
2 X[0]=1 y0 X[1]=2
Y[0]=1 Y[0]=1 Y[1]=kx[1]+b=1.57 Y[1]=y0+k=1.57 Y[2]=y1+k=2.14 Y[2]=kx[2]+b=2.14 Y[3]=y2+k=2.71 Y[3]=kx[3]+b=2.71 Y[4]=y3+k=3.28 Y[4]=kx[4]+b=3.28 Y[5]=y4+k=3.85 Y[5]=kx[5]+b=3.85 Y[6]=y5+k=4.4 Y[6]=kx[6]+b=4.4 Y[7]=5 Y[7]=5
第3章 基本图形生 成算法
1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域） 4 字符图元算法
2015/4/19
1
图元
• 图元：图形软件包中用了描述各种几何 图形元素的函数称为图形输出原语，简 称图元。 • 描述对象几何要素的输出图元一般称为 几何图元。点的定位和直线段是最简单 的几何图元。 • 在选定坐标系中指定一个图形的几何要 素后，输出图元投影到该输出设备显示 区域对于的二维平面上，并扫描转换到 帧缓存的整数像素位置。
2015/4/19
5

1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域） 4 字符图元算法
1 直线的DDA算法
2015/4/19
6
OpenGL画点和画线函数 1) 画点函数 glVertex*( ); (*={234}{sifd}[v]) 表示该函数有后缀，指 明空间尺寸、坐标数据类型或向量形式描述。 Ex: glBegin(GL_POINTS); glVertex2i(100,50); glEnd(); glBegin(GL_POINTS); glVertex2i(100,50); glVertex2i(75,90); glVertex2i(300,590); glEnd();
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

动画演示
扫描线种子填充算法特点
1. 该算法考虑了扫描线上象素的相关性，种子象 素不再代表一个孤立的象素，而是代表一个尚 未填充的区段。 2. 进栈时，只将每个区段选一个象素进栈（每个 区段最右边或最左边的象素），这样解决了堆 栈溢出的问题。 3. 种子出栈时，则填充整个区段。 4. 这样有机的结合：一边对尚未填充象素的登记 （象素进栈），一边进行填充（象素出栈）， 既可以节省堆栈空间，又可以实施快速填充。
计算机图形学讲义
第2章 基本图形的生成与计算
—区域填充算法
dx rx dt
黄可坤
嘉应学院
主要内容
1. 逐点判断填充算法 2. 种子填充算法
2.1 深度递归的种子填充算法 2.2 扫描线种子填充算法
3. 扫描线多边形填充算法
１.逐点判断填充算法
区域填充的基本(初级)方法:逐点判断填充算法
– 逐点判断绘图窗口内的每一个像素；
3.扫描线多边形填充算法
扫描线多边形区域填充算法是按扫描线顺序，计 算扫描线与多边形的相交区间，再用要求的颜色显 示这些区间的象素，即完成填充工作。 区间的端点可以通过计算扫描线与多边形边界 线的交点获得。 对于一条扫描线，多边形的填充过程可以分为 四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等 等；每对交点代表扫描线与多边形的一个相交区间; （4）填色：把相交区间内的象素置成多边形颜色;
考察象素与区域的关系，使得几十万甚至几百万个象 素都要一一判别，每次判别又要多次求交点，需要做 大量的乘除运算，花费很多时间。
如何判断点在多边形的内或 外？即包含性检查。
具体计算方法如何？ 图形求交中再仔细讲解。
Hale Waihona Puke 2.种子填充算法种子填充算法假设在多边形内有一象 素已知，由此出发利用连通性找到区域内 的所有象素，并进行填充。

扫描线种子填充算法的具体步骤
① 初始化：堆栈置空。将种子点（x，y）入 栈。 ② 出栈：若栈空则结束。否则取栈顶元素（x， y），以y作为当前扫描线。 ③ 填充并确定种子点所在区段：从种子点（x， y）出发，沿当前扫描线向左、右两个方向 填充，直到非内部。分别标记区段的左、 右端点坐标为xl和xr。 ④ 并确定新的种子点：在区间[xl，xr]中检 查与当前扫描线y上、下相邻的两条扫描线 上的象素。若存在非边界、未填充的象素， 则把每一区间的最右象素作为种子点压入 堆栈，返回第（2）步。
3、内点(x,y)的检测条件
– (1) if(getpixel(x,y)!=边界色 &&
getpixel(x,y)!=填充色) – (2) if(getpixel(x,y)!=背景色)
这两个条件任何一个都可以用来检
测象素点(x,y)是不是尚未填充。推 荐使用条件(1)进行象素点检测。
注意： （1） 八连通区域中，既然区域内的两个象素可以通 过对角线相通，那么，区域边界上的象素则不能通过 对角线相连，否则填充就会溢出到区域外，因此，八 连通区域的边界线必须是四连通的，见下图(a)； （2）而四连通区域，其边界象素是四连通和八连通的 都可以，见下图(b)。

深度递归的种子填色算法的优缺点 种子填充的递归算法原理和程序都很简单， 容易理解。 但由于多次递归，费时、费内存，效率不高。 太大的区域会由于递归太深而不能运行。虽 然也可利用栈非递归实现，但也有同样的问 题。 可以考虑利用队列进行广度优先填色，但是 也是逐点判断，而且要重复判断一个点很多 次，效率也不高。 为了减少递归次数，提高效率可以采用采用 扫描线种子算法。
1. 填充条件
区域内一点的坐标即种子坐标、边界色、填充色。
2. 连通方式
区域是互相连通着的象素的集合，连通方式可分 为四连通和八连通。 四连通：从区域内一点出发，可通过四个方向： 上、下、左、右到达该区域内部的任意象素。 八连通：区域内部从一个象素到达另一个象素的 移动路径，除了上、下、左、右四个方向外，还 允许沿着对角线方向。
建立或调整AET(ActiveEdgeList)；
按照AET中的接点顺序填充；

void polyfill (多边形 polygon, 颜色 color) { for (各条扫描线i ) { 初始化新边表头指针NET [i]；把ymin = i 的边放进边表NET [i]; } y = 最低扫描线号； 初始化活性边表AET为空； for (各条扫描线i ) { 把新边表NET[i]中的边结点用插入排序法插入AET表，使 之按x坐标递增顺序排列； 遍历AET表，把y max= i 的结点从AET表中删除，并把y max > i结点的x值递增D x； 若允许多边形的边自相交，则用冒泡排序法对AET表重新 排序； 遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)， 用drawpixel (x, y, color) 改写象素颜色值； } } /* polyfill */

3. 已知有一个5边形如下。建立新边表 NET，并写出每一条扫描线经过时活性边 表AET中的数据状态。

2.2 扫描线种子填充算法
算法的基本过程如下：当给定种子点(x,y) 时，首先填充种子点所在扫描线上的位于给 定区域的一个区段，然后确定与这一区段相 连通的上、下两条扫描线上位于给定区域内 的区段，确定新种子点，并依次保存下来。 反复这个过程，直到填充结束。 上述算法对于每一个待填充区段，只需压栈 一次；而在递归算法中，每个象素都需要压 栈。因此，扫描线填充算法提高了区域填充 的效率。
动画演示
扫描线多边形填充算法的特点
该算法充分利用多边形的边相关性
和扫描线的相关性，使用ET表对多 边形的非水平边进行登记； 用AET表的建立和更新来支持填充， 大大地减少了求交点的计算量，有 效地提高了填充速度。
作业
1. 当用深度递归的种子填色算法并选用编号为6 的点作为种子填充如图所示区域时，写出区 域内被填色的点先后顺序。其中采用四连通 算法，填色顺序为右左上下。 2. 当用扫描线种子填色算法并选用编号为6的点 作为种子填充如图所示区域时，写出区域内 被填色的点先后顺序。算法步骤见2.2。
2.1 深度递归的种子填充算法
2.2 扫描线种子填充算法
2.1 深度递归的种子填充算法
种子填色又称边界填色(Boundary Filling)。 它的功能是，给出多边形光栅化后的边界位置及边 界色代码oundary_color，以及多边形内的一点(x, y)位置，要求将颜色fill_color填满多边形。
重合点的处理: 当扫描线和边界相交于左顶点或右顶点时，同时产生 两个交点，通常采用 “起闭终开”或“起开终闭” 。 P4 P3 [P4，P5) [P2,p3) P2
P5 [P5,p1)
P1
[P1,p2)
水平边处理 水平边不参加求交计算，跳过。
把与当前扫描线相交的边称为活性边， 并把它们按与扫描线交点x坐标递增的顺序 存放在一个链表中，称此链表为活性边表 (AET)。 活性边表的每个节点的内容：
扫描线6的活性边表AET
扫描线7的活性边表AET
为了方便活性边表的建立与更新，我们为每一条扫 描线建立一个新边表（NET）,存放在该扫描线第一 次出现的边。也就是说， 若某边的较低端点为ymin， 则该边就放在扫描线ymin 的新边表中。

扫描线多边形填充算法的主要步骤 建立NET(NewEdgeList) 从最低扫描线开始到最高扫描线循环：
X ΔX Ymax
第1项存当前扫描线与边的交点坐标x值； 第2项存从当前扫描线到下一条扫描线间x的增量Dx; 第3项存该边所交的最高扫描线号ymax； 第4项存指向下一条边的指针。
假定当前扫描线与多边形某一条边的交点的x 坐标为x，则下一条扫描线与该边的交点不要重计 算，只要加一个增量△x。(连贯性) 设该边的直线方程为：ax+by+c=0； 若y＝yi，x=x i；则当y = y i+1时， x i+1=xi-b/a 其中ΔX= -b/a为常数， 另外使用增量法计算时，我们需要知道一条边 何时不再与下一条扫描线相交，以便及时把它从 活性边表中删除出去。
– 若在区域的内部：用指定的属性设置该点； – 否则不予处理；
设有如下函数： Inside(D,x,y)=
True when x D
D
False when x D
取矩形R(x1≤x≤x2,y1≤y≤y2)，使R包围D， 则逐点判断填充算法如下：
for(y=y1;y<=y2;y++) for(x=x1;x<=x2;x++) if(inside(D,x,y)) drawpixel(x,y,color); 上述算法原理简单、实用，但效率低；效 率低的原因是没有考虑各象素之间的联系，孤立地

(a) 八连通区域四连通边界
(b) 四连通区域八连通(或四连通)边界
深度递归的种子填色算法
void seed_filling（x，y，fcolor，bcolor ） int x，y，fcolor，bcolor； { int c； c=getpixel（x，y）； if（c!=fcolor&&c!=bcolor） { putpixel（x，y，fcolor）； seed_filling（x+1，y，fcolor，bcolor）； seed_filling（x-1，y，fcolor，bcolor）； seed_filling（x，y+1，fcolor，bcolor）； seed_filling（x，y-1，fcolor，bcolor）； } }