分形图生成算法与实例

分形图生成算法与实例介绍 1分形的定义 对于分形的概念一直没有严格的定义。不同学科领域的学者对分形的理解是 不同的，所以很难给出统一的，让所有的科研人员都能接受的定义。曼德尔布罗 特先后对分形给出两个定义，第一个定义是 1982年提出的，四年后，他又提出 了更为实用，更易于理解的定义，所以后一种定义一直沿用至今。 定义 1 如果一个集合在欧式空间中的 Hausdorff维数 HD 恒大于其拓扑维数 rD ，则称该集合为分形集，简称分形。 定义 2 组成部分以某种方式与整体相似的形体叫分形。 对于定义 1 的理解需要一定的数学基础， 不仅要知道什么是 Hausdorff 维 数，而且要知道什么是拓扑维数，看起来很抽象，也不容易推广。定义 2 比较 笼统的说明了自然界中的物质只要局部和局部或者局部和整体之间存在自相似 性，那么这个物质就是分形。正是这一比较“模糊”的概念被人们普遍接受，同 时也促进了分形的发展。 根据自相似性的程度，分形可分为有规分形和无规分形。有规分形是指具有 严格的自相似的分形，比如，三分康托集，Koch 曲线。无规分形是指具有统计 意义上的自相似性的分形，比如，曲折的海岸线，漂浮的云等。 2. 分形图的递归算法 2.1 三分康托集 1883年，德国数学家康托(G.Cantor)提出了如今广为人知的三分康托集。三 分康托集是很容易构造的，然而，它却显示出许多最典型的分形特征。它是从单 位区间出发，再由这个区间不断地去掉部分子区间的过程构造出来的(如图 1) 其详细构造过程是：第一步，把闭区间[0，1]平均分为三段，去掉中间的 1/3 部分段，则只剩下两个闭区间[0，1/3]和[2/3，1]。第二步，再将剩下的两个闭 区间各自平均分为三段，同样去掉中间的区间段，这时剩下四段闭区间：[0，1/9]， [2/9，1/3]，[2/3，7/9]和[8/9，1]。第三步，重复删除每个小区间中间的 1/3 段。如此不断的分割下去， 最后剩下的各个小区间段就构成了三分康托集。 三 分康托集的 Hausdorff维数是 0.6309。 图 1 三分康托集的构造过程 Cantor三分集的递归算法设计为构造一个函数为 ( , , , )Cantor ax ay bx by ， 其中 ( , )ax ay 和 ( , )bx by 分别代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 初始位置端点的坐标。取 err为递归终止的极小 量，取 h为不同层次线段之间的距离，且设出 ( , )cx cy 和 ( , )dx dy 如图 2 图 2 建立 Cantor三分集模型 其核心算法就是在 Cantor函数内递归调用 Cantor函数， ( , , , )Cantor ax ay bx by { plot([ax,bx],[ay,by]); %画出每个层次上的图形 if (bx-ax)>err %设定有限次递归 { cx = ax + ( bx – ax ) / 3; cy = ay – h; dx = bx – ( bx – ax ) / 3; dy = by – h; ay = ay – h; by = by – h; Cantor(ax,ay,cx,cy); %内部调用 Cantor函数 Cantor(dx,dy,bx,by); %内部调用 Cantor函数 } } 最后实现的结果如图 3所示 图 3 Cantor三分集结果 推而广之，假如我们在平面上构造康托集，那么最终生成的集合称为康托尘。 康托尘的构造和三分康托集的构造很相似，它是将一个正方形分割成 16 个小正 方形，保留其中的四个，去掉其它的小正方形，依次类推，无限的循环下去。康 托尘具有和康托集相似的性质，这里不在论述。如果去掉不同的正方形，所获得 的集合是不同的。 2．2 Koch 曲线 1904年，瑞典数学家柯赫构造了 “Koch曲线”几何图形。Koch曲线大 于一维，具有无限的长度，但是又小于二维，并且生成的图形的面积为零。它和 三分康托集一样，是一个典型的分形。根据分形的次数不同，生成的 Koch 曲线 也有很多种，比如三次 Koch 曲线，四次 Koch 曲线等。下面以三次 Koch 曲线 为例，介绍 Koch 曲线的构造 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，其它的可依此类推。 三次 Koch 曲线的构造过程主要分为三大步骤：第一步，给定一个初始图形 一条线段；第二步，将这条线段中间的 1/3 处向外折起；第三步，按照第二步 的方法不断的把各段线段中间的 1/3 处向外折起。这样无限的进行下去，最终 即可构造出 Koch曲线。其图例构造过程如下图 4所示(迭代了 6 次的图形) 图 4 Koch曲线生成过程 无可否认，Koch曲线的生成过程是简单的，但其曲线又是复杂的。首先，它 有很多个折点，而且这些折点是不可微的，当然也就没有切线了。其次，Koch 曲线在许多方面的性质与三分康托集列出的那些性质类似，它由四个与总体相似 的“四分之一”部分组成，但是比例系数是 1/3。它在任何尺度下的不规则性反 映了它的精细结构，但是这样错综复杂的构造却出自于一个基本的简单结构。 在设计 Koch曲线的递归算法时参考 Cantor集的方法，先建立一个模型如下， 图 5 Koch曲线模型 其中令 L为线段长度，a为基线与水平线正方向夹角。同样设 err为递归的终极 小量，其核心算法如下， ( , , , )Koch ax ay bx by { err=1; %递归终极小量 line([ax bx],[ay by])；hold on; %画出图形 if ((bx-ax)^2+(by-ay)^2)>err %递归终止条件 { cx=ax+(bx-ax)/3; cy=ay+(by-ay)/3; ex=bx-(bx-ax)/3; ey=by-(by-ay)/3; L=sqrt((ex-cx)^2+(ey-cy)^2); %计算 L alpha=atan((ey-cy)/(ex-cx)); %计算 a if((ex-cx)<0) { alpha=alpha+pi; %图形旋转 } dy=cy+sin(alpha+pi/3)*L; dx=cx+cos(alpha+pi/3)*L; Koch(ax,ay,cx,cy); %递归调用 Koch(ex,ey,bx,by); Koch(cx,cy,dx,dy); Koch(dx,dy,ex,ey); } } 最后实现的结果如图 6所示 图 6 Koch曲线生成结果 2.3 Sierpinski垫片的递归算法 在 Cantor 集与 Koch 集的基础上继续讨论 Sierpinski 垫片的生成算法，同 样先建立模型如下图 7，同时展示生成后的图形. 图 7 Sierpinski垫片模型 图 8 Sierpinski垫片效果图 其中先设定正三角形中心点坐标为 ( , )x y ，边长为 L，迭代深度为 n，三角形 顶点分别为 ( , ), 1,2,3.i ix y i = 且下一层正三角形的中心坐标为 ( , ), 01,02,03.i ix y i = 故 Sierpinski垫片的递归算法设计如下， ( , , , )Sierpinski x y L n {if (n==1) x1=x-L/2; y1=y-L/2*tan(pi/6); x2=x+L/2; y2=y-L/2*tan(pi/6); x3=x; y3=y+L/2*tan(pi/6); line([x1 x2],[y1 y2],'Color','r','LineWidth',2); hold on; line([x2 x3],[y2 y3],'Color','g','LineWidth',2); hold on; line([x3 x1],[y3 y1],'Color','y','LineWidth',2); hold on; else x01=x-L/4; y01=y-L/4*tan(pi/6); x02=x+L/4; y02=y-L/4*tan(pi/6); x03=x; y03=y+L/2*tan(pi/6); Sierpinski(x01,y01,L/2,n-1); %递归调用 Sierpinski(x02,y02,L/2,n-1); Sierpinski(x03,y03,L/2,n-1); end } 程序的运行结果如图 9_1和图 9_2， 图 9_1 n=6时 Sierpinski垫片生成图 图 9_2 n=10时 Sierpinski垫片生成图 2.4分支结构分形递归算法 研究如下图的分支结构图的递归算法 图 10 分支结构分形图 细分此分支结构，建立模型如下，其中取 A为起点，且记 A点坐标为 ( , )x y ， B 点坐标为 1 1( , )x y ，线段 ,AB L= 2 . 3 BC BD L= = 且设定 AB 与水平面的夹角为 alpha, 递归深度为 n. 故分支结构图的生城算法设计如下 ( , , , , )Ramus x y alpha L n if n>0 x1=x+cos(alpha)*L; y1=y+sin(alpha)*L; line([x,x1],[y,y1],'Color','g','LineWidth',2); alpha_L=alpha+pi/8; alpha_R=alpha-pi/8; L=2*L/3; Ramus(x1,y1,alpha_L,L,n-1); %递归调用 Ramus(x1,y1,alpha_R,L,n-1); end 设定 , 4 p a = 算法的生成效果如下图 11- 1， 图 11-1 分支结构生成图 设定 , 2 p a = 算法的生成效果如下图 11-2， 图 11-2 分支结构生成图 2.5分形树递归算法 研究如下图的分形树的递归算法， 图 12 分形树效果图 细分分形树图像，建立如下简单的模型，其中对于参数我们有， a为主干生长方向与水平面的夹角； b为侧干与主干的夹角；g 为主干偏转 角度。且令 1 1s = ，其为长度小量，用以控制递归深度；令 2 2s = ，其为长度小 量，用以控制递归深度；最后令 3 1.2s = ，其为长度小量，用以控制递归深度； 图 13 分形树简单模型 有图可知，对于变量的设置，我们有， 取主干线段 AB L= ，令 A点坐标为 ( , )x y ，中间 C点坐标为 1 1( , )x y ，主干终 点 B 点坐标为 2 2( , )x y ；且第一左分支终点 D 的坐标为 1 1( , )x L y L ；第一右分支终 点 E的坐标为 1 1( , )x R y R ；第二左分支终点 F的坐标为 2 2( , )x L y L ；第二右分支终 点 F的坐标为 2 2( , )x R y R . 故分形树递归算法设计如下 ( , , , )tree x y L alpha if L>s1 x2=x+L*cos(A); y2=y+L*sin(A); x2L=x2+L/s2*cos(A+B); y2L=y2+L/s2*sin(A+B); x2R=x2+L/s2*cos(A-B); y2R=y2+L/s2*sin(A-B); x1=x+L/s2*cos(A); y1=y+L/s2*sin(A); x1L=x1+L/s2*cos(A+B); y1L=y1+L/s2*sin(A+B); x1R=x1+L/s2*cos(A-B); y1R=y1+L/s2*sin(A-B); line([x,x2],[y,y2],'Color','g','LineWidth',2);hold on; line([x2,x2L],[y2,y2L],'Color','g','LineWidth',2);hold on; line([x2,x2R],[y2,y2R],'Color','g','LineWidth',2);hold on; line([x1,x1L],[y1,y1L],'Color','g','LineWidth',2);hold on; line([x1,x1R],[y1,y1R],'Color','g','LineWidth',2);hold on; tree(x2,y2,L/s3,A-C); tree(x2L,y2L,L/s2,A+B); %递归调用 tree(x2R,y2R,L/s2,A-B); tree(x1L,y1L,L/s2,A+B); tree(x1R,y1R,L/s2,A-B); end 故设定 , 2 p a = , . 3 8 a a b g= = 可以得出分形树的生成图如下 图 14 分形树生成图 3.文法构图算法 3.1 LS文法 一维的 LS文法绘图规则为： 1.字母表：L，R 2.生成规则：L→R，R→L R 举例如下，初始字母为 R时，则有 R→L R→R L R →L R R L R→R L R L R R L R →L R R L R R L R L R R L R→…… 3,如下图 15所示 图 15 文法构图效果 二维的 LS文法绘图规则为： F：以当前方向前进一步，并画线； f：以当前方向前进一步，不画线； ＋：逆时针旋转角； －：顺时针旋转角； [：将当前信息入栈； ]：将“[”时刻的信息出栈。 3.2 单一规则的 LS文法生成 探讨 2.2中所讨论的 Koch曲线的 LS文法构图规则，建立文法构图模型如下 图 16 Koch曲线的 LS文法构图模型 由此可将 Koch曲线的 LS文法构图模型描述为， 字母表设置 :w F； 旋转角度设置 3 p d = ； LS文法生成规则为 :P F F F F F® + - - + ； 则文法图的生成步骤为， 步骤 0：F 步骤 1：F ＋ F － － F ＋ F 步骤 2： F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F － － F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F 步骤 3： F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F － － F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F － － F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F － － F ＋F － － F ＋F ＋ F ＋ F － － F ＋ F － － F＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F ＋ F ＋ F － － F ＋ F － － F＋ F － － F ＋F ＋ F ＋ F － － F ＋ F 以此类推 …… . 一条由左向右延伸的线段，长度为 3F，如果把它的中间一段替换为一个没有 底的等边三角形，就成了图中下部所示的折线。变换前后，两种图形起点到终点 之间的距离不变。接下去，如果再把图形中每一条线段都替换为相应的折线，并 不断重复下去，最终就形成了 Koch曲线。 图 17 koch曲线 LS文法图生成模型 三条相同的 Koch曲线首尾顺次相连，就构成了 Koch雪花。Koch雪花的 LS 算法如下： Omega = F++F++F； Omage的意义是 3条线首尾顺次相连，每一条画完之后转 120度继续画 Delta = 60o； P : F -> F+F—F+F； P所表明的迭代方式是：画一段直线，右转 60度（这里绘制的方向与上图例 中的绘制方向是对称的），再画一段，再左转 120度，再画一段，再右转 60度， 再画最后一段，这就是一条折线即 Koch曲线的绘制过程，是用来替代原来此位 置的一条直线段。 设置其中的变量如下 :L 线段长度； :a 基线与水平方向的夹角； :d 偏转生成角度； :befx 起始点横坐标； :aftx 终止点纵坐标； :befy 起始点横坐标； :afty 终止点纵坐标； 1:str 被替换字符串； 2 :str 替换字符串； :y 所生成的 LS文法字符串； :n 字符串替换次数； 绘制 Koch雪花的 Matlab程序及其运行结果如下所示： %变量初始化 str1='F'; %被替换字符串 str2='F+F--F+F'; %替换字符串 L=5; alpha=0; delta=pi/3; befx=100; befy=150; n=5; y=str1; %生成文法字符串 for i=1:n state=''; yL=length(y); j=1; while j<=yL if y(j)=='F' state=strcat(state,str2); j=j+1; else state=strcat(state,y(j)); j=j+1; end end y=state end %根据生成的文法绘制 KOCH曲线的 LS图形 for k=1:length(y) if y(k)=='F' aftx=befx+L*cos(alpha); afty=befy+L*sin(alpha); line([befx,aftx],[befy,afty],'Color','b','LineWidth',2); befx=aftx; befy=afty; elseif y(k)=='+' alpha=alpha+delta; else alpha=alpha-delta; end end 生成效果图如下，取 5n = 的结果 图 17 koch曲线 LS文法效果图 3.3 多规则的 LS文法生成 进一步探讨 2.3中 Sierpinski垫片的 LS文法图算法，首先建立 Sierpinski 垫片的文法构图规则如下， 1 2 : : 60 : : w LR P L R L R P R L R L d ® + - - + ® - + + - o 显然与 Koch曲线的 LS图相比，此处有两种不同的文法映射，最后要完成的 Sierpinski垫片 LS文法效果图如下， 图 18 Sierpinski垫片 LS文法效果图 设置其中的变量如下 :L 线段长度； :a 基线与水平方向的夹角； :d 偏转生成角度； :befx 起始点横坐标； :aftx 终止点纵坐标； :befy 起始点横坐标； :afty 终止点纵坐标； :w 初始字符串； Re 1:str P1对应的替换字符串； Re 2 :str P2对应的替换字符串 :y 所生成的 LS文法字符串； :n 字符串替换次数； 绘制 Sierpinski垫片 LS文法图的 Matlab程序及其运行结果如下所示： %变量初始化 w='LR'; Restr1='+R-L-R+'; Restr2='-L+R+L-'; L=5; alpha=0; delta=pi/3; befx=100; befy=100; n=8; y=w; %生成文法字符串 for i=1:n state=''; yL=length(y); j=1; while j0 theta=atan(wy/wx); elseif wx<0 theta=pi+atan(wy/wx); else theta=pi/2; end theta=theta/2; r=sqrt(wx^2+wy^2); p=rand(1); if p<0.5 r=sqrt(r); else r=-sqrt(r); end zx(i+1)=r*cos(theta); zy(i+1)=r*sin(theta); end plot(plotx(100:end),ploty(100:end),'b.') 取 0.75 0.35C i= - - 生成 Julia集如下 图 24 Julia集生成图 5.逃逸时间算法 逃逸时间算法，假设有一个充分大的整数 N，当未逃逸区域 M 中的初始 点 a 经过小于 N 次迭代就达到未逃逸区域 M 的边界，甚至超出了边界，我 们就认为点 a 逃逸出去了；而如果经过 N 次迭代后 a 的轨迹仍未达到 M 的 边界，我们就认为 a 是 A 上的点。用这样的方法绘制出 A 的边界图形，这 便是逃逸时间算法的基本思想。 5.1 Julia集逃逸时间算法 设 2( )F Z Z C= + ，当 0.C = 时，由于 z是复数，即 z=x+yi，则有 2 2 2 2( ) 2Z x yi x y xyi= + = - + 设复数 z=x+yi的绝对值，即 2 2Z x y= + 则 2 20 0 0 0 0( ) 2F z x y x y i= - + 2 2 2 20 0 0 0( ) (2 )x y x y= - + 4 4 2 20 0 0 04x y x y= + + 2 20 0x y= + 2 0Z= 若 0<|z0|<1, |F(z0)|<| z0|，对于每一次迭代 z趋向 0，即 z向 0收敛。 若|z0|>1, 经过迭代 z会趋向无穷，z向无穷逃逸，且 z是平面上的单位圆。 当 c≠0时，其吸引子不再是 0，而是一个区域，称混沌区。如图，假设有一 个充分大的整数 N，当未逃逸区域 M中的初始点 a经过小于 N次迭代就达到未逃 逸区域 M的边界，甚至超出了边界，我们就认为点 a逃逸出去了；而如果经过 N 次迭代后 a的轨迹仍未到达 M的边界，我们就认为，a是 A上的点。用这样的方 法，描绘出 A的边界图形。见下图 设置 Julia集的逃逸时间算法设计为 xres = 2000;%x resolution yres = 2000;%y resolution x = linspace(-1.5,1.5,xres); y = linspace(-1.5,1.5,yres); c = zeros(length(y),length(x)); xn= 0; yn= 0; xnew = 0; ynew = 0; lenx = length(x); leny = length(y); zval = zeros(lenx,leny); %array containing iterations for each julia set iter_arr=[50 200 100 50 100 100 200 100 50 ... 100 100 200 100 200 200 200]; %list of 16 constants for 16 different julia set liststr={'-0.7500-0.3500i';'-0.4000+0.6000i'; '+0.2850+0.0100i';'+0.4500+0.1428i'; '-0.7017+0.3842i';'-0.8350-0.2321i'; '-0.8000+0.1560i';'-0.2365-0.6721i'; '+0.2311+0.6068i';'-0.7322-0.2628i'; '-0.79543+0.17308i';'-0.51251+0.52129i'; '-0.81000-0.17950i';'0.36237+0.32i'; '-0.4959345-0.52287731i';'-0.4942345+0.52287731i'}; [s,v] = listdlg('PromptString','Select any one',... 'SelectionMode','single',... 'ListString',liststr); if v==1 an=liststr{s}; a = real(str2num(an)); b = imag(str2num(an)); h_msg = msgbox(' Please Wait ',' '); iter = iter_a