GIS算法-分形

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

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

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

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

5、函數(shù)中所用的參數(shù)為：xa, ya, xb, yb :線段的起點和終點坐標；a : 線段的方向角；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 曲線的維數(shù)曲線的維數(shù)一個幾何對象的維數(shù)還可以從測量的角度來定義：ln(N) / ln(S)其中：維數(shù)縮小系數(shù)的倒數(shù)每步的分段數(shù)在Koch曲線中，S3 ( 縮小系數(shù)是1/3 )；4。所以Koch曲線的維數(shù)為：ln(4) / ln(3)依據(jù) Koch 曲線的生成原理，設(shè)計不同的生成元，便可以構(gòu)畫出多種多樣的分形曲線。*.Dragon 曲線曲線（）（）Dragon 曲線的生成規(guī)則曲線的生成規(guī)則變化的起始是一條原始直線段。第一步是將該直線段由中間點隆起，使其變成一個等腰直角三角形的兩腰。接下去再分別對兩

8、腰作和前面同樣的變化，如此不斷進行。（圖例）不難看出，Dragon 曲線完全是由長度相等的線段組成，且兩兩相交處都成直角。另外，每次分形后，曲線的長度是原來曲線長度的 2 倍。因此，經(jīng)過無數(shù)次變化，Dragon 曲線也將變成無限長。這一點正符合分形曲線的特點。 下面我們來分析 Dragon 曲線的生成規(guī)則：假如我們從線段 1 開始，順著曲線前進，那么在這個過程中，每到一個線段末端拐角處，就必須向左或向右轉(zhuǎn)90 。于是，待要解決的關(guā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 。并且對于第 i 段線 段，以T ( i )來表示其轉(zhuǎn)向代碼。則 對于上圖有：T ( 1 )=1 T ( 5 )=1T ( 2 )=1 T ( 6 )=3T ( 3 )=3 T ( 7 )=3T ( 4 )=1因此，對于第 i 段線段末了的轉(zhuǎn)角:A ( i )=T ( i )*90 。因為向右轉(zhuǎn)90 就等于向左轉(zhuǎn)270 。對于 i 的任意整數(shù)值，其T ( i )的值可由下式確定：T ( i )=T ( i / 2 ) ; 對于 i 是偶數(shù)T ( i )=T ( i % 4 ) ; 對于 i 是奇數(shù)( 2 )生成生成 Dragon 曲線的程序曲線的

10、程序Dragon 曲線可以用分步判別繪線的方法繪制出來。其主要的程序段如下：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曲線也是不自相交的，但是在圖形上它沒有如 Koch 曲線那樣可明顯看出。但只要把曲線中 90的拐角改畫一個小的倒角，情況就清楚了。（看運行圖例）.其他分形實例其他分形實例用 分形 可以構(gòu)造很多自然界的形體，下面是幾種常見的例子：（）分枝（）分枝 Koch 曲線和Dragon曲線都是連續(xù)的，分枝結(jié)構(gòu)是不連續(xù)的，它的生成元類似于圖例所示。其生成元描述為：F : F L F F R F F * （）粒子模型的圖例（）粒子模型的圖例 * （）巖石（）巖石這種分形由平面多邊形（如三角形、四邊形等）用隨機插值法迭代生成，可模擬山巒。如圖所示：Z取中點在邊直線上在中點上加一個隨機法向量以四邊形為例：分割原始四邊形為四個小四邊