分形算法与程序设计

参考书：《分形算法与程序设计》1第1章初识分形1.1Fractal的含义1.2分形的几何特征1.3分形的度量1.4分形维数1.5分形是一种方法论1.6分形与计算机图形学参考书：《分形算法与程序设计》21.1Fractal的含义英文单词Fractal，在大陆被译为“分形”，在台湾被译为“碎形”。它是由美籍法国数学家曼德勃罗（BenoitMandelbrot）创造出来的。其含义是不规则的、破碎的、分数的。曼德勃罗是想用此词来描述自然界中传统欧几里得几何学所不能描述的一大类复杂无规的几何对象。参考书：《分形算法与程序设计》31.2分形的几何特征自相似性自相似，便是局部与整体的相似。自仿射性自仿射性是自相似性的一种拓展。如果，将自相似性看成是局部到整体在各个方向上的等比例变换的结果的话，那么，自仿射性就是局部到整体在不同方向上的不等比例变换的结果。前者称为自相似变换，后者称为自仿射变换。精细结构任意小局部总是包含细致的结构。参考书：《分形算法与程序设计》41.3分形的度量（1）长度的测量Length(n=0)=1Length(n=1)=4/3Length(n=2)=16/9…………Length=lim(Length(n))=lim(4/3)=∞n→∞n→∞n参考书：《分形算法与程序设计》51.3分形的度量（2）面积的测量Area(n0)=(1╳√3/6)/2=√3/12Area(n1)=√3/12╳(4/9)Area(n2)=√3/12╳(4/9)2…………Area(n)=lim(√3/12╳(4/9)n)=0n→∞如上所述，koch曲线在一维欧氏空间中的度量为∞，在二维欧氏空间中的面积为0。如此看来，Koch曲线在传统欧氏空间中不可度量。参考书：《分形算法与程序设计》61.4分形维数分形维数是分形的很好的不变量，它一般是分数，用它可以把握住分形体的基本特征。图a是边长为1的正方形，当边长变成原来的1∕2时，原正方形中包含4个小正方形，如图b，而4=22；图c是边长为1的正立方体，当边长变成原来的1∕2时，原正立方体中包含8个小正立方体，如图d，而8=23。则有N＝kD,D=log(N)/log(k)这样Koch曲线的分形维数D=log(4)log(3)=1.2618参考书：《分形算法与程序设计》71.4分形维数对于实际的自然景物，我们可以用计盒维数的方法测量分维。参考书：《分形算法与程序设计》81.5分形是一种方法论沃尔夫奖（WolfPrize）在颁发给分形理论创始人曼德勃罗时的评语所说的，“分形几何改变了我们对世界的看法”。分形理论至少会在三个方面改变我们对世界的认识。首先，自然界中许多不规则的形态其背后都有规则，都可以用分形的方法建立模型并在计算机上构造出以假乱真的景象来，显然利用这套方法我们可以把世界压缩到几个分形规则中，便于携带和传播。其次，许多以前被认为是随机的现象，从分形理论的角度看并不是随机的，比如布朗运动、股票价格的波动、传染病的流行传播等，这为我们控制这些貌似随机的现象奠定了理论基础。最后，分形理论中的分数维概念，为我们认识世界中的复杂形态提供了一个新的尺度。复杂性科学是现代科学的前沿，在这门科学的研究过程中，发现了许多符合分形规则的复杂形态，而分数维是测量这些形态复杂程度的一种度量。也就是说，我们找到了对复杂性做定量分析的工具。参考书：《分形算法与程序设计》91.6分形与计算机图形学分形理论的发展离不开计算机图形学的支持，如果一个分形构造的表达，不用计算机的帮助是很难让人理解的。不仅如此，分形算法与现有计算机图形学的其他算法相结合，还会产生出非常美丽的图形，而且可以构造出复杂纹理和复杂形状，从而产生非常逼真的物质形态和视觉效果。分形作为一种方法，在图形学领域主要是利用迭代、递归等技术来实现某一具体的分形构造。分形几何学与计算机图形学相结合，将会产生一门新的学科——分形图形学。它的主要任务是以分形几何学为数学基础，构造非规则的几何图素，从而实现分形体的可视化，以及对自然景物的逼真模拟。参考书：《分形算法与程序设计》10第2章分形图的递归算法2.1Cantor三分集的递归算法2.2Koch曲线的递归算法2.3Sierpinski垫片的递归算法2.4Hilbert-Peano曲线的算法2.5分支结构分形递归算法2.6分形树递归算法参考书：《分形算法与程序设计》11递归算法u直接递归调用的例子如下：voidRecur(n){……Recur(m);……}过程Recur的内部又调用了自身——Recur过程。参考书：《分形算法与程序设计》12递归算法u间接递归调用的例子如下：voidRecur_A(n){……Recur_B(m);……}voidRecur_B(n){……Recur_A(m);……}参考书：《分形算法与程序设计》132.1Cantor三分集的递归算法算法：Cantor(ax,ay,bx,by)标题：Cantor三分集的递归算法参数：c（终止递归的小量）d（不同层次线之间的距离）变量：ax,ay（曲线端点坐标）bx,by（曲线端点坐标）cx,xy（曲线端点坐标）dx,dy（曲线端点坐标）函数：plot(x1,y1)–(x2,y2)（画直线函数）BEGINIF((bx-ax)c)THENBEGINplot(ax,ay)-(bx,by)ENDELSEBEGINplot(ax,ay)-(bx,by)cx=ax+(bx-ax)/3cy=ay+ddx=bx-(bx-ax)/3dy=by+day=ay+dby=by+dcantor(ax,ay,cx,cy)cantor(dx,dy,bx,by)ENDEND参考书：《分形算法与程序设计》142.2Koch曲线的递归算法算法：Koch(ax,ay,bx,by,c)标题：Koch曲线的递归算法参数：c（终止递归的小量）PI（π值）变量：ax,ay（线段端点坐标）bx,by（线段端点坐标）cx,xy（线段端点坐标）dx,dy（线段端点坐标）ex,ey（线段端点坐标）L（线段长度）alpha（基线与水平线正方向夹角）函数：plot(x1,y1)–(x2,y2)（画直线函数）sin()（正弦函数）cos()（余弦函数）ArcTan()（反正切函数）sqrt()（开平方函数）参考书：《分形算法与程序设计》152.2Koch曲线的递归算法BEGINIF((bx-ax)*(bx-ax)+(by-ay)*(by-ay))cTHENBEGINplot(ax,ay)-(bx,by)ENDELSEBEGINcx=ax+(bx-ax)/3cy=ay+(by-ay)/3ex=bx-(bx-ax)/3ey=by-(by-ay)/3L=sqrt((ex-cx)*(ex-cx)+(ey-cy)*(ey-cy))alpha=ArcTan((ey-cy)/(ex-cx))IF((ex-cx)0)THEN参考书：《分形算法与程序设计》162.2Koch曲线的递归算法BEGINalpha=alpha+PIENDdy=cy+sin(alpha+PI/3)*Ldx=cx+cos(alpha+PI/3)*LKoch(ax,ay,cx,cy,c)Koch(ex,ey,bx,by,c)Koch(cx,cy,dx,dy,c)Koch(dx,dy,ex,ey,c)ENDEND参考书：《分形算法与程序设计》172.3Sierpinski垫片的递归算法算法：Sierpinski(x,y,L,n)标题：Sierpinski垫片递归算法参数：n（递归深度）变量：x,y（三角形中心点坐标）x1,y1（三角形顶点坐标）x2,y2（三角形顶点坐标）x3,y3（三角形顶点坐标）x01,y01（小三角形中心点坐标）x02,y02（小三角形中心点坐标）x03,y03（小三角形中心点坐标）L（三角形的边长）函数：plot(x1,y1)–(x2,y2)（画直线函数）sin()（正弦函数）cos()（余弦函数）sqrt()（开平方函数）参考书：《分形算法与程序设计》182.3Sierpinski垫片的递归算法BEGINIF(n=1)THENBEGINx1=x-L/2y1=y+L*(sin(PI/6)/cos(PI/6))/2x2=x+L/2y2=y+L*(sin(PI/6)/cos(PI/6))/2x3=xy3=y-L*(sin(PI/6)/cos(PI/6))plot(x1,y1)-(x1,y1)plot(x2,y2)-(x2,y2)plot(x3,y3)-(x3,y3)ENDELSEBEGINx01=x-L/4y01=y+L*(sin(PI/6)/cos(PI/6))/4x02=x-L/4y02=y+L*(sin(PI/6)/cos(PI/6))/4x03=xy03=y-L*(sin(PI/6)/cos(PI/6))/2Sierpinski(x01,y01,L/2,n-1)Sierpinski(x02,y02,L/2,n-1)Sierpinski(x03,y03,L/2,n-1)ENDEND参考书：《分形算法与程序设计》192.4Hilbert-Peano曲线的算法算法：Peano(n)标题：Hilbert-Peano曲线递归算法变量：n（递归深度）len（线的长度）x,y（端点坐标）函数：lineto(x,y)（画直线函数）过程：a(n)（基本元素构型）b(n)（基本元素构型）c(n)（基本元素构型）d(n)（基本元素构型）参考书：《分形算法与程序设计》202.4Hilbert-Peano曲线的算法BEGINa(n)BEGINIFn0THENBEGINd(n-1)x=x-lenlineto(x,y)a(n-1)y=y+lenlineto(x,y)a(n-1)x=x+lenlineto(x,y)b(n-1)ENDENDb(n)BEGINIFn0THENBEGINc(n-1)y=y-lenlineto(x,y)b(n-1)x=x+lenlineto(x,y)b(n-1)y=y+lenlineto(x,y)a(n-1)ENDENDc(n)BEGINIFn0THENBEGINb(n-1)x=x-lenlineto(x,y)c(n-1)y=y+lenlineto(x,y)c(n-1)x=x+lenlineto(x,y)d(n-1)ENDENDd(n)BEGINIFn0THENBEGINa(n-1)y=y-lenlineto(x,y)d(n-1)x=x+lenlineto(x,y)d(n-1)y=y+lenlineto(x,y)c(n-1)ENDENDEND参考书：《分形算法与程序设计》212.5分支结构分形递归算法算法：Ramus(x,y,alpha,L,n)标题：分支结构递归算法参数：PI（π值）变量：n（递归深度）L（线段长度）x,y（线段起点坐标）x1,y1（线段终点坐标）alpha（主干生成角度）alpha_L（左支干生成角度）alpha_R（右支干生成角度）函数：plot(x1,y1)-(x2,y2)（画直线函数）sin()（正弦函数）cos()（余弦函数）参考书：《分形算法与程序设计》222.5分支结构分形递归算法BEGINIF(n0)THENBEGINx1=x+cos(alpha)*Ly1=y-sin(alpha)*Lplot(x,y)-(x1,y1)alpha_L=alpha+PI/8alpha_R=alpha-PI/8L=2*L/3Ramus(x2,y2,alpha_L,L,n-1)Ramus(x2,y2,alpha_R,L,n-1)ENDEND参考书：《分形算法与程序设计》232.6分形树递归算法算法：tree(x,y,L,alpha)标题：分形树递归算法参数：PI（π值）A（主干生长方向）B（侧干与主干的夹角）C（主干偏转角度）s1（长度小量，控制递归深度）s2（主干与侧干之比）s3（上一级主干与下一级主干之比）变量：L（主干的长度）x,y（主干起点坐标）x1,y1（中间分叉点坐标）x2,y2（主干终点坐标）