【導讀】學生畢業(yè)設(shè)計（論文）。課題名稱分形理論在圖形學中的應用。院系計算機科學系。專業(yè)信息管理與信息系統(tǒng)

　　

【正文】 則通向無窮遠處。這樣在計算機上我們就用不同的顏色來繪制不同的點，就得到了一個很精細復雜的分形圖。這就是逃逸時間算法的基本思想。上面用迭代算法得到的 M 集和 J 集也可以用逃逸時間算法得到。逃逸時間算法是一種非常實用的方法，用此方法可以得到許多復雜的分形圖。特別是隨著計算機的發(fā)展，用這種方法編寫的代碼在計算機上實現(xiàn)分形圖非常方便。 4. 經(jīng)典分形圖形 分形圖形 根據(jù)它的實現(xiàn)算法的不同，可以分為幾種類型：自相似分形、復迭代中的分形、牛頓法迭代分形、 Lsystem 分形等。本章主要描述一些經(jīng)典的分形圖形的生成原理，以便推導出更一般的分形圖形的生成方法。 23 一個系統(tǒng)的自相似性是指某種結(jié)構(gòu)或過程的特征從不同的空間尺度或時間尺度來看都是相似的，或者某系統(tǒng)或結(jié)構(gòu)的局域性質(zhì)或局域結(jié)構(gòu)與整體類似。另外，在整體與整體之間或部分與部分之間，也會存在自相似性。一般情況下自相似性有比較復雜的表現(xiàn)形式，而不是局域放大一定倍數(shù)以后簡單地和整體完全重合。但是，表征自相似系統(tǒng)或結(jié)構(gòu)的定 量性質(zhì)如分形維數(shù)，并不會因為放大或縮小等操作而變化，所改變的只是其外部的表現(xiàn)形式。下面介紹一些常見的以自相似性為原理的分形圖形。 . Cantor 集 康托爾 ()在 1883 年構(gòu)造了如下的一類集合。選取一個歐氏長度為L0的直線段，將該線段三等分，去掉中間一段，剩下兩段。將剩下的兩段分別再三等分，各去掉中間一段，剩下四段。這樣的操作繼續(xù)下去，直至無窮，則可得到一個離散的點集，點數(shù)趨于無窮多，而歐氏長度趨于零。經(jīng)無限次操作，達到極限時所得到的離散點集稱之為 Cantor 集，如圖 所示。從連通性看，這個集合是非連通的。 圖 三分 Cantor 集 去掉中間三分之一的 Cantor 集，也稱為三分 Cantor 集，它是一種人們最了解，同時也是最容易構(gòu)造的分形，顯示出許多典型的分形特征。設(shè) E0 是閉區(qū)間[0， 1]， E1表示 E0除去中間 1/3 之后得到的集，即 E1包含 [0， 1/3]和 [2/3， 1]兩個區(qū)間。再分別去掉這兩個區(qū)間的中間 1/3而得到 E2，即 E 包含 [0， 1/9]、 [2/9，1/3]、 [2/3， 7/9]、 [8/9， 1]四個區(qū)間。按此種方法繼續(xù)下去，則 Ek是由 2k個 24 長度各為 3k的區(qū)間（線段）組成。 三分 Cantor 集 F 是由屬于所有 Ek當 k 趨于無窮時的極限，是一個不可數(shù)的無窮集。 按相似維數(shù)的計算公式，可得三分 Cantor 集的維數(shù)： 2lnD s ?? . Koch曲線 Koch 曲線是瑞典數(shù)學家科赫 ( Koch)在 1904 年首次提出的，其生成的原理如圖 所示。設(shè) E0是單位長度的直線段， E1是由 E0除去中間 1/3 的線段，而代之以底邊在被除去的線段上的等邊三角形的另兩條邊所得到的集，它包含四個線段。把同樣的過程應用到 E1的每個直線段而構(gòu)造出 E2，以此類推，于是 Ek是把 Ek1的 每個直線段中間 1/3 用等邊三角形的另外兩邊取代而得到的。當 k充分大，曲線 Ek和 Ek1只在精細的細節(jié)上不同，而當 k→∞ ,折線序列趨于極限曲線 F,稱 F 為三次 Koch 曲線。 從圖 的三次 Koch 曲線，按相似維數(shù)的計算公式，由于 N=4， r=1/3，可求得它的相似維數(shù)： 4lnD s ?? 這個數(shù)與 Koch 曲線大于一維（具有無限的長度）但小于二維（具有零面積）的結(jié)論是相一致的，另外應注意的事，它比 E0的歐氏維數(shù)（一維）要大。 由圖 可以清楚地看到， Koch 曲線每操作一次，曲線的歐 氏長度有規(guī)律地增加，計算表明 Ek的長度為 (4/3)k，令 k 趨于無窮，則 F的長度趨于無窮大，所以從測度的角度來說 Koch 曲線的 1維測度是無限大，它的 2 維測度是 0，因為 F在直觀上是曲線，在平面內(nèi)的面積為零，所以表示面積的 2維測度自然就等于 0。在這里，長度和面積對 F的形狀和大小都沒有提供很有效的描述。進一步的數(shù)學解析發(fā)現(xiàn)， Koch 曲線的 Hausdorff 測度，在 Dlog34 時，其測度為無限大，當Dlog34 時為 0， D=log34 為有限。 根據(jù) Hausdorff 維數(shù)的定義， Koch 曲線的 3ln4ln4lo g 3 ??HD ，即HD =，與相似維數(shù)相一致。 25 圖 Koch 曲線 Koch 曲線在許多方面的性質(zhì)與三分 Cantor 集列出的那些性質(zhì)類似，它由四個與總體相似的“四分之一”部分組成，但比例系數(shù)是 1/3。它在任何尺度下的不規(guī)則性反映了它的精細結(jié)構(gòu)，但這樣錯綜復雜的構(gòu)造卻出自于一個基本的簡單結(jié)構(gòu)。雖然稱 F為曲線是合理的，但它是如此不規(guī)則，以至于在傳統(tǒng)的意義下，它沒有任何切線。 對于三分 Koch 曲線的構(gòu)造原則還可以加以推廣，其中第一種推廣是改變等分數(shù) 目。例如，四次 Koch 曲線，其相似維數(shù)為： 8ln ??sD 另一種推廣，是將上述的直線段向二維歐氏平面推廣。例如，將一個等邊三角形四等分，再將中間的小等邊三角形改為向上凸起的三個全等的三角形，和原來中間的小三角形構(gòu)成一個正四面體。對該四面體無限次等分操作后，原來的等邊三角形成了具有相似結(jié)構(gòu)的不均勻地向上凸起的面。其相似維數(shù)為： 6ln ??sD 生成 Koch 曲線的算法如下： void Koch(x1,x2,y1,y2,n)//n 為遞歸次數(shù) { if (n=0) 26 {LineTo(AB)； } else { 圖 Koch 曲線原理圖 先計算 X1 坐標； //計算 X1， X2， X3，可根據(jù)數(shù)學法則 Koch(xa,yb,x1,y1,n1)； //xa,yb,x1,y1分別為 A 與 X1的坐標 計算 X2 的坐標； Koch(x1,y1,x2,y2,n1)； //x2,y2為 X2的坐標 計算 X3的坐標； Koch(x2,y2,x3,y3,n1)； //x3,y3為 X3的坐標 Koch(x3,y3,xb,yb,n1)； //xb,yb 為 B 的坐標 } } . Sierpinski 集 Cantor 集與 Koch 曲線的初始操作都是一個歐氏長度為 E 的直線段，二者的差別在于： Cantor 集是去掉中間的一段，而 Koch 曲線在去掉中間的一段后，還增加一些線段。在這一節(jié)中，我們將長度為 E的直線段推廣到歐氏平面上的規(guī)整幾何圖形，如等邊三角形和正方形。也可以推廣到三維歐氏空間中的規(guī)整幾何圖形，如正六面體和正四面體，等等。 首先將一個等邊三角形四等分，得到四個小等邊三角形，去掉中間的一個，保留它的三條邊。將剩下的三個小等邊三角形再分別進行四等分，并分別去掉中間的一個 ，保留它們的邊。重復操作直至無窮，就可以得到如圖 所示的圖形，人們稱這樣的集合為 Sierpinski 墊。該集合的面積是零，而線的歐氏長度趨于無窮大。因為 N=3,r=1/2，所以其相似維數(shù)為： 3ln ??sD 其次，將一個正方形九等分，去掉中間的一個，保留四條邊，剩下八個小正方形。將這八個小正方形再分別進行九等分，各自去掉中間的一個，保留它們的 27 邊。重復上述操作直至無窮，就可得到如圖 所示的圖形，人們稱這樣的集合為 Sierpinski 地毯。 圖 Sierpinski 墊 28 圖 Sierpinski 地毯 同樣地，該集合的面積趨于零，而線的歐氏長度趨于無窮大。一個原來規(guī)整的正方形，經(jīng)上述操作之后，成了千窗百孔。在這里， N=8， r=1/3，所以，其相似維數(shù)為： 8ln ??sD 對于所有的 Sierpinski 集，它們都有共同的特征： (1)它們都是經(jīng)典幾何無法描述的徒刑。在 Sierpinski 墊中，它的面積趨于零，而其周長趨于無窮大，因此它的維數(shù)只可能介于 1 和 2 之間； Sierpinski 海綿的體積趨于零，而其表面積卻趨于無窮大，所以它的 維數(shù)只能介于 2 和 3 之間。因此，它們常被稱為病態(tài)的幾何圖形，是一種“只有皮沒有肉”的幾何集合。 (2)它們都具有無窮多個自相似的內(nèi)部結(jié)構(gòu)。任何一個分割后的圖形經(jīng)適當放大后都是原來圖形的翻版。如令初始圖形為 E0，每操作一次后得到的集合依次 E1， E2，?， En 來表示，則Sierpinski 集合為： nn EE ???? 1 即由無窮多個閉集的交來構(gòu)成，從而 E也是閉集。 在復平面 C上，復數(shù)域的迭代具有非常奇妙，像在復平面 C上 ??? 2)( zzf 這樣的簡單 函數(shù)，對不同的λ值 (λ∈ C)，能生成各種形狀奇特的分形，這些集合通常稱為 Julia 集。如果根據(jù)不同的λ值對應的 Julia 集的連通性對參數(shù)λ進行分類，還可以在參數(shù)空間做出稱為 Mandelbrot 集的λ的點集，而且 Mandelbrot集局部與其上點對應的 Julia 集還有某種“相似性”。 對于復平面迭代產(chǎn)生的 Julia集、 Mandelbrot集的研究大大豐富了分形理論，也顯示了分形幾何在處理復雜圖形上的突出作用，并且為計算機圖像模擬開辟了一個廣闊的天地。下面就簡單介紹由復平面迭代產(chǎn)生的分形圖形。 29 . Julia 集 Julia 集是由法國數(shù)學家 Gaston Julia 和 Pierre Faton 在發(fā)展了復變函數(shù)迭代的基論后獲得的。 Julia 集由一個復變函數(shù) f的迭代生成。 一般地， Julia 集是動力系統(tǒng)中的斥子，通過對復平面上的解析函數(shù)的研究，可關(guān)于排斥集構(gòu)造的很多知識。為了說明斥子的定義，先看一下吸引子的定義。粗略一個吸引子就是一個集合并且使得附近的所有軌道都收斂到這個集合上。精確的定下： 設(shè) D 是 nR 的一個子集 (通常就是 nR 本身 )，并且設(shè) f: D→ D是一個連續(xù)映射，表示 f的 k次迭代。稱 D的子集 F為 f的吸引子，如果 F是一個閉集，并且在 f的下是不變的 (即 f(F)=f)，使得對包含 F 的一個開集 V 中的所有點 x， kf (x)到 F 的距 k趨于無窮大而趨于零。集 V稱為 F 的吸引域。 類似地，對一個閉不變子集 F，如果 F 附近（但不在 F 中）的所有點經(jīng)迭代后 F，那么 F 就稱為斥子。 在這里，一個迭代函數(shù)圖 { kf }就稱為一個離散的動力系統(tǒng)。吸引子和斥子可能是一個周期為 p的軌道。通常，如果 f有分 形吸引子或分形斥子 F，那么 f在 F 上質(zhì)表現(xiàn)為“混沌”的。 為了敘述方便，我們?nèi)?f: C→ C 為復系數(shù)的 n≥ 2 階的多項式nn zazaazf ???? ?110)( 注意到，如果 f 是拓廣的復平面 C∪ {∞ }上的有理函數(shù))()()()( zqzpzpzf ? (此處 p, q 都是式 )，只要稍微修改一下，一般理論仍然正確。若 f 為任一亞純函數(shù)（除去有限個外，在 C∪ {∞ }上是解析的），一般理論的大部分也是成立的。 Julia 集是將 C值固定，即 p 和 q保持為常數(shù)，讓 Z作為原始點通過迭代而生成新的 Z，以此循環(huán)，每選定一個 C值，就可以在復平面上生成一幅新的計算機圖形。其生成算法步驟如下： 第一步，固定參數(shù) C，即 p和 q的值為確定的，選定 minx ， miny ， maxx ， maxy和圖像顯示區(qū)域的長 a、寬 b 及最大迭代步數(shù) N，并選定一個用以判斷是否趨于無窮的較大的實數(shù) M。 30 第二步，令 )1()( m inm a x ??? axxdx ， )1()( m inm a x ??? byydy ，對顯示區(qū)域內(nèi) 的所有點，按序執(zhí)行下面的循環(huán)操作。 第三步，令 xdxx x *m in0 ?? ， ydyy y *m in0 ?? ，循環(huán)步數(shù) k 賦初值 0。 第四步，由上式的迭代公式，從 (kx ， ky )計算出 ( 1?kx ， 1?ky )，并令 k=k+1。 第五步，計算當前點的模 2 12 1 ?? ?? AA yxr ，判斷是否超過預設(shè)的值 M。如果 rM，則該點經(jīng)過迭代后發(fā)散，即趨向于無窮定常吸引子，此時根據(jù) k值將該點以一定的顏色顯示在屏幕上，并退出本次循環(huán)，進入下一個點的循環(huán)迭代；如果 r≤ M，且 kN，則返回第四步驟，繼續(xù)進行本次循環(huán)；如果 r≤ M，且 k=N，則選擇某一特定的顏色，將該點顯示在屏幕上，并結(jié)束本次循環(huán)，進入下一點的循環(huán)迭代。 . Mandelbrot 集 Mandelbrot集是由分形理論的創(chuàng)始人美國科學家 Mandelbrot開發(fā)的經(jīng)典分形圖形， Mandelbrot 集是對二次多項式 czzfc ?? 2)( 在參數(shù)平面（參數(shù) c 所在平面為參數(shù)平面）上進行迭代產(chǎn)生的圖形。由于在參數(shù)空間中僅僅考慮 c 值的影響，這就有了如下 Mandelbrot 集的定義： Mandelbrot 集為使 f c 的 Julia 集連通的參數(shù) c 的集，即： M={c∈ C:J(f c)是連通的 } () M 看來似乎與 J(f c)的一個相當特殊的性質(zhì)有關(guān)，事實上， M 包含了關(guān)于 Julia集構(gòu)造的無窮信息。 由于定義 ()不適合計算的目的，下面將給出一個等價定義，它在確定參數(shù)c 是否在 M 中，及在研究 M 的非常復雜的結(jié)構(gòu)中十分有用。定義如下 : M={c∈ C: {fck