木匣子

Web/Game/Programming/Life etc.

L系统与分形图

分形是自然界中非常美丽的自相似现象的数学抽象。例如希尔伯特曲线以及科赫曲线就是其中比较有名的代表。

hilbert-curve

小学参加NOIP的时候曾遇到过另外一个著名的谢尔宾斯基三角形,当时的题目是让我们用Logo语言绘制一个谢尔宾斯基三角形,当时我就懵了。画二叉树的递归已经够让我头疼了,现在又要搞一个更复杂的图形。直至比赛后看了参考答案,依旧是一头雾水。所以对此事一直念念不忘,等到中学时代慢慢理解了递归思想后,终于搞明白了。

后来在学习 Generative Art 的时候发现了递归以外的另一种描述分形的方法叫 L-System,它是一种很有趣的迭代方法。

Lindenmayer系统,简称L系统,是由荷兰Utrecht大学的生物学和植物学家,匈牙利裔的林登麦伊尔(Aristid Lindenmayer)于1968年提出的有关生长发展中的细胞交互作用的数学模型,尤其被广泛应用于植物生长过程的研究。L-system是一系列不同形式的正规语法规则,多被用于植物生长过程建模,但是也被用于模拟各种生物体的形态。此外 L-system 也能用于生成自相似的分形,例如迭代函数系统。
wikipedia

实践

L-system 用几个简单的基本概念来描述分形的生长过程:

G={V,S,ω,P}
  • V 变量符号集合
  • S 常量符号集合
  • ω 初始状态
  • P 产生式规则

变量是在迭代过程中会成长变化的符号,常量是在迭代过程中不会变化的符号。初始状态也被称为公理,在植物世界里相当于"种子"。产生式规则简称规则,用来描述变量在每次迭代过程中的变化规则。

藻类

维基百科上有个比较好理解的例子,描述一种藻类的生长过程:

变量: A,B; 常量: 无; 公理:A 规则:

  • A → AB
  • B → A

在系统一开始的时候,我们有公理,也就是藻类的种子:

A

一个生命周期后,根据规则,A → AB,藻子长大了:

AB

又一个生命周期后,它变成了这样,其中最后面的A是由规则B → A而来:

ABA

慢慢的,慢慢的

ABAAB
ABAABABA
ABAABABAABAAB
ABAABABAABAABABAABABA
ABAABABAABAABABAABABAABAABABAABAAB

藻子七周岁了。如果你仔细数一数藻子每一岁的长度,会发现它是一个斐波那契数。

但是这一串枯燥的文字怎么和植物联系起来呢。是的,我们还需要一个渲染引擎,将变量常量赋予特定的动作,这样根据最后的迭代结果,我们就可以从头到尾把它画出来了。

二叉树

另一个例子是二叉树:

变量: ,1; 常量[,]; 公理:; 规则:

  • 1 → 11
  • 0 → 1[

我们略过分析直接看生长过程:

0
1[0]0
11[1[0]0]1[0]0
1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0
…

现在,为了把它画出来,我们给每个符号定义动作:

  • 0 绘制一条直线,为叶子;
  • 1 绘制一条直线,为枝干;
  • [ 将当前的画笔位置和角度入栈,并左转45度;
  • ] 将画笔位置出栈(恢复上次的状态),并右转45度;

于是我们把可以把这棵二叉树3周岁的样子画出来了!

binary-tree

理解了这些概念后,想要绘制更加复杂的分形就是小菜一叠了,有兴趣的话可以Google一下用 L-System 创造的各种艺术图形吧!