北大計算機圖形學(xué)講義3

計算機圖形學(xué)

北京大學(xué)計算中心王竹威

zhuweiw@pku.

基本圖形的生成和計算

第三章基本圖形的生成和計算

3.1直線的生成算法

3.2圓的生成算法

3.3橢圓生成算法

3.4區(qū)域填充算法

3.5字符的生成

3.6圖形的裁剪

zhuweiw@

基本圖形的生成和計算

概述

現(xiàn)在的計算機能夠生成非常復(fù)雜的圖形，但是

無論圖形多么復(fù)雜，它都是由基本圖形組合而

成的。本章主要敘述一些能在指定輸出設(shè)備上,

根據(jù)坐標描述構(gòu)造二維幾何圖形的方法，即介

紹一些基本圖形的生成算法，包括直線、圓、

橢圓的生成方法，多邊形的填充方法，字符的

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

要針對點陣設(shè)備，而有的算法則主要針對矢量

設(shè)備。

zhuweiw@

基本圖形的生成和計算

直線的生成算法

直線的概念

直線是最基本的圖形，一些復(fù)雜的圖形往往由很

短的直線組成，因此直線生成算法在圖形軟件設(shè)

計中起著重要的作用，生成直線的質(zhì)量好壞與速

度將直接影響整個圖形的質(zhì)量和速度。

幾何學(xué)上的一條直線由兩點決定，它在數(shù)學(xué)上可

以有各種表示方法，而在計算機圖形學(xué)中，直線

是由逼近理想直線段的離散像素點組成的。

zhuweiw@

基本圖形的生成和計算

直線的生成算法

直線生成算法

直線生成算法的主要研究內(nèi)容是將直線光柵化，并減

少直線顯示時的階梯效應(yīng)。對計算機生成直線的一般

要求是：逼近程度好，線段端點的位置要準確，線上

各點的亮度要均勻，線段生成的速度要快。

zhuweiw@

基本圖形的生成和計算

直線的生成算法

生成直線的數(shù)值微分法

在光柵掃描顯示器上生成直線一般采用數(shù)值微分

法(DigitalDifferentialAnalyzer,DDA),它是根

據(jù)直線的微分方程來生成直線的。

設(shè)直線的起點和終點分別為(XSM)和械項)，令

Ax=xe-xs?Ay=ye-ys,則直線.微分方程為

Ax

zhuweiw@

基本圖形的生成和計算

直線的生成算法

生成直線的數(shù)值微分法

設(shè)直線當(dāng)前點位置是求下一個點(Xi+iy+i)

的坐標，它們之間同樣滿足上述直線微分方程，

即

Ay=y+i-yi

AxXi+i-方

若Xi+1-Xi=￡,Ax

則有Yi+1=Yi+￡,Ay

zhuweiw@

!本圖形的生成和計算

直線的生成算法

生成直線的數(shù)值微分法

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

步長向前增長，兩個方向上每次的增量分別與Ax

和Ay成正比，這樣，在精度為理想的顯示器上可

以將x和y遞增￡,Ax和yAy來產(chǎn)生直線（g是一個

小量），即遞推公式為

cxi+1=%&Ax

{Yi+i=%+，Ay

當(dāng)￡取值不同時，便形成對稱DDA法和簡單DDA法。

zhuweiw@

基本圖形的生成和計算

直線的生成算法

對稱DDA法

在對稱DDA法中，選擇8=24n由下式來確定：

n1n

2-<max(|Ax|,|Ay|)<2,n為正整數(shù)

對于顯示器來說，所產(chǎn)生的坐標必須是整數(shù)才能

顯示，可以采用算術(shù)溢出方法來實現(xià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

⑵按遞推公式循環(huán)計算點的坐標，并取整顯示。

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法的

另一個優(yōu)點是容易用硬件來實現(xiàn)，因為g選

用2的負指數(shù)賽，這樣存放Ax和Ay的寄存器

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

以得到坐標增量￡?Ax和8Ay,計算直線上每

一點只用兩次加法就可以實現(xiàn)。

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直線生成算法練習(xí)

用對稱DDA算法生成從A

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

的直線。

zhuweiw@

基本圖形的生成和計算

直線的生成算法

Bresenham直線生成算法

本算法由Bresenham在1965年提出，最初是為數(shù)

控繪圖機設(shè)計的，現(xiàn)在被廣泛應(yīng)用于光柵掃描圖

形顯示器中。

設(shè)直線起點為（Xs,ys）,終點為（Xe,ye），則斜率k為：

dy_=ye-ys

―dx—Xe-xs

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

zhuweiw@

基本圖形的生成和計算

直線的生成算法

Bresenham直線生成算法

與簡單DDA算法相

同，按照直線從起

點到終點的方向不

同，可以分為8個象

限。

對于方向在第la象

限內(nèi)的直線，增量

取為Dx=l。

zhuweiw@

基本圖形的生成和計算

直線的生成算法

Bresenham直線生成算法

當(dāng)已知光柵化后前一

點的坐標國'),計算

下一點的坐標(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與下面點近，取乂+產(chǎn)乂。

因此，算法的關(guān)鍵在于簡便地求出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直線星成算法命判斷公式，可

以看出，公式較為復(fù)雜，計算量較大。為了降低

計算量，可以利用遞推公式進行計算。

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

當(dāng)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象限內(nèi)的直線Bresenham算法的遞推

公式：

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

Pi=2dy-dx

JXi=X、i+l

當(dāng)PiNO時，yi=yi-i+l,pi+i=Pi+2(dy-dx)

當(dāng)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;

⑵按遞推公式循環(huán)計算點的坐標并顯示。

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直線生成算法具有以下優(yōu)點：

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

(2)不用浮點數(shù)，只用整數(shù)；

(3)只做整數(shù)加減運算和乘2運算，而乘2運算

可以通過移位操作來實現(xiàn)。

由于Bresenham算法具有這些優(yōu)點，因此它的運

算速度快，并適合于硬件實現(xiàn)。

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象限方向去，以實現(xiàn)程序處理的

簡潔。

zhuweiw@

基本圖形的生成和計算

的生成算法

圓的概念

圓是某些應(yīng)用領(lǐng)域中最重要的基

本圖形，它被定義為到給定中心

位置(XcJc)距離為R的點集。產(chǎn)生

圓的算法很多，這里主要介紹生

成圓的逐點比較法、Bresenham算

法等。

zhuweiw@

基本圖形的生成和計算

的生成算法

逐點比較法生成圓弧

逐點比較法主要針對筆式繪圖機。

繪圖機每走完一步，就要把繪圖

機當(dāng)前位置到圓心的距離與圓弧

的半徑進行比較，根據(jù)比較結(jié)果

決定下一■步的走向，這樣一■步步

地用階梯折線來逼近圓弧。由于

每一步即為繪圖機的一個步距，

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

仍然是光滑的。

zhuweiw@

基本圖形的生成和計算

的生成算法

逐點比較法生成圓弧

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

（順時針還是逆時針）進行。若圓弧跨過幾個

象限，則應(yīng)按象限分段生成。

為了推導(dǎo)方便并減少計算量，可以建立局部

坐標系，它把原點作為圓心，將各點坐標減

去圓心坐標就得到局部坐標。繪制圓弧時，

只要用各點局部坐標加上圓心坐標，就是每

點實際坐標位置。

zhuweiw@

基本圖形的生成和計算

的生成算法

逐點比較法生成圓弧

設(shè)圓弧的起點為A(xa?ya),

終點為B(Xb.y小圓心在原

點。設(shè)繪圖筆當(dāng)前位置為

M(xi,yi),它相對于圓弧的

位置著三種情況：點M在

圓弧外側(cè)、內(nèi)側(cè)以及在圓

弧上。因此點M的位置決

定了走步方向。

zhuweiw@

基本圖形的生成和計算

的生成算法

逐點比較法生成圓弧

為了判斷點M與圓弧的相對位置，引入偏差函

數(shù)F。

Fi=Xj2+yj2_R2

其中R是半徑。對于以上三種位置，偏差函數(shù)

分別為：點M在圓弧外側(cè)時，F(xiàn)/0;在內(nèi)側(cè)時,

Fi<0;在圓弧上時，F(xiàn)rOo由此來推導(dǎo)下一點

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

zhuweiw@

基本圖形的生成和計算

的生成算法

逐點比較法生成圓弧

在生成第一象限的逆時針圓弧時，其推導(dǎo)公式

如下：

(1)若Fi〈O,則應(yīng)向+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,則應(yīng)向-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由當(dāng)前點的坐

標值及偏差來計算，根據(jù)Fj+］的正負號決定下

一步走向，逐步進行，直到到達圓弧的終點

結(jié)良。終止判斷可由總步數(shù)月Xb-Xal+'b-yal來

控制，每走一步J減去，J=0時到達終點。

zhuweiw@

基本圖形的生成和計算

的生成算法

逐點比較法生成圓弧

根據(jù)以上分析，我們可得到第一象限的逆時

針圓弧逐點比較法遞推計算公式：

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

Fo=O

當(dāng)耳>0時,xi+1=xrl,yi+i=yi9Fi+1=Fr2xi+l

（當(dāng)Fi〈O時，%+1=\,yi+i=yi+l,Fi+i=Fi+2yi+l

當(dāng)Fj=O時，可選擇上述兩種方法之一

J=J-1

lj=O時結(jié)束

zhuweiw@

基本圖形的生成和計算

的生成算法

逐點比較法生成圓弧(例)

例：設(shè)起點為A(5,3),終點為B(0,6),圓心為0(0,0),

用逐點比較法逆時針生成圓弧。

解：

根據(jù)遞推公式，算法初始偏差值Fo=O,總步數(shù)

J=|0-5|+|6-3|=8,則計算結(jié)果如下￡

zhuweiw@

基本圖形的生成和計算

的生成算法

逐點比較法生成圓?。ɡ?/p>

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

基本圖形的生成和計算

的生成算法

逐點比較法生成圓?。ɡ?/p>

個

765

——

-、3

4

X

21

A

zhuweiw@

基本圖形的生成和計算

的生成算法

逐點比較法生成圓弧

其它各象限與第一象限類似，其偏差公式及

走步規(guī)律見下表：

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利用圓的對稱

性可以減少計算量。

只要掃描轉(zhuǎn)換八分之

一■圓弧，就可以求出

整個圓弧的像素集。

zhuweiw@

基本圖形的生成和計算

的生成算法

Bresenham算法生成圓弧

設(shè)圓的半徑為r,圓心在

(0,0),考慮從x=0,y=i＞開始

的順時針方向的1/8圓弧生

成過程。在這種情況下，x

方向每步增加1,從x=0開

始，到y(tǒng)=x結(jié)束。因此有：

Xi+1=Xi+l

對應(yīng)的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算法生成圓弧

推導(dǎo)判別變量的遞推公式：

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

當(dāng)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當(dāng)pNO時，yi+i=yrl,pi+i=pi+4（xryi）+10

當(dāng)p<0時，yi+i=%Pi+i=pi+4xi+6

<直到x=y時結(jié)束

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@

基本圖形的生成和計算

橢圓生成算法

中點橢圓算法

橢圓可以認為是拉長了的圓，因此，橢圓的生成

可通過修改畫圓程序，使之沿長軸和短軸尺寸不

同來實現(xiàn)。

設(shè)橢圓的中心坐標為（Xc,y）長軸和短軸分別是僅

ry,它們與坐標軸平行，則橢圓的方程可寫為：

zhuweiw@

基本圖形的生成和計算

橢圓生成算法

中點橢圓算法

考慮到標準位置的橢圓在

四分象限中是對稱的，因

此只要計算一個四分象限

中橢圓曲線的像素位置

（第一象限），再由對稱

性就可以得到其它三個象

限中的像素位置。

zhuweiw@

基本圖形的生成和計算

橢圓生成算法

中點橢圓算法

中心點在原點、長短軸平行于坐標軸的橢圓方

程為：

222222

定義橢圓函數(shù)為：f(x,y)=ryx+rxyxry

則有：

r<0若(x,y)位于橢圓邊界內(nèi)

f(x,y)|=0若(x,y)位于橢圓邊界上

〔>0若(x,y)位于橢圓邊界外

zhuweiw@

基本圖形的生成和計算

橢圓生成算法

中點橢圓算法

在第一象限中，將橢圓分成兩

個區(qū)域。算法沿橢圓順時針方

向變化，以（0網(wǎng)）為起點，在區(qū)

域1沿X方向取單位步長，而進

入?yún)^(qū)域2后轉(zhuǎn)化為y方向上的單

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

檢測曲線的斜率值，即：

dx―2yx2y

zhuweiw@

基本圖形的生成和計算

橢圓生成算法

中點橢圓算法

222222=222222

ryx+rxy-ryrx0ryx+rxy-ryrx=0

zhuweiw@

基本圖形的生成和計算

區(qū)域填充算法

概述

實際應(yīng)用中不僅需要畫出各種圖形，還要對某一

封閉區(qū)域填以不同的顏色，這就是區(qū)域填充。區(qū)

域填充即給出一個區(qū)域的邊界，要求對邊界范圍

內(nèi)的所有像素單元賦予指定的顏色代碼，其關(guān)鍵

在于確定填充哪些像素。

區(qū)域填充中的算法分為兩大類：一類是掃描線填

充算法，另一類是種子填充算法。

zhuweiw@

基本圖形的生成和計算

區(qū)域填充算法

掃描線填充算法

掃描線填充算法中用到了兩種相關(guān)性：掃描線相

關(guān)性和邊相關(guān)性。其中，掃描線相關(guān)性是指多邊

形與掃描線兩個交點之間的線段有兩類：在多邊

形內(nèi)部和外部，且兩類線段相間排列，在掃描線

上，如果某個像素在多邊形內(nèi)，則相鄰的像素一

般也在多邊形內(nèi)；邊相關(guān)性是指由前一條掃描線

上的交點序列及邊的直線方程，可算出下一條掃

描線的交點序列。

zhuweiw@

基本圖形的生成和計算

區(qū)域填充算法

掃描線填充算法?(XY)算法

用一■根水平掃描線

自左而右通過多邊

形，掃描線與多邊

形的邊界相交，相

交奇次數(shù)時進入該

多邊形，相交偶次

數(shù)時走出該多邊形。

基本圖形的生成和計算

區(qū)域填充算法

掃描線填充算法?(XY)算法

(XY)算法的步驟：

⑴按多邊形的各頂點y坐標大小排序，并求出最大與

最小的y值ymax,Ymin0

⑵求交。計算每一條掃描線與各邊的交點。

(3)排序。若交點多于兩個，則按x增加的順序排序。

(4)配對。每對交點代表一個相交區(qū)間。

(5)填充。將每一對交點之間的像素置成指定像素值。

(6)沿y軸讓掃描線遞增，并判斷是否大于ymax，若大

于則填充結(jié)束，否則轉(zhuǎn)到步驟(2),直到結(jié)束。

zhuweiw@

基本圖形的生成和計算

區(qū)域填充算法

掃描線填充算法?(XY)算法

(XY)算法的核心是按(x,y)的值對交點作一次分類，

以找出相關(guān)的像素。此算法是對每一對交點之間所

有像素進行填充，因此交點的個數(shù)必須是偶數(shù)才能

保證填充的準確性。當(dāng)掃描線恰好通過多邊形的頂

點(又稱為奇異點)時，不合適的計數(shù)就會導(dǎo)致出

錯。處理奇異點的方法是：若共享交點的兩條邊分

別落在掃描線的兩側(cè)，則交點只算一個；若共享交

點的兩條邊在掃描線的同側(cè)，則交點計為零個或兩

個。

zhuweiw@

基本圖形的生成和計算

區(qū)域填充算法

掃描線填充算法?(XY)算法

0

zhuweiw@

基本圖形的生成和計算

區(qū)域填充算法

種子填充算法

種子填充算法是設(shè)一個封閉的區(qū)域內(nèi)有一

個種子（像素）是已知的，區(qū)域內(nèi)的各點填

充與種子相同的顏色或值，而區(qū)域外和邊界

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

為起點，按一定的規(guī)律檢查種子的四周是否

具有和邊界一樣的顏色或值，如果有則舍棄,

否則填充種子顏色或值。

zhuweiw@

基本圖形的生成和計算

區(qū)域填充算法

種子填充算法

區(qū)域可以分為四連通和八連通兩種，四連通

區(qū)域是指各像素在四個方向上連通；八連通

區(qū)域是指各像素在八個方向上連通。

種子填充算法中允許從四個方向?qū)ふ蚁乱粋€

像素的算法稱為四向算法；允許從八個方向

搜索下一像素的算法稱為八向算法。四向算

法通不過一些狹窄區(qū)域，有時不能填滿多邊

形，而八向算法的缺點是有時要填出多邊形

的邊界。

zhuweiw@

基本圖形的生成和計算

區(qū)域填充算法

種子填充算法

種子填充算法的步驟如下：

⑴把種子像素壓入堆棧。

(2)把種子像素設(shè)置成需要的顏色。

(3)按照右、上、左、下的順序，檢查每個當(dāng)前

像素的周圍四個像素是否和邊界像素的顏色

相等，或者已經(jīng)設(shè)置了和種子一樣的顏色，

只要是其中的一種情況就舍棄，否則，把該

像素壓入堆棧。

(4)從堆棧中彈出一個像素，重復(fù)執(zhí)行步驟(3),

直到堆棧的元素為空。

zhuweiw@

基本圖形的生成和計算

區(qū)域填充算法

種子填充算法

本算法適用于區(qū)域內(nèi)為單一的顏色和灰度,

其操作過程非常簡單，但缺點在于要進行

深度的遞歸，堆?？赡芎艽螅档土怂惴?/p>

的效率。

四向算法種子填色程序很簡單，在它的基

礎(chǔ)上可以寫出各種改進的算法。

zhuweiw@

基本圖形的生成和計算

區(qū)域填充算法

種子填充算法

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@

基本圖形的生成和計算

區(qū)域填充算法

掃描線種子填充算法

當(dāng)給定種子點(x,y)時，首先填充種子點所

在掃描線上的位于給定區(qū)域的一個區(qū)段，

然后確定與這一區(qū)段相連通的上、下兩條

掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次

保存下來。反復(fù)這個過程，直到填充結(jié)束。

掃描線種子填充算法能夠?qū)⒍褩Ｗ钚』?/p>

zhuweiw@

!本圖形的生成和計算

區(qū)域填充算法

掃描線種子填充算法

區(qū)域填充的掃描線算法可通過下列四個步驟實現(xiàn)：

(1)初始化：堆棧置空，將種子點(x,y)入棧。

(2)出棧：若棧空則結(jié)束，否則取棧頂元素(x,y),以y

作為當(dāng)前掃描線。

⑶填充并確定種子點所在區(qū)段：從種子點(x,y)出發(fā)，

沿當(dāng)前掃描線向左、右兩個方向填充，直卸邊界。

(4)確定新的種子點：在上述區(qū)間檢查與當(dāng)前掃描線相

鄰的兩條掃描線，若存在非邊界、未填充的像素，

則把每一區(qū)間的最右像素作為種子點壓入堆棧，返

回第(2)步。

zhuweiw@

基本圖形的生成和計算

字符的生成

概述

字符指數(shù)字、字母、漢字等各種符號，常用于圖形的

標注、說明等。國際上應(yīng)用最廣的字符集是ASCII碼。

我國除采用ASCII碼外，還制定了漢字編碼的國家標準

字符集GB2312-80。每個字符由一個區(qū)碼和一個位碼共

同標識。區(qū)碼和位碼各用一個字節(jié)來表示。為了能夠

區(qū)分ASCII碼和漢字編碼，采用字節(jié)的最高位來標識。

為了在顯示器等輸