基于分形算法的仿真系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

鄒麗萍

（國(guó)電南瑞科技股份有限公司 江蘇 南京210061）

基于分形算法的仿真系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

鄒麗萍

（國(guó)電南瑞科技股份有限公司 江蘇 南京210061）

分形理論是非線(xiàn)性科學(xué)的三大理論前沿之一，迄今為止尚未出現(xiàn)比分形幾何學(xué)描述自然形態(tài)更好的幾何學(xué)，因此分形在眾多領(lǐng)域應(yīng)用廣泛，但是分形算法具有較高的理論深度，使傳統(tǒng)的理論教學(xué)顯得捉襟見(jiàn)肘。本文基于Visual Studio 2005實(shí)現(xiàn)了典型分形算法的計(jì)算機(jī)模擬，并提供一定的交互功能。結(jié)果表明，該平臺(tái)為師生研究分形算法提供理論背景和實(shí)驗(yàn)平臺(tái)，并對(duì)提高教育教學(xué)質(zhì)量起到明顯的推動(dòng)作用。

分形算法；仿真；系統(tǒng)；分形圖形學(xué)

1967 年，美籍?dāng)?shù)學(xué)家B.B.Mandelbrot在《Science》上發(fā)表了題為 《How Long Is the Coast of Britain Statistical Self-Similarity and Fractional Dimension》的論文，標(biāo)志著“分形”學(xué)科的誕生[1]。如今，分形在數(shù)學(xué)、物理學(xué)、城市規(guī)劃、環(huán)境科學(xué)、地質(zhì)勘探、虛擬現(xiàn)實(shí)、信息與計(jì)算機(jī)科學(xué)等領(lǐng)域應(yīng)用廣泛[2]。目前國(guó)內(nèi)外高校普遍開(kāi)設(shè)了分形課程，甚至已經(jīng)成為數(shù)學(xué)、物理學(xué)、信息與計(jì)算機(jī)科學(xué)等專(zhuān)業(yè)的核心課程[3]。

美國(guó)教育家John Wheeler曾預(yù)言“誰(shuí)不知道熵概念就不能被認(rèn)為是科學(xué)上的文化人，將來(lái)誰(shuí)不知道分形概念，也不能稱(chēng)為有知識(shí)”[4]。然而，傳統(tǒng)分形算法的教學(xué)內(nèi)容抽象、理論性強(qiáng)，需要較好的數(shù)學(xué)基礎(chǔ)與較強(qiáng)的邏輯思維，使師生在教學(xué)過(guò)程中筋疲力盡也難于領(lǐng)悟其精髓。基于分形算法的教學(xué)仿真實(shí)驗(yàn)平臺(tái)實(shí)現(xiàn)了典型分形算法的計(jì)算機(jī)模擬，并提供一定的交互功能，為師生研究分形算法提供理論基礎(chǔ)和實(shí)現(xiàn)平臺(tái)，是鼓勵(lì)教師參與教學(xué)研究并實(shí)現(xiàn)教學(xué)現(xiàn)代化的重要保證，也是促進(jìn)學(xué)生加深算法理解與激發(fā)學(xué)習(xí)興趣的有效途徑[5]。

1 平臺(tái)概要設(shè)計(jì)和主要功能

基于分形算法的教學(xué)仿真實(shí)驗(yàn)平臺(tái)提供了文法構(gòu)圖算法、迭代函數(shù)系統(tǒng)算法、逃逸時(shí)間算法與反函數(shù)迭代算法的理論介紹與發(fā)展現(xiàn)狀，并展示了典型分形曲線(xiàn)的實(shí)現(xiàn)流程、仿真結(jié)果與優(yōu)缺點(diǎn)總結(jié)，同時(shí)，向用戶(hù)提供了調(diào)整分形曲線(xiàn)位置與顏色、研究分形算法關(guān)鍵參數(shù)以及操作提示等交互功能。

首先，教師借助平臺(tái)向?qū)W生展示算法的基本理論與發(fā)展現(xiàn)狀，并對(duì)典型分形曲線(xiàn)的程序流程圖進(jìn)行講解；然后，學(xué)生通過(guò)人機(jī)接口對(duì)分形曲線(xiàn)進(jìn)行調(diào)整與設(shè)置，熟悉關(guān)鍵參數(shù)對(duì)分形曲線(xiàn)的影響；最后，通過(guò)對(duì)比評(píng)論算法的優(yōu)缺點(diǎn)并總結(jié)關(guān)鍵參數(shù)的影響，從而加深學(xué)生對(duì)算法的理解與把握，并有效地增強(qiáng)了課堂的互動(dòng)性和趣味性。

基于分形算法的教學(xué)仿真實(shí)驗(yàn)平臺(tái)引入了系統(tǒng)科學(xué)的觀念，分形算法仿真系統(tǒng)模塊劃分圖如圖1所示，各模塊相對(duì)獨(dú)立，有利于提高系統(tǒng)的健壯性和擴(kuò)展性。

2 系統(tǒng)具體設(shè)計(jì)與實(shí)現(xiàn)

2.1 算法介紹

分形幾何創(chuàng)始人B.B.Mandelbrot曾經(jīng)定義過(guò)分形幾何的概念，然而隨著理論與應(yīng)用的不斷發(fā)展，目前尚無(wú)明確的定義可以詳盡描述分形豐富的內(nèi)涵。一般地，分形是簡(jiǎn)單空間上的復(fù)雜點(diǎn)集，并且是所在空間的緊子集，同時(shí)兼具以下全部或部分幾何性質(zhì)[6]：

1)分形集具有精細(xì)的結(jié)構(gòu)；

圖1 分形算法仿真系統(tǒng)模塊劃分圖Fig.1 Module division figure of fractal algorithm simulation system

2)分形集不是滿(mǎn)足某些條件的點(diǎn)集，也不是某些簡(jiǎn)單方程的解集，更不能用傳統(tǒng)的幾何語(yǔ)言描述；

3)分形集可能是近似的自相似或者是統(tǒng)計(jì)的自相似；

4)分形集的拓?fù)渚S數(shù)通常嚴(yán)格小于其按照不同方式定義的分形維數(shù)；

5)分形集應(yīng)用時(shí)通常以變換迭代等簡(jiǎn)單方法進(jìn)行定義。

以基于復(fù)平面上Julia集的反函數(shù)迭代算法為例研究分形算法的基本思想。

1918 年，法國(guó)數(shù)學(xué)家Gaston Julia基于復(fù)變函數(shù)迭代理論提出了復(fù)平面上二次函數(shù)的幾何結(jié)構(gòu)[7]，其基本形式即為Julia集合：

式（1）中，Z和C都是復(fù)數(shù)。在實(shí)際計(jì)算和編程時(shí)，需要設(shè)Z的實(shí)部為x、虛部為y，C的實(shí)部為cx、虛部為cy，即：

根據(jù)式（1），設(shè)Z0已知，并滿(mǎn)足F(Z)=Z2+C=Z0，可以得到以下兩個(gè)反函數(shù)：

若將｛ω1，ω2，C｝ 視為一個(gè)迭代函數(shù)系統(tǒng)，概率 p1=p2=

1/2 ，N為迭代次數(shù)，分別畫(huà)出ω1和ω2[8]：

1)當(dāng)k=0時(shí)，壓棧并繪制點(diǎn)Z0；

2)從棧頂取一點(diǎn)(Z0，k)；

3)根據(jù)概率p1和p2，計(jì)算出：和并繪制點(diǎn)ω1和ω2，將(ω2，k+1)壓棧并使Z0=ω1；

4)重復(fù)步驟3)直至k=N-1；

6)判斷棧是否為空棧，如果不是空棧，重復(fù)步驟2)～6)，否則結(jié)束。

其中，Z0與C是復(fù)數(shù)，需要根據(jù)式(2)用實(shí)部和虛部表示；Julia集中C設(shè)置不同的cx、cy會(huì)產(chǎn)生不同的Julia集分形圖形。

2.2 算法實(shí)現(xiàn)

以基于復(fù)平面上Julia集的反函數(shù)迭代算法為例研究分形算法的實(shí)現(xiàn)流程。

預(yù)先定義功能函數(shù)sqrz(double a,double b,double*x, double*y,double*theta)，其中，宏定義pi為3.141593，流程圖如圖2所示。

圖2 sqrz(double a,double b,double*x,double*y,double*theta)流程圖Fig.2 sqrz(double a,double b,double*x,double*y,double*theta)flowchart

基于復(fù)平面上Julia集的反函數(shù)迭代算法程序流程圖[9]如圖3。用戶(hù)通過(guò)對(duì)話(huà)框設(shè)置Julia集F(Z)=Z2+C中C的實(shí)部cx與cy虛部，研究參數(shù)對(duì)分形曲線(xiàn)的影響。其中，條件1為((x+cx)*(x+cx)+(y+cy)*(y+cy))?((-x+cx)*(-x+cx)+(-y+cy)*(-y+ cy))，條件2為(double)rand()/(double)RAND_MAX?p，宏定義RAND_MAX為0x7fff。

2.3 算法仿真

基于復(fù)平面上Julia集的反函數(shù)迭代算法分形曲線(xiàn)如圖4所示。

通過(guò)仿真Julia集分形曲線(xiàn)發(fā)現(xiàn)，Julia集對(duì)不同cx、cy取值會(huì)產(chǎn)生形態(tài)各異的分形曲線(xiàn)。根據(jù)圖4（a）與（b）、（c）與（d）、（e）與（f）可以初步判定cx相同而cy互為相反數(shù)的Julia集曲線(xiàn)關(guān)于y軸對(duì)稱(chēng)，cy相同而cx互為相反數(shù)的Julia集曲線(xiàn)沒(méi)有對(duì)稱(chēng)特性且形態(tài)相異甚大。

圖3 程序流程圖Fig.3 The program flowchart

圖4 算法仿真曲線(xiàn)Fig.4 The simulation results

3 結(jié)論

分形理論與計(jì)算機(jī)圖形學(xué)交叉形成的分形圖形學(xué)為研究分形算法提供了理論支持和實(shí)現(xiàn)手段，使仿真實(shí)驗(yàn)平臺(tái)成為一種新的實(shí)踐教學(xué)方式[10]。本文基于分形算法與Visual Studio 2005創(chuàng)建的教學(xué)仿真實(shí)驗(yàn)平臺(tái)，實(shí)現(xiàn)了文法構(gòu)圖算法、迭代函數(shù)系統(tǒng)算法、逃逸時(shí)間算法和反函數(shù)迭代算法等典型分形算法的介紹、實(shí)現(xiàn)與仿真功能，并向用戶(hù)提供了一定的交互功能，為師生研究分形算法提供了理想的平臺(tái)，并為用戶(hù)深入研究復(fù)雜分形曲線(xiàn)提供理論背景和實(shí)現(xiàn)手段，具有一定的研究意義和應(yīng)用價(jià)值。

[1]劉廣,宋光輝.分形:非線(xiàn)性科學(xué)理論、創(chuàng)新與實(shí)踐[J].系統(tǒng)科學(xué)學(xué)報(bào),2013,21(2):47-50. LIU Guang,SONG Guang-hui.Fractal:the theory,practice and innovation of nonlinear science[J].Journal of System Science,2013,21(2):47-50.

[2]鄒麗萍.基于虛擬現(xiàn)實(shí)的氣象災(zāi)害場(chǎng)景關(guān)鍵技術(shù)研究[D].南京：南京信息工程大學(xué),2012.

[3]徐新黎,胡磊，等.智能搜索算法在線(xiàn)教學(xué)實(shí)驗(yàn)平臺(tái)的設(shè)計(jì)與實(shí)現(xiàn)[J].實(shí)驗(yàn)技術(shù)與管理,2012,29(5):112-117. XU Xin-li,HU Lei,et al.Design and implementation of online teaching experimental platform based on intelligent search algorithm [J].Experimental Technology and Management, 2012,29(5):112-117.

[4]陳寅.不規(guī)則形體建筑表皮的結(jié)構(gòu)邏輯和材料構(gòu)造邏輯研究[D].北京：清華大學(xué),2011.

[5]劉佳,鄒麗萍.用于教學(xué)的分形仿真實(shí)驗(yàn)軟件：中國(guó), 2012SR021442[P].2012-03-20.

[6]曾文曲,王向陽(yáng)，等.分形理論與分形的計(jì)算機(jī)模擬[M].沈陽(yáng)：東北大學(xué)出版社,2001.

[7]楊杰,孫國(guó)忠，等.Julia集的反函數(shù)迭代算法[J].計(jì)算機(jī)仿真,2006,23(5):68-70. YANG Jie,SUN Guo-zhong,et al.Inverse function iterative algorithm for the Julia set[J].Computer Simulation,2006,23(5): 68-70.

[8]朱華,姬翠翠.分形理論及其應(yīng)用[M].北京：科學(xué)出版社, 2011.

[9]孫博文.分形算法與程序設(shè)計(jì)-Visual C++實(shí)現(xiàn)[M].北京：科學(xué)出版社,2004.

[10]楊亮,劉鐘馨，等.構(gòu)建真空鍍膜實(shí)驗(yàn)三維仿真系統(tǒng)[J].實(shí)驗(yàn)技術(shù)與管理,2012,29(2):71-75. YANG Liang,LIU Zhong-xin,et al.Constructing three-dimensional simulation system of vacuum film experiment[J].Experimental Technology and Management,2012,29(2):71-75.

Design and implementation of simulation system based on fractal

ZOU Li-ping
（NARI Technology Development Co.,Ltd,Nanjing 210061,China）

Fractal theory is one of the three frontier theory of nonlinear science.So far fractal geometry is the best geometry describes natural form,which applied in many fields widely.But the fractal algorithm has higher theoretical depth,which makes the traditional theory teaching difficult.In this paper,the typical fractal algorithm has been simulated based on Visual Studio 2005 with some interactive functions.The results show that this platform provides the theoretical background and experimental platform for teachers and students to study the fractal algorithm,and plays a significant role to improve education and teaching quality.

fractal algorithm;simulation;system;fractal graphics

TN02

A

1674－6236（2015）07-0064-03

2014-05-20 稿件編號(hào)：201405129

鄒麗萍(1985—)，女，吉林白城人，碩士。研究方向：分形算法、虛擬現(xiàn)實(shí)。