一、 实验目的
1、 通过编程实现分形图 ，更深入的了解分形图和LS文法的思想
2、 了解分形图的LS文法实现。
二、 实验环境说明
开发工具：Microsoft Visual C＋＋ 6.0
用其中的MFC AppWizard(exe)-Single documents.
操作环境：Microsoft Windows XP SP1
三、 实现功能说明（包括操作说明）
点击菜单栏－>“画图”，可以画特定的分形图包括：
1． 分形树（5种）
2． 手帕曲线（2种）
3． Sierpinski三角形
4． Peano曲线
5． Koch反雪花曲线
6． Koch雪花曲线
7． 柳条
8． 多规则分形树
9． “止”字曲线
10． 环形肠
点击菜单栏－>“设置”，可以设置递归深度 看随着递归深度的增加，图形的变化。
点击菜单栏－>“作者”，有作者信息。
四、 算法与数据结构（程序设计）
主要数据结构（主要是一些变量和数组）：
int i,j,k;/*辅助变量*/
double pi;/*圆周率*/
int seta;//偏转角
struct point//结点
{
double x;/*x坐标*/
double y;/*y坐标*/
double angle;/*前进角度*/
}point1,point2;
string tree,temptree,unit,unit1,unit2;/*实现ls的辅助字符串*/
int length;/*字符长度*/
int step,setstep;/*步长*/
int deep,setdeep,depth,/*递归深度*/message;/*表示画某种图*/
• 程序请参考源代码
Ls文法的主要思想是：
仿照语言学中的语法生成方法来构造图形的一种算法
递归生成语法
一个或者几个初始字母
一组生成规则
将生成规则反复作用到初始字母和新生成的字母上
Ls文法的实现分形图绘制的主要过程就是：
一类独特的迭代过程
核心概念是重写
公理
用字母表和符号串来表达生成对象的初始形式
一组产生式重写规则
将初始形式的每个字符依次替换成为新的字符形式
反复替换重写，生成终极图形
二维LS文法字母表的绘图规则如下：
F：以当前方向前进一步，并画线
f：以当前方向前进一步，不画线
＋：逆时针旋转dº
－：顺时针旋转dº
[：将当前信息压栈
]：将“[”时刻的信息出栈
算法的设计主要包括三各部分：
1．初始化（ 公理 规则 偏转角）
if(message==0){MemDC.TextOut(100,150,"因为有的图形递归深度过高不好看，被置为为小的",44);
MemDC.TextOut(100,170,"有的图形步长太小不好看，所以被置为适当大小",42);}
else if(message==1)//分形树1
{
tree="F";
unit="F[+F]F[-F][F]";
seta=25;
point1.x=300;point1.y=400;
point1.angle=90;
}
else if(message==2)//分形树2
{
tree="F";
unit="F[+F]F[-F+F]";
seta=30;
step--;
point1.x=300;point1.y=400;
point1.angle=90;
}
else if(message==3)//分形树3
{
tree="F";
unit="FF+[+F-F-F]-[-F+F+F]";
seta=25;
if(step>3){step=3;}
point1.x=300;point1.y=400;
point1.angle=90;
}
else if(message==4)//分形树4
{
tree="F";
unit="F[-F][+F]F";
seta=25;
point1.x=300;point1.y=400;
point1.angle=90;
}
else if(message==5)//分形树5
{
tree="F";
unit="F[-F][+F][--F]F[++F]F";
seta=25;
point1.x=300;point1.y=400;
point1.angle=90;
}
else if(message==6)//柳条
{
if(deep>3){deep=3;}
tree="F";
unit="F[+F]F[-F]+F";
seta=20;
step*=4;
point1.x=100;point1.y=300;
point1.angle=90;
}
else if(message==7){//手帕曲线1
tree="F+F+F+F";
unit="FF[+F+F+F]F";
seta=90;
step=4;
point1.x=100;point1.y=10;
point1.angle=0;
}
else if(message==8){//手帕曲线2
tree="F+F+F+F";
unit="F[F]+F-F[++F]-F+F";
seta=90;
step=4;
point1.x=30;point1.y=10;
point1.angle=0;
}
else if(message==9){//“止”字曲线
if(deep>3){deep=3;}
tree="F+F+F+F";
unit="F+F-F-FFF+F+F-F";
seta=90;
step=3;
point1.x=200;point1.y=200;
point1.angle=0;
}
else if(message==10){//环形肠
if(deep>4){ deep=4;}
tree="F+F+F+F";
unit="FF-F-F-F-F-F+F";
seta=90;
step/=2;
point1.x=300;point1.y=300;
point1.angle=0;
}
else if(message==11)//koch雪花
{
tree="F++F++F";
unit="F-F++F-F";
seta=60;
step=1;
point1.x=250;point1.y=150;
point1.angle=0;
}
else if(message==12)//koch反雪花
{
tree="F++F++F";
unit="F+F--F+F";
seta=60;
step=1;
point1.x=250;point1.y=150;
point1.angle=0;
}
else if(message==13)//多规则分形树
{
tree="X";
unit="F-[[X]+X]+F[+FX]-X";
seta=22.5;
step*=3;
point1.x=250;point1.y=350;
point1.angle=90;
}
else if(message==14)//peano曲线
{
tree="X";
unit1="-YF+XFX+FY-";
unit2="+XF-YFY-FX+";
seta=90;
step-=2;
point1.x=250;point1.y=400;
point1.angle=0;
}
else if(message==15){//Sierpinski垫片
tree="L";
unit1="+R-L-R+";
unit2="-L+R+L-";
seta=60;
step=3;
point1.x=250;point1.y=400;
point1.angle=60;
}
length=tree.size();
2．替换
depth=deep;
while(depth--)
{
length=tree.size();
temptree=tree;
tree="";
j=0;
while(j<length)
{
if(temptree[j]=='X'&&message>12)
{
if(message==13)
tree+=unit;
else
tree+=unit1;
}
else if(temptree[j]=='Y'&&message>12)
{
tree+=unit2;
}
else if(temptree[j]=='F'&&message<13)
{
tree+=unit;
}
else if(temptree[j]=='L')
{
tree+=unit1;
}
else if(temptree[j]=='R')
{
tree+=unit2;
}
else tree+=temptree[j];
j++;
}
}
length=tree.size();
3．画图
int i=0;
MemDC.MoveTo(point1.x,point1.y);
while(i<length)
{
switch(tree[i++])
{
case 'F':
point1.angle=point1.angle;
point1.x=point1.x+step*cos(point1.angle*pi/180);
point1.y=point1.y-step*sin(point1.angle*pi/180);
MemDC.LineTo(point1.x,point1.y);
break;
case 'f':
point1.angle=point1.angle;
point1.x=point1.x+step*cos(point1.angle*pi/180);
point1.y=point1.y-step*sin(point1.angle*pi/180);
MemDC.MoveTo(point1.x,point1.y);
break;
case '-':
point1.angle=point1.angle+seta;
break;
case '+':
point1.angle=point1.angle-seta;
break;
case '[':
stack1.push(point1);
break;
case ']':
point1=stack1.top();stack1.pop();
MemDC.MoveTo(point1.x,point1.y);
break;
case 'L':{
point1.angle=point1.angle;
point1.x=point1.x+step*cos(point1.angle*pi/180);
point1.y=point1.y-step*sin(point1.angle*pi/180);
MemDC.LineTo(point1.x,point1.y);
break;}
case 'R':{
point1.angle=point1.angle;
point1.x=point1.x+step*cos(point1.angle*pi/180);
point1.y=point1.y-step*sin(point1.angle*pi/180);
MemDC.LineTo(point1.x,point1.y);
break;}
case 'X':if(message==13){
point1.angle=point1.angle;
point1.x=point1.x+step*cos(point1.angle*pi/180);
point1.y=point1.y-step*sin(point1.angle*pi/180);
MemDC.LineTo(point1.x,point1.y);
break;}
}
}
五、 部分实验截图 。
通过点击菜单栏－>“设置”，可以设置递归深度 看随着递归深度的增加，图形的变化。
下面截取一部分实验效果图：
柳条
多规则生成树
Peano曲线
Sierpinski三角形垫片
六、实验小结
通过这个实验，我对ls文法有了更深的理解，体会到了分形图的魅力。用LS文法实现分形图比用递归实现更加有效率，更美观，程序的可读性也提高了很多，通过这次实验，觉得要有好的理论是很重要的。
