论文 分形图形的计算机 实现.doc

南京大学金陵学院毕 业 论 文（设 计）作 者:黄耕毓学 号：2011021199014系 部:计算机科学与工程系专 业:电子信息技术与科学（方 向）:（三号楷体）题 目:分行图形的计算机实现（内容过长可分两行）指导老师于广亮副教授提交日期2011年5月15日南京大学金陵学院 毕业设计（论文） 分形图形及其计算机实现摘 要分形理论是近十多年才开始兴起与发展的一门学科，其主要描述自然界和非线性系统中不光滑和不规则的集合形体。它有很广泛的应用，如数学、物理、化学、材料科学、生物与医学、地质与地理学、地震和天文学以及计算机科学等。所以对分形理论的研究有重要意义，具有非常广泛的实际应用价值。本文主要阐述了什么是分形理论和分形图形，在了解分形理论的基本只是和分形的几何维数的基础上，用计算机实现了分形图形的形成。以c+，vb、tc、mytc作为软件开发的工具，实现了对一些经典分形图形的绘制，在计算机上实现了迭代分形图、koch曲线、分形树等经典图形。通过对一些参数的修改，从而改变了分形图形的形状，位置等属性。在计算机图形中引用分形理论，可以生成许多美丽纷繁的艺术图形，计算机与艺术很好的结合在一起。此外分形图形在生物学、地球物理学、天文学等学科中也有广阔的应用空间。关键词：分形；分形图形; 迭代函数系统；ABSTRACTFractal theory is a science newly started and developed in the past several ten years ,it can describe roughness and irregular geometric shapes the nature or in non-linear system .Fractal theory is extensive applied to many fields, such as mathematics ,physics ,chemistry ,material science ,biology and medicine ,geography ,earthquake and astronomy ,computer science and so on.So the research on fractal theory has both theoretical significance and extensive applied value.This article mainly expounds what is the fractal theory and fractal graph.In understanding the basic is of fractal theory and fractal geometry dimension,Using computer to realize the formation of fractal graphics .the paper can realized the software of drawing fractal graphics using C/VB/TC/MYTC language,On the computer for iterative fractal graph,Koch curve,fractal tree classic graphics,etc.Through modification of some parameters,which changed the shape of the fractal graphics,positioning properties .Quote fractal theory in computer graphics, graphics can generate many beautiful intricate art, computer art and very good together. Besides the fractal graphics in disciplines such as physics, astronomy, biology, earth also has a broad application space.Keywords: fractal; fractal graphics;IFS;目录第一章 绪论1.1非线性科学- 1 -1.1.1什么是非线性科学- 1 -1.1.2非线性问题研究的历史概况- 2 -1.2课题研究的背景- 2 -1.3课题研究的主要内容- 3 -1.4课题研究的目的及意义- 3 -1.5课题研究的方法- 4 -第二章 分形理论与分形图形- 4 -2.1分形理论及其基本概念- 5 -2.1.1分形的定义- 6 -2.1.2分维的定义- 7 -2.1.3分形的特征- 7 - 2.2分形图及其计算机图形- 8 -2.2.1分形图形艺术的概念- 8 -2.2.2分形图形的特征- 8 -第三章 分形图形的计算机实现方法- 10 -3.1典型的分形集- 10 -3.2 各种曲线的设计方案- 11 -3.2.1 Koch 曲线的设计方案- 12 -3.2.2 Helibert 曲线的设计方案- 13 -3.3 基于L-system 的分形图形生成方法- 13 -3.4 迭代函数系统法- 15 -第四章 图形的绘制及程序实现- 16 -4.1 重复旋转与位移曲线kock- 17 -4.1.1kock图形的设计- 17 -4.1.2迭代程序设计过程- 18 - 4.2绘制Sierpinski三角形- 20 -4.2.1 希尔宾斯基三角形设计- 20 - 4.2.2 程序设计过程- 20 - 4.2.3 生成图形- 22 -4.3 软件操作- 22 -4.3.1 新工程建立- 22 -4.3.2新项目的建立与编译- 23 -4.3.3 生成图形- 23 -第五章结束语- 24 -第六章 致谢- 25 -主要参考文献- 26 -V第一章 绪论分形理论又被称为大自然的科学，阐述了自然界中大量非线性不可逆现象，是现代数学的一个新分支，为科学研究提出了新的理论与实验方法。它与动力系统的混沌理论交叉结合，相辅相成。它阐述了自然界中一些事物在某种条件下自身局部与整体的自相似性，它承认空间维数的变化既可以是离散的也可以是连续的，因而拓展了视野。值得注意的是，近年来分形理论的应用远远超过了分形理论本身的发展，尤其在物理学和数学研究中。各种分形维数计算方法和实验方法的建立、改进和完善，使之理论简便，可操作性强。分形绘画是计算机绘画的一种，脱胎于分形几何学的应用分支。它充分利用了数学公式，通过数学计算来求得每一个像素的数值，然后把众多像素组合起来就构成了奇妙的图形。分形绘画这种度他的绘画艺术所表现的是奇妙的数学结构，展现的是数学世界的瑰丽景象，它使枯燥的数学不再仅仅是抽象的哲理，从而成为很具体的感受。计算机分形绘画常常被用来描绘闪电、树枝、雪花、浮云、流水等自然现象，也被用来制作抽象风格的对称或者是不对称的图案。分形理论提出后，已经被人们作为工具，帮助人们从新的方面探索研究问题，让人们更好的了解自然与社会。1.1非线性科学1.1.1什么是非线性科学非线性是一个数学名词，不像线性两个量之间有某种正比关系。在自然科界中大部分不是有序的、平衡的、稳定的，而是处于无序的、不平衡的和随机的状态之中;当然社会科学也是如此，例如工程结构在变形比较大的情况下就要用到非线性的结构力学;在无线电技术中常要用到非线性的振荡理论;而在化学反应系统中出现的螺纹波时，它的起源要用非线性模型才能进行阐述。这类例子比比皆是，不胜枚举。1.1.2非线性问题研究的历史概况分线性问题一直是科学研究中比较难处理的，对非线性问题的处理也一直比较分散。而随着20世纪70年代分形理论的提出，分线性系统的研究却是取得了重大的突破：一方面从可积系统的一端，即从研究多自由度的非线性偏微分方程的一端获得重大进展。另一方面科学家们借用计算机，探索了原先不能用解析方法处理的非线性问题，从中得到规律性的认识，现能够从多个方面了解，探索非线性系统。1.2课题研究的背景分形这个词最早是分形的创始人曼德尔布诺特提来的，他给分形下的定义就是：一个集合形状，可以细分为若干部分，而每一部分都是整体的精确或不精确的相似形。分形这个词也是他创造的，含有“不规则”和“支离破碎”的意思。分形的概念出现很早，从十九世纪末维尔斯特拉斯构造的处处连续但处处不可微的函数，到上个世纪初的康托三分集，科赫曲线和谢尔宾斯基海绵。但是分形作为一个独立的学科被人开始研究，是一直到七十年代曼德尔布诺特提出分形的概念开始。而一直到八十年代，对于分形的研究才真正被大家所关注。分形通常跟分数维，自相似，自组织，非线性系统，混沌等联系起来出现。它是数学的一个分支，有人认为数学就是美，而分形的美，更能够被大众所接受，因为它可以通过图形化的方式表达出来。而更由于它美的直观性，被很多艺术家所青睐。分形在自然界里面也经常可以看到，最多被举出来当作分形的例子，就是海岸线，源自于曼德尔布诺特的著名论文英国的海岸线有多长。而在生物界，分形的例子也比比皆是。近20年来，分形的研究受到非常广泛的重视，其原因在于分形既有深刻的理论意义，又有巨大的实用价值。分形向人们展示了一类具有标度不变对称性的新世界，吸引着人们寻求其中可能存在着的新规律和新特征。分形理论两大基本理论为自相似和迭代，它保证了分形在一般几何变换下的不变性，即标度无关性。从不同尺度出发的自相似性，其实就是递归。分形形体中的自相似性可以是完全相同，也可以是统计意义上的相似。分形诞生在以多种概念和方法相互冲击和融合为特征的当代。随着研究的广泛深入，分形艺术的外延已经不只局限于复数迭代产生的图象了，现代分形艺术的外延等同于超级矢量。它是传统矢量绘画的扩展，放大图片的时候能在不丢失细节的前提下显现更多的细节层次。分形结合混沌的理念已经渗透到数学、理化、生物、大气、海洋以至社会学科，在音乐、美术间也产生了一定的影响。总之，分形是一门新兴的科学，作为一种新的概念和方法目前还在发展当中，被应用涉及到许多领域，同时其应用性也在许多领域中被探索与研究。美国著名的物理学家惠勒说过：今后谁不熟悉分形，谁就不能被称为科学的文化人1，正因为分形蕴含哲理，造型独特，且应用前景宽广，才能引起科学家和艺术家们的浓厚兴趣。1.3课题研究的主要内容分形理论发展到现在，分形在自然科学领域的研究已经取得了不小的进步，而在计算机实现方面还停留在初级阶段。本文从分形图形计算机实现的角度出发，发掘分形图中蕴含的价值及其设计应用；努力运用软件平台实现分形图形，并对这些分形加以了解运用，努力使这些变化纷繁的分形图，不再单单以一种数学的概念和形态出现，而是具有一定的艺术美感与功能。在课题中，将首先介绍分形理论的基本概念及其特征，探讨分形理论中蕴含的分形思想，运用计算机软件生成分形图形，了解分形图形在科学研究创作中的价值。本文通过对几种常见分形图形的介绍，对比传统的艺术图形的审美判断标准，寻找运用计算机生成的分形图形的独特处，并归纳、总结出分形图的使实用价值，同时根据其现有的应用基础，寻找更多的应用空间和平台。文中会介绍一些典型分形图形的设计理念，并对分形图的软件生成加以介绍，从而让人们能够直观的感受到分形图的计算机设计过程，拉近与分形图设计的距离，以期能更好的将分形图加以应用。1.4课题研究的目的及意义分形理论真正发展起来才十余年，目前，国内外关于分形的研究侧重于数学、物理、生命科学等方面。经过多年的探索、发现，分形理论的应用已经远远超出分形理论本身的发展，并且给分形的数学理论提出了更新更高的要求。各种分形维数计算方法和实验方法的建立、改进和完善，使之理论简便，可操作性强，计算机实现分形图形的技术越来越成熟，方法越来越多，很大程度方便了科学的研究和创作。在最初阶段，新兴的科学的发展总离不开研究人员对其基本理论的整合与归纳。本文就是出于这样的目的，对这种数学建模，编程语言实现的图形进行艺术性的分析，归纳总结出其本身蕴含的实际运用价值，让更多的人了解分形图形，为分形图形探索更多的应用空间或平台，拉近分形艺术图形与人们生活之间的距离。1.5课题研究的方法本人通过网络、书籍、报刊等资料大量收集了有关分形理论方面的知识。并仔细研观测大量分形图形。同时，分析现有的一些分形作品，借助审美心理学、美学、哲学、计算机科学等边缘科学进行综合研究。更是关注了分形发展的最新动态，了解分形理论发展与研究方向。研究分析国内外优秀分形图形相关作品，坚持理论与实践相结合的研究方法，吸取前人的成功经验，努力完成毕业设计 第二章 分形理论与分形图形分形这个词含有“不规则”和“支离破碎”的意思。分形通常跟分数维、自相似、自组织、非线性系统、混沌等联系起来出现。它是数学的一个分支，有人认为数学就是美，而分形的美，更能够被大众所接受，因为它可以通过图形化的方式表达出来。而更由于它美的直观性，被很多艺术家所青睐。它对自然科学、社会科学、数学、物理学等广泛的学科领域，提供了一种新的科学方法和思考方式。分形理论为分形图形的形成发展提供了理论依据与思想指导，分形图形则是分形理论的实践与外在表现形式。2.1分形理论及其基本概念分形是近年来提出来的一个重要理论，被誉为大自然几何学的分形是现在数学的一个新分支。但它提出了新的世界观和方法论，为科学研究提出了新的解决办法。自然界提供了许多分形实例。例如，羊齿植物、菜花和硬花甘兰，以及许多其他植物，它们的每一分支和嫩枝都与其整体非常相似。其生成规则保证了小尺度上的特征成长后就变成大尺度上的特征。分形几何学证明这些就是大自然中真实存在分形现象。近年来分形理论的应用远远超过了理论的发展。同时，用于研究分形集的数学理论与方法也有了巨大的发展，逐渐完善了分形理论自身的体系。分形理论的发展大致可分为三个阶段：第一阶段(1875年一1925年)，人们提出了典型的分形对象及其相关问题，并为讨论这些问题提供了最基本的工具。第二阶段(1926年一1975年)，人们实际上对分形集的性质做了深入的研究，特别是维数理论的研究己获得了丰富的成果。第三阶段(1975年一至今)，是分形几何在各领域的应用取得全面发展并形成独立学科的阶段。分形几何受到各国学者的进一步重视和公认，国际学术界出现一股分形热的学术空气，纷纷对分形概念作各种各样的研究和分析，特别是分形理论的研究，使一些原已死寂一般的老的学科方向焕发了新的生机2。虽然到现在为止，分形理论还是不完备的，但分形理论是一种非常深刻、有价值、让人着迷的理论，是非线性科学中最重要的概念之一。赋予人们新鲜的创造性的理论思维。2.1.1分形的定义 对于什么是分形，目前还没有严格的数学定义，只能给出描述性的定义。简单的说，分形是自身局部与整体存在自相似性的一类事物3。这类事物本身及其的零碎、不规则，无法用传统的欧几里德几何来描述，但这类事物都具有自相似性或自仿射性的特质，如多节开叉的树枝，连绵起伏的山脉，浩瀚的星系，遍布全身的血液循环管道等等，大多数分形在一定的标度范围内不断放大其任何部分，其不规则程度都是一样的，这个性质为比例自相似性;按照统计的观点，其任何局部经移位、旋转、缩放变换后与其他任意部分相似。分形为一些极其复杂、不规则的几何图形提供了新的研究方法，在现代数学中起着重要作用，同时也作为研究处理自然与社会科学中不规则图形的有力工具。在自然界中不规则的几何形态随处可见，微观世界复杂物质的结构，宏观世界浩瀚天体的演变等，更展现了层出不穷的不规则几何形态，他们往往都是分形几何的研究对象，正因为如此，分形被誉为是大自然的几何学4。1973年，曼德尔布罗特在法兰西学院讲课时，首先提出分维和分形几何的设想。1975年，他正式提出分形的概念，并从拉丁形容词fractus创造出fractal这一词5。传统几何学明确的定义了点、线、面、体。由这些几何要素构成的图形是相当规则和光滑的，至今几何形体仍被人们用来描述实物的特征6。但是传统的几何形体对于描述复杂纷繁的真实形体显得十分困难，自然界的形态有一个明显而共同的特征，就是一分再分，部分与整体呈现某种自相似性，这就需要分形语言对其进行解释。分形图形本身的自组织现象，自相似性，标度不变性对计算机图形技术的发展有重大的意义。2.1.2分维的定义在分形研究中，分维的定义并不唯一。应为测定维数的对象不同，分形维数的适用性也不相同。它是基于测度上的一个数学概念，往往笼统的把取非整数值得维数统称为分形维数，它是定量测度复杂分形客体的重要参数7。分形几何可以用来描绘自然物体的复杂性，不管其起源或构造方法如何，所有的分形都具有一个重要的特征：可通过一个特征数，即分形维数测定其不平度，复杂性或卷积度。分维恰好是正确的码尺。在一定意义上说，不规则的程度对于物体占有空间的有效性，一条简单的一维欧几里德线根本不占有空间。但科克曲线的轮廓，以它的无限长度挤在有限的面积之中，确实占有空间(经络也是)。它比线要多，但比平面又少。它比一维大，但仍不及二维图形8。曼德勃罗特给出了精确的刻划分数维数。直觉的起了重要作用。2.1.3分形的特征分形的主要特征为，自相似性、自仿射性、标度不变性和层次性。自相似性：是某种结构或过程的特征从不同的空间尺度时间尺度来看都是相同的。或者说从整体中取出的局部(局域)能够体现整体的基本特征。标度不变性(无特征长度)：是指任选整体的一局部，对它进行放大或缩小它都能显示出原图形的形态特性，它的各种性质都不发生变化。层次性，递归性：自相似性是不同尺度上的对称，是跨层次的共性观(分形元，不变性)同样形态在不同尺度，不同层次上的相同，或相似结构的重复构建与变换，其结构套着结构，特征或结构隐含嵌套，具有多层次性和递归性。 自仿射性：自相似系统是局部与整体在不同方向上的缩放，拉伸的拷贝，其比例都是同一的，是常数。而自仿射系统，其在各方向上的伸缩，拉放拷贝的比例不同9。2.2分形图形及其计算机图形分形图形是计算机图形艺术的一种。分形模型能够很好的描述自然景物，制作出许多大自然中真实存在的景物，计算机绘制的分形图形有的针对科学研究中要表达的一些特别的对象，有的则完全是为了最求艺术效果。2.2.1分形图形艺术的概念分形图形艺术是计算机图形艺术的一种。计算机图形(绘画)艺术一般分作两大流派： 计算机绘画艺术 = 波普(popular)派 + 数学公式派，波普派主要通过画笔、鼠标、扫描仪等工具在屏幕上进行创作，不直接采用数学公式，虽然计算机在后台必定一定程度上也在利用数学公式进行复杂的运算10。这一派广泛流行于媒体宣传与民间绘画。数学公式派则有意识地运用数学公式进行造型、色彩和构图设计，他们像画家能够感觉到空间纵深、颜色冷暖和关系紧张一样，能够看出数学公式的内在结构以及这种结构配上色彩后所表现的热烈、庄严和静穆。两者并没有本质的区别，只不过一个专注于图形的制作，一个追求的是分形图形艺术美的体现，两者相辅相成，共同发展。并且，更为重要的是，这种区分只是为了说明方便，实际中这种划分也有一定的任意性，两者在现实中的边界日益模糊。走相结合的道路，至少不排斥对方，才是正确的选择。定义：根据非线性科学原理，通过计算机数值计算，生成某种同时具有审美情趣和科学内涵的图形、动画，并以某种方式向观众演示、播放、展览，这样的一门艺术叫做分形图形艺术10。2.2.2分形图形的特征分形图形与一般的几何图形有很大的区别，分形图形一般都有自相似性，就是说我们能够从分形图形的局部观测到整个图形特性和结构，如果局部不断放大我们将发现其多个层次更精细的结构可谓永无止境。如果我们在在分形画面的不同区域涂上不同的色彩，展现在我们面前的，将会是非常美丽的画面。分形图形呈现出来，给出其形式化的表达，分形作为一类例证，为数学理论与实践中所蕴涵的美，给出了一类精彩的注记。充分反映了数学科学中的简单、和谐、统一的内涵！从整体上看，分形几何图形是处处不规则的。例如，多支分节的树杈和贝壳螺纹，从远距离观察，其形状是极不规则的。在不同尺度上，图形的规则性又是相同的。上述的树杈和贝壳螺纹，从近距离观察，其局部形状又和整体形态相似，它们从整体到局部，都是自相似的。当然，也有一些特殊的分形几何图形，它们并不完全是自相似的。它们是分形、一般几何形态、混沌与非线性的混合体。现代绘画艺术形式多种多样，百花齐放，很难用一种模式概括，分形图形艺术只是其中的一部分，但随着计算机图形技术的发展，这一部分会快速成长，也必将给艺术观念带来变革。第三章 分形图形的计算机实现方法由于分形具有自我相似性、自我复制性和自我嵌套的性质，随着计算机性能的快速提高，分形图形的生成方法也得到了深入的发展。近年来，计算机图形学在蓬勃发展和广泛应用，传统的欧氏几何学为它提供了有力的数学模型，在描述一些抽象图形或人造物体的形态时是非常有力的。借助于分形的计算机生成，从少量的数据生成复杂的自然景物图形，使我们在仿真模拟方面前进了一大步。3.1典型的分形集a.康托集(Cantor set)其构造过程如下：选取一个单位长度，将单位长度平均分为3段，去掉中间的13，得到的集合为剩余的两端，接着分别以剩余的两段为主体进行3等分，并去掉中间1/3，如此不断c重复上述过程，直到无穷，即为广义康托集。康托集就是剩下的离散的点集，最后，它们的数目无穷多，但总长度趋向于零。如图(31)； 图31康托集的生成过程(图片摘自设计数学)b.科赫曲线1904年，瑞典数学家HVON Koch设计出类似雪花和岛屿边缘的一类曲线，它们处处连续、处处不光滑、不可微。如果在一个正三角形上按生成规则生成，则曲线形状像雪花，故又称为科奇雪花曲线。其具体画法如下：任取一个正三角形，将三角形每条边三等分，将三等分后的中间一段去掉换成为原尺寸13的正三角形，成为一个六角形；再在六角形的各边上作上述处理直至无穷。 如图3-2首先取一个等边三角形，连接各边中点从而将原三角形分为四个小等边三角形，然后去掉位于中间的一个，将剩下的三个小三角形按上面同样的方法再分别进行四等分，并分别去掉位于中间的那个小三角形，它们都是经典几何无法描述的图形，极限情况下这样生成的图形其面积趋向于零，但周长趋向于无穷大。如此不断重复直至无穷，就形成了一个中间有大量空隙洞孔三角形，即谢尔斯宾斯基三角形。拥有无穷多个自相似的内部结构。 图3-2d.Mandelbrot集Mandelbrot集是数学中最复杂的几何体之一，它的图形生成是从原始图形出发，无限向外延伸，生成不可思议的具有自相似性的美丽图形。它的程序原理为，在复数平面内对映射z z*z+c进行迭代，取个数与本身相乘，再加上最初的数，不断重复以上步奏，就可以得到Mandelbrot集。3.2 各种曲线的设计方案3.2.1 Koch 曲线的设计方案 Koch 曲线的设计方法是：迭代初始把单位线段平均3等分，并将中间的三分之一去掉，而用与去掉部分构成正三角形的另两边来替代。重复以上迭代过程，将生成图形的每条直线进行3等分，然后去掉中间的那部分，用与去掉部分构成等边三角形的另二边来替代。因此我们可以发现这些曲线的构成单元为“_/_”，曲线就由每条直线反复以上迭代过程生成。于是，只要约定好记号，把生成元的构造用字符串表示出来，并且反复迭代，就可以直接得到我们需要的曲线。由于此例中生成元及迭代都比较“规则”，因此做法还是比较简单的。首先做记号的约定：A：沿逆时针方向转一角度；B：沿顺时针方向转一角度；C：从当前点开始沿当前方向画一长度L 的线段。有了这些记号之后就可以用一个字符串表示一个图形。为了叙述方便，有时把字符串说成图形（该字符串所代表的图形），有时把字符串或字符说成一动作（绘制该字符串所代表的图形所需的动作）。规定初始点在原点，初始角度为0，=/3。则字符串“C”代表一条起点在(0，0)终点在(1，0)的线段。而“CACBBCAC”代表最下边的那条曲线。其中第一个C 表示向前画一线段，长度L=1/3，（已规定初始点在原点，初始方向-角度为0），这样当前点（上一个动作完成之后“画笔”停留的位置）变为(1/3，0)；下一字符为A，故应沿逆时针方向转一角度/3，在第二个字符A操作之后，当前点为(1/3，0)，沿当前方向/3画一线段，L=1/3；当第三个字符C“操作”之后，当前点变成(1/2， 3 /2)当前角度不变（还是/3）；接下去二个字符BB，代表沿顺时针方向转二次，每次转/3，这两个字符“操作”之后，当前点(1/2， 3 /2)不变，而当前方向为-/3；接下去第六个字符为C，“操作”之后，当前点为（2/3，0）当前方向为-/3；再接下去第七个字符A。“操作”之后，当前点为（2/3，0），而当前方向为0；最后，完成最后一“操作”，字符C画出（2/3，0）到（1，0）之间的线段。从 Koch 曲线的作法可知：其下一步是把“CACBBCAC”中的C 这一“操作”用复合“操作”C$=“CACBBCAC”来替代，故知道下一步的图形是：C$+“A”+C$+“BB”+C$+“A”+C$注意这时画线段的长度应为上次长度（1/3）的1/3即1/9。综上所述，von Koch 曲线可描述如下：第一步图形为“C”，画线长度L(1)=1，若第k 步图形为V(k)$，画线长度为L(k)，则第k+1步的图形V(k+1)$中的所有“C”用C$=“CACBBCAC“来代替，其它字符不变，而得到的新的字符串；画线长度L(k+1)=L(k)/311。3.2.2 Helibert 曲线的设计方案记号：A：沿逆时针方向转一角度；B：沿顺时针方向转一角度；C：从当前点开始沿当前方向画一长度L 的线段。D、E：这两个字符在下一次迭代中将分别为D$和E$所替代。迭代规则如下：第一步图形为P（1）$=“D”，若第K 步图形为P（k）$，则第k+1步的图形P(K+1)$是将P(k)$中的所有D 和E 分别用D$和E$来替换，其他字符不变而得到的新的字符串。其中：D$ = “AECBDCDBCEA”E$ = “BDCAECEACDB”角度 = /2。需要指出的是：在每次画线这一操作中，其第K 步的线段长度L（K）=ML(1) ，则第K+1 步的线段长度L(K+1)=(2 1)(1)M +L ，并且当K=2 时，M=312.3.3 基于L-system 的分形图形生成方法L - 系统由美国植物学家Aristid Lindenmayer 在研究植物的构造与进化时，于1968 年提出，是用形式语言描述植物形态与生长的拓扑结构，由文法生成的句子极其中间过程阐述植物的生长发育13。由于它出色的仿真能力，后来被引入计算机图形学形成了现在运用十分广泛的模拟自然景物的L - 系统方法。理论上说，L - 系统可生成无限嵌套的结构，是特别类型的迭代过程。L-系统方法又被称为文法构图方法，它的核心思想是并行重写。从一个初始图出发根据重写规则集P 改写初始元的一部分，如此迭代嵌套以生成最终图形。重写的基本思想是根据预先定义的重写规则集(重写规则或生成式)，递归地进行生成复合形状并用它来代替前一步得到的简单形态的某些部分，来定义一个更复杂形态。用L - 系统可以生成典型的分形。尽管生成一个复杂的L - 系统常常需要花费大量的时间，但是指定L - 系统的公式往往非常简单。L系统这种方法对自然界中部分景物的模拟极为逼真，但要求所绘制对象的生成元和迭代规则必须很清晰。先定义如下的图形符号：F：以当前方向前进一步，步长为d，并画线。f：以当前方向前进一步，步长为d，不画线。+：逆时针旋转。：顺时针旋转。：将当前信息压栈。：将“”时刻的信息出栈14。在绘图时，只要输入如下参数：初始元，重写规则集P，初始元角度，步长比率因子，迭代次数，既可绘制出分形图形。例如给定：F；=60；P：FF-F+F-F，则有迭代一次的Koch 曲线，迭代4 次，最终生成所谓的Koch 曲线。在绘图过程中，根据需要可以改变相应的、P 或的值，便会产生不同的图案。3.4 迭代函数系统法迭代函数系统IFS是分形理论的重要分支，它的理论和实践在分形学中占有十分重要的地位，IFS将要生成的图案看成是与整体有着自相似性的许多小块拼贴而成。在讲述IFS之前，先引进仿射变换的概念15。设x，y是平面上的一对变量，a，b，c，d，ef是实数。做下面二维迭代Xn+1=aXn+bYn+eYn+1=cXn+dYn+f n=0，1，21. （3.1）则式（3.1）就是平面上的一个仿射变换。可以把式（3.1）写成矩阵变换形式。设A为一个二阶矩阵，q是二维向量，其中 a b eA= c d ， q= f ，a，b，c，d，e，f R （3.2） 式中R是实数集合，又设平面上一个点（x，y），定义变换x a b x e W Y = c d y + f （3.3）或等价的写成 W（t)=At+q （3.4） 式中t是向量，称变换式（3.3）或（3.4）为一个（平面上的）二阶仿射变换。我们说仿射变换W是压缩的，如果对平面上两个点t1和t2，则有d(W(t1)， W(t2) s*d(t1，t2)， 0s1 (3.5) 对某集合X中所有不同点t1和t2都成立。式中d(t1，t2)表示两个点t1和t2之间的距离，s是其对应的压缩因子。但仅仅一个仿射变换是不能够画出漂亮的图画来的。设N个仿射变换W1，W2.Wn都是压缩的，他们的压缩因子分别是s1，s2，.，Sn，定义 n W（t）= W(t) （3.6） n=1则可以证明这个W变换也是压缩的，其压缩因子为 S=MAXs1，s2，.，sn1以后我们称这个W加s为一个迭代函数系统IFS，记之为 X;Wn，n=1，2，.，N (3.7)具体画图时，仍然是用逃逸时间法，即对给定的集合E0，看n次迭代后会产生什么样的效果。第四章 图形的绘制及程序实现4.1 重复旋转与位移曲线koch4.1.1kock图形的设计如图4-1设N0为单位区间0，1，第一步，即n=1，将N0等分为三份，以中间三分之一线段为底，向上作一个等边三角形，然后去掉区间（1/3，2/3)，得一条四折线段的多边形N1。第二步，即n=2，对E1的4条折线重复上述过程，得一条十六折线多边形N2，再重复上述过程，当n趋向于无穷大时，便得到一条柯克曲线，他是一条连续但非常曲折的曲线。柯克曲线无法用简单的函数y=f(x)来描述，它是一条连续但极其复杂粗糙的图形。当n=1时，他有4条线段，每条线段长为1/3，当n=2时，他有4*4=16条线段，每条线段长度为1/3*3=1/9。最后会得到4的n次方条线段，每条线段长3的n次方分之一。N=0 N=1N=2 n=3 图4-1koch曲线如图4-2为KOCH主要图形，4条折线有4个仿射变换，另4个仿射变换为W(n)(B)=A(n)B+Tn，n=1，2，3，42 3 1 4图4-2 KOCH主型图则 1/3 0 0A1= 0 1/3 t= 0W2是把原线段压缩1/3，然后左旋转60度，再右移1/3。 cos60 -sin60 1/3 A2=1/3 ，t2= sin60 cos60 0 W3则是把原线段先压缩1/3，接着负旋转60度，随后先右移1/2，再上移，即 cos(-60) -sin(-60) 1/2 0 1/2A3=1/3 ，t3= + = Sin(-60) cos(-60) 0 3 /6 3 /6W4把原线段先压缩1/3，然后右移2/3，即 2/3 A4=A1，t4= 04.1.2迭代程序设计过程 (1) 迭代过程函数 #include ”graphics.h” #include ”math.h” #include “stdio.h”void koch (double a0， double b0， double a1， double b1， int k) /给出直线N0两端坐标 double a2， b2， a3， b3， a4， b4; /定义其他交点坐标 a2=2.0/3*a0+1.0/3*a1; b2=2.0/3*b0+1.0/3*b1; a3=1.0/3*a0+2.0/3*a1; b3=1.0/3*b0+2.0/3*b1; a4=1.0/2*(a0+a1)-sqrt(3.0)/6*(b1-b0);b4=1.0/2*(b0+b1)+sqrt(3.0)/6*(a1-a0);if( k1) koch(a0， b0， a2， b2， k-1); /以新生成线段为单员进行重复迭代 koch(a2， b2， a4， b4， k-1); koch(a4， b4， a3， b3， k-1); koch(a3， b3， a1， b1， k-1); else line(a0， b0， a2， b2); /用直线连接新生成各点line(a2， b2， a4， b4); line(a4， b4， a3， b3); line(a3， b3， a1， b1); main() int n， gdriver=DETECT， gmode; /定义迭代次数Initgraph (&gdriver， &gmode，”); /图形初始化printf (”请输入一个小于9的正整数n：”); scanf (“%d”， &n); /输入迭代次数setcolor (RED); koch(60， 120， 450， 120， n); Getch(); closegraph (); /关闭图形系统 （二）生成图形 三次迭代生成图形 九次迭代生成图形4.2绘制Sierpinski三角形4.2.1 希尔宾斯基三角形设计A如图4-3设E0是三个顶点分别在A(0，1)，B(0，0)，C(1，0)的直角三角形W3（E0） C1A1W2(E0)W1(E0)CBB1 图4-3 图4-3显然 W1(A)=A1 W2(A)=C1 W1(B)=B W1(E0)=A1BB1 W2(B)=B1 W2(E0)=C1B1C W1(C)=B1 W2(C)=C W3(A)=A W3(B)=A1 W3(E0)=AA1C1 W3(C)=C1重复以上迭代过程则可生成希尔宾斯基三角形。4.2.2 程序设计过程#include #include void sierpinspi(float a1， float b1， float a2， float b2， int p) /给出生成单元上各点坐标 float a3， b3; a3=(a1+a2)/2.0; if( p1) sierpinspi(a3， b1， a2， b3， p-1); /以新生成的各图形为单元进行迭代sierpinspi(a1， b3， a3