基于规则的分形图形生成方法
展开全文
基于规则的分形图形生成方法
摘要：本文先对分形理论的简要介绍，随后字符串替换算法，Lindermayer系统画图元部分规则描述及其实现三个方面详细地阐述了L系统的分形图形生成方法，还给出了生成图形算法的核心部分的vc实现。
关键词：分形 Fractal Lindermayer系统
1      分形理论简介
分形的概念是美籍法国数学家Benoit Mandelbrot 率先提出的。1967 年他在美国《科学》杂志上发表了题为《英国的海岸线有多长?》的著名论文, 1975 年他又发表了《分形:形、机遇和维数》,至此分形几何正式创立了。1982 年曼德布罗特又发表了《大自然的分形几何学》一书,从而使分形几何学再次引起了学术界的高度重视,并使分形理论进入发展的高潮。那么什么是分
形呢?分形是指其组成部分与整体以某种方式相似的形,也就是说,分形一般具有自相似性,其中也包括一个对象的部分与整体具有自仿射变换关系的相似。根据上面的定义,可以得出,分形具有下面5 个基本特征或性质: ①形态的不规则性; ②结构的精细性; ③局部与整体的自相似性; ④维数的非整数性; ⑤生成的迭代性。分形几何与大自然中的各种形态是具有非常紧密的联系的,如天空的云团、植物的叶脉、海岸线的形状等,可以看出分形的形态是极其不规则的,并且具有非常精细的结构,如著名的Koch曲线等,无论把其放大多少倍,都能看到其局部与整体的相似性及精致性。
2 lindermayer系统原理---分形的字符串替换算法
20世纪50年代,著名语言学家乔姆斯基(N. Chomsky)提出了递归生成语法的方法:首先指定一个或几个初始字母和一组“生成规则”,将生成规则反复作用到初始字母和新生成的字母上,直至不能再应用规则为止,从而产生出整个语言,即对应的字母和符号。因此可以用字符串表示生成元的构成,再把字符串反迭代来生成所希望得到的分形图。其实字符替换算法本质上是上述递归算法的一种文法
表示,这种算法可以用在生成元比较明确的分形图上
在美国生物学家Lindermayer发明的一种LS文法描述方法graftal上逐渐发展起来的形式语言的一个重要分支，称之为L-system.
LS文法是一类独特的迭代过程,它的核心思想就是重写.作为一种形式化的语言,LS文法用字母表和符号串来表达生成对象的初始形式,称为公理.然后根据一组产生式重写规则,将初始的每个字符依次替换为新的字符形式,反复进行,直到最后生成图形.
3 Lindermayer系统画图元部分
Lindermayer系统（简称L系统）是另外一种分形图形生成的方法，其主要原理在具体实现过程中也可以这样叙述：设定基本简单的绘图规则，然后让计算机根据这些规则进行反复迭代，就可以生成各种各样的图形来。用L系统可以非常逼真的模拟植物的生长过程。根据规则的不同，来显示不同的图形。
首先，考察一下画图的过程。无论什么样的复杂图形，都可以把图形看成若干线条构成的，而一个线条是由起点和它的方向决定的，这样，人们复杂的画图动作可以分解为若干线条的连接组合。根据这些，我们来讨论计算机绘图。
计算机绘图也是要确定一个起始点和开始画线的方向这叫做初始状态，当画图进行到任意一个阶段的时候，我们可以用（x,y,a）这三个量来确定任意一个画图的状态，即当前的坐标x,y和当前要画线条的方向角a。然后，我们需要考虑的是状态到状态是如何转换的。我们把状态之间的转换称为动作，不难看出，仅仅用平移和旋转方向就能完成状态之间的转换。接下来，我们用符号定义一些简单的动作（包括平移、旋转和辅助动作）。
F：表示在当前的位置画一条长为l的直线段。l是由用户事先任意设定的数值，表示基本线段的长度。
+：表示逆时针旋转一个角θ，θ的数值由用户事先确定；
-：表示顺时针旋转一个角θ；
[：表示暂时保存当前的画图状态
]：表示提取出保存的画图状态。 “[”和“]”要成对的出现。
这样，确定了开始的坐标和方向，由上面符号组成的任意的一系列指令就能指导画图了。比
如：FF+F，其中长度l=1,θ=90度角，开始坐标是(2，0)，开始方向角是90度，那么画出来的图就是：
其中蓝的线条是画图指令画出的图。开始的时候画图状态为(2,0,90)，也就是说起点在2,0这个点，并且这个时候画图的方向是朝上的，然后开始画指令F，它的意思是方向不变，往前走1个步长并且画线连接上起始的点和下一个将要移动到的点(2,1)，因此画图机器就往正上方画了一条蓝的长度为1的线段，并且把当前的状态改为了(2,1,90)就是说坐标移动到了2，1这个点，而方向角没变还是垂直向上。接下来画下一个F，仍然是朝上方画一个长度为1的线段。然后是+表示画图状态的方向逆时针旋转90度，然后这个时候的状态变为(2,2,180)，就是说坐标为(2,2)方向朝左方。然后再画一个F，就是往左画一个小线段状态改为(1,2,90)，到此画图命令FF+F执行结束。综合起来，我们能得到下面的表：
指令
状态
画图动作
起始时刻
(2,0,90)
无
F
(2,1,90)
向上画一条长为1的线段
F
(2,2,90)
向上画一条长为1的线段
+
(2,2,180)
逆时针旋转90度，不画图
F
(1,2,180)
向左画一条长为1的线段
4 Lindermayer系统的规则描述及其实现
规则是形如X->Y的式子，X叫做左件，Y叫做右件。X->Y表示X能够推导出Y。如果X是一个字符串，Y也是字符串，那么X->Y表示能够用Y来替换X。例如如果给定一个初始时刻的字符串ABXXTT，那么运用规则X->Y就能把这个字符串变成ABYYTT。如果产生式的右件多于一个字符，那么就能推导出比原来字符串更长的字符串来。例如如果X->YYY，那么ABXTT会被替换成ABYYYTT，显然后来的字符串比原来的长。我们已经看到了从简单的字符串生成复杂字符串的可行性了。
接下来，要说明的是产生式可以进行嵌套的表示，比如说X->XY就是一种嵌套的形式。因为当你用右件XY代替前件X的时候产生的新字符又会产生X，而X又可以运用规则X->XY，这样可以无限次的迭代下去。
有了产生式就不难理解产生式系统了，它就是由若干个产生式构成的一组语句。并且各个产生式之间可以相互替换字符串。比如如下的产生式系统：X->YF, Y->+FX，开始时刻的字符串是X，用这两个规则迭代1次就能得到字符串：+FXF，迭代2次就是+F+FXFF，3次是+F+F+FXFFF，……。（这里迭代一次表示的是用产生式系统中的所有产生式规则都来替换
当前的字符串）。我们已经看到，最后的式子就是形如我们上面列举的指令例子，如果把最后的X忽略掉，这个指令串就能指导机器画图了！
常见的几种图形的规则描述：
(1) 斜草
G
G- GFX[+++++GFG][-----GFG]
X- F-XF
(2) 树枝
F
F include意思F[+F]F[-F]F
(3) 星星
F F-F++F-F
(4) 蒲公英
Y
X X[-FFF][+FFF]FX
Y YFX[+Y][-Y]
其他的规则可参看源代码
5 Lindermayer系统的设计与实现
该演示系统的核心在于画图指令的生成部分，包括具体图形对应的LS文法的描述和迭代替换过程。
//设计保存规则的数据结构
struct SRule {
CString left;
CString right;
};
//得到画图指令   
strDraw = strStart;
for (int i=0;i<nIterator;i++)
{
for (int j=0;j<6 && !rule[j].right.IsEmpty();j++)
{
strDraw.Replace(rule[j].left,rule[j].right) ;
}
}
//分析画图指令
while (i<strDraw.GetLength())
{
switch(strDraw[i]){
case 'F': DrawF(curState,pDC);break;
case '[': Push(curState);break;
case ']': curState=Pop();break;
case '+': curState.angle = AntiClockwise(curState.angle);break;
case '-': curState.angle = Clockwise(curState.angle);break;
default:break;
}
i++;
}
6 结论
分形虽然是一门新兴学科,但它已经激发了各个领域的科学家们的极大兴趣,在许多领域开展了应用探索。其应用遍及数学、物理、计算机科学乃至艺术等领域。。随着分形技术和计算机技术的快速结合及迅速发展,其应用必将深入到人类生活的各个方面。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。