北大计算机图形学讲义3

计算机图形学

北京大学计算中心王竹威

zhuweiw@pku.

基本图形的生成和计算

第三章基本图形的生成和计算

3.1直线的生成算法

3.2圆的生成算法

3.3椭圆生成算法

3.4区域填充算法

3.5字符的生成

3.6图形的裁剪

zhuweiw@

基本图形的生成和计算

概述

现在的计算机能够生成非常复杂的图形，但是

无论图形多么复杂，它都是由基本图形组合而

成的。本章主要叙述一些能在指定输出设备上,

根据坐标描述构造二维几何图形的方法，即介

绍一些基本图形的生成算法，包括直线、圆、

椭圆的生成方法，多边形的填充方法，字符的

生成方法，图形的裁剪等。其中，有些算法主

要针对点阵设备，而有的算法则主要针对矢量

设备。

zhuweiw@

基本图形的生成和计算

直线的生成算法

直线的概念

直线是最基本的图形，一些复杂的图形往往由很

短的直线组成，因此直线生成算法在图形软件设

计中起着重要的作用，生成直线的质量好坏与速

度将直接影响整个图形的质量和速度。

几何学上的一条直线由两点决定，它在数学上可

以有各种表示方法，而在计算机图形学中，直线

是由逼近理想直线段的离散像素点组成的。

zhuweiw@

基本图形的生成和计算

直线的生成算法

直线生成算法

直线生成算法的主要研究内容是将直线光栅化，并减

少直线显示时的阶梯效应。对计算机生成直线的一般

要求是：逼近程度好，线段端点的位置要准确，线上

各点的亮度要均匀，线段生成的速度要快。

zhuweiw@

基本图形的生成和计算

直线的生成算法

生成直线的数值微分法

在光栅扫描显示器上生成直线一般采用数值微分

法(DigitalDifferentialAnalyzer,DDA),它是根

据直线的微分方程来生成直线的。

设直线的起点和终点分别为(XSM)和械项)，令

Ax=xe-xs?Ay=ye-ys,则直线.微分方程为

Ax

zhuweiw@

基本图形的生成和计算

直线的生成算法

生成直线的数值微分法

设直线当前点位置是求下一个点(Xi+iy+i)

的坐标，它们之间同样满足上述直线微分方程，

即

Ay=y+i-yi

AxXi+i-方

若Xi+1-Xi=£,Ax

则有Yi+1=Yi+£,Ay

zhuweiw@

!本图形的生成和计算

直线的生成算法

生成直线的数值微分法

因此，DDA法的工作原理是使x和y同时以很小的

步长向前增长，两个方向上每次的增量分别与Ax

和Ay成正比，这样，在精度为理想的显示器上可

以将x和y递增£,Ax和yAy来产生直线（g是一个

小量），即递推公式为

cxi+1=%&Ax

{Yi+i=%+，Ay

当£取值不同时，便形成对称DDA法和简单DDA法。

zhuweiw@

基本图形的生成和计算

直线的生成算法

对称DDA法

在对称DDA法中，选择8=24n由下式来确定：

n1n

2-<max(|Ax|,|Ay|)<2,n为正整数

对于显示器来说，所产生的坐标必须是整数才能

显示，可以采用算术溢出方法来实现。

zhuweiw@

基本图形的生成和计算

直线的生成算法

对称DDA法

总的递推公式：

<x0=xs+0.5

yo=ys+o.5

Xi+i=Xi+&Ax

(yi+i=yi+&Ay

Xip=[Xi]

=

YiP[yi]

(i=0,l,2,

zhuweiw@

基本图形的生成和计算

直线的生成算法

对称DDA法(例)

例：已知起点A(3,l)和终点B(13,8),用对称DDA法在

A和B之间生成一段直线。

解：

(1)计算初值：Ax=10,Ay=7,则n=4,£=2-4=0.0625,因

此，增量分别为：

£,Ax=0.625,£,Ay=0.4375o

⑵按递推公式循环计算点的坐标，并取整显示。

zhuweiw@

基本图形的生成和计算

直线的生成算法

对称DDA法（例）

计算坐标显示坐标计算坐标显示坐标

ii

XiViXipVipXiViXipVip

03.51.53199.1255.437595

14.1251.937541109.755.87595

24.752.375421110.3756.3125106

35.3752.8125521211.06.75116

46.03.25631311.6257.1875117

56.6253.6875631412.257.625127

67.254.125741512.8758.0625128

77.8754.5625741613.58.5138

88.55.085

zhuweiw@

基本图形的生成和计算

直线的生成算法

对称DDA法（例）

zhuweiw@

基本图形的生成和计算

直线的生成算法

对称DDA法

对称DDA法生成的直线比较精确，像素点位

置偏离直线不超过半个像素。对称DDA法的

另一个优点是容易用硬件来实现，因为g选

用2的负指数赛，这样存放Ax和Ay的寄存器

不需要使用除法运算，只通过移位操作就可

以得到坐标增量£•Ax和8Ay,计算直线上每

一点只用两次加法就可以实现。

zhuweiw@

基本图形的生成和计算

直线的生成算法

简单DDA法

在简单DDA法中，选择

e=l/L,L=max(Ax|,|Ay|),

计算时的递归方法与对称DDA法相同。

简单DDA法的基本思路是：选定Ax、Ay中较

大者作为前进方向。对于具有斜率绝对值小于

1的线段，由x方向的单位增量计算y方向的增

量，而对斜率绝对值大于1的线段，则由y方向

的单位增量计算x方向的增量。

zhuweiw@

基本图形的生成和计算

直线的生成算法

简单DDA法

|k|<l：k|>l:

<x0=xs+0.5<x0=xs+0.5

yo=ys+o.5y0=ys+o.5

Xi+i=Xi±l1+1=为±1/k

5yi+i=y±k(yi+e±1

Xip=[Xi]Xip=[Xi]

==

YiP[yi]YiP[yi]

(i=0,l,2,Axli=0,l,2,Ay

zhuweiw@

基本图形的生成和计算

直线的生成算法

简单DDA法

按照直线从My)到

(Xe,ye)的方向不同，

可以分为8个象限。

在la象限里，Dx=l,

Dy=k;在1b象限里，

Dy=l,Dx=l/ko在

其它象限里依此类推。

zhuweiw@

基本图形的生成和计算

直线的生成算法

简单DDA法

Dx、Dy在各象限中的取值

象限|Ax|>|Ay|?DxDy

1a是

1b否1/k

2a是■1

2b否-1/k

3a是■1

3b否-1/k-1

4a是-k

4b否1/k-1

zhuweiw@

基本图形的生成和计算

直线的生成算法

DDA直线生成程序

dda_line(x1,y1,x2,y2,c)x=xl+0.5;

intxl,yl,x2,y2,c;y=yl+0.5；

{floatincre_x,incre_y,x,y;putpixel(int(x),int(y),c);

intdx,dy,steps,k;for(k=l;k<=steps;k++)

dx=xl-x2;{x+=incre_x;

dy=yl-y2;y+=incre_y;

if(abs(dx)>abs(dy))steps=abs(dx);putpixel(int(x),int(y),c);

elsesteps=abs(dy);

incre_x=(float)dx/(float)steps;

incre_y=(float)dy/(float)steps;

zhuweiw@

基本图形的生成和计算

直线的生成算法

DDA直线生成算法练习

用对称DDA算法生成从A

(5,12)到B(10,25)

的直线。

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法

本算法由Bresenham在1965年提出，最初是为数

控绘图机设计的，现在被广泛应用于光栅扫描图

形显示器中。

设直线起点为（Xs,ys）,终点为（Xe,ye），则斜率k为：

dy_=ye-ys

―dx—Xe-xs

直线方程可表示为：y=kx+b,其中b=ys-kxs。

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法

与简单DDA算法相

同，按照直线从起

点到终点的方向不

同，可以分为8个象

限。

对于方向在第la象

限内的直线，增量

取为Dx=l。

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法

当已知光栅化后前一

点的坐标国'),计算

下一点的坐标(Xj+iji+i)

时，Xj+1增加1个单彳立，

yi+i只可能取两个位置:

y+尸yi+1及yi+i=y，具

体选择哪一点，要看

精确值y与哪一点最近。

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法

因此，需要计算精确值y与它们的距离d]和d2:

di=y-yi

d2=yi+「y=yi+i-y

其中：y=k(Xj+l)+b

如果d]-d2>0,则精确被丫与上面点近，取

yi+1=yi+l,否则精确值y与下面点近，取乂+产乂。

因此，算法的关键在于简便地求出d「d2的符号。

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法

di-d2=2y-2y「l

=2(kxi+1+b)-2yi-l

=2(xj+l)dy/dx-2yi+2b-1

Pi=(di-d2)dx

=2xidy-2yidx+2dy+(2b-1)dx

这就是Bresenham直线星成算法命判断公式，可

以看出，公式较为复杂，计算量较大。为了降低

计算量，可以利用递推公式进行计算。

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法

同样，在点(Xi+1,yi+1)处的判断公式为：

pi+1=2xi+1dy-2yi+1dx+2dy+(2b-l)dx

两式相戒:

Pi+1-pi=2xi+1dy-2xidy-2yi+1dx+2yjdx

因此，宥递推公式：

pi+1=pi+2dy-2(yi+i-yi)dx

当Pi>0,则yi+i=yi+l,递推公式为pi+i=pi+2(dy-dx)

否则yi+1=yi,递程公式为Pi+i=pi+2dy

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法

计算递推公式的初值：

因为ys=kxs+b=xsdy/dx+b

故有p1=2xsdy-2ysdx+2dy+(2b-1)dx

=2xsdy-2(xsdy/dx+b)dx+2dy+(2b-1)dx

=2dy-dx

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法

由此得到第la象限内的直线Bresenham算法的递推

公式：

<Xi=x“yi=ys,i=o

Pi=2dy-dx

JXi=X、i+l

当PiNO时，yi=yi-i+l,pi+i=Pi+2(dy-dx)

当R<0时，yi=yji,pi+i=pi+2dy

Ii=l,2,…,dx

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法(例)

例：已知起点人(3,1)和终点(13,9),用Bresenham算

法在A和B之间生成一段直线。

解：

(1)计算初值：dx=13-3=10,dy=9-l=8,判别式增

量分别为：2dy=16,2(dy-dx)=-4,判别式初值为

2dy-dx=6;

⑵按递推公式循环计算点的坐标并显示。

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法（例）

jj

Pi(Xi+bYi+i)Pi(Xi+bYi+i)

0(3,1)66(9,6)

16(4,2)72(10,7)

22(5,3)8-2(11,7)

3-2(6,3)914(12,8)

414(7,4)1010(13,9)

510(8,5)

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法（例）

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成算法

Bresenham直线生成算法具有以下优点：

(1)不必计算直线的斜率，因此不用做除法；

(2)不用浮点数，只用整数；

(3)只做整数加减运算和乘2运算，而乘2运算

可以通过移位操作来实现。

由于Bresenham算法具有这些优点，因此它的运

算速度快，并适合于硬件实现。

zhuweiw@

基本图形的生成和计算

直线的生成算法

Bresenham直线生成程序

第50页的程序3.2适用于所有8个方向的直线的生

成。程序画出一条端点为(x1,y1(x2,y2)直线,

其颜色为c。其中变量的含义是：p是判断变量；

constl和const2是判别的逐点变化量；inc是x或y的

单位递变量，值为1或-1:tmp是用祚象限变换时

的临时变量。程序以判断|dx|>|dy|为分支，并分别

将2a,3a象限方向的直线和3b,4b束限方向的直线变

换到la,4a和2b,1b象限方向去，以实现程序处理的

简洁。

zhuweiw@

基本图形的生成和计算

的生成算法

圆的概念

圆是某些应用领域中最重要的基

本图形，它被定义为到给定中心

位置(XcJc)距离为R的点集。产生

圆的算法很多，这里主要介绍生

成圆的逐点比较法、Bresenham算

法等。

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧

逐点比较法主要针对笔式绘图机。

绘图机每走完一步，就要把绘图

机当前位置到圆心的距离与圆弧

的半径进行比较，根据比较结果

决定下一■步的走向，这样一■步步

地用阶梯折线来逼近圆弧。由于

每一步即为绘图机的一个步距，

一般疝0.1mm以下，所以看上去

仍然是光滑的。

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧

圆弧的生成按圆弧所在的象限以及圆弧方向

（顺时针还是逆时针）进行。若圆弧跨过几个

象限，则应按象限分段生成。

为了推导方便并减少计算量，可以建立局部

坐标系，它把原点作为圆心，将各点坐标减

去圆心坐标就得到局部坐标。绘制圆弧时，

只要用各点局部坐标加上圆心坐标，就是每

点实际坐标位置。

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧

设圆弧的起点为A(xa?ya),

终点为B(Xb.y小圆心在原

点。设绘图笔当前位置为

M(xi,yi),它相对于圆弧的

位置着三种情况：点M在

圆弧外侧、内侧以及在圆

弧上。因此点M的位置决

定了走步方向。

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧

为了判断点M与圆弧的相对位置，引入偏差函

数F。

Fi=Xj2+yj2_R2

其中R是半径。对于以上三种位置，偏差函数

分别为：点M在圆弧外侧时，F/0;在内侧时,

Fi<0;在圆弧上时，FrOo由此来推导下一点

(Xi+i,yi+i)的位置。

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧

在生成第一象限的逆时针圆弧时，其推导公式

如下：

(1)若Fi〈O,则应向+y方向走一步，即Xi+i=x〃

yi+i=yi+i，新点的偏差为:

222

Fi+1=xi+1+yi+1-R

=Xi2+(yi+l)2-R2

=%2+%2_1<2+2%+1

=Fj+2yi+l

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧

(2)若Fj>0,则应向-x方向走一步,即Xj+i=Xi-l,

yi+1=yp新点的偏差为:

222

Fi+1=xi+1+yi+1-R

222

=(xi-l)+yi-R

=Xi2+yj2_R2_2xi+1

=F「2xj+l

⑶若F『0,则可自定义按⑴或(2)处理。

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧

Fj的初值F。是起点的偏差，由于起点位于圆

弧上，因此Fo=O。新点偏差Fi+i由当前点的坐

标值及偏差来计算，根据Fj+］的正负号决定下

一步走向，逐步进行，直到到达圆弧的终点

结良。终止判断可由总步数月Xb-Xal+'b-yal来

控制，每走一步J减去，J=0时到达终点。

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧

根据以上分析，我们可得到第一象限的逆时

针圆弧逐点比较法递推计算公式：

<x0=xa?y0=ya,>|xb-xa|+|yb-ya|

Fo=O

当耳>0时,xi+1=xrl,yi+i=yi9Fi+1=Fr2xi+l

（当Fi〈O时，%+1=\,yi+i=yi+l,Fi+i=Fi+2yi+l

当Fj=O时，可选择上述两种方法之一

J=J-1

lj=O时结束

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧(例)

例：设起点为A(5,3),终点为B(0,6),圆心为0(0,0),

用逐点比较法逆时针生成圆弧。

解：

根据递推公式，算法初始偏差值Fo=O,总步数

J=|0-5|+|6-3|=8,则计算结果如下£

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧（例）

iXiYiE增量J计算偏差

053F（）=0+dy8Fi=0+2*3+l=7

154Fi=7>0-dx7F2=7-2*5+l=-2

244F2=-2<0+dy6F3=-2+2*4+l=7

345F3=7>0-dx5F4=7-2*4+l=0

435F4=O+dy4F5=0+2*5+l=U

536F5=ll>0-dx3F6=ll-2*3+l=6

626F6=6>0-dx2F7=6-2*2+l=3

716F7=3>0-dx1F8=3-2*1+1=2

806F8=2>0-dx0

zhuweiw(^>p.cn

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧（例）

个

765

——

-、3

4

X

21

A

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧

其它各象限与第一象限类似，其偏差公式及

走步规律见下表：

Fi>0Fi<0

象限

走向运算公式走向运算公式

「F=F+2+1

-------XFi+i=F2|xj|+li+iilyil

IXi+lHXjl-1+y的+11=氏|

—-

+xIVi+iHyil-ylYi+lHYil+1

Fi+i=F「2|yi|+lFi+l=Fi+2lxil+1

-y-X

|xi+il=|Xi|氏+11=%|+1

四+y|yi+il=|yil-i+xlYi+lHYil

zhuweiw@

基本图形的生成和计算

的生成算法

逐点比较法生成圆弧

1Y

zhuweiw@

基本图形的生成和计算

的生成算法

Bresenham算法生成圆弧

圆心位于原点的圆有

四条可以利用的对称

轴:x=0,y=0,x=y,

x=-yo利用圆的对称

性可以减少计算量。

只要扫描转换八分之

一■圆弧，就可以求出

整个圆弧的像素集。

zhuweiw@

基本图形的生成和计算

的生成算法

Bresenham算法生成圆弧

设圆的半径为r,圆心在

(0,0),考虑从x=0,y=i＞开始

的顺时针方向的1/8圆弧生

成过程。在这种情况下，x

方向每步增加1,从x=0开

始，到y=x结束。因此有：

Xi+1=Xi+l

对应的yi+i则宥两种可能

yi+i=yi或乂+1=丫厂1

zhuweiw@

基本图形的生成和计算

的生成算法

Bresenham算法生成圆弧

具体选择哪一点，需要考察精确值y（圆弧上）靠近

y还是靠近y-L

(xi,yi)[J(xi+1,yi)

|(xi+2,yi^2)

zhuweiw@

基本图形的生成和计算

的生成算法

Bresenham算法生成圆弧

由于y在圆弧上，因此它满足圆的方程：

y2=r2-(Xi+l)2

则％到精确值y的距离为

22222

d1=yi-y=yi-r+(xi+1)

yZ到精确值y的距离为

22

d2=y2-(yr1)2=3(%+l)-(yrl)

将上面两式相减，并令判别变量Pi=d「d2，则有

Pi=2(xi+l)2+yi2+(yi-l)2-2r2

=2为2+4%+2%2-2丫j+3-2r2

zhuweiw@

基本图形的生成和计算

的生成算法

Bresenham算法生成圆弧

推导判别变量的递推公式：

2

pi+i=2xi+i+4xi+1+2yi+12-2yi+1+3-2/

2

pi+1-Pi=2xj+i+4xi+1+2yi+12-2yi+1+3-2於

222

-(2xi+4xi+2yi-2yi+3-2r)

=4Xi+2(yi+/-yi2)-2(yi+「yi)+6

22

即:Pi+i=Pi+4xi+2(yi+1-yi)-2(yi+1-yi)+6

当p<0时，选择上面的点，即yi+i=y/则Pi+i=pi+4xj+6

否则选择下面的点，即yi+1=yrl,则Pi+i=Pi+4(xi-yi)+10

判别变量的初值Po=3-2r

zhuweiw@

基本图形的生成和计算

的生成算法

Bresenham算法生成圆弧

Bresenham算法生成八分之一圆弧的递推公式:

'x（）=0,y（）=r,p（）=3-2r

1+1=、+1

J当pNO时，yi+i=yrl,pi+i=pi+4（xryi）+10

当p<0时，yi+i=%Pi+i=pi+4xi+6

<直到x=y时结束

zhuweiw@

基本图形的生成和计算

的生成算法

Bresenham算法生成圆弧

生成圆的Bresenham算法：

Brecircle(xc,yc,r,color)

intxc,yc,r,color;

{intx,y,tp;,y,p;

x=0;

y=r;

p=3-2r;

zhuweiw@

基本图形的生成和计算

的生成算法

Bresenham算法生成圆弧

while(x<y){

drawcircle(xc,yc,x,y,color);

if(p<0)

p+=4*x+6;

else{

p+=4*(x-y)+10；

y-=i;}

x++;}

if(x==y)

drawcircle(xc,yc,x,y,color);}

zhuweiw@

基本图形的生成和计算

的生成算法

Bresenham算法生成圆弧

draw_circle(xc,yc,x,y,c)

intxc,yc,x,y,c;

{putpixel(xc+x,yc+y,c);

putpixel(xc-x,yc+y,c);

putpixel(xc+x,yc-y,c);

putpixel(xc-x,yc-y,c);

putpixel(xc+y,yc+x,c);

putpixel(xc-y,yc+x,c);

putpixel(xc+y,yc-x,c);

putpixel(xc-y,yc-x,c);}

zhuweiw@

基本图形的生成和计算

椭圆生成算法

中点椭圆算法

椭圆可以认为是拉长了的圆，因此，椭圆的生成

可通过修改画圆程序，使之沿长轴和短轴尺寸不

同来实现。

设椭圆的中心坐标为（Xc,y）长轴和短轴分别是仅

ry,它们与坐标轴平行，则椭圆的方程可写为：

zhuweiw@

基本图形的生成和计算

椭圆生成算法

中点椭圆算法

考虑到标准位置的椭圆在

四分象限中是对称的，因

此只要计算一个四分象限

中椭圆曲线的像素位置

（第一象限），再由对称

性就可以得到其它三个象

限中的像素位置。

zhuweiw@

基本图形的生成和计算

椭圆生成算法

中点椭圆算法

中心点在原点、长短轴平行于坐标轴的椭圆方

程为：

222222

定义椭圆函数为：f(x,y)=ryx+rxyxry

则有：

r<0若(x,y)位于椭圆边界内

f(x,y)|=0若(x,y)位于椭圆边界上

〔>0若(x,y)位于椭圆边界外

zhuweiw@

基本图形的生成和计算

椭圆生成算法

中点椭圆算法

在第一象限中，将椭圆分成两

个区域。算法沿椭圆顺时针方

向变化，以（0网）为起点，在区

域1沿X方向取单位步长，而进

入区域2后转化为y方向上的单

位步长。因此，每一步中，需

检测曲线的斜率值，即：

dx―2yx2y

zhuweiw@

基本图形的生成和计算

椭圆生成算法

中点椭圆算法

222222=222222

ryx+rxy-ryrx0ryx+rxy-ryrx=0

zhuweiw@

基本图形的生成和计算

区域填充算法

概述

实际应用中不仅需要画出各种图形，还要对某一

封闭区域填以不同的颜色，这就是区域填充。区

域填充即给出一个区域的边界，要求对边界范围

内的所有像素单元赋予指定的颜色代码，其关键

在于确定填充哪些像素。

区域填充中的算法分为两大类：一类是扫描线填

充算法，另一类是种子填充算法。

zhuweiw@

基本图形的生成和计算

区域填充算法

扫描线填充算法

扫描线填充算法中用到了两种相关性：扫描线相

关性和边相关性。其中，扫描线相关性是指多边

形与扫描线两个交点之间的线段有两类：在多边

形内部和外部，且两类线段相间排列，在扫描线

上，如果某个像素在多边形内，则相邻的像素一

般也在多边形内；边相关性是指由前一条扫描线

上的交点序列及边的直线方程，可算出下一条扫

描线的交点序列。

zhuweiw@

基本图形的生成和计算

区域填充算法

扫描线填充算法・(XY)算法

用一■根水平扫描线

自左而右通过多边

形，扫描线与多边

形的边界相交，相

交奇次数时进入该

多边形，相交偶次

数时走出该多边形。

基本图形的生成和计算

区域填充算法

扫描线填充算法・(XY)算法

(XY)算法的步骤：

⑴按多边形的各顶点y坐标大小排序，并求出最大与

最小的y值ymax,Ymin0

⑵求交。计算每一条扫描线与各边的交点。

(3)排序。若交点多于两个，则按x增加的顺序排序。

(4)配对。每对交点代表一个相交区间。

(5)填充。将每一对交点之间的像素置成指定像素值。

(6)沿y轴让扫描线递增，并判断是否大于ymax，若大

于则填充结束，否则转到步骤(2),直到结束。

zhuweiw@

基本图形的生成和计算

区域填充算法

扫描线填充算法・(XY)算法

(XY)算法的核心是按(x,y)的值对交点作一次分类，

以找出相关的像素。此算法是对每一对交点之间所

有像素进行填充，因此交点的个数必须是偶数才能

保证填充的准确性。当扫描线恰好通过多边形的顶

点(又称为奇异点)时，不合适的计数就会导致出

错。处理奇异点的方法是：若共享交点的两条边分

别落在扫描线的两侧，则交点只算一个；若共享交

点的两条边在扫描线的同侧，则交点计为零个或两

个。

zhuweiw@

基本图形的生成和计算

区域填充算法

扫描线填充算法・(XY)算法

0

zhuweiw@

基本图形的生成和计算

区域填充算法

种子填充算法

种子填充算法是设一个封闭的区域内有一

个种子（像素）是已知的，区域内的各点填

充与种子相同的颜色或值，而区域外和边界

的像素具有另外的颜色值。本算法是以种子

为起点，按一定的规律检查种子的四周是否

具有和边界一样的颜色或值，如果有则舍弃,

否则填充种子颜色或值。

zhuweiw@

基本图形的生成和计算

区域填充算法

种子填充算法

区域可以分为四连通和八连通两种，四连通

区域是指各像素在四个方向上连通；八连通

区域是指各像素在八个方向上连通。

种子填充算法中允许从四个方向寻找下一个

像素的算法称为四向算法；允许从八个方向

搜索下一像素的算法称为八向算法。四向算

法通不过一些狭窄区域，有时不能填满多边

形，而八向算法的缺点是有时要填出多边形

的边界。

zhuweiw@

基本图形的生成和计算

区域填充算法

种子填充算法

种子填充算法的步骤如下：

⑴把种子像素压入堆栈。

(2)把种子像素设置成需要的颜色。

(3)按照右、上、左、下的顺序，检查每个当前

像素的周围四个像素是否和边界像素的颜色

相等，或者已经设置了和种子一样的颜色，

只要是其中的一种情况就舍弃，否则，把该

像素压入堆栈。

(4)从堆栈中弹出一个像素，重复执行步骤(3),

直到堆栈的元素为空。

zhuweiw@

基本图形的生成和计算

区域填充算法

种子填充算法

本算法适用于区域内为单一的颜色和灰度,

其操作过程非常简单，但缺点在于要进行

深度的递归，堆栈可能很大，降低了算法

的效率。

四向算法种子填色程序很简单，在它的基

础上可以写出各种改进的算法。

zhuweiw@

基本图形的生成和计算

区域填充算法

种子填充算法

voidseed_filling(x,y,fill_color,boundary_color)

intx,y,fill_color,boundary_color;

{intcolor;

color=getpixel(x,y);

if((color<>boundary_color)&&(color<>fill_color))

{~~

putpixel(x,y,fill_color);

seed_filling(x+1,y,fill_color,boundary_color);

seedfilling(x-1,y,fillcolor,boimdhryjcolor);

seed_filling(x,y+1,fill_color,boundary_color);

seed_filling(x,y-1,fill_color,boundary_color);

}

)

zhuweiw@

基本图形的生成和计算

区域填充算法

扫描线种子填充算法

当给定种子点(x,y)时，首先填充种子点所

在扫描线上的位于给定区域的一个区段，

然后确定与这一区段相连通的上、下两条

扫描线上位于给定区域内的区段，并依次

保存下来。反复这个过程，直到填充结束。

扫描线种子填充算法能够将堆栈最小化。

zhuweiw@

!本图形的生成和计算

区域填充算法

扫描线种子填充算法

区域填充的扫描线算法可通过下列四个步骤实现：

(1)初始化：堆栈置空，将种子点(x,y)入栈。

(2)出栈：若栈空则结束，否则取栈顶元素(x,y),以y

作为当前扫描线。

⑶填充并确定种子点所在区段：从种子点(x,y)出发，

沿当前扫描线向左、右两个方向填充，直卸边界。

(4)确定新的种子点：在上述区间检查与当前扫描线相

邻的两条扫描线，若存在非边界、未填充的像素，

则把每一区间的最右像素作为种子点压入堆栈，返

回第(2)步。

zhuweiw@

基本图形的生成和计算

字符的生成

概述

字符指数字、字母、汉字等各种符号，常用于图形的

标注、说明等。国际上应用最广的字符集是ASCII码。

我国除采用ASCII码外，还制定了汉字编码的国家标准

字符集GB2312-80。每个字符由一个区码和一个位码共

同标识。区码和位码各用一个字节来表示。为了能够

区分ASCII码和汉字编码，采用字节的最高位来标识。

为了在显示器等输