分形之Julia集及其算法實(shí)現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)成績(jī)： 課程名稱：智能信息處理概論分形之Julia集及其算法實(shí)現(xiàn)摘要：本文從自然界的幾何現(xiàn)象引出分形的概念，再?gòu)钠涠x、幾何特征和分形維的計(jì)算這三個(gè)方面來(lái)加以介紹。以Julia集和Mandelbort集為例來(lái)具體描述分形。本文主要從Julia集的特點(diǎn)和算法實(shí)現(xiàn)來(lái)描述分形以及其實(shí)現(xiàn)的方法。關(guān)鍵詞：分形、分?jǐn)?shù)維、Julia集、Mandelbort集、算法實(shí)現(xiàn)引言大自然是個(gè)很偉大的造物者，它留給我們一大筆美麗景觀：蜿蜒曲折的海岸線、起伏不定的山脈，變幻無(wú)常的浮云，粗糙不堪的斷

2、面，裊裊上升的煙柱，九曲回腸的河流，縱橫交錯(cuò)的血管，令人眼花繚亂的滿天繁星那么，我們又能從這些美妙的自然現(xiàn)象中得到什么有趣的結(jié)論呢？正文分形概述分形的英文單詞為fractal，是由美籍法國(guó)數(shù)學(xué)家曼德勃羅（Benoit Mandelbrot）創(chuàng)造出來(lái)的。其取自拉丁文詞frangere（破碎、產(chǎn)生無(wú)規(guī)則碎片）之頭，擷英文之尾所合成，本意是不規(guī)則的、破碎的、分?jǐn)?shù)的。他曾說(shuō)：分形就是通過(guò)將光滑的形狀弄成多個(gè)小塊，反復(fù)的碎弄。1975年，曼德勃羅出版了他的法文專著分形對(duì)象：形、機(jī)遇與維數(shù)，標(biāo)志著分形理論正式誕生?！?】?jī)煞N定義其一：具有自相似性結(jié)構(gòu)的叫做分形；其二：數(shù)學(xué)定義：豪斯道夫維Df=拓?fù)渚SDt。

3、若一有界集合，包含N個(gè)不相重疊的子集，當(dāng)其放大或縮小r倍后，仍與原集合疊合，則稱為自相似集合。自相似集合是分形集。具有相似性的系統(tǒng)叫做分形。當(dāng)放大或縮小的倍數(shù)r不是一個(gè)常數(shù)，而必須是r（r1，r2，.）的各種不同放大倍數(shù)去放大或縮小各子集，才能與原集合重合時(shí)，稱為自仿射集合。具有自仿射性的系統(tǒng)叫做分形?！?】特征自相似性：局部與整體的相似，是局部到整體在各個(gè)方向上的等比例變換的結(jié)果；自仿射性：是自相似性的一種拓展，是局部到整體在不同方向上的不等比例變換的結(jié)果；精細(xì)結(jié)構(gòu)：即使對(duì)該分形圖放大無(wú)窮多倍，還是能看到與整體相似的結(jié)構(gòu)，表現(xiàn)出無(wú)休止的重復(fù)；分形集無(wú)法用傳統(tǒng)幾何語(yǔ)言來(lái)描述，它不是某些簡(jiǎn)單方程

4、的解集，也不是滿足某些條件的點(diǎn)的軌跡；分形集一般可以用簡(jiǎn)單的方法定義和產(chǎn)生，如遞歸、迭代；分形其實(shí)是由一些簡(jiǎn)單的圖形，經(jīng)過(guò)遞歸或者迭代產(chǎn)生的復(fù)雜、精細(xì)的結(jié)構(gòu)；無(wú)確定的標(biāo)度且具有分?jǐn)?shù)維數(shù)。【3】分?jǐn)?shù)維拓?fù)渚SDt：又稱橡皮幾何學(xué)。研究幾何圖形在一對(duì)一的雙方連續(xù)變換下不變的性質(zhì)，稱為拓?fù)湫再|(zhì)。 豪斯道夫維數(shù)Df：1919年提出連續(xù)空間的定義：即空間維數(shù)不是躍變的，而是可以連續(xù)變化的，既可以是整數(shù)，也可以是分?jǐn)?shù)，通過(guò)具體計(jì)算來(lái)確定維數(shù)。分?jǐn)?shù)性質(zhì) 豪斯道夫維數(shù)有三種求解方法：1.放大求解：豪斯道夫維Df的幾何對(duì)象，每個(gè)棱邊長(zhǎng)度放大L倍，幾何對(duì)象對(duì)應(yīng)放大K倍。那么，由LDf=K，可推導(dǎo)出 Df=lnKln

5、L。2.縮小求解：豪斯道夫維Df的幾何對(duì)象，等分成N個(gè)小的幾何圖形，則每個(gè)小圖形每維縮小為原來(lái)的r維。而N個(gè)小圖形的總和應(yīng)為NrDf=1。那么，分維為Df=lnNln1r。 3.測(cè)量學(xué)求解：對(duì)一個(gè)體積為A，分維為Df的幾何對(duì)象，要用半徑為r的小球去測(cè)度，則所需小球數(shù)目為Nr=ACrDf1rDf 。其中，C為結(jié)構(gòu)因子。所以分維為Df=lnNrln1r。 這里的分維也稱為科爾莫哥諾夫容量維。 定義容量維為Dcp=limr0lnNrln1r，且其與Df=lnNln1r相一致。各棱邊放大L倍，相應(yīng)的幾何對(duì)象體積放大K倍，則所需小球數(shù)目應(yīng)為 N=KArDf。若小球半徑r縮小L倍，而A保持不變，則所需小球

6、數(shù)目仍應(yīng)為N。那么所需小球數(shù)目的表達(dá)式應(yīng)為 N=ArLDf。由上述兩個(gè)式子可得 Df=lnKlnL。即可得到結(jié)論容量維與豪斯道夫維相一致?！?】分形舉例Julia集Julia 集是由數(shù)學(xué)家 Gaston Julia 和 Pierre Faton 在發(fā)展了復(fù)變函數(shù)迭代的基礎(chǔ)理論后獲得的。其也是一個(gè)典型的分形，只是在表達(dá)上相當(dāng)復(fù)雜，難以用古典的描述。Julia集與Mandelbort集來(lái)自于復(fù)數(shù)非線性映射fZ=Z2+C。通過(guò)給定的不同初始值，經(jīng)過(guò)無(wú)窮次的迭代產(chǎn)生的分形圖集。當(dāng)C給定初始值，而Z值作為一個(gè)變量，通過(guò)無(wú)數(shù)次迭代產(chǎn)生的分形圖集稱為Julia集; 當(dāng)Z給定初始值，而C值作為一個(gè)變量，通過(guò)無(wú)

7、數(shù)次迭代產(chǎn)生的分形圖集稱為Mandelbort集。特點(diǎn)對(duì)于映射Zn+1=Zn2+C而言，若C=Cr+iCi , Z=x+iy , 則有二維映射xn+1=xn2-yn2+Cryn+1=2xnyn+Ci例如取C=0+0i，則有以下情況發(fā)生：如果Z01，則在復(fù)Z平面上迭代結(jié)果Zn；那么，無(wú)窮是ZZ2的吸引子。復(fù)平面上所有與零點(diǎn)的距離超過(guò)1的點(diǎn)，都產(chǎn)生趨向無(wú)窮的序列。如果Z0=1，則Zn=1；那么，產(chǎn)生的序列總出現(xiàn)在上面兩個(gè)吸引區(qū)域之間的邊界上。此時(shí)，邊界恰為復(fù)平面上的單位圓周Z=1，就是Julia集。然而，當(dāng)C0時(shí)，其吸引子不再是0，而變?yōu)橐粋€(gè)區(qū)域，被吸進(jìn)去的點(diǎn)會(huì)遍歷整個(gè)區(qū)間，這個(gè)區(qū)域被稱做混沌區(qū)。

8、與此同時(shí)，分割混沌區(qū)和向逃逸的分界線不再是單位圓Z=1，而是一個(gè)不規(guī)則、非光滑的分界線。當(dāng)C值越來(lái)越大時(shí)，復(fù)平面上甚至?xí)a(chǎn)生幾個(gè)離散的吸引區(qū)域，而每個(gè)孤島的分界線都是不滾則和不光滑的。Julia集的實(shí)際例子是求解三次方程fZ=Z3+1=0。 三個(gè)根的Newton迭代法是：Zn+1=Zn-fZnfZn或Zn+1=Zn -Zn3-13Zn2。上述式子的三個(gè)根是1，-12+32i 和 -12-32i，即該式有三個(gè)吸引子。那么，從復(fù)平面上任何地方的初值Z0開(kāi)始迭代，最終應(yīng)該滑到其中的一個(gè)吸引子。自然而然，我們所得到的三個(gè)吸引區(qū)的邊界也應(yīng)該是簡(jiǎn)單，明顯的。然而，繪圖時(shí)發(fā)現(xiàn)，三個(gè)扇形區(qū)域的邊界具有一種特別

9、的性質(zhì)，即上面的每個(gè)點(diǎn)都隔開(kāi)所有三個(gè)區(qū)域，形成了一種復(fù)雜的邊界。當(dāng)我們把這邊界放大時(shí)，又會(huì)形成自相似的結(jié)構(gòu)。因此，Julia集通常被認(rèn)為具有分?jǐn)?shù)維結(jié)構(gòu)，并且在這個(gè)集上的迭代過(guò)程是一種混沌運(yùn)動(dòng)。剛剛，Julia集是在復(fù)數(shù)平面x，y上考慮的；那么，讓我們從復(fù)參數(shù)平面Cr,Ci上進(jìn)行。此時(shí)取定Z0，經(jīng)過(guò)無(wú)數(shù)次迭代產(chǎn)生的使Zn有界的點(diǎn)集Cr,Ci就是Mandelbort集?！?】【6】逃逸時(shí)間算法Julia集是復(fù)數(shù)映ZZ2+C ，當(dāng)C為某一固定值時(shí)的一個(gè)吸引域，其中C=p+iq , Z=x+iy , 則有二維映射xt+1=xt2-yt2+pyt+1=2xtyt+q。從逃逸時(shí)間算法的角度看，Julia集

10、的內(nèi)部收斂于某一點(diǎn)或某幾個(gè)點(diǎn)，而Julia集的外部隨著逃逸時(shí)間t的增加將發(fā)散至，其逃逸邊界便是Julia集。我們可以根據(jù)點(diǎn)x，y逃向的速度決定逃逸區(qū)中個(gè)點(diǎn)的著色。設(shè)計(jì)思路：假設(shè)繪圖窗口的圖形分辨率是ab點(diǎn)，可顯示顏色K+1種，以數(shù)字0K表示，且0表示黑色。1.選定參數(shù)C=p+iq ，xmin=ymin=-1.5 , M=100 ; 令x=xmax-xmina-1 , y=ymax-yminb-1 , 對(duì)所有的點(diǎn)nx,ny , nx=0,1,a-1及ny=0,1,b-1，完成如下步驟的循環(huán)。2.令x0=xmin+nx*x , y0=ymin+ny*y , t=0。3.根據(jù)下式的迭代過(guò)程從xi,y

11、i算出xi+1,yi+1 ， 計(jì)數(shù)t=t+1。xt+1=xt2-yt2+pyt+1=2xtyt+q4.計(jì)算r=xt2+yt2 ： 如果rM , 則選擇顏色t，轉(zhuǎn)至步驟5； 如果t=K , 則選擇顏色0（黑色），轉(zhuǎn)至步驟5； 如果rM 且tK 則轉(zhuǎn)至步驟5。5.對(duì)點(diǎn) nx,ny 著顏色t并轉(zhuǎn)至下一點(diǎn)，再?gòu)念^做步驟5。【7】【8】程序設(shè)計(jì)：CJuliaView: :CJuliaView() /TODO: : add construction code here K=100;/逃逸時(shí)間 m=500;/逃逸半徑 Mx=800; My=600;/繪圖范圍 xs= -1.5; x1= 1.5; ys= -

12、1.5; y1= 1.5; /復(fù)平面上C的坐標(biāo) p=0.32; q=0.043;void CJuliaview: :OnDraw(CDC* pDC) CJuliaDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); / TODO: add draw code for native data here xb=(x1-xs)/Mx; yb=(y1-ys)/My; for(nx=0;nx=Mx;nx+) for(ny=0;nym) H=k; goto loop2; If(k=K) H=int(r*10); goto loop2; If(r=m&kSetPixe

13、l(nx,ny,H*1000); 在Julia View.h文件夾定義變量如下：public: double x1,xs; double y1,ys;double x0,y0; double xb,yb; double xk,yk; double r; double p,q; int H,K,k,m; int Mx,My; int nx,ny;c =0.194-0.6557ic =0.31+0.04ic =-1.25c =-0.12+0.74i復(fù)平面上的IFS算法：相似變換是指在各個(gè)方向上變換的比率必須相同的一種比例變換，仿射變換是指在不同方向上變化的比率可以不同的一種比例變換。相似變換可放大

14、或縮小甚至旋轉(zhuǎn)，但不變形；而仿射變換可能會(huì)變形。仿射變換的數(shù)學(xué)表達(dá)式為:x=ax+by+ey=cx+dy+f 其中，代表仿射變換，x和y是變換前圖形的坐標(biāo)值，x和y是變換后的圖形的坐標(biāo)值；a, b, c, d, e, f 是仿射變換系數(shù)。對(duì)于一個(gè)比較復(fù)雜的圖形，可能需要多個(gè)不同的仿射變換來(lái)實(shí)現(xiàn)，放射變換族n控制著圖形的結(jié)構(gòu)和形狀，由于仿射變換的形式是相同的，所以不同的形狀取決于仿射變換的系數(shù)。另外，仿射變換族n中，每一個(gè)仿射變換被調(diào)用的概率是不一定等同的，也就是說(shuō)，落入圖形各部分中點(diǎn)的數(shù)目是不一定相同，這就引入了一個(gè)新的量，即仿射變換被調(diào)用的概率P。從而，6個(gè)仿射變換系數(shù)（a, b, c, d

15、, e, f）和一個(gè)概率（P）便組成了IFS算法最關(guān)鍵的部分IFS碼。設(shè)計(jì)思路：對(duì)于復(fù)映射FZ=Z2+C ，設(shè)Z0為給定點(diǎn)，我們尋找Z使得FZ=Z2+C=Z0 ，由此給出兩個(gè)反函數(shù)，即1Z=Z-C 和2Z=-Z-C 。則可以將1，2，C看成是一個(gè)IFS，然后取概率p1=p2=12 , 分別畫(huà)1和2。具體步驟如下：1.當(dāng)k=0(k為迭代的次數(shù))時(shí)，壓棧，畫(huà)點(diǎn)Z0；2.從棧頂取一點(diǎn)（Z，k）；3.根據(jù)概率p1和p2，分別計(jì)算1Z=Z-C 和2Z=-Z-C ，畫(huà)點(diǎn)1，2 ，將（1，k）壓棧，令Z=1；4.重復(fù)步驟3直至k=N-1 ；5.畫(huà)點(diǎn)Z-C 和-Z-C；6.判斷棧是否為空，若?？眨瑒t停止，否則

16、重復(fù)26 ?！?】【10】程序設(shè)計(jì)：/CJULIAView drawingvoid CJULIAView: :OnDraw(CDC* pDC)CJULIADoc* pDoc = GetDocument();ASSERT_VALID(pDoc);/TODO: add draw code for native data herefloat k;for(i=0;i10) /CClientDC pDC(this); pDC-SetPixel(m,n,m_pColor); wx=x-cx; wy=y-cy; if(wx0) theta=atan(wy/wx);if(wx0) theta=PI+atan(

17、wy/wx); if(wx=0) theta=PI/2; theta=theta/2; r=sqrt(wx*wx+wy*wy); k=(float)rand(); rnd=(float)(k/RAND_MAX); if(rnd0.5) r=sqrt(r); else r=-sqrt(r); x=r*cos(theta); y=r*sin(theta);/CJULIAView message handlersvoid CJULIAView: :OnParamSet() /TODO: Add your command handler code here CCsetPara dlg; cx=dlg.

18、m_cx; cy=dlg.m_cy; x=dlg.m_x;y=dlg.m_y;Invalidate(); 結(jié)論分形是一種由簡(jiǎn)單的直線或者方程通過(guò)無(wú)窮次簡(jiǎn)單的迭代形式而產(chǎn)生的具有無(wú)比精細(xì)的結(jié)構(gòu)，這個(gè)過(guò)程又稱之為混沌。其兩者是密不可分的。分形理論表現(xiàn)出兩個(gè)重要原則自相似原則和迭代生成原則。而這兩種原則正是分形算法實(shí)現(xiàn)的重要依據(jù)。自然界的奧秘是無(wú)窮的，它還有許許多多的分形結(jié)構(gòu)等著我們?nèi)ヌ剿?、去發(fā)現(xiàn)。我們一定不能放慢腳步，要勇于創(chuàng)新，把大自然留給我們的寶藏發(fā)掘出來(lái)，為之己用！參考文獻(xiàn)1作者：孫博文； 書(shū)名M：分形算法與程序設(shè)計(jì)Visual C+實(shí)現(xiàn)； 版本：第一版；出版地：北京； 出版者：科學(xué)出版社； 出版年：2004年11月； 起止頁(yè)碼：1-1.2作者：林鴻溢、李映雪； 書(shū)名M：分形論奇異性探索； 版本：第一版；出版地：北京； 出版者：北京理工大學(xué)出版社； 出版年：1992年9月； 起止頁(yè)碼：62-63.3作者：孫博文； 書(shū)名M：分形算法與程序設(shè)計(jì)Visual