計(jì)算機(jī)圖形學(xué)之分形幾何

1、8.18.1分形和分維分形和分維 真實(shí)的世界并不規(guī)則，閃電不是直線，海真實(shí)的世界并不規(guī)則，閃電不是直線，海岸線不是弧線，云團(tuán)不是球體，山巒也不是錐岸線不是弧線，云團(tuán)不是球體，山巒也不是錐體。自然界的許多對(duì)象是如此不規(guī)則和支離破體。自然界的許多對(duì)象是如此不規(guī)則和支離破碎，以致歐氏幾何學(xué)不能真實(shí)有效地再現(xiàn)大自碎，以致歐氏幾何學(xué)不能真實(shí)有效地再現(xiàn)大自然。然。 為了再現(xiàn)真實(shí)世界，必須選擇新的工具，為了再現(xiàn)真實(shí)世界，必須選擇新的工具，分形幾何學(xué)應(yīng)運(yùn)而生。分形幾何是以非規(guī)則物分形幾何學(xué)應(yīng)運(yùn)而生。分形幾何是以非規(guī)則物體為研究對(duì)象的幾何學(xué)。由于閃電、海岸線、體為研究對(duì)象的幾何學(xué)。由于閃電、海岸線、云團(tuán)、山巒、

2、海浪、野草、森林、火光等非規(guī)云團(tuán)、山巒、海浪、野草、森林、火光等非規(guī)則物體在自然界里比比皆是，因此分形幾何學(xué)則物體在自然界里比比皆是，因此分形幾何學(xué)又被稱為描述大自然的幾何學(xué)。又被稱為描述大自然的幾何學(xué)。 分形山n8.1.1 8.1.1 分形的誕生分形的誕生 n8.1.2 8.1.2 分形的基本特征分形的基本特征n8.1.3 8.1.3 分形的定義分形的定義 n8.1.4 8.1.4 分形維數(shù)的定義分形維數(shù)的定義 8.1.1 8.1.1 分形的誕生分形的誕生 分形（分形（FractalFractal）這個(gè)詞，是由美籍法國(guó)）這個(gè)詞，是由美籍法國(guó)數(shù)學(xué)家曼德?tīng)柌剂_特（數(shù)學(xué)家曼德?tīng)柌剂_特（Benoit

3、 Benoit B.MandelbrotB.Mandelbrot）自己創(chuàng)造出來(lái)的，此詞來(lái)源于拉丁文自己創(chuàng)造出來(lái)的，此詞來(lái)源于拉丁文fractusfractus，意為不規(guī)則、支離破碎。意為不規(guī)則、支離破碎。19671967年曼德?tīng)柌剂_特年曼德?tīng)柌剂_特在美國(guó)在美國(guó)科學(xué)科學(xué)雜志上發(fā)表了劃時(shí)代的論文雜志上發(fā)表了劃時(shí)代的論文英國(guó)海岸線有多長(zhǎng)？統(tǒng)計(jì)自相似與分?jǐn)?shù)維英國(guó)海岸線有多長(zhǎng)？統(tǒng)計(jì)自相似與分?jǐn)?shù)維，成為其分形思想萌芽的重要標(biāo)志。成為其分形思想萌芽的重要標(biāo)志。19731973年，在年，在法蘭西學(xué)院講學(xué)期間，曼德?tīng)柌剂_特提出了分法蘭西學(xué)院講學(xué)期間，曼德?tīng)柌剂_特提出了分形幾何學(xué)的整體思想，并認(rèn)為分?jǐn)?shù)維是個(gè)可用形

4、幾何學(xué)的整體思想，并認(rèn)為分?jǐn)?shù)維是個(gè)可用于研究許多物理現(xiàn)象的有力工具。于研究許多物理現(xiàn)象的有力工具。19821982年曼德年曼德?tīng)柌剂_特出版了爾布羅特出版了大自然的分形幾何學(xué)大自然的分形幾何學(xué)，引，引起了學(xué)術(shù)界的廣泛重視，曼德?tīng)柌剂_特也因此起了學(xué)術(shù)界的廣泛重視，曼德?tīng)柌剂_特也因此一舉成名。一舉成名。 英國(guó)的海岸線 蕨類植物葉的自相似性8.1.2 8.1.2 分形的基本特征分形的基本特征 1.1.自相似性自相似性 自相似性是指局部與整體相似的性自相似性是指局部與整體相似的性質(zhì)。質(zhì)。在自然界中，具有自相似性的物體在自然界中，具有自相似性的物體比比皆是，起伏的山巒中一座座山峰和比比皆是，起伏的山巒中一

5、座座山峰和整體山脈，彎曲的河流中一個(gè)個(gè)支流和整體山脈，彎曲的河流中一個(gè)個(gè)支流和整體河川，茂密的樹(shù)木上的一條條樹(shù)杈整體河川，茂密的樹(shù)木上的一條條樹(shù)杈和整體樹(shù)木等，均具有自相似性，如圖和整體樹(shù)木等，均具有自相似性，如圖8-38-3所示的是蕨類植物葉子上的細(xì)葉和整所示的是蕨類植物葉子上的細(xì)葉和整體葉子的相似性。體葉子的相似性。 2.2.無(wú)標(biāo)度性無(wú)標(biāo)度性 標(biāo)度是計(jì)量單位的刻度。比如標(biāo)度是計(jì)量單位的刻度。比如長(zhǎng)度的標(biāo)度是米；重量的標(biāo)度是公長(zhǎng)度的標(biāo)度是米；重量的標(biāo)度是公斤；面積的標(biāo)度是平方米等。對(duì)歐斤；面積的標(biāo)度是平方米等。對(duì)歐氏幾何學(xué)內(nèi)的不同形體，可以選擇氏幾何學(xué)內(nèi)的不同形體，可以選擇不同的標(biāo)度去度量。

6、例如，直線是不同的標(biāo)度去度量。例如，直線是多長(zhǎng)，面積是多大，體積是多少。多長(zhǎng)，面積是多大，體積是多少。自然界中很多的物體具有特征長(zhǎng)度，自然界中很多的物體具有特征長(zhǎng)度，如人有高度、山有海拔等等。如人有高度、山有海拔等等。 8.1.3 8.1.3 分形的定義分形的定義 n一般認(rèn)為，滿足下列條件的圖形稱為分形集：一般認(rèn)為，滿足下列條件的圖形稱為分形集：n分形集具有任意尺度下的比例細(xì)節(jié)，或者說(shuō)分形集具有任意尺度下的比例細(xì)節(jié)，或者說(shuō)具有精細(xì)結(jié)構(gòu)；具有精細(xì)結(jié)構(gòu)；n分形集是不規(guī)則的，以致于不能用傳統(tǒng)的幾分形集是不規(guī)則的，以致于不能用傳統(tǒng)的幾何語(yǔ)言來(lái)描述。何語(yǔ)言來(lái)描述。n分形集通常具有某種自相似性，或許是近似

7、分形集通常具有某種自相似性，或許是近似的或許是統(tǒng)計(jì)意義下的自相似。的或許是統(tǒng)計(jì)意義下的自相似。n分形集在某種方式下定義的分形集在某種方式下定義的“分維數(shù)分維數(shù)”一般一般大于它的拓?fù)渚S數(shù)。大于它的拓?fù)渚S數(shù)。n分形集的定義常常是非常簡(jiǎn)單的，或許是遞分形集的定義常常是非常簡(jiǎn)單的，或許是遞歸的。歸的。 n 維數(shù)是幾何對(duì)象的一個(gè)重要特征量，它是歐氏幾維數(shù)是幾何對(duì)象的一個(gè)重要特征量，它是歐氏幾何學(xué)描述點(diǎn)的位置所需的獨(dú)立坐標(biāo)數(shù)目。為了定量地何學(xué)描述點(diǎn)的位置所需的獨(dú)立坐標(biāo)數(shù)目。為了定量地刻畫分形，引入了分?jǐn)?shù)維數(shù)的概念。分?jǐn)?shù)維數(shù)與歐氏刻畫分形，引入了分?jǐn)?shù)維數(shù)的概念。分?jǐn)?shù)維數(shù)與歐氏幾何學(xué)中的整數(shù)維數(shù)相對(duì)應(yīng)。幾何學(xué)

8、中的整數(shù)維數(shù)相對(duì)應(yīng)。 n分形理論認(rèn)為，維數(shù)中可以包含有小數(shù)。把分?jǐn)?shù)維數(shù)分形理論認(rèn)為，維數(shù)中可以包含有小數(shù)。把分?jǐn)?shù)維數(shù)記為記為D D，一般稱為分?jǐn)?shù)維或分維。，一般稱為分?jǐn)?shù)維或分維。n分維的計(jì)算公式為：分維的計(jì)算公式為： n其中其中D D代表分維，代表分維，N N為和整體自相似的局部形體個(gè)數(shù)，為和整體自相似的局部形體個(gè)數(shù)，S S為相似比，等于整體和局部之比。為相似比，等于整體和局部之比。n注：分維的計(jì)算結(jié)果是兩個(gè)參數(shù)的對(duì)數(shù)值之比，所以注：分維的計(jì)算結(jié)果是兩個(gè)參數(shù)的對(duì)數(shù)值之比，所以分維的計(jì)算結(jié)果不一定是整數(shù)。分維的計(jì)算結(jié)果不一定是整數(shù)。SNDlnlnn對(duì)于直線：對(duì)于直線：n 將一直線段二等分，將一直

9、線段二等分， 則則N=2N=2，S=2S=2，即即2=22=21 1，所以，分維，所以，分維D=1 D=1 n對(duì)于平面：對(duì)于平面： n 將正方形四等分，則將正方形四等分，則N=4N=4，S=2S=2，即，即4=24=22 2，所以，分維，所以，分維D=2 D=2 n對(duì)于立體：對(duì)于立體：n 將立方體八等分，將立方體八等分， N=8N=8，S=2S=2，即，即8=238=23，所以，分維，所以，分維D=3 D=3 n對(duì)于典型的分形曲線，例如對(duì)于典型的分形曲線，例如KochKoch曲線，構(gòu)成方法如下：曲線，構(gòu)成方法如下：n 取一直線段，將其三等分，保留兩端的兩段，將中間取一直線段，將其三等分，保留兩

10、端的兩段，將中間一段拉起為等邊三角形的兩條邊。一段拉起為等邊三角形的兩條邊。N=4N=4，S=3S=3，分維，分維D=ln4/ln3=1.26186D=ln4/ln3=1.26186。從圖。從圖8-78-7中中n n5 5的遞歸圖形中可以看的遞歸圖形中可以看出出kochkoch曲線點(diǎn)點(diǎn)連續(xù)，但點(diǎn)點(diǎn)不可導(dǎo)，屬于病態(tài)曲線；曲線點(diǎn)點(diǎn)連續(xù)，但點(diǎn)點(diǎn)不可導(dǎo)，屬于病態(tài)曲線；kochkoch曲線局部和整體相似，具有自相似性。因此可以使用曲線局部和整體相似，具有自相似性。因此可以使用kochkoch曲線來(lái)模擬海岸線。曲線來(lái)模擬海岸線。8.28.2遞歸模型遞歸模型 分形圖形的傳統(tǒng)實(shí)現(xiàn)模型是遞歸模型。在調(diào)用一個(gè)函分

11、形圖形的傳統(tǒng)實(shí)現(xiàn)模型是遞歸模型。在調(diào)用一個(gè)函數(shù)的過(guò)程中，直接或間接地調(diào)用函數(shù)自身，稱為遞歸調(diào)用。數(shù)的過(guò)程中，直接或間接地調(diào)用函數(shù)自身，稱為遞歸調(diào)用。例如例如n n！可以采用遞歸模型實(shí)現(xiàn)。即！可以采用遞歸模型實(shí)現(xiàn)。即5 5！5 54 4！，而！，而4 4！4 43 3！，！，1 1！1 1，遞歸公式表示如下：，遞歸公式表示如下：階乘遞歸子函數(shù)如下：階乘遞歸子函數(shù)如下：Long Long fac(intfac(int n) n) long f; long f; If (n=0 | 1 If (n=0 | 1） f=1;f=1; Else f=fac(n-1) Else f=fac(n-1)* *n

12、;n; Return f; Return f; ) 1()!1() 1 , 0(1!nnnnnn8.2.1 Cantor8.2.1 Cantor集集n8.2.2 Koch8.2.2 Koch曲線曲線 n8.2.3 8.2.3 PeanoPeano-Hilbert-Hilbert曲線曲線 n8.2.4 8.2.4 SierpinskiSierpinski墊片、地毯和墊片、地毯和海綿海綿n8.2.5 C8.2.5 C字曲線字曲線n8.2.6 8.2.6 CaleyCaley樹(shù)樹(shù)8.28.2遞歸模型遞歸模型8.2.1 Cantor8.2.1 Cantor集集 n集合論的創(chuàng)始人康托（集合論的創(chuàng)始人康托

13、（G.CantorG.Cantor，1845184519181918）在）在18831883年曾構(gòu)造了年曾構(gòu)造了一種三等分一種三等分CantorCantor集，其幾何表示如下：集，其幾何表示如下：n生成規(guī)則：取一段長(zhǎng)度為生成規(guī)則：取一段長(zhǎng)度為L(zhǎng)0L0的直線段，將其三等分，保留兩端的線的直線段，將其三等分，保留兩端的線段，將中間一段拋棄，如圖段，將中間一段拋棄，如圖8-98-9的的n n1 1的操作；再將剩下的兩段直的操作；再將剩下的兩段直線分別三等分，然后將其中間一段拋棄，如圖線分別三等分，然后將其中間一段拋棄，如圖8-98-9的的n n2 2的操作；的操作；依此類推，便形成了無(wú)數(shù)個(gè)塵埃似的散

14、點(diǎn)，所以依此類推，便形成了無(wú)數(shù)個(gè)塵埃似的散點(diǎn)，所以cantorcantor三分集也稱三分集也稱為為cantorcantor灰塵?；覊m。n“病態(tài)病態(tài)”原因：數(shù)目無(wú)窮多，但長(zhǎng)度趨近于零。原因：數(shù)目無(wú)窮多，但長(zhǎng)度趨近于零。n分形維數(shù)：分形維數(shù)：D Dln2/ln3=0.6309ln2/ln3=0.6309。 nCantorCantor的生成元：的生成元：n這些點(diǎn)之間的幾何關(guān)系為這些點(diǎn)之間的幾何關(guān)系為xxxxxxyyxxyyba2(ba )ca,ca ,da,da33 n19041904年，瑞典數(shù)學(xué)家科和（年，瑞典數(shù)學(xué)家科和（KochKoch，1870187019241924）發(fā)現(xiàn)一種）發(fā)現(xiàn)一種曲線，

15、其幾何表示如下：曲線，其幾何表示如下：n生成規(guī)則：取一段長(zhǎng)度為生成規(guī)則：取一段長(zhǎng)度為L(zhǎng)0L0的直線段，將其三等分，保留的直線段，將其三等分，保留兩端的線段，將中間一段改換成夾角為兩端的線段，將中間一段改換成夾角為6060的兩個(gè)的兩個(gè)L0/3L0/3等等長(zhǎng)直線段；將長(zhǎng)度為長(zhǎng)直線段；將長(zhǎng)度為L(zhǎng)0/3L0/3的的4 4個(gè)直線段分別三等分，并將個(gè)直線段分別三等分，并將它們中間的一段改換成夾角為它們中間的一段改換成夾角為6060的兩個(gè)的兩個(gè)L0/9L0/9等長(zhǎng)直線段。等長(zhǎng)直線段。依此類推，便得到具有自相似結(jié)構(gòu)的折線。如果在等邊三依此類推，便得到具有自相似結(jié)構(gòu)的折線。如果在等邊三角形上按上述規(guī)則在每邊的中

16、間各凸起一個(gè)小三角形，這角形上按上述規(guī)則在每邊的中間各凸起一個(gè)小三角形，這樣一直進(jìn)行下去，則曲線形狀近似為似一朵雪花，稱為樣一直進(jìn)行下去，則曲線形狀近似為似一朵雪花，稱為KochKoch雪花。雪花。 理論上可以證明這種不斷構(gòu)造的雪理論上可以證明這種不斷構(gòu)造的雪花周長(zhǎng)是無(wú)窮的，但其面積卻是有限的，花周長(zhǎng)是無(wú)窮的，但其面積卻是有限的，這和傳統(tǒng)的數(shù)學(xué)觀念是不相符的，采用這和傳統(tǒng)的數(shù)學(xué)觀念是不相符的，采用周長(zhǎng)和面積都無(wú)法刻劃出這種雪花的特周長(zhǎng)和面積都無(wú)法刻劃出這種雪花的特點(diǎn)，歐氏幾何學(xué)對(duì)描述這種雪花無(wú)能為點(diǎn)，歐氏幾何學(xué)對(duì)描述這種雪花無(wú)能為力。力。 “ “病態(tài)病態(tài)”原因：處處連續(xù)，處處不可導(dǎo)。原因：處處

17、連續(xù)，處處不可導(dǎo)。 分形維數(shù)：分形維數(shù)：D=ln4/ln3=1.26186D=ln4/ln3=1.26186。 生成元：生成元：kochkoch曲線是著名的分形曲線，具有自相似性。其曲線是著名的分形曲線，具有自相似性。其中生成元是圖中生成元是圖8-128-12所示的圖形。生成元的所示的圖形。生成元的第一第一段直線段和第二段直線段和第二段直線段之間的夾角可以為任意角度（段直線段之間的夾角可以為任意角度（0 090MoreMore”按鈕，可以展開(kāi)對(duì)話框輸入相按鈕，可以展開(kāi)對(duì)話框輸入相關(guān)參數(shù)，如圖關(guān)參數(shù)，如圖8-618-61所示。單擊所示。單擊“OKOK”按鈕則按鈕則繪制曲線的初始狀態(tài)，單擊圖繪制曲

18、線的初始狀態(tài)，單擊圖8-628-62所示的工所示的工具條按鈕具條按鈕“”和和“調(diào)節(jié)遞歸深度，動(dòng)態(tài)演示分形圖形變化過(guò)程。調(diào)節(jié)遞歸深度，動(dòng)態(tài)演示分形圖形變化過(guò)程。使用該系統(tǒng)繪制的使用該系統(tǒng)繪制的C C字曲線如圖字曲線如圖8-638-63所示。所示?！?圖圖8-59 8-59 曲線匯總曲線匯總 圖圖8 8-60 C-60 C字曲線對(duì)話框?qū)υ捒蜃智€對(duì)話框?qū)υ捒?圖圖8 8-61 C-61 C字曲線對(duì)話框展開(kāi)形式字曲線對(duì)話框展開(kāi)形式 圖圖8-62 8-62 “后退后退”和和“前進(jìn)前進(jìn)”按鈕按鈕 圖圖8 8-63 C-63 C字曲線字曲線8.8.已知單規(guī)則已知單規(guī)則L-L-系統(tǒng)，字母表為為系統(tǒng)，字母表為

19、為F F，初始字母為初始字母為F F，生成規(guī)則為：，生成規(guī)則為：FFFFFFFFFF，請(qǐng)編程繪制圖請(qǐng)編程繪制圖8-648-64所示的所示的“小草小草”。圖圖8-64 8-64 第第8 8題題n n6 6的小草的小草 9.9.已知多規(guī)則已知多規(guī)則L-L-系統(tǒng)，字母表為系統(tǒng)，字母表為F F，X X，Y Y，初，初始字母為始字母為Y Y，生成規(guī)則，生成規(guī)則1 1為：為：YYFXYYFXYFYYFYYFYYFY，生成規(guī)則，生成規(guī)則2 2為：為：XFXFXFXF，X X和和Y Y只進(jìn)行字符串的替換，不參與繪圖，只根據(jù)只進(jìn)行字符串的替換，不參與繪圖，只根據(jù)F F繪圖。繪圖。請(qǐng)編程繪制圖請(qǐng)編程繪制圖8-658-65所示的所示的“搖曳的小草搖曳的小草”。圖圖8-65 8-65 第第9 9題題n n6 6搖曳的小草搖曳的小草 10.10.請(qǐng)推導(dǎo)出表請(qǐng)推導(dǎo)出表8-48-4的的SierpinskiSierpinski地毯的地毯的IFSIFS碼，碼，并編程繪制如圖并編程繪制如圖8-668-66所示的所示的SierpinskiSierpinski地毯。地毯。圖圖8-6