GIS算法-分形

1、分分 形形 造造 型型一、分形的概念一、分形的概念分形是最近二十多年來(lái)發(fā)展起來(lái)的新學(xué)科。分形的原文是 Fractals，是由著名數(shù)學(xué)家 B . Mandelbrot 于 1975 年用拉丁詞根構(gòu)造的單詞，他創(chuàng)立了獨(dú)立于歐幾里德幾何學(xué)之外的數(shù)學(xué)方法：分形幾何。自然界中存在著不可勝數(shù)的不規(guī)則形 體。多少年來(lái)，人們都是用傳統(tǒng)的幾何方法對(duì)它們進(jìn)行描述，采用的主要手段是用規(guī)則形體去逼近。這種用規(guī)則形體去描述不規(guī)則形體所得到的結(jié)果，與現(xiàn)實(shí)是有很大差距的，并且這種方法需要大量的數(shù)據(jù)，所以有時(shí)甚至是不可能的。其實(shí)，當(dāng)用計(jì)算機(jī)模擬自然景物時(shí)， 最主要的是所生成的對(duì)象確實(shí)使人感 受到是預(yù)期的那一類(lèi)，而不必非是某

2、個(gè)具體的個(gè)體。因此，為此目的，不 必使用大量的數(shù)據(jù)。是很自然的。 分形幾何學(xué)的創(chuàng)立，為自然景物的描 述和計(jì)算機(jī)模擬提供了強(qiáng)有力的數(shù)學(xué) 工具。正因?yàn)槿绱?，所以人們說(shuō)，分 形是大自然的幾何學(xué)。分形具有下面列出的典型幾何性質(zhì)分形具有下面列出的典型幾何性質(zhì)（）分形集都具有任意小尺度下的比例細(xì)節(jié)，或者說(shuō)它具有精細(xì)的結(jié)構(gòu)。（）分形集不能用傳統(tǒng)的幾何語(yǔ)言來(lái)描述，它既不是滿(mǎn)足于某些條件的點(diǎn)的軌跡，也不是某些簡(jiǎn)單方程的解集。（）分形集具有某種自相似的形式，可能是近似的或統(tǒng)計(jì)的自相似。 （）一般說(shuō)來(lái)，分形集的維數(shù)是一個(gè)分?jǐn)?shù)，所以分形也稱(chēng)為分?jǐn)?shù)維；（）在大多數(shù)令人感興趣的情形下，分形集由非常簡(jiǎn)單的方法定義，可以用變

3、換的迭代產(chǎn)生。分形的四種構(gòu)成方法分形的四種構(gòu)成方法（）基于系統(tǒng)的分形模型（）迭代函數(shù)系統(tǒng)模型（）粒子系統(tǒng)模型（）隨機(jī)插值模型二、典型的分形模型二、典型的分形模型 .Koch 曲線(xiàn)曲線(xiàn)( 1 ) Koch 曲線(xiàn)的生成規(guī)則曲線(xiàn)的生成規(guī)則Koch 曲線(xiàn)是 Von Koch 于1904年第一次描述的。它的構(gòu)造是：迭代初始把原線(xiàn)段去掉中間的三分之一，代之以底邊在被去線(xiàn)段上的等邊三角形的兩腰；以后每一步的迭代都是這樣的重復(fù)。（圖例）從以上過(guò)程可以清楚地看出，Koch曲線(xiàn)（其它分形集也是如此）可以由簡(jiǎn)單的 圖，稱(chēng)為 生成元 ，迭代產(chǎn)生。在這里，Koch曲線(xiàn)的生成元是：在這里，假如我們約定好記號(hào)，就可以把Ko

4、ch曲線(xiàn)的生成元的構(gòu)造用一個(gè)字符串符號(hào)表示出來(lái)。設(shè)：F從當(dāng)前點(diǎn)開(kāi)始，向前移動(dòng)一距離dL向左（逆時(shí)針）轉(zhuǎn)一定角R向右（順時(shí)針）轉(zhuǎn)一定角則Koch曲線(xiàn)的生成元可表示為：T F L F R R F L F （ 60）曲線(xiàn)由把每一折線(xiàn)段反復(fù)迭代成縮小比例的三分之一的生成元而成。即字符串T F L F R R F L F 中的每一個(gè) F 又是字符串 T 本身。而每次迭代后，生成的曲線(xiàn)長(zhǎng)是原來(lái)曲線(xiàn)長(zhǎng)的三分之四倍?？梢?jiàn)，無(wú)數(shù)次迭代后，Koch 曲線(xiàn)將變得具有無(wú)限長(zhǎng)度。并且，Koch 曲線(xiàn)是永遠(yuǎn)不自相交的。 ( 2 )生成生成Koch 曲線(xiàn)的程序曲線(xiàn)的程序函數(shù) side( )，用于繪制Koch 曲線(xiàn)的生成元，

5、函數(shù)中所用的參數(shù)為：xa, ya, xb, yb :線(xiàn)段的起點(diǎn)和終點(diǎn)坐標(biāo)；a : 線(xiàn)段的方向角；n : 迭代次數(shù)（遞歸深度）。void side ( xa, ya, xb, yb, a, n ) int n ; float xa, ya, xb, yb, a ; float x1, y1, x2, y2, x3, y3, dl, a1, a2 ; int xs, ys, xe, ye ; if (n=0) xs=(int)(xa+0.5) ; ys=(int)(ya+0.5) ; xe=(int)(xb+0.5) ; ye=(int)(yb+0.5) ; moveto(xs,480-ys) ;

6、 lineto(xe,480-ye); else dl=sqrt(xb-xa)*(xb-xa)+(yb-ya)*(yb-ya) / 3. ; x1=xa+(xb-xa) / 3. ; y1=ya+(yb-ya) / 3. ; side(xa, ya, x1, y1, a, n-1) ; a1=a+AF ; x2=x1+dl*cos(a1) ; y2=y1+dl*sin(a1) ; side(x1, y1, x2, y2, a1, n-1) ;a2=a1-2.*AF ; x3=x2+dl*cos(a2) ; y3=y2+dl*sin(a2) ; side(x2, y2, x3, y3, a2,

7、n-1) ; side(x3, y3, xb, yb, a, n-1) ; * ( 3 )Koch 曲線(xiàn)的維數(shù)曲線(xiàn)的維數(shù)一個(gè)幾何對(duì)象的維數(shù)還可以從測(cè)量的角度來(lái)定義：ln(N) / ln(S)其中：維數(shù)縮小系數(shù)的倒數(shù)每步的分段數(shù)在Koch曲線(xiàn)中，S3 ( 縮小系數(shù)是1/3 )；4。所以Koch曲線(xiàn)的維數(shù)為：ln(4) / ln(3)依據(jù) Koch 曲線(xiàn)的生成原理，設(shè)計(jì)不同的生成元，便可以構(gòu)畫(huà)出多種多樣的分形曲線(xiàn)。*.Dragon 曲線(xiàn)曲線(xiàn)（）（）Dragon 曲線(xiàn)的生成規(guī)則曲線(xiàn)的生成規(guī)則變化的起始是一條原始直線(xiàn)段。第一步是將該直線(xiàn)段由中間點(diǎn)隆起，使其變成一個(gè)等腰直角三角形的兩腰。接下去再分別對(duì)兩

8、腰作和前面同樣的變化，如此不斷進(jìn)行。（圖例）不難看出，Dragon 曲線(xiàn)完全是由長(zhǎng)度相等的線(xiàn)段組成，且兩兩相交處都成直角。另外，每次分形后，曲線(xiàn)的長(zhǎng)度是原來(lái)曲線(xiàn)長(zhǎng)度的 2 倍。因此，經(jīng)過(guò)無(wú)數(shù)次變化，Dragon 曲線(xiàn)也將變成無(wú)限長(zhǎng)。這一點(diǎn)正符合分形曲線(xiàn)的特點(diǎn)。 下面我們來(lái)分析 Dragon 曲線(xiàn)的生成規(guī)則：假如我們從線(xiàn)段 1 開(kāi)始，順著曲線(xiàn)前進(jìn)，那么在這個(gè)過(guò)程中，每到一個(gè)線(xiàn)段末端拐角處，就必須向左或向右轉(zhuǎn)90 。于是，待要解決的關(guān)鍵問(wèn)題就是如何確定是向左轉(zhuǎn)還是向右轉(zhuǎn)。T(1)= 90T(2)= 90T(3)= -90T(4)= 90T(5)= 90T(6)= -90T(7)= -90如果用代碼

9、 1 表示向左轉(zhuǎn)90 ，用 3 表示向右轉(zhuǎn)90 。并且對(duì)于第 i 段線(xiàn) 段，以T ( i )來(lái)表示其轉(zhuǎn)向代碼。則 對(duì)于上圖有：T ( 1 )=1 T ( 5 )=1T ( 2 )=1 T ( 6 )=3T ( 3 )=3 T ( 7 )=3T ( 4 )=1因此，對(duì)于第 i 段線(xiàn)段末了的轉(zhuǎn)角:A ( i )=T ( i )*90 。因?yàn)橄蛴肄D(zhuǎn)90 就等于向左轉(zhuǎn)270 。對(duì)于 i 的任意整數(shù)值，其T ( i )的值可由下式確定：T ( i )=T ( i / 2 ) ; 對(duì)于 i 是偶數(shù)T ( i )=T ( i % 4 ) ; 對(duì)于 i 是奇數(shù)( 2 )生成生成 Dragon 曲線(xiàn)的程序曲線(xiàn)的

10、程序Dragon 曲線(xiàn)可以用分步判別繪線(xiàn)的方法繪制出來(lái)。其主要的程序段如下：for ( i=1; i1 ;j=j % 4 ;a=(a+j) % 4 ;x1= x1+d*cos( a*PI ) ; y1= y1- d*sin( a*PI ) ;x=(int)(x1+0.5) ; y=(int)(y1+0.5) ;lineto( x , y ) ;*同樣，Dragon曲線(xiàn)也是不自相交的，但是在圖形上它沒(méi)有如 Koch 曲線(xiàn)那樣可明顯看出。但只要把曲線(xiàn)中 90的拐角改畫(huà)一個(gè)小的倒角，情況就清楚了。（看運(yùn)行圖例）.其他分形實(shí)例其他分形實(shí)例用 分形 可以構(gòu)造很多自然界的形體，下面是幾種常見(jiàn)的例子：（）分枝（）分枝 Koch 曲線(xiàn)和Dragon曲線(xiàn)都是連續(xù)的，分枝結(jié)構(gòu)是不連續(xù)的，它的生成元類(lèi)似于圖例所示。其生成元描述為：F : F L F F R F F * （）粒子模型的圖例（）粒子模型的圖例 * （）巖石（）巖石這種分形由平面多邊形（如三角形、四邊形等）用隨機(jī)插值法迭代生成，可模擬山巒。如圖所示：Z取中點(diǎn)在邊直線(xiàn)上在中點(diǎn)上加一個(gè)隨機(jī)法向量以四邊形為例：分割原始四邊形為四個(gè)小四邊