Search

碎形與L-system - iThome Online

起始元(Initiator)與生成元(Generator)是描繪碎形的方式之一,若想以簡約語言來記錄碎形生成過程,我們可以採用L-system制定正式文法(Formal grammar),而這也便於使用機器處理這類碎形語言,令碎形的描述與繪製過程通用化。

碎形圖案

在繪製碎形圖案時,海龜繪圖是經常運用的方法之一,因為透過海龜的操作,開發者可以免除複雜的數學計算,只要透過程式碼操作海龜相關動作,命令它前進、轉彎等,之後就可以繪製出複雜的碎形圖案。

儘管使用的程式語言或程式庫不同,然而,我們應該還是可以察覺到:在繪製各種碎形時,看似不同的程式進行流程,卻又似乎隱含著某種流程的相似性,因此,我們可否將這類流程抽出,令其通用化,之後只要撰寫相異部份的程式碼就可以了?

若試著採用Koch發展出來的「起始元與生成元」,透過這種碎形描繪方式來實現程式碼,我們就可以更進一步發現:流程中隱含的相似性,來自於碎形的自相似性;在起始元與生成元方法中,起始元是初始圖案,生成元會「取代」前次迭代的某圖案單元,而不同的圖案單元則會有各自對應的生成元。

例如,超始元定義為實心三角形,而實心三角形的生成元是將之畫分為四個小三角形,中間三角形為空,其餘三角形實心,在每次迭代時,將先前全部的實心三角形以生成元取代,就會生成自相似的謝爾賓斯基三角形(Sierpiński triangle)。

根據起始元與生成元的取代過程,顯而易見地,生成元就是自相似性的來源;只不過方才描述超始元、生成元的方式過於冗長了,可否有正式、精確些的描述方式?

L-system規範碎形構造

在先前專欄〈遞迴、碎形與數學〉談過「1,1,1,2,1,2,3,1,2,4,3,1,5,2,4,6...」這串像密碼般的數字,因為數列中的子數列具有自我相似性,是一種碎形數列;談到密碼,人們常稱費式數列是大自然的密碼,因為費式數列與許多生物的成長規律有關,而Fn = Fn-1 + Fn-2是人們熟知的描述方式。

其實,換個方式來描述費式數列,也可以視其為碎形數列。而這種方式是給個起始元A,以及兩個生成元A→AB、B→A,在首次迭代時,根據A→AB,A被生成元AB取代,接著第二次迭代時就會是ABA(因為AB取代前次的A,而A取代前次的B),三次迭代時,就會是ABAAB,接著是ABAABABA、ABAABABAABAAB……數數看每次迭代的符號數量,會發現是1,2,3,5,8,13. ……這不就是費式數列!(因為是從起始元A開始,也就只有一個1作為數列開頭)

若將A看為成年兔子,B視為未成年兔,A→AB就是每個月成年兔會生出一隻未成年兔(而成為兩隻),B→A表示在未成年兔下個月成長為成年兔,A、A→AB、B→A就描述了費式數列介紹時常見的兔生兔範例了。想知道某個月成年兔、未成年兔各是幾隻嗎?數數看符號中A與B的數列就知道了,例如,某月的ABAABABA,代表有五隻成年、三隻未成年兔。

A、A→AB、B→A實際上是生物學家Lindenmayer研究海藻生長時,為了以符號描述其成長模型而提出,後來這種符號描述方式正式規範為L-system(L代表Lindenmayer),而成為一套文法描述方式,L-system的定義為G={V,ω,P},G代表文法,V是符號集合,ω是起始元,P是衍生規則,以方才的範例來說,V是{A, B},ω是A,P是{A→AB, B→A}。

若將零到一的線予以三等分,去掉中間的線,左右的線依同樣方式,持續區分下去,得到的會是康托爾集(Cantor set),這是個無限大的集合,然而,這個集合中又什麼都沒有。假如康托爾集用L-system來描述的話,起始元是A,衍生規則是A→ABA,B→BBB。

如果A代表往前移動畫線,B代表往前移動不畫線,在每次迭代時畫出的圖案,會是有趣的紋身圖案(可參考維基百科〈康托爾集〉條目的圖片)。

L-system與海龜繪圖

方才建立碎形圖案時採用的起始元與生成元方法,與L-system其實是同種方式,而在我談康托爾集時,曾說到A、B可代表前進時畫線與否,就像在命令海龜,實際上以L-system來描述碎形圖案的建構,是常見的應用。

例如,起始元F,衍生規則F→F-F++F-F,描述的就是科赫(Koch)曲線的生成文法,因為F代表命令海龜前進並繪線,+表示左轉,-表示右轉,若前進長度固定為1,轉動角度固定為60度,F-F++F-F就是一次科赫曲線,F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F就是二次科赫曲線,依此類推。

在L-system結合海龜繪圖時有幾個常用符號,各對應至海龜的指令,除了方才談到的F+-之外,還有f為前進不繪線,|轉動180度,[將目前海龜狀態置入堆疊,]將海龜狀態從堆疊中取出等。

光這幾個符號,就可以創造諸多L-system文法,建構許多碎形圖案,我在〈lsystem2_collection〉收集一些規則,有興趣者可以參考。

我們也可以將其擴充至3D版的海龜繪圖,最基本的就是增加&(抬頭)、^(低頭)、\(左滾)、/(右滾)等符號,我在〈lsystem3_collection〉也收集了幾個3D版的L-system。

從海龜的角度來看,F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F就是語言,畢竟它看懂並遵照指示繪圖,若以方才的F+-|[]符號構造L-system文法規則,生成的語言是屬於下推自動機(PushDown Automaton),因為其具有堆疊結構,也就是說,若想實現可指定規則並繪圖的L-system程式庫,首先要依規則及迭代次數生成程式碼(像是F-F++F-F),接著剖析程式碼並執行。

回到一開始的話題「可否將這類流程抽取出來,令其通用化,之後只要撰寫相異部份的程式碼就可以了呢?」若我們只是根據相異部份程式碼來執行,那麼,就是方才談到的「剖析程式碼並執行」的階段。

試著實現L-system

既然L-system本身就是文法系統,文法如果越豐富,功能就會越強。常見的一種變化,是可設定每次迭代時,是否採用某規則的機率,而這常用於模擬植物生成時既有規律、又具備隨機而產生的多樣性,此時的L-system被擴充為Stochastic L-system,也就是隨機L-system。

方才所談到的做法,都是上下文無關(Context-free)的L-system,也可以進一步增加文法至上下文相關。有興趣的話,我們可參考《The Algorithmic Beauty of Plants》第一章〈Graphical modeling using L-systems〉,當中從基本的L-system談到上下文相關的L-system,是個非常詳盡的介紹。

整體而言,我們可以試著自行實現L-system並結合海龜繪圖指令,這並不難,而在這個過程中,能夠體會到構造簡單語言、碎形創作等樂趣。若要從簡單的範例開始,可以參考《用Python做科學計算》的〈繪製L-System的碎形圖〉。

Let's block ads! (Why?)



"複雜的" - Google 新聞
May 28, 2020 at 08:19AM
https://ift.tt/3c8ZGbd

碎形與L-system - iThome Online
"複雜的" - Google 新聞
https://ift.tt/3d3dcyJ
Shoes Man Tutorial
Pos News Update
Meme Update
Korean Entertainment News
Japan News Update

Bagikan Berita Ini

0 Response to "碎形與L-system - iThome Online"

Post a Comment

Powered by Blogger.