3.1 L文法系统（L-System）

琼粒蕃滋争结穟，龙枝屈曲竞分形。

—宋·夏竦《奉和御制内苑嘉谷》

L-System的字母L，指的是美国生物学家Aristid Lindenmayer。1968年，他提出了一种方法，这种方法被用来研究植物的形态与生长。方法最初关注的是植物的拓扑结构，即植物的主干、旁支等之间的关系，之后加入了几何解释，由此形成了L文法系统。L文法系统在1984年被引进计算机图形学领域，用于模拟自然景物形态。1990年，The Algorithmic Beauty of Plant《植物的算法之美》一书出版，这本书详细地总结了由Lindenmayer领导的理论生物小组与Prusinkiewiez领导的计算机图形学小组合作进行的大量研究工作。

L 文法系统是一种采用文法（也就是仿照语言学中的语法）的方式来构造图形的算法，这种算法的核心概念是字符串的替换和构图。首先，初始形式是一个字母表和一个初始的符号串（又叫作公理 Axiom），然后，根据一组规则，将公理 Axiom 中的每个字符都依次替换，生成一个新的字符串，再在新的字符串上应用规则依次替换每个字符，如此反复迭代替换，直到迭代结束，形成一个最终的字符串。之后，用预先定义的、每个字符在几何绘图上的语义来解释这个最终的字符串，依据字符串中的字符来生成图形。简而言之，字符串就是图形的语义表达。

L文法系统可定义为一个三元组〈V，ω，P〉。

V：字母表（alphabet）。

ω：初始字符串，由字母表中的字符组成，不能为空。

P：生成规则集。

假设，

字母表V：a，b

公理ω：a

规则集P：规则1：a→ab；规则2：b→a

字符串的替换过程如下：

a

ab

aba

abaab

abaababa

在规则集P中有两条规则，第一次替换是在初始的公理a上应用规则1，将字符a变为字符串ab；第二次替换先在字符串ab的字符a上应用规则1，将字符a变为字符串ab，再在字符串ab的字符b上应用规则2，将字符b变为字符a，由此整个的字符串变为aba；第三次替换先在字符串aba的字符a上应用规则1，变为ab，再在字符串aba的字符b上应用规则2，变为a，最后，在字符串aba的字符a上应用规则1，变为ab，所以，整个字符串就变成了abaab；以此类推，形成最终的字符串。

包含了几何绘图意义的L文法系统被称为“龟图”（turtle），龟图的状态可以用三元组（x， y， d）来表示，其中x和y分别代表横坐标和纵坐标，d代表当前的方向。假设δ为角度增量，L为步长。部分通用符号的图形学解释如下。

字符“F”：在当前方向向前进一步，步长为 L，并在两点之间绘制一条线段。假设在执行字符F前，龟图的状态为（x， y， d），那么在执行字符F后，龟图的状态就变为（x₁， y₁， d），方向d保持不变，横坐标x和纵坐标y会发生改变，新的x₁、y₁需要根据方向d的角度来进行计算，两者之间的关系如下：

x₁=x+Lcos（d），d为角度，L为步长

y₁=y+Lsin（d），d为角度，L为步长

字符“f”：在当前方向向前进一步，步长为 L，但是两点之间不会绘制线段，画笔只是移了一个位置而已。在执行字符f后，龟图的状态为（x₁， y₁， d），同样是方向d保持不变，而新的x₁、y₁需要根据x、y、d来进行计算，计算的公式与字符F相同。

字符“+”：逆时针旋转δ度。假设在执行字符“+”前，龟图的状态为（x， y， d），那么，在执行字符“+”后，横坐标和纵坐标保持不变，而方向角度会转换为d+δ，即龟图的状态为（x， y， d+δ）。

字符“-”：顺时针旋转δ度。假设在执行字符“-”前，龟图的状态为（x， y， d），那么，在执行字符“-”后，横坐标和纵坐标保持不变，而方向角度会转换为d-δ，即龟图的状态为（x， y， d-δ）。

字符“[”：将龟图的当前状态压进栈（stack）。栈是一种数据存储的结构。在执行字符“[”后，龟图的状态并不会改变，而是会在栈里保存起来，供稍后调用。

字符“]”：从栈中取出保存的龟图状态。在执行字符“]”后，龟图的当前状态就会被从栈中所取出的状态所替换。字符“[”和字符“]”常被用于绘制植物的分支结构。

以上是本书源码中所用到的L文法系统的符号，除此之外，L文法系统还有一些其他常用符号。L文法系统常用符号如表3-1所示。