分形大自然的几何学课件.ppt

第,1,页,/,共,66,页,第,2,页,/,共,66,页,第,3,页,/,共,66,页,-,四川文理学院,计算机科学系,王安志,第,4,页,/,共,66,页,在过去，一个人如果不懂得“熵”是怎么回事，,就不能说是科学上有教养的人；,在将来，一个人如果不能同样熟悉分形，他就,不能被,认为是科学上的文化人。,-,著名理论物理学家约翰,惠勒,(J.Wheeler),第,5,页,/,共,66,页,分形几何产生的背景,?,在经典的欧氏几何中，我们可以用直线、圆,锥、球等这一类规则的形状去描述如墙、车,轮、道路、建筑物等人造物体。,第,6,页,/,共,66,页,分形几何产生的背景,?,但在自然界中，却存在很多“不规则”的、,“不可名状的”、“病态的”复杂的几何,对象，如山脉、云烟、波浪、树木、闪电，,以及星团、短痕、浸润、冲积扇、泥裂、,冻豆腐、水系、晶簇、蜂窝石、小麦须根,系、树冠、支气管、星,系、材料断口、小,肠绒毛、大脑皮层,第,7,页,/,共,66,页,第,8,页,/,共,66,页,第,9,页,/,共,66,页,?,这些对象如何描述和研究？,?,如何用计算机来生成？,?,用经典几何图形来描述？,Never,！人们发现，,传统的数学模型苍白无力！因为它们不再,具有我们所早已熟知的连续、光滑可微这,一基本性质了。,第,10,页,/,共,66,页,分形几何的历史,?,萌芽期：十九世纪末，二十世纪初,.,Cantor,集，,Weierstrass,函数等的提出,.,?,形成期：二十世纪六、七十年代,.,Mandelbrot,的大量工作,.,1.1967,年，,Science,英国的海岸线有多长？,2.1975,年，分形对象：形，机遇和维数,.,分形,(fractal),这个词源于这本书,.,它从拉丁语,“,fractus”,意思是“不规则的或者断裂的”,派生来的,.,第,11,页,/,共,66,页,分形几何的历史,?,发展期：二十世纪八十年代至今,.,1.Hutchinson,1981,分形与自相似,.,给出了自相似集合的数学理论基础,.,2.Mandelbrot,1982,自然界的分形几何,.,3.Barnsley,1988,Fractal everywhere,.,4.Falconer,1990,分形几何,数学基础,及其应用,.,第,12,页,/,共,66,页,德国数学家维尔斯特拉斯这位分析学大师在,1872,年发现了处处连续但处处不可微分的函数：,这一结果的发表曾经使数学界为之震惊。现在,维尔斯特拉斯函数已有许多变形。例如：,第,13,页,/,共,66,页,英国的海岸线有多长？,测量方法,：,我们想象一个人沿着一段海岸线拣尽可,能短的道路步行，并规定每步长度不超过,，,设这样测得的海岸线长度为,L(,).,然后重新开,始，并使他在海岸线上最长的步长越来越短。,用一只小老鼠代替人测量。,用苍蝇代替小老鼠测量。,测量结论,：随着步长,越来越短，我们测量出,来的海岸线长度越来越长。,第,14,页,/,共,66,页,英国的海岸线有多长？,第,15,页,/,共,66,页,动力系统（迭代）的问题,第,16,页,/,共,66,页,Julia,集,第,17,页,/,共,66,页,第,18,页,/,共,66,页,Julia,集,第,19,页,/,共,66,页,Mandelbrot,集,第,20,页,/,共,66,页,牛顿行星,非线性系统中的分形吸引域,第,21,页,/,共,66,页,分形的定义和特征,?,F,具有精细的结构。分形图不管被放大多少倍，都,能看到细节具有与整体相似的结构，这一特征非常,接近于自然界中大多数的对象。,?,F,是不规则的，其整体与局部都不能用传统几何学,来描述；,?,F,通常具有自相似形式,(,统计意义上的自相似,),；,?,自仿射性,即局部到整体在不同方向上存在不等比例,变换；,?,分数维。描述自相似性的一个重要参数，为认识世,界中的复杂形态提供了一个新的尺度，在复杂性科,学的研究过程中，分维是测量这些形态复杂度的一,种度量，是人们对复杂性做定量分析的工具。,?,在大多数情形下，,F,可通过简单的迭代过程产生。,第,22,页,/,共,66,页,分形几何的研究对象,自相似集,?,Cantor,集,?,Sierpinski,垫片,?,Koch,曲线,?,海岸线,?,分形图像压缩,?,分形山,?,分形植物模拟,?,。,第,23,页,/,共,66,页,Cantor,集,C,第,24,页,/,共,66,页,?,1883,年，康托尔,(G.F.P.Cantor,1845-1918),构造了,三分集，也叫康托尔非连续统,(Cantor di,scontinuum),。,?,1890,年，皮亚诺,(G.Peano,1858-1932),提出充满空,间的曲线,皮亚诺曲线。,?,1891,年，希尔伯特,(D.Hilbert,1862-1943),在数学,年刊,(Mathematische Annalin),上发表短文，提出,了能充满平面区域的著名的希尔伯特曲线。,?,1904,年，瑞典数学家柯赫,(H.von Koch,1870-1924),构造出柯赫雪花曲线。,第,25,页,/,共,66,页,?,1915-1916,年，波兰数学家谢尔宾斯基,(W.Sierpinski,1882-1969),构造了谢氏曲线、,海绵、墓垛。谢氏地毯是平面万有曲线,(plane,universal curve),谢氏海绵是空间万有曲线。,?,1918-1920,年左右，法国数学家朱丽亚,(G.Julia,1893-1978),、法图,(P.J.L.Fatou,1878-1929),研究复迭代。朱丽亚于,1918,年,(,当时他,25,岁,),在纯粹数学与应用数学杂志,上发表了长达,199,页的杰作，一举成名。,?,1924,年,11,月,20,日,Mandelbrot,生于波兰。,第,26,页,/,共,66,页,Koch,曲线,第,27,页,/,共,66,页,第,28,页,/,共,66,页,雪花曲线,三段,Koch,曲线连在一起构成,随机,Koch,曲线,对海岸线的模拟,第,29,页,/,共,66,页,第,30,页,/,共,66,页,Sierpinsk,垫片的生成过程,第,31,页,/,共,66,页,L,系统,L,系统是一个基于字符串的并行重写系,统，其核心概念就是重写。,“重写”的基本思想：通过对植物形,态结构进行经验总结、概括和抽象，可预,先定义出一系列的生长规则和初始状态,根,据生成规则最终得到模拟对象。,第,32,页,/,共,66,页,表,1,字符串替换过程,Tab.1 string replacement process,迭代次数,生成规则,生成结果,开始,公理,Q,第一次,QP,P,第二次,PPQ,PQ,第三次,PPQ;QP,PQP,第四次,PPQ;QP,PQPPQ,第五次,PPQ;QP,PQPPQPQP,第六次,PPQ;QP,PQPPQPQPPQPPQ,第七次,PPQ;QP,PQPPQPQPPQPPQPQPPQPQP,第,33,页,/,共,66,页,开始,设定公理、产生式集、初始,点、初始角度、迭代次数,迭代上限,改写产生式，生成,新字符串,迭代次数加,1,龟形解释并绘图,结束,N,Y,三维,Sierpinski,金字塔,三维,Sierpinski,海绵,3-D Sierpinski 3-D Sierpinski,20,:F,P:F,FF+F-F-F-F+F+F,?,?,?,?,?,?,?,?,?,o,25,:F,P:F,F+FF-F+F,?,?,?,?,?,?,?,?,?,o,(a),(b),单规则,L,系统模拟的植物,plant simulation based on Single rules L-system,?,?,?,?,?,?,1,2,3,P,1,P,2,P,3,25,:F,:,F,F+FF-FF,:,F,F+FF-F+F,:,F,FF-F+F+F+F-F-F,P,P,P,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,o,同一个随机,L,系统,4,次产生的不同植物形态,4 different plant morphology generated by a stochastic L-system,用微分,L,系统模拟的植物连续生长过程,Continuous simulation of plant growth process using dL-system,通常在所模拟对象的植物学意义较为明确的情况下，上下,文相关,L,系统用来表达植物体内部各部分之间的相互影响。,以,Hogeweg,和,Hesper,应用,2L,系统构造的植物图形为例：,n,30,22.5,#,:,1,1,1,0,0,0,0,0,0,1,1,F1F1,0,1,0,1,0,1,1,1,1,0,0,0,1,0,1,1F1,1,1,0,0,1,1,1,0,*,*,*,*,ignore,F,F,F,F,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,o,n,30,22.5,#,:,1,1,1,0,0,0,1,0,0,1,1,F1F1,0,1,0,1,0,1,1,1,1,0,0,0,1,0,1,1F1,1,1,0,1,1,1,1,0,*,*,*,*,ignore,F,F,F,F,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,o,n,26,22.5,#,:,1,1,1,0,0,0,0,0,0,1,1,F1F1,0,1,0,1,0,1,1,1,1,0,0,0,1,0,1,1F1,1,1,0,1,1,1,1,0,*,*,*,*,ignore,F,F,F,F,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,o,DLA,算法,迭代函数系统,(IFS),一个迭代函数系统由一组满足一定条件,的映射函数,及一组变换发生的概率,Pi,组成。,可表示为,IFS=(i,Pi),i=1,2,3 n.,对应于每,一个,n,有一个伴随概率,0Pn1,，且,Pn=1,。,压缩映射集,n,和对应的伴随概率,Pn,确定,了,IFS,码。由分形空间的压缩映射定理可知，,如果获取了某个给定图形的,IFS,码，则用较少,的代码就可以生成极为复杂的分形图。,仿射变换参数的赋值,初始点,(x0,y0),、迭代次数,NUM,及总画点,数,POINT,的初始化,生成随机数以决定执行哪一个变换,Wi,(x1,y1)=Wi(x0,y0),x0=x1,y0=y1,n+,画点,(x0,y0),m+,nNUM,mPOINT,结束,开始,Yes,NO,NO,Yes,随机,IFS,生成图形的流程图,IFS,分形树的拼贴示意图,IFS,分形树,分形树的,IFS,码,IFS-code of fractal tree,i,ai,bi,ci,di,ei,fi,pi,1,0.195,-0.49,0.35,0.44,0.44,0.25,0.2,2,0.461,0.415,-0.25,0.436,0.25,0.57,0.2,3,-0.055,-0.07,0.45,-0.11,0.6,0.1,0.25,4,-0.035,0.07,-0.47,-0.022,0.49,0.505,0.15,5,-0.635,0,0,0.5,0.855,0.25,0.1,6,0.08,0.25,-0.12,0.15,0.805,0.7,0.1,Barnsley,也指出，迭代函数系统并不仅,仅用于描述分形图形。常用于图像的压缩和,变换。,另外，用于,IFS,的仿射变换必须是压缩仿,射变换，,IFS,的保形性取决于它的收缩性。,对某一个静态场景的分形压缩,分形山,分形山,分形图形艺术,根据非线性科学原理，通过计算机数值计算，,生成某种同时具有审美情趣和科学内涵的图形、,动画，并以某种方式向观众演示、播放、展览，,这样的一门艺术叫做,分形图形艺术,。,科学求“真”的同时，也求“善”，也求,“美”。科学家有探索真理的自由，但真理并不,只是某种“,符合”，科学家对社会承担责任。科,学家探索自然、社会和人生，追求简单性，追求,规律之美。,分形图形艺术的特点,?,第一，有科学内涵，作品有内在的数学结,构；,?,第二，一般采用计算机数值计算；,?,第三，画面一般具有多重自相似结构；,?,第四，有后现代主义的风味，一般不强调,作品的稀缺性，美感是其第一考虑。,性命圭旨中的“化身五五图”,芒德勃罗集局部的一个“五五分形”过程,国王映射图谱,1994,年“科学与艺术奇才”皮克欧沃,(C.A.Pickover),出版了混沌奇境：分形世界虚拟历险记,三翅鹰映射图谱,第,61,页,/,共,66,页,第,62,页,/,共,66,页,第,63,页,/,共,66,页,第,64,页,/,共,66,页,第,65,页,/,共,66,页,第,66,页,/,共,66,页,