分形算法與程序設(shè)計(jì)

第1

章初識分形1.1Fractal的含義1.2分形的幾何特征1.3分形的度量1.4分形維數(shù)1.5分形是一種方法論1.6分形與計(jì)算機(jī)圖形學(xué)1參考書：《分形算法與程序設(shè)計(jì)》1.1Fractal的含義

英文單詞Fractal，在大陸被譯為“分形”，在臺灣被譯為“碎形”。它是由美籍法國數(shù)學(xué)家曼德勃羅（BenoitMandelbrot）創(chuàng)造出來的。其含義是不規(guī)則的、破碎的、分?jǐn)?shù)的。曼德勃羅是想用此詞來描述自然界中傳統(tǒng)歐幾里得幾何學(xué)所不能描述的一大類復(fù)雜無規(guī)的幾何對象。

2參考書：《分形算法與程序設(shè)計(jì)》1.2分形的幾何特征自相似性

自相似，便是局部與整體的相似。自仿射性

自仿射性是自相似性的一種拓展。如果，將自相似性看成是局部到整體在各個方向上的等比例變換的結(jié)果的話，那么，自仿射性就是局部到整體在不同方向上的不等比例變換的結(jié)果。前者稱為自相似變換，后者稱為自仿射變換。

精細(xì)結(jié)構(gòu)

任意小局部總是包含細(xì)致的結(jié)構(gòu)。3參考書：《分形算法與程序設(shè)計(jì)》1.3分形的度量（1）長度的測量

Length(n=0)=1

Length(n=1)=4/3

Length(n=2)=16/9…………Length=lim(Length(n))=lim(4/3)=∞n→∞n→∞n4參考書：《分形算法與程序設(shè)計(jì)》1.3分形的度量（2）面積的測量

Area(n0)=(1╳√3/6)/2=√3/12

Area(n1)=√3/12╳(4/9)Area(n2)=√3/12╳(4/9)2…………

Area(n)=lim(√3/12╳(4/9)n)=0n→∞如上所述，koch曲線在一維歐氏空間中的度量為∞，在二維歐氏空間中的面積為0。如此看來，Koch曲線在傳統(tǒng)歐氏空間中不可度量。5參考書：《分形算法與程序設(shè)計(jì)》1.4分形維數(shù)

分形維數(shù)是分形的很好的不變量，它一般是分?jǐn)?shù)，用它可以把握住分形體的基本特征。

圖a是邊長為1的正方形，當(dāng)邊長變成原來的1∕2時，原正方形中包含4個小正方形，如圖b，而4=22；圖c是邊長為1的正立方體，當(dāng)邊長變成原來的1∕2時，原正立方體中包含8個小正立方體，如圖d，而8=23。則有N＝kD,D=log(N)/log(k)這樣Koch曲線的分形維數(shù)D=log(4)log(3)=1.26186參考書：《分形算法與程序設(shè)計(jì)》1.4分形維數(shù)

對于實(shí)際的自然景物，我們可以用計(jì)盒維數(shù)的方法測量分維。7參考書：《分形算法與程序設(shè)計(jì)》1.5分形是一種方法論

沃爾夫獎（WolfPrize）在頒發(fā)給分形理論創(chuàng)始人曼德勃羅時的評語所說的，“分形幾何改變了我們對世界的看法”。

分形理論至少會在三個方面改變我們對世界的認(rèn)識。首先，自然界中許多不規(guī)則的形態(tài)其背后都有規(guī)則，都可以用分形的方法建立模型并在計(jì)算機(jī)上構(gòu)造出以假亂真的景象來，顯然利用這套方法我們可以把世界壓縮到幾個分形規(guī)則中，便于攜帶和傳播。其次，許多以前被認(rèn)為是隨機(jī)的現(xiàn)象，從分形理論的角度看并不是隨機(jī)的，比如布朗運(yùn)動、股票價格的波動、傳染病的流行傳播等，這為我們控制這些貌似隨機(jī)的現(xiàn)象奠定了理論基礎(chǔ)。最后，分形理論中的分?jǐn)?shù)維概念，為我們認(rèn)識世界中的復(fù)雜形態(tài)提供了一個新的尺度。復(fù)雜性科學(xué)是現(xiàn)代科學(xué)的前沿，在這門科學(xué)的研究過程中，發(fā)現(xiàn)了許多符合分形規(guī)則的復(fù)雜形態(tài)，而分?jǐn)?shù)維是測量這些形態(tài)復(fù)雜程度的一種度量。也就是說，我們找到了對復(fù)雜性做定量分析的工具。8參考書：《分形算法與程序設(shè)計(jì)》1.6分形與計(jì)算機(jī)圖形學(xué)

分形理論的發(fā)展離不開計(jì)算機(jī)圖形學(xué)的支持，如果一個分形構(gòu)造的表達(dá)，不用計(jì)算機(jī)的幫助是很難讓人理解的。不僅如此，分形算法與現(xiàn)有計(jì)算機(jī)圖形學(xué)的其他算法相結(jié)合，還會產(chǎn)生出非常美麗的圖形，而且可以構(gòu)造出復(fù)雜紋理和復(fù)雜形狀，從而產(chǎn)生非常逼真的物質(zhì)形態(tài)和視覺效果。分形作為一種方法，在圖形學(xué)領(lǐng)域主要是利用迭代、遞歸等技術(shù)來實(shí)現(xiàn)某一具體的分形構(gòu)造。分形幾何學(xué)與計(jì)算機(jī)圖形學(xué)相結(jié)合，將會產(chǎn)生一門新的學(xué)科——分形圖形學(xué)。它的主要任務(wù)是以分形幾何學(xué)為數(shù)學(xué)基礎(chǔ)，構(gòu)造非規(guī)則的幾何圖素，從而實(shí)現(xiàn)分形體的可視化，以及對自然景物的逼真模擬。9參考書：《分形算法與程序設(shè)計(jì)》第2

章分形圖的遞歸算法2.1Cantor三分集的遞歸算法2.2Koch曲線的遞歸算法

2.3Sierpinski墊片的遞歸算法2.4Hilbert-Peano曲線的算法2.5分支結(jié)構(gòu)分形遞歸算法2.6分形樹遞歸算法10參考書：《分形算法與程序設(shè)計(jì)》遞歸算法u

直接遞歸調(diào)用的例子如下：voidRecur(n){

……Recur(m);……}過程Recur的內(nèi)部又調(diào)用了自身——Recur過程。

11參考書：《分形算法與程序設(shè)計(jì)》遞歸算法u

間接遞歸調(diào)用的例子如下：voidRecur_A(n){……Recur_B(m);……}voidRecur_B(n){……Recur_A(m);……}

12參考書：《分形算法與程序設(shè)計(jì)》2.1Cantor三分集的遞歸算法算法：Cantor(ax,ay,bx,by)標(biāo)題：Cantor三分集的遞歸算法參數(shù)：c（終止遞歸的小量）

d（不同層次線之間的距離）變量：ax,ay（曲線端點(diǎn)坐標(biāo)）

bx,by（曲線端點(diǎn)坐標(biāo)）

cx,xy

（曲線端點(diǎn)坐標(biāo)）

dx,dy（曲線端點(diǎn)坐標(biāo)）函數(shù)：plot(x1,y1)–(x2,y2)

（畫直線函數(shù)）BEGINIF((bx-ax)<c)THENBEGIN

plot(ax,ay)-(bx,by)ENDELSEBEGIN

plot(ax,ay)-(bx,by)

cx=ax+(bx-ax)/3cy=ay+d

dx=bx-(bx-ax)/3

dy=by+day=ay+dby=by+d

cantor(ax,ay,cx,cy)

cantor(dx,dy,bx,by)ENDEND13參考書：《分形算法與程序設(shè)計(jì)》2.2Koch曲線的遞歸算法算法：Koch(ax,ay,bx,by,c)標(biāo)題：Koch曲線的遞歸算法參數(shù)：c（終止遞歸的小量）

PI（π值）變量：ax,ay（線段端點(diǎn)坐標(biāo)）

bx,by（線段端點(diǎn)坐標(biāo)）

cx,xy

（線段端點(diǎn)坐標(biāo)）

dx,dy（線段端點(diǎn)坐標(biāo)）

ex,ey

（線段端點(diǎn)坐標(biāo)）

L

（線段長度）

alpha（基線與水平線正方向夾角）函數(shù)：plot(x1,y1)–(x2,y2)

（畫直線函數(shù)）

sin()

（正弦函數(shù)）

cos()

（余弦函數(shù)）

ArcTan()

（反正切函數(shù)）

sqrt()

（開平方函數(shù)）14參考書：《分形算法與程序設(shè)計(jì)》2.2Koch曲線的遞歸算法BEGIN

IF((bx-ax)*(bx-ax)+(by-ay)*(by-ay))<cTHEN

BEGIN

plot(ax,ay)-(bx,by)

END

ELSEBEGIN

cx=ax+(bx-ax)/3cy=ay+(by-ay)/3ex=bx-(bx-ax)/3

ey=by-(by-ay)/3L=sqrt((ex-cx)*(ex-cx)+(ey-cy)*(ey-cy))alpha=ArcTan((ey-cy)/(ex-cx))

IF((ex-cx)<0)THEN15參考書：《分形算法與程序設(shè)計(jì)》2.2Koch曲線的遞歸算法

BEGINalpha=alpha+PI

END

dy=cy+sin(alpha+PI/3)*L

dx=cx+cos(alpha+PI/3)*L

Koch(ax,ay,cx,cy,c)

Koch(ex,ey,bx,by,c)

Koch(cx,cy,dx,dy,c)

Koch(dx,dy,ex,ey,c)ENDEND16參考書：《分形算法與程序設(shè)計(jì)》2.3Sierpinski墊片的遞歸算法算法：Sierpinski(x,y,L,n)標(biāo)題：Sierpinski墊片遞歸算法參數(shù)：n（遞歸深度）變量：x,y

（三角形中心點(diǎn)坐標(biāo)）

x1,y1

（三角形頂點(diǎn)坐標(biāo)）

x2,y2（三角形頂點(diǎn)坐標(biāo)）

x3,y3

（三角形頂點(diǎn)坐標(biāo)）

x01,y01（小三角形中心點(diǎn)坐標(biāo)）

x02,y02（小三角形中心點(diǎn)坐標(biāo)）

x03,y03（小三角形中心點(diǎn)坐標(biāo)）

L

（三角形的邊長）函數(shù)：plot(x1,y1)–(x2,y2)

（畫直線函數(shù)）

sin()

（正弦函數(shù)）

cos()

（余弦函數(shù)）

sqrt()

（開平方函數(shù)）17參考書：《分形算法與程序設(shè)計(jì)》2.3Sierpinski墊片的遞歸算法BEGINIF(n=1)THENBEGIN

x1=x-L/2y1=y+L*(sin(PI/6)/cos(PI/6))/2x2=x+L/2y2=y+L*(sin(PI/6)/cos(PI/6))/2x3=xy3=y-L*(sin(PI/6)/cos(PI/6))

plot(x1,y1)-(x1,y1)plot(x2,y2)-(x2,y2)plot(x3,y3)-(x3,y3)

ENDELSEBEGIN

x01=x-L/4y01=y+L*(sin(PI/6)/cos(PI/6))/4x02=x-L/4y02=y+L*(sin(PI/6)/cos(PI/6))/4x03=xy03=y-L*(sin(PI/6)/cos(PI/6))/2Sierpinski(x01,y01,L/2,n-1)Sierpinski(x02,y02,L/2,n-1)Sierpinski(x03,y03,L/2,n-1)ENDEND18參考書：《分形算法與程序設(shè)計(jì)》2.4Hilbert-Peano曲線的算法算法：Peano(n)標(biāo)題：Hilbert-Peano曲線遞歸算法變量：n（遞歸深度）

len（線的長度）

x,y（端點(diǎn)坐標(biāo)）函數(shù)：lineto(x,y)（畫直線函數(shù)）過程：a(n)（基本元素構(gòu)型）

b(n)（基本元素構(gòu)型）

c(n)（基本元素構(gòu)型）

d(n)（基本元素構(gòu)型）

19參考書：《分形算法與程序設(shè)計(jì)》2.4Hilbert-Peano曲線的算法BEGIN

a(n)

BEGIN

IFn>0THEN

BEGINd(n-1)x=x-len

lineto(x,y)a(n-1)y=y+len

lineto(x,y)a(n-1)x=x+len

lineto(x,y)b(n-1)

END

END

b(n)

BEGIN

IFn>0THEN

BEGINc(n-1)y=y-len

lineto(x,y)b(n-1)x=x+len

lineto(x,y)b(n-1)y=y+len

lineto(x,y)a(n-1)

END

END

c(n)

BEGIN

IFn>0THEN

BEGINb(n-1)x=x-len

lineto(x,y)c(n-1)y=y+len

lineto(x,y)c(n-1)x=x+len

lineto(x,y)d(n-1)

END

END

d(n)

BEGIN

IFn>0THEN

BEGINa(n-1)y=y-len

lineto(x,y)d(n-1)x=x+len

lineto(x,y)d(n-1)y=y+len

lineto(x,y)c(n-1)

END

ENDEND20參考書：《分形算法與程序設(shè)計(jì)》2.5分支結(jié)構(gòu)分形遞歸算法算法：Ramus

(x,y,alpha,L,n)標(biāo)題：分支結(jié)構(gòu)遞歸算法參數(shù)：PI（π值）變量：n（遞歸深度）

L（線段長度）

x,y

（線段起點(diǎn)坐標(biāo)）

x1,y1（線段終點(diǎn)坐標(biāo)）

alpha

（主干生成角度）

alpha_L（左支干生成角度）

alpha_R（右支干生成角度）函數(shù)：plot(x1,y1)-(x2,y2)

（畫直線函數(shù)）

sin()（正弦函數(shù)）

cos()（余弦函數(shù)）21參考書：《分形算法與程序設(shè)計(jì)》2.5分支結(jié)構(gòu)分形遞歸算法BEGIN

IF(n>0)THEN

BEGINx1=x+cos(alpha)*Ly1=y-sin(alpha)*Lplot(x,y)-(x1,y1)

alpha_L=alpha+PI/8

alpha_R=alpha-PI/8L=2*L/3Ramus(x2,y2,alpha_L,L,n-1)Ramus(x2,y2,alpha_R,L,n-1)

ENDEND22參考書：《分形算法與程序設(shè)計(jì)》2.6分形樹遞歸算法算法：tree

(x,y,L,alpha)標(biāo)題：分形樹遞歸算法參數(shù)：PI（π值）

A（主干生長方向）

B（側(cè)干與主干的夾角）

C（主干偏轉(zhuǎn)角度）

s1（長度小量，控制遞歸深度）

s2（主干與側(cè)干之比）

s3（上一級主干與下一級主干之比）變量：L

（主干的長度）

x,y

（主干起點(diǎn)坐標(biāo)）

x1,y1（中間分叉點(diǎn)坐標(biāo)）

x2,y2（主干終點(diǎn)坐標(biāo)）

x1L,y1L（第一左分支終點(diǎn)坐標(biāo)）

x1R,y1R（第一右分支終點(diǎn)坐標(biāo)）

x2L,y2L（第二左分支終點(diǎn)坐標(biāo)）

x2R,y2R（第二右分支終點(diǎn)坐標(biāo)）函數(shù)：plot(x1,y1)-(x2,y2)

（畫直線函數(shù)）

sin()（正弦函數(shù)）

cos()（余弦函數(shù)）23參考書：《分形算法與程序設(shè)計(jì)》2.6分形樹遞歸算法BEGIN

IF(L>s1)THEN

BEGINx2=x+L*cos(A*PI/180)y2=y-L*sin(A*PI/180)x2L=x2+L/s2*cos((A+B)*PI/180)y2L=y2-L/s2*sin((A+B)*PI/180)x2R=x2+L/s2*cos((A-B)*PI/180)y2R=y2-L/s2*sin((A-B)*PI/180)x1=x+L/s2*cos(A*PI/180)y1=y-L/s2*sin(A*PI/180)x1L=x1+L/s2*cos((A+B)*PI/180)y1L=y1-L/s2*sin((A+B)*PI/180)x1R=x1+L/s2*cos((A-B)*PI/180)y1R=y1+L/s2*sin((A-B)*PI/180)plot(x,y)-(x2,y2)plot(x2,y2)-(x2L,y2L)plot(x2,y2)-(x2R,y2R)plot(x1,y1)-(x1R,y1R)plot(x1,y1)-(x1L,y1L)tree(x2,y2,L/s3,A-C)tree(x2L,y2L,L/s2,A+B)tree(x2R,y2R,L/s2,A-B)tree(x1R,y1R,L/s2,A-B)tree(x1L,y1L,L/s2,A-B)

ENDEND24參考書：《分形算法與程序設(shè)計(jì)》第3

章文法構(gòu)圖算法3.1LS文法3.2單一規(guī)則的LS文法生成

3.3多規(guī)則的LS文法生成3.4隨機(jī)LS文法25參考書：《分形算法與程序設(shè)計(jì)》文法構(gòu)圖算法字母表：L，R生成規(guī)則：L→R，R→LR初始字母：R則有：R→LR→RLR→LRRLR→RLRLRRLR→LRRLRRLRLRRLR→……26參考書：《分形算法與程序設(shè)計(jì)》3.1LS文法二維LS是字母表的繪圖規(guī)則如下：F：以當(dāng)前方向前進(jìn)一步，并畫線；f：以當(dāng)前方向前進(jìn)一步，不畫線；＋：逆時針旋轉(zhuǎn)角；－：順時針旋轉(zhuǎn)角；[：將海龜當(dāng)前信息壓棧；]：將“[”時刻的海龜信息出棧。27參考書：《分形算法與程序設(shè)計(jì)》3.2單一規(guī)則的LS文法生成Koch曲線的LS文法如下：

w：Fa：60oP：F→F＋F－－F＋F

步驟0：F

步驟1：F＋

F－－F＋F

步驟2：F＋

F－－F＋

F＋

F＋

F－－F＋

F－－F＋

F－－F＋

F＋

F＋

F－－F＋

F

步驟3：F＋

F－－F＋

F＋

F＋

F－－F＋

F－－F＋

F－－F＋

F＋

F＋

F－－F＋

F＋

F＋

F－－F＋

F＋

F＋

F－－F＋

F－－F＋

F－－F＋

F＋

F＋

F－－F＋

F－－F＋F－－F＋F＋

F＋

F－－F＋

F－－F＋

F－－F＋

F＋

F＋

F－－F＋

F＋

F＋

F－－F＋

F＋

F＋

F－－F＋

F－－F＋

F－－F＋F＋

F＋

F－－F＋

F

步驟4：……

28參考書：《分形算法與程序設(shè)計(jì)》3.3單一規(guī)則的LS算法實(shí)現(xiàn)算法：LS標(biāo)題：L_System生成算法參數(shù)：Axiom（公理）

n（字符串替換次數(shù)）變量：a[]（被替換字符）

x[]，y[]（替換字符串）

len（線段長度）

Aipha（基線與水平線夾角）

Dalta（生成角度）

ox,oy（起始坐標(biāo)點(diǎn)）

n（遞歸深度）

bef（前一節(jié)點(diǎn)）

aft（后一節(jié)點(diǎn)）函數(shù)：lineto(x,y)（畫直線函數(shù)）

GetLength(x)（字符串長度）BEGIN//初始化

x[0]=“F”a[1]=“F”x[1]=“F+F--F+F”

len=10

Aipha=0Delta=60ox=100

oy=400n=429參考書：《分形算法與程序設(shè)計(jì)》3.3單一規(guī)則的LS算法實(shí)現(xiàn)

y[]=x[0]

FORi=1TOn

yL=GetLength(y)j=0

WHILE(j<yL)

IF

y[j]==a[1]THENtree[]=tree[]+x[1]j=j+1

ELSEtree[]=tree[]+y[j]j=j+1

ENDIFENDWHILE

y[]=tree[]

tree.Empty()//清空

ENDFOR

tree[]=y[]

//按字符繪圖

WHILE(i<xL)

SWITCH(tree[i])

CASE“F”

aft.x=bef.x+len*cos(Aipha*PI/180)

aft.y=bef.y-len*sin(Aipha*PI/180)

aft.d=bef.d//方向

LineTO(aft.x,aft.y)

bef=aft

BREAK

CASE“[”

stack[k]=befk=k+1

BREAK

CASE“]”

bef=stack[k-1]30參考書：《分形算法與程序設(shè)計(jì)》3.3單一規(guī)則的LS算法實(shí)現(xiàn)

k=k-1

LineTO(bef.x,bef.y)

BREAK

CASE“+”

bef=bef+DeltaBREAK

CASE“-”

bef=bef-Delta

BREAK

ENDSWITCHi=i+1

ENDWHILEEND31參考書：《分形算法與程序設(shè)計(jì)》3.3多規(guī)則的LS文法生成為了生成更復(fù)雜的圖形，可將字母表增加字母元素Sierpinski墊片的LS文法如下：

w：La：600P1：L→＋R－L－R＋

P2：R→－L＋

R＋

L－相應(yīng)的改造1：x[0]=“L”a[1]=“L”x[1]=“+R-L-R+”a[2]=“R”x[2]=“-L+R+L-”Delta=6032參考書：《分形算法與程序設(shè)計(jì)》3.3多規(guī)則的LS文法生成相應(yīng)的改造2：

WHILE(j<xL)

IF

y[j]==a[1]THENtree[]=tree[]+x[1]j=j+1ELSEIFy[j]==a[2]THEN

tree[]=tree[]+x[2]j=j+1

ELSEtree[]=tree[]+y[i]j=j+1

ENDIFy[]=tree[]

ENDWHILE

33參考書：《分形算法與程序設(shè)計(jì)》3.3多規(guī)則的LS文法生成相應(yīng)的改造3：

CASE“L”

aft.x=bef.x+len*cos(Aipha*PI/180)

aft.y=bef.y-len*sin(Aipha*PI/180)

aft.d=bef.d//方向

LineTO(aft.x,aft.y)

bef=aft

BREAK

CASE“R”

aft.x=bef.x+len*cos(Aipha*PI/180)

aft.y=bef.y-len*sin(Aipha*PI/180)

aft.d=bef.d//方向

LineTO(aft.x,aft.y)

bef=aft

BREAK34參考書：《分形算法與程序設(shè)計(jì)》3.4隨機(jī)LS文法w:Fa:25P1：F————→F[＋F]F[－F]FP2：F————→F[＋F]F[－F[＋F]]P3：F————→FF[－F＋F＋F]＋[＋F－F－F]為了更好的模擬自然景物，需要隨機(jī)使用多個變換規(guī)則。p1p2p3相應(yīng)的改造1：x[0]=“F[+F]F[-F]F”x[1]=“F[+F]F[-F[+F]]”x[2]=“FF-[-F+F+F]+[+F-F-F]”相應(yīng)的改造2：

WHILE(j<xL)

IF

y[j]==“F”THEN

r=Rand()%3tree[]=tree[]+x[r]j=j+1

ELSEtree[]=tree[]+y[r]j=j+1

ENDIFENDWHILE35參考書：《分形算法與程序設(shè)計(jì)》3.4隨機(jī)LS文法36參考書：《分形算法與程序設(shè)計(jì)》第4

章迭代函數(shù)系統(tǒng)算法4.1混沌游戲4.2迭代函數(shù)系統(tǒng)4.3相似變換與仿射變換4.4IFS碼4.5Sierpinski墊片的IFS生成4.6拼貼與IFS碼的確定

4.7IFS植物形態(tài)實(shí)例4.8復(fù)平面上的IFS算法37參考書：《分形算法與程序設(shè)計(jì)》混沌游戲4.1給定平面上三點(diǎn)A,B,C。再任意給定初始點(diǎn)Z0,做下列迭代。???íì+++=+,2/)(,2/)(,2/)(1CZBZAZZnnnn當(dāng)擲出的硬幣呈正面當(dāng)擲出的硬幣呈反面當(dāng)擲出的硬幣呈側(cè)面38參考書：《分形算法與程序設(shè)計(jì)》迭代函數(shù)系統(tǒng)4.2迭代函數(shù)系統(tǒng)（IteratedFunctionSystem，IFS）是分形理論的重要分支。它將待生成的圖像看成是由許多與整體相似的（自相似）或經(jīng)過一定變換與整體相似的（自仿射）小塊拼貼而成。39參考書：《分形算法與程序設(shè)計(jì)》相似變換與仿射變換直觀上看：相似變換是指在各個方向上變換的比率必須相同的一種比例變換，仿射變換是指在不同的方向上變化的比率可以不同的一種比例變換。

4.3相似變換：如果對于任意兩點(diǎn)A、B，以及對應(yīng)點(diǎn)A’、B’，總有A’B’=k·AB（k為正實(shí)數(shù)），那么，這個變換叫做相似變換，實(shí)數(shù)k叫做相似比。仿射變換：x’=ax+by+ey’=cx+dy+f其中a,b,c,d,e,f為仿射變換系數(shù)。40參考書：《分形算法與程序設(shè)計(jì)》4.4IFS碼用多個仿射變換式表達(dá)一個圖象w1,w2,w3,……，使用每一個仿射變換式的概率p可以不同，一般面積越大，p值越大。于是，只要獲得a,b,c,d,e,f,p（IFS碼）的值便可以得到要表達(dá)的圖形。x’=a1·x+b1·y+e1y’=c1·x+d1·y+f1w1x’=a2·x+b2·y+e2y’=c2·x+d2·y+f2w2x’=a3·x+b3·y+e3y’=c3·x+d3·y+f3w3p1p2p3p1+p2+p3=141參考書：《分形算法與程序設(shè)計(jì)》4.5Sierpinski墊片的IFS生成

由于生成的三個小三角形的面積相等，所以我們可以讓w1、w2、w3出現(xiàn)的概率相同或相近。

x’=0.5xy’=0.5yx’=0.5x+0.5y’=0.5yx’=0.5x+0.25y’=0.5y-0.5x’=0.5·x+0·y+0y’=0·x+0.5·y+0x’=0.5·x+0·y+0.5y’=0·x+0.5·y+0x’=0.5·x+0·y+0.25y’=0·x+0.5·y-0.5w1w2w342參考書：《分形算法與程序設(shè)計(jì)》4.5Sierpinski墊片的IFS生成

算法：IFS標(biāo)題：IFS生成算法參數(shù)：

n（迭代次數(shù)）

m[]（存儲IFS碼值）變量：a,b,c,d,e,f,p（IFS碼變量）函數(shù)：Pset(x,y)（畫點(diǎn)函數(shù)）

Rand（隨機(jī)函數(shù)）BEGIN//IFS碼賦值

m[0,0]=0.5;m[0,1]=0;m[0,2]=0m[0,3]=0;m[0,4]=0;m[0,5]=0m[0,6]=0.333m[1,0]=0.5;m[1,1]=0;m[1,2]=0m[1,3]=0.5;m[1,4]=0.5;m[1,5]=0m[1,6]=0.333m[2,0]=0.5;m[2,1]=0;m[2,2]=0m[2,3]=0.5;m[2,4]=0.25;m[2,5]=0.5m[2,6]=0.334n=6000

WHILEn>0p=Rand

SWITCH(P)

CASEIS<=m[0,6]a=m[0,0];b=m[0,1];c=m[0,2]d=m[0,3];e=m[0,4];f=m[0,5]

BREAK

CASEIS<=(m[0,6]+m[1,6])a=m[1,0];b=m[1,1];c=m[1,2]d=m[1,3];e=m[1,4];f=m[1,5]

BREAK43參考書：《分形算法與程序設(shè)計(jì)》4.5Sierpinski墊片的IFS生成

CASEIS<=(m[0,6]+m[1,6]+m[2,6])a=m[2,0];b=m[2,1];c=m[2,2]d=m[2,3];e=m[2,4];f=m[2,5]BREAKCASEIS<=(m[0,6]+m[1,6]+m[2,6]+m[3,6])a=m[3,0];b=m[3,1];c=m[3,2]d=m[3,3];e=m[3,4];f=m[3,5]

ENDSWITCH

x=a*x+b*y+ex=c*x+d*y+fPset(100+600*x,500-600*y)n=n-1

ENDWHILEEND（源代碼：書中程序4.1）44參考書：《分形算法與程序設(shè)計(jì)》4.6拼貼與IFS碼的確定

此時四個子圖分別是目標(biāo)圖的1/4、1/5、1/4、1/2大小的復(fù)制品。然后按順序交互式地在屏幕上調(diào)節(jié)每一個子圖的仿射變換參數(shù)ai、bi、ci、di、ei，使得平移、旋轉(zhuǎn)后基本覆蓋住目標(biāo)圖。

45參考書：《分形算法與程序設(shè)計(jì)》4.7IFS植物形態(tài)實(shí)例

IFS碼在書中表4.18IFS碼在書中表4.20IFS碼在書中表4.1946參考書：《分形算法與程序設(shè)計(jì)》4.8復(fù)平面上的IFS算法

47參考書：《分形算法與程序設(shè)計(jì)》4.8復(fù)平面上的IFS算法

算法：Julia_IFS標(biāo)題：Julia集的IFS算法參數(shù)：z（迭代次數(shù)）

PI（π值）

RAND_MAX（隨機(jī)最大值）變量：k（概率變量）

x,y（z的實(shí)部和虛部）

cx,cy（c的實(shí)部和虛部）

r（極距）

a,b,e,f,m,n,wx,wy,theta

函數(shù)：Pset(x,y)（畫點(diǎn)函數(shù)）

Rand（隨機(jī)函數(shù)）

sin（正弦函數(shù)）

cos（余弦函數(shù)）

atan（反正切函數(shù)）BEGINFORi=1TOzm=a*x+en=b*y+fIFi>10THEN

Pset(m,n)ENDIF

wx=x-cx

wy=y-cyIFwx>0THENtheta=atan(wy/wx)ENDIFIFwx<0THENtheta=PI+atan(wy/wx)ENDIFIFwx=0THENtheta=PI/2ENDIF48參考書：《分形算法與程序設(shè)計(jì)》4.8復(fù)平面上的IFS算法

theta=theta/2r=sqit(wx*wx+wy*wy)k=rand

rnd=k/RAND_MAXIFrnd<0.5THENr=sqrt(r)ELSEr=-sqrt(r)ENDIFx=r*cos(theta)y=r*sin(theta)ENDFOREND49參考書：《分形算法與程序設(shè)計(jì)》第5

章逃逸時間算法5.1基本思想

5.2Julia集的逃逸時間算法

5.3Mandelbrot集的逃逸時間算法5.4基于牛頓迭代的Julia集的逃逸時間算法50參考書：《分形算法與程序設(shè)計(jì)》逃逸時間算法的基本思想F(z)=z2+c當(dāng)c=0時，由于z是復(fù)數(shù)，即z=x+yi，則有z2=z×z=(x+yi)×(x+yi)=x2+y2i2+2xyi=(x2-y2)+(2xy)i設(shè)復(fù)數(shù)z=x+yi的絕對值，即

|z|=SQR(x2+y2)|F(z0)|=|x02-y02+2x0y0i|=SQR((x02-y02)2+(2x0y0)2)=SQR(x04+y04-2x02y02+4x02y02)=SQR((x02+y02)2)=|z0|2若0<|z0|<1,|F(z0)|<|z0|，對于每一次迭代z趨向0，即z向0收斂。若|z0|>1,經(jīng)過迭代z會趨向無窮，z向無窮逃逸。若|z0|>1,

z是平面上的單位圓。5.151參考書：《分形算法與程序設(shè)計(jì)》逃逸時間算法的基本思想當(dāng)c≠0時，其吸引子不再是0，而是一個區(qū)域，稱混沌區(qū)。如圖，假設(shè)有一個充分大的整數(shù)N，當(dāng)未逃逸區(qū)域M中的初始點(diǎn)a經(jīng)過小于N次迭代就達(dá)到未逃逸區(qū)域M的邊界，甚至超出了邊界，我們就認(rèn)為點(diǎn)a逃逸出去了；而如果經(jīng)過N次迭代后a的軌跡仍未到達(dá)M的邊界，我們就認(rèn)為，a是A上的點(diǎn)。用這樣的方法，描繪出A的邊界圖形，這便是逃逸時間算法的基本思想。

5.152參考書：《分形算法與程序設(shè)計(jì)》5.2Julia集的逃逸時間算法

53參考書：《分形算法與程序設(shè)計(jì)》5.2Julia集的逃逸時間算法

算法：Julia標(biāo)題：Julia集的逃逸時間算法參數(shù)：K（逃逸時間）

m（逃逸半徑）

Mx,My（繪圖范圍）

xs,xl,ys,yl（窗口范圍）

p,q（復(fù)平面上C的坐標(biāo)）變量：x0,y0（坐標(biāo)變量）

r（膜變量）函數(shù)：SetP(x,y,color)（畫點(diǎn)函數(shù)）

BEGIN//初始化

K=100m=500

Mx=800My=600

xs=-1.5xl=1.5

ys=-1.5

yl=1.5p=0.23q=0.043

xb=(xl-xs)/Mx

yb=(yl-ys)/My

54參考書：《分形算法與程序設(shè)計(jì)》5.2Julia集的逃逸時間算法

FOR

nx=0TO

Mx

FOR

ny=0TOMyx0=xs+nx*xby0=ys+ny*ybk=0Loop1:

xk=x0*x0-y0*y0+p

yk=2*x0*y0+qk=k+1r=xk*xk+yk*ykx0=xky0=yk

IFr>mTHENH=k;

gotoLoop2

ENDIF

IFk==KTHENH=r

GOTOLoop2

ENDIF

IFr<=m&&k<KTHEN

GOTOLoop1

ENDIF

Loop2:

SetP(nx,ny,H)

ENDFOR

ENDFOREND55參考書：《分形算法與程序設(shè)計(jì)》56參考書：《分形算法與程序設(shè)計(jì)》5.3Mandelbrot集的逃逸時間算法

算法：Mandelbrot標(biāo)題：Mandelbrot集的逃逸時間算法參數(shù)：K（逃逸時間）

m（逃逸半徑）

Mx,My（繪圖范圍）

xs,xl,ys,yl（窗口范圍）

p,q（復(fù)平面上C的坐標(biāo)）變量：x0,y0（坐標(biāo)變量）

r（膜變量）函數(shù)：SetP(x,y,color)（畫點(diǎn)函數(shù)）

BEGINpl=0.9

ps=2.3

ql=1.2

qs=-1.2K=100m=500

Mx=800My=600p=(pl-ps)/Mxq=(ql-qs)/My

FOR

np=0TO

Mx

FOR

nq=0TOMyp0=ps+np*pq0=qs+nq*qk=057參考書：《分形算法與程序設(shè)計(jì)》5.3Mandelbrot集的逃逸時間算法

x0=0y0=0Loop1:

xk=x0*x0-y0*y0+p0

yk=2*x0*y0+q0k=k+1r=xk*xk+yk*ykx0=xky0=yk

IFr>mTHENH=kGOTOLoop2

ENDIF

IFr<=mANDk<KTHEN

GOTOLoop1

ENDIFLoop2:

SetP(np,nq,H)

ENDFOR

ENDFOREND58參考書：《分形算法與程序設(shè)計(jì)》59參考書：《分形算法與程序設(shè)計(jì)》5.4基于牛頓迭代的Julia集的逃逸時間算法

牛頓迭代法求根公式：zn+1=zn-f(zn)/f’(zn)

其中，f’(zn)是f(zn)的導(dǎo)數(shù)?？紤]f(z)=z3-1=0的情況,那么相應(yīng)的牛頓變換是f(z)=(2z3+1)/3z2則z的三個根分別是w1=1,w2=ei2π/3,w3=ei4π/3，三個根的吸引域A(w1)，A(w2)，A(w3)的交界便是牛頓函數(shù)的Julia集。經(jīng)過迭代，在A(wi)上的點(diǎn)都會被吸引到點(diǎn)wi上。設(shè)一個較大的迭代次數(shù)N，以及一個距離小量r，當(dāng)?shù)螖?shù)達(dá)到N，其與根點(diǎn)的距離小于r的被認(rèn)為是收斂到某根上了，否則被認(rèn)為是逃逸了。60參考書：《分形算法與程序設(shè)計(jì)》5.4基于牛頓迭代的Julia集的逃逸時間算法

算法：Julia_Newton標(biāo)題：Julia集的牛頓迭代逃逸時間算法參數(shù)：N（迭代次數(shù)）

r（距離小量）

Mx,My（繪圖范圍）

xs,xl,ys,yl（窗口范圍）

p,q（復(fù)平面上C的坐標(biāo)）變量：x0,y0（坐標(biāo)變量）

r（膜變量）函數(shù)：SetP(x,y,color)（畫點(diǎn)函數(shù)）

BEGIN

fnm(x,y)=x*x+y*y

FORi=-150TO150

FORj=-150TO150x=i/75y=i/75

FORk=1TOn

IFi=0ANDj=0THEN

GOTOLoop

ENDIF

IFfnm(x-1,y)<rTHENSetP(i,j)

GOTOLoop

ENDIFfm=3*fnm(x,y)*fnm(x,y)61參考書：《分形算法與程序設(shè)計(jì)》5.4基于牛頓迭代的Julia集的逃逸時間算法

nx=2*x/3+(x*x-y*y)/fm

ny=2*y/3-2*x*y/fmx=nxy=ny

ENDFORLoop

ENDFOR

ENDFOREND62參考書：《分形算法與程序設(shè)計(jì)》第6

章分形顯微鏡6.1逃逸時間算法的放縮原理6.2Mandelbrot集的局部放大6.3Julia集的局部放大

6.4牛頓迭代法的局部放大6.5作為Julia集字典的Mandelbrot集63參考書：《分形算法與程序設(shè)計(jì)》逃逸時間算法的放縮原理6.164參考書：《分形算法與程序設(shè)計(jì)》6.2Mandelbrot集的局部放大

BEGIN

dp=(pmax-pmin)/(w_right-w_left)

dq=(qmax-qmin)/(w_bottom-w_top)FORi=w_leftTOw_rightp=pmin+dp*i;FORj=w_topTOw_bottomx0=0y0=0q=qmin+dq*jFORk=0TOm_times x=x0*x0-y0*y0+py=2*x0*y0+qr=x*x+y*yx0=xy0=y算法：Mandelbrot_zoom標(biāo)題：Mandelbrot集的局部放大參數(shù)：m_times（逃逸時間）

m_deep（逃逸半徑）變量：pmin，qmin

（參數(shù)窗口左上角坐標(biāo)）

pmax，qmax

（參數(shù)窗口右下角坐標(biāo)）

w_left，w_top

（繪圖窗口左上角坐標(biāo)）

w_right，w_bottom

（繪圖窗口右下角坐標(biāo)）

p,q（參數(shù)坐標(biāo)）

x,y（繪圖坐標(biāo)）

x0,y0（繪圖坐標(biāo)）

r（極距）函數(shù)：SPost(x,y,color)

（畫點(diǎn)）65參考書：《分形算法與程序設(shè)計(jì)》6.2Mandelbrot集的局部放大

IF(r>m_deep)THENbreakIF(k>=m_times)THENk=r

SPost(i,j,k);ENDFORENDFORENDFOREND 66參考書：《分形算法與程序設(shè)計(jì)》6.3Julia集的局部放大BEGIN

dp=(pmax-pmin)/(w_right-w_left)

dq=(qmax-qmin)/(w_bottom-w_top)FORi=w_leftTOw_rightp=pmin+dp*i;FORj=w_topTOw_bottomx0=pmin+dp*i;y0=qmin+dq*j;q=qmin+dq*jFORk=0TOm_times x=x0*x0-y0*y0+py=2*x0*y0+qr=x*x+y*yx0=xy0=y算法：Julia_zoom標(biāo)題：Julia集的局部放大參數(shù)：m_times（逃逸時間）

m_deep（逃逸半徑）變量：pmin，qmin

（參數(shù)窗口左上角坐標(biāo)）

pmax，qmax

（參數(shù)窗口右下角坐標(biāo)）

w_left，w_top

（繪圖窗口左上角坐標(biāo)）

w_right，w_bottom

（繪圖窗口右下角坐標(biāo)）

p,q（參數(shù)坐標(biāo)）

x,y（繪圖坐標(biāo)）

x0,y0（繪圖坐標(biāo)）

r（極距）函數(shù)：SPost(x,y,color)

（畫點(diǎn)）67參考書：《分形算法與程序設(shè)計(jì)》6.3Julia集的局部放大

IF(r>m_deep)THENbreakIF(k>=m_times)THENk=r

SPost(i,j,k);ENDFORENDFORENDFOREND 68參考書：《分形算法與程序設(shè)計(jì)》6.4牛頓迭代法的局部放大BEGIN

dp=(pmax-pmin)/(w_right-w_left)

dq=(qmax-qmin)/(w_bottom-w_top)FORi=w_leftTOw_rightFORj=w_topTOw_bottomx=pmin+dp*i;y=qmin+dq*j;count=0;WHILE(count<N)xx=x*x

yy=y*y d=3*((xx-yy)*(xx-yy)+4*xx*yy)

tmp=x; x=(2/3)*x+(xx-yy)/dy=(2/3)*y-2*tmp*y/d count=count+1; ENDWHILE算法：Newton_zoom標(biāo)題：Newton法的局部放大參數(shù)：m_times（逃逸時間）

m_deep（逃逸半徑）變量：pmin，qmin

（參數(shù)窗口左上角坐標(biāo)）

pmax，qmax

（參數(shù)窗口右下角坐標(biāo)）

w_left，w_top

（繪圖窗口左上角坐標(biāo)）

w_right，w_bottom

（繪圖窗口右下角坐標(biāo)）

p,q（參數(shù)坐標(biāo)）

x,y（繪圖坐標(biāo)）

xx,yy（繪圖坐標(biāo)）

d（極距）函數(shù)：SPost(x,y,color)

（畫點(diǎn)）69參考書：《分形算法與程序設(shè)計(jì)》6.4牛頓迭代法的局部放大IF(x>0)THENcolor=countELSEIF(x<-0.3)AND(y>0.0)THENcolor=count+100ELSEcolor=count+200ENDIFENDFORENDFOREND 70參考書：《分形算法與程序設(shè)計(jì)》6.5作為Julia集字典的Mandelbrot集

Julia集是一個固定的值的圖形展現(xiàn)，而Mandelbrot集卻要走遍所有的值，顯然，每一個值都對應(yīng)一個Julia集，所以我們說Mandelbrot集是Julia集微縮字典。我們可以在Mandelbrot集的繪圖空間中任意取一點(diǎn)，并將其還原成相應(yīng)的值，再將此值作為Julia集程序中選定的值，來繪制Julia集的圖形。dp=(pl-ps)/Mxdq=(ql-qs)/MyDrawJulia(ps+dp*point.x,qs+dq*point.y)71參考書：《分形算法與程序設(shè)計(jì)》第7

章分形演化算法7.1從邏輯運(yùn)算談起7.2一維元胞自動機(jī)7.3二維元胞自動機(jī)7.4分形演化的DLA模型7.5用DLA模型模擬植物的生長7.6不同初始條件的DLA形態(tài)72參考書：《分形算法與程序設(shè)計(jì)》73參考書：《分形算法與程序設(shè)計(jì)》從邏輯運(yùn)算談起7.1邏輯異或

本行：00011011下一行：0110

74參考書：《分形算法與程序設(shè)計(jì)》7.2一維元胞自動機(jī)元胞按等間隔方式分布在一條向兩側(cè)無限延伸的直線中，稱為一維元胞自動機(jī)。

本行：001