填充图元的生成

第四章填充图元的生成

・扫描转换矩形

・扫描转换多边形

・扫描转换扇形区域

•区域填充

•以图像填充区域

­字符的表示与输出

1

'般步骤

1.确定那些像素位于填充图元的内部

2.确定以什么颜色填充这些像素

2

扫描转换矩形（1/2）

•方法

voidFillRectangle(Rectangle*rect,intcolor)

{intx,y;

for(y=rect->ymin;y<=rect->ymax;y++)

for(x=rect->xmin;x<=rect->xmax;x++)

PutPixel(x,yfcolor);

}/女endofFillRectangleQV

扫描转换矩形（2/2）

•问题：

-矩形是简单的多边形，那么为什么要单独处

理矩形？

-共享边界如何处理？

■原则：左闭右开，下闭上开

属于谁?4

扫描转换多边形(1/19)

-扫描转换多边形：将顶点表示形式转换成点

阵表示形式

5

扫描转换多边形(2/19)

•逐点判断算法

-方法

voidFillPolygonPbyP(Polygon*P,intpolygonColor)

{intx,y;

for(y=ymin;y<=ymax;y++)

for(x=xmin;x<=xmax;x++)

if(IsInside(P^y))

PutPixel(x,y,polygonColor);

else

PutPixel(x^backgroundColor);

}/*endofFillPolygonPbyP()*/

6

扫描转换多边形(3/19)

-问题：如何判别点(x,y)关于多边形区域P

的内外关系？

-射线法

•步骤：

1.从待判别点V发出射线

2.求交点个数k

3.K的奇偶性决定了点与多边形的内外关系

•奇异情况处理

扫描转换多边形(4/19)

累计角度法

•步骤

1.从v点向多边形p顶点发出射线，形成有向角q

2.计算有相交的和，得出结论--------------

位于之外

>0.—\vP

占z[±2»»位于月之内

•奇异情况处理

■例子：五角星

•离散计算方法：编码方法

8

扫描转换多边形(5/19)

-算法优点：简单

-算法缺点：计算量太大，速度慢

•扫描线算法

-目标：利用像素之间的连贯性，提高算法效

率

处理对象：非自交多边形

9

扫描转换多边形(6/19)

_基本原理演示：Morphlnk

一条扫描线与多边形的边有偶数个交点

-步骤：

1.求交

2.排序

3.填充

10

扫描转换多边形(7/19)

-边的连贯性

■第一类交点：新出现的边与扫描线的交点

・第二类交点：位于同一条变上的后继交点

11

扫描转换多边形(8/19)

-交点的取整规则

•要求：使生成的像素全部位于多边形之内

-用于线画图元扫描转换的四舍五入原则导致部分像素

位于多边形之外，从而不可用

•假定非水平变与扫描线y=e

相交，交点的合作标为x,

规则如下

12

扫描转换多边形(9/19)

1.X为小数

•(a)交点位于左边之上，相右取整

•(b)交点位于右边之上，相左取整

13

扫描转换多边形(10/19))

2.(x,e)落在像素之上

-(a)(x,e)位于左边之上，属于多边形

-(b)(x,e)位于右边之上，不属于多边形

14

扫描转换多边形(11/19)

3.交点位多边形的顶点

-(a)算作1个交点

-(b)算作1个交点

-(c)算作2个交点

-(d)算作0个交点

9)

(d)

15

扫描转换多边形(12/19)

-特殊情况处理

•水平边:扔掉!

•尖角：凡混淆

扫描转换多边形(13/19)

-数据结构

•边

typedefstruct{intymax;

floatx,deltax;

Edge^nextEdge;

/Edge;

­边的分类表E

按照变得下端点y坐标对非水平边进行分类的指针数组

•活化边表AEL

纪录与当前扫描线相交的边(交点)

17

扫描转换多边形(14/19)

ET

(a)

(b)

扫描转换多边形（15/19）

-算法

1、建立ET；

2、将扫描线纵坐标y的初值置为ET中非空元素的最小序号，如在上图中,

y=i；

3、置AEL为空；

4、执行下列步骤直至ET和AEL都为空.

4.1、如ET中的第y类非空，则将其中的所有边取出并插入AEL中；

4.2＞如果有新边插入AEL,则对AEL中各边排序；

4.3＞对AEL中的边两两配对，（1和2为一对，3和4为一对，…），将每

对边中x坐标按规则取整，获得有效的填充区段，再填充.

4.4、将当前扫描线纵坐标y值递值1；

4.5、将AEL中满足y=ymax边删去（因为每条边被看作下闭上开的）；

4.6＞对'AEL中剩下的每一条边的x递增deltax,BPx=x+deltax.

思考题

19

扫描转换多边形(16/19)

•边缘填充算法

-原理：以求余运算代替扫描线算法中的排序

运算

-求余(A=OxFFFFFFFF)

M=A-M=MXorA

-算法1：(以扫描线为中心的边缘填充算法)

1、将当前扫描线上的所有象素着上值为防的颜色；

2、求余：

for(i=0;i<=m;i++)

在当前扫描线上，从x坐标为交点向右求余；

20

扫描转换多边形(17/19)

(a)(b)

(c)(d)21

扫描转换多边形(18/19)

-算法2：(以边为中心的边缘填充算法)

1、将绘图窗口的背景色置为；

2、对多边形的每一条非水平边做：

从该边上的每个象素开始向右求余;

22

扫描转换多边形(19/19)

23

扫描转换扇形区域（1⑸

•扇形区域的描述

■原理：同扫描转换多边形

•问题：如何确定扫描线与直线段和圆弧

段的相交顺序

•方法：分类

按点，和P2点所处象限的不同，需要将扇形区域分成

4X4=16种情况

扫描转换扇形区域(2/5)

•假设2点落在第一象限，扇形区域的扫描

转换分四种情况

1、22落在第一象限

25

扫描转换扇形区域(3/5)

2、2落在第二象限,

•当时

•当乂>^2时

扫描转换扇形区域(4/5)

扫描转换扇形区域(5/5)

・遗留问题：当小落在其它区域时？

•其它方法：

多边形迫近方法

28

区域填充(1/10)

•区域：点阵表示的图形，像素集合

•表示方法：内点表示、边界表示

•内点表示

-枚举处区域内部的所有像素

-内部的所有像素着同一个颜色

-边界像素像素着与内部像素不同的颜色

•边界表示

-枚举出边界上所有的像素

-边界上的所有像素着同一颜色

-内部像素着与边界像素不同的颜色

29

区域填充(2/10)

•区域填充

-将指定的颜色从种子点扩展到整个取得过程

例子：PaintBrush例子：PhotoShop

30

区域填充(3/10)

•连通性：4连通、8连通

31

区域填充(4/10)

•4连通与8连通区域的区别

-连通性

-对边界的要求

32

区域填充(5/10)

•递归填充算法

-内点表示的4连通区域

voidFloodFill4(intx,inty,intoldColor,intnewColor)

{if(GetPixel(x,y)==oldColor)

{PutPixel(x9yfnewColor);

FloodFill4(xfy+l9oldColor,newColor);

FloodFill4(x,y-l,oldColor,newColor);

FloodFill4(x-l,y9oldColor,newColor);

FloodFill4(x+l,y,oldColor,newColor);

}

*endofFloodFill4()V

33

区域填充(6/10)

34

区域填充(7/10)

-边界表示的4连通区域

voidBoundaryFill4(intx,intyfintoldColorjntnewColor)

{intcolor;

color=GetPixel(x,y);

if((color!=boundaryColor)&&(color!=newColor))

{PutPixel(x,y,newColor);

BoundaryFill4(x,y^r1,oldColor,newColor);

BoundaryFill4(x,y-l,oldColor,newColor);

BoundaryFill4(x-1,y,oldColor,ne^Color);

BoundaryFill4(x+1fy,oldColor,newColor);

)

}/*endofBoundaryFill4()*/

35

区域填充(8/10)

-内点表示与边界表示的8连通区域?

-递归填充算法的特点

•算法、程序简单

•递归层次太多，效率极低

■例子：判断填充方法

例子：PaintBrush例子：PhotoShop

36

区域填充(9/10)

•扫描线算法

-目标：减少递归层次

-