计算机科学

首页 > 计算机科学

L系统

2018-08-30 10:01:34     所属分类:形式语言
使用 L-系统 生成的 3D 杂草

Lindenmayer系统,简称L系统,是由荷兰Utrecht大学的生物学和植物学家,匈牙利裔的林登麦伊尔(Aristid Lindenmayer)于1968年提出的有关生长发展中的细胞交互作用的数学模型,尤其被广泛应用于植物生长过程的研究。

L-system是一系列不同形式的正规语法规则,多被用于植物生长过程建模,但是也被用于模拟各种生物体的形态。L-system也能用于生成自相似的分形,例如迭代函数系统。

目录

  • 1 起源
  • 2 L-system 结构
  • 3 L系统的例子
    • 3.1 例1:海藻的生长
    • 3.2 例1的解释
  • 4 开放问题
  • 5 参考文献
  • 6 外部链接
  • 7 参见

起源

作为一位生物学家,Lindenmayer工作的内容是酵母菌和丝状真菌,并研究多种类型的海藻的生长模式,例如蓝绿细菌项圈藻(Anabaena catenula,淡水藻类的一种)。最初,L系统被设计成用于提供一种关于简单多细胞生物体生长的正规描述,并且试图证明植物细胞之间的紧密关系。不久以后,这个系统被扩展成描述高等植物及其复杂枝杈结构。

L-system 结构

L-system的自然递归规则导致自相似性,也因此使得分形一类形式可以很容易的使用L-system描述。植物模型和自然界的有机结构生成,非常相似并很容易被定义,因此通过增加递归的层数,可以缓慢生长并逐渐变得更复杂。L-system同样在制造人造生命领域。 L-system 语法与Chomsky语法非常相似,说到L-system通常指的是带参数的L-system,定义如下:

G={V,S,ω,P},

V:变量符号集合

S:常量符号集合

ω:初始状态串

P:产生式规则

自初始状态开始迭代套入L-system的文法规则,和正规文法所产生的语言不同处在于,L-system在一次迭代中可同时套用许多不同的文法规则。如果在一次迭代中只能够套用一个文法规则,产生出来的结果被称为语言而不是L-system。由此可知,L-system为正规文法所产生出的语言的子集合。

L系统的例子

例1:海藻的生长

Lindenmayer研究海藻生长模式时提出的最早的L-系统:

变量 : A B
常量 : 无
公理 : A
规则 : (A → AB), (B → A)

迭代过程:

n = 0 : A
n = 1 : AB
n = 2 : ABA
n = 3 : ABAAB
n = 4 : ABAABABA
n = 5 : ABAABABAABAAB
n = 6 : ABAABABAABAABABAABABA
n = 7 : ABAABABAABAABABAABABAABAABABAABAAB

例1的解释

n=0:         A           开始 (公理/起始点)
            / 
n=1:       A   B         根据规则(A → AB)起始点A拓展成AB,由于起始点没有B,规则(B → A)没有被用到
          /|    
n=2:     A B     A       AB中的A拓展成AB,B变成A,于是得到了ABA
        /| |     |
n=3:   A B A     A B     可以看到每个A都是一个新的子树的根,由此引发出和整体结构同构的子结构。
      /| | |    | 
n=4: A B A A B   A B A   

如果我们观察这个序列的长度就会发现这是一个斐波那契数列—— 1 2 3 5 8 13 21 34 55 89 ... (因为我们选择从A开始,故第一个1少掉了) 如果我们把A看成一只成年兔子,B看成未成年兔子,那么这个构造和那个著名的兔生兔的构造是一致的。 即每个月B会成长成A,而A每个月又会生出一个B。

开放问题

许多涉及L-systems研究的问题有待解决,比如:

  • 描述所有那些确定的局部连锁的上下文无关L-systems(目前已知完成解决的只有包含两个变量的这一种情况)。
  • 给定一个结构,找出生成此结构的L-systems文法。

参考文献

外部链接

  • David J. Wright's article on L-systems
  • Algorithmic Botany at the University of Calgary
  • Branching: L-system Tree A Java applet of the botanical tree growth simulation using the L-system.
  • Fractint L-System True Fractals
  • "An introduction to Lindenmayer systems", by Gabriela Ochoa。Brief description of L-systems and how the strings they generate can be interpreted by computer.
  • "powerPlant" an open-source landscape modelling software
  • Fractint home page
  • L-Systems in Architecture
  • A simple L-systems generator (Windows)
  • Lyndyhop: another simple L-systems generator (Windows & Mac)
  • An evolutionary L-systems generator (anyos*)
  • "LsystemComposition". Page at Pawfal ("poor artists working for a living") about using L-systems and genetic algorithms to generate music.
  • eXtended L-Systems (XL), Relational Growth Grammars, and open-source software platform GroIMP.
  • A JAVA applet with many fractal figures generated by L-systems.
  • Another L-system applet, supporting programming, with explanation and examples.
  • L-systems in Architecture; genetic housing.
  • L-systems in Plant Growth,Simulation and Visualization (PlantVR).
  • Musical L-systems: Theory and applications about using L-systems to generate musical structures, from waveforms to macro-forms.
  • L-system digital sound synthesis: 'Do Digital Monkeys Inhabit Virtual Trees?' Electronic music piece composed with L-systems.
  • LSys/JS - Interactive L-System interpreter using the Canvas HTML element。
  • Lindenmayer System for plant visualisation (Java Applet)。
  • Fractal Grower: Free Java paper folding L-System intended for elementary and middle school students.
  • Programmatic animations in actionscript showing various L-systems.[失效链接]
  • Java applet showing random L-Systems while driving down Lindenmayer Boulevard
  • Magic Garden - Artificial Plants Laboratory - free plants generator using L-Systems
  • Inkscape a free software vector graphics program which implements, among its plugins, an L-system generator
  • Garabatos,an interactive evolutionary image generator based in L-Systems
  • Online experiments with L-Systems using JSXGraph (JavaScript)

参见

  • 分形
  • 迭代函数系统
  • 希尔伯特曲线
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/340060.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


上一篇:可识别语言
下一篇:不收缩文法
相关推荐