《第六章形体的表示及其数据结构.ppt》由会员分享，可在线阅读，更多相关《第六章形体的表示及其数据结构.ppt（95页珍藏版）》请在三一文库上搜索。
1、第六章 形体的表示及其数据结构,与空间任意形体有关的信息可以分为图形信息和非图形信息两类。图形信息指构成它们的点、线、面的位置,相互关系及大小等;非图形信息指形体的颜色、亮度、质量、体积等一些性质。 形体的图形信息又可以分为几何信息和拓扑信息两类。几何信息指形体在空间的位置和大小,拓扑信息指组成形体各部分的数目及相互间的连接关系。,第一节 二维形体的表示,二维图形的边界表示 折线法和带树法 折线法就是用多段线段形成的折线去逼近曲线 折线表示曲线应该解决的关键问题是:如何恰当地确定曲线上一系列点,使之在某些判定准则下达到最优。,设已经用某种方法取得了曲线上足够多的点,使连接那些点的折线可以很好地
2、表达该曲线。问题是:怎样在其中选择尽可能少的点,使选出的点仍能较好地表达原曲线。具体地说,使选出的点满足以下二条准则: (1)共线性 设Pj和Pk是选出的两点,则在Pj到Pk之间所有点到直线PjPk的垂直距离,应小于某个预先给定的限制阈值0,这里00,是一个可以由应用问题需要而确定的很小的正数。若不小于0,应寻找距离为最大之点并考虑是否可以在该点将这一段分裂为两段。,(2)设选出的连续三点是Pi,Pj,Pk,则向量PiPj与PjPk的夹角的绝对值,应大于某个预先给定的限制阈值0。,若小于0,则Pj不应选取而应考虑是否能将Pi至Pj和Pj至Pk两段合并。,设有曲线上n+1个点的坐标序列,各点依次
3、编号为0,1,2,n;为使删去各点距留下前后二点所形成直线的距离不很大而预先给定的阈值0;为使选出连续三点所成向量夹角不很小而预先给定的阈值0;参数k0表示每次向前检查k0个点。,1.初始化 i0,j0,kk0,输出点编号0,s1。i记最近己选之点,初始起点0为必选,j记待检查之点,算法中保持ij,待检查线是点j到k的直线。 2.共线性检查检查点j到k间各点共线性。若不能通过,距离直线PjPk最远的点是m,则km返回本步开头。否则继续。本步必能通过,因最坏在k=j+1时能通过。 3.暂定j前后两线方向L2点j到k的方向,若i=j则L1L2,到6;否则继续。L2是暂定找到从j向后的新线方向,L1
4、是前次找到原有线方向。,4.向量夹角检查检查Pi,Pj,Pk三点形成二向量L1和L2的夹角的绝对值,若可以通过即应发生合并,做ji然后返2,否则继续。本步检查通过即点j不能选取,而要检查原i到k的直线。 5.找到一个选取点ij,L1点j到k的方向,输出点编号j,ss+1。 6.准备下次jk,kk+k0,若kn则kn,若jn-1则返2,否则继续。 7.最后取点输出点编号n,算法结束。,P0,P1,P2,P3,P4,P5,P6,i0,j0,kk0 (3) PjPk即P0P3,若通过； j k,k k+ k0 , PjPk即P3P6,带树法 带树是一棵二叉树,树的每个结点对应一个矩形带段,这样每个结
5、点可由八个字段组成,前六个字段描述矩形带段,后二个是指向两个子结点的指针, 即矩形带段的起点是(xb,yb),终点是(xe,ye)。相对从起点到终点的连线,矩形有两边与之平行,两边与之垂直,平行两边与之距离分别为wl和wr。,设要表示的曲线是由经过适当选取已确定的一组离散点P0,P1,Pn序列给出,则生成表示曲线的分辨率为w0的带树的算法,可简略描述如下: 1. 找出由起点P0,终点Pn确定的矩形带段,其中包含P0至Pn的全部点,构造此矩形带段的对应结点并令为根。 2. 找出P0至Pn之间距离连线P0Pn为最远的点Pk,然后对P0至Pk和Pk至Pn这两组点分别做与步1中相同的构造矩形带段及对应
6、结点的操作,产生的两个结点,分别是根的左右子结点。 3. 反复执行上述操作,直到所产生结点的w=wl+wr w0。这样的结点是叶结点。,BINARY *Create(float P,int i,int j，float W) /* BINARY带树节点类型 Pi至Pj描述折线表示的曲线 W为分辨率 */ Search(P,i,j-i+1,wl,wr); /确定Pi至Pj所有点所形成的矩 形带段的宽度 root=new(BINARY); /获取带树节点 CBINARY(root,wl,wr,P,i,j); /构造根节点 if (wl+wr=W) return root; /返回带树根节点 else
7、 maxdis(P,i,j,k);/找出距Pi与Pj连线垂直距离最远的点Pk t1= Create( P,i,k, W); /构造Pi至Pk点间的带树 t2= Create( P,k,j, W); /构造Pk至Pj点间的带树 Left(root,t1); /t1作为root左子树 Right(root,t2); / t2作为root右子树 return(root);/ ,设表示曲线有5个点(3,7)(9,12),(15,4),(18,5),(20,7) ,取分辨率w0=1,则上述算法构造的带树,以不同的分辨率显示用带树表示的曲线 设给出允许的分辨率为w*,表示曲线的带树的分辨率为w0,并设w0
8、w*,则显示算法可简略描述如下: 从根结点开始,若当前正考查结点的W=wl+wr w*,则显示该结点对应的矩形带段;若不然,即W w*则转去分别考查该结点的左右两个子结点,对子结点做同样的处理。左右子结点都被显示的结点就认为是被显示了,按此看法,显示带树表示的曲线就是显示带树的结点。,void Display(BINARY *root,float W,float W*) /* BINARY带树节点类型root带树根指针 W带树分辨率 W*显示分辨率 */ if (WW*) printf(“error”);return; else if( Width(root)left,W,W*); /显示左子
9、树 Display(root-right,W,W*); /显示右子树 return; ,带树表示的曲线求交 两个矩形带段S1和S2的位置关系有如下三种: (1) 不相交。 (2) 良性相交,即S1的与起点至终点连线平行的两条边都与S2相交,S2的与起点至终点连线平行的两条边也都与S1相交。 (3) 可能性相交,这时不是良性相交,但也不是不相交。,设表示要求交两曲线的带树己构造得足够精确,即在树叶一层,来自不同带树的矩形带段或是不相交或是良性相交,而没有可能性相交出现。 两带树T1和T2表示的两条曲线是否相交的算法,可以简略叙述如下: 若T1和T2对应的矩形带段互不相交,那么它们代表的曲线不相交
10、; 若T1和T2对应的矩形带段良性相交,那么它们代表的曲线相交; 若T1和T2对应的矩形带段可能性相交,且T1的面积大于或等T2的面积,那么分别执行T2与T1的左右两个儿子结点的相交性检查。,若T1的面积小于T2的面积,则把它们位置对换一下再如上进行两个检查。若两个检查的结果都是不相交,则认为所表示曲线不相交;若两个检查中有一个是良性相交,则认为所表示曲线相交;若不是上述两情形,即出现可能性相交,则对可能性相交的两个矩形带段中面积较大者,取其对应结点的两个子结点,如此进行可直到树叶那一层。 实践表明用带树方法表示曲线对提高计算效率是有帮助的。另外两个带树对并、交等运算是封闭的,与用象素阵列来表
11、示图形的方法比较空间需求也算是节省的。,平面图形的四叉树表示方法 假定一个平面图形是黑白的二值图形,即组成图形象素阵列的仅有黑色象素值1,白色象素值0,设表现图形的象素阵列由2n2n个象素组成。 表示该图形的四叉树结构可以如下形成:图形显然包括2n2n的正方形中，这个正方形是四叉树的根结点。 若图形整个地占据这个正方形,则图形就用该正方形表示,否则将该正方形均分为四个小正方形，每个小正方形边长为原正方形边长的一半.它们是根结点的四个子结点,可编号为0,1,2,3。,再考查每个小正方形,若整个被图形占据,则标记相应结点为1,可称为黑结点。若整个与图形不相交,则标记相应结点为0，可称为白结点。 若
12、不是上述两情形，即与图形部分相交，则称相应结点是灰结点并将其一分为四。当再分生成小正方形边长达到一个象素单位时，再分终止，此时一般应将仍是灰结点的改为黑结点，如此形成了平面图形的四叉树表示,TREE * tree_4(Box b,Graph g) / b为正方形 g为二维形体 TREE为四叉树结点类型 if (g包含b) 构造树根结点root（属性为黑）;return(root)； else if (b与g之交集为空) return null； else b分成b0,b1,b2,b3四个相同小正方形; 构造树根结点root（属性为灰）； r1=tree_4(b0,g); r2=tree_4(b
13、1,g); r3=tree_4(b2,g); r4=tree_4(b3,g); r1,r2,r3,r4链接为root结点的四个子结点； return(root); ,四叉树的存储结构，即规则方式、线性方式和一对四方式，相应的四叉树也就称为规则四叉树、线性四叉树和一对四式四叉树。 规则四叉树是用五个字段的记录来表示树中的每个结点，其中一个用来描述结点的特性，即是灰、黑、白三类结点中的哪一种。其余四个用于存放指向四个子结点的指针。 线性四叉树以某一预先确定的次序遍历四叉树形成一个线性表结构 。 RAabcdBCDefgh。其中R表示根，字母右上角加表示是灰结点。,一对四式四叉树的存储结构 每个结点
14、有五个字段，其中四个字段用来描述该结点的四个子结点的状态，另一个结点存放指向子结点记录存放处的指针。四个子结点对应的记录是依次连续存放的。,为节省存贮空间,有两个途径可以采取。一个是增加计算量；另一个途径是在记录中再增加一个字节,一分为四,每个子结点对应2位,表示它的子结点在指针指向区域中的偏移。,第二节 三维几何模型,几何元素 形体的模型主要指的就是包含图形信息所形成的模型。 形体本身的构造有一定的层次性，低层部分组合构成上一层部分，而上一层部分组合又可以构成更高一层的部分，依此类推可形成多层结构。其中，每一层中的部分，我们把它有称为几何元素。,点 它是0维几何元素，有端点、交点、切点、孤立
15、点等形式。 曲线、曲面的应用中会涉及到三种类型 的点： 型值点 相应曲线、曲面必然经过的点。 控制点 相应曲线、曲面不一定经过的点，仅 用于确定位置和形状。 插值点 在型值点之间插入的一系列点，用于 提高曲线曲面的输出精度。,不同的空间中点的表示方式 一维空间中用一元组t表示； 二维空间中用二元组x,y或x(t),y(t)表示； 三维空间中用三元组x,y,z或x(t),y(t),z(t)表示 点是几何造型中的最基本的元素，曲线、曲面和其它形体都可以用有序的点集描述。 用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。,边 边是一维几何元素，是两个邻面（正则形体）或多个邻面（非正则
16、形体）的交界。边分直线边和曲线边。直线边由起点和终点两端点确定；曲线边由一系列型值点或控制点表示，也可以用显示、隐式方程描述。 环 环是有序有向边（直线段或曲线段）组成的面的封闭边界。环中的边不能相交，相邻两条边共享一个端点。环有内外之分，确定面的最大外边界的环称之为外环，通常其边按逆时针方向排序。而把确定面中内孔或凸台边界的环称之为内环，其边相应外环排序方向相反，通常按顺时针方向排序。,面 面是二维元素，是形体上一个有限、非零的区域，它由一个外环和若干个内环所界定。 面有方向性，一般用其外法向量作为该面的正向。若一个面的外法向量向外，此面为正；否则，为反向面。 体 体是三维几何元素，由封闭表
17、面围成的空间，它是欧氏空间R3中非空、有界的封闭子集，其边界是有限面的并集。在实际应用中，要求形体是正则形体，即形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆。不满足上述要求的形体称为非正则形体。存在悬面、悬边的形体是非正则形体。,体素 体素是可以用有限个尺寸参数定位和定型的体，常有下面三种定义形式。 一组单元实体 长方体、圆柱体、圆锥体、球体。 扫描体 由参数定义的一条（一组）截面轮廓线沿一条（一组）空间参数曲线作扫描运动而产生的形体。 用代数半空间定义的形体，在此半空间中点集可定义(x,y,z)|f(x,y,z) 0此处的f应是不可约的多项式。 形体的层次结构 点边环面外壳形体。
18、,运动轨迹,初始运动面,在几何造型中最基本的几何元素是点（V）、边(E)、面(F),这三种元素一共有九种连接关系,线框、表面及实体表示 常用的多面体表示法是三表表示法，即采用三个表:顶点表,用来存放多面体各顶点的坐标;边表,指出哪两个顶点之间有多面体的边；面表，指出哪些边围成了多面体的表面。 任意多面体容易得到它的三表表示,但任意三张表却不一定表示了一个真实的多面体。这里必须满足的条件至少有以下几项:顶点表中的每个顶点至少是三边的端点;边表中的每条边是两个多边形面的公共边；每个多边形面是封闭的等等。,顶点表,面表,边表,空间正二十面体V20, 的三表表示。 引人一个正数0,它满足二次方程2-1
19、=0,因此=(1+ )/21.618034。,X,Y,Z,三维实体表示方法 从用户角度来看，形体以特征表示和构造的实体几何表示比较适宜；从计算机对形体的存储管理和操作运算角度看，以边界表示最为实用。 1 构造的实体几何法 构造的实体几何(CSG:Constructive Solid Geometry)法是指任意复杂的形体都可以用简单形体(体素)的组合来表示。 形体的CSG表示可看成是一棵有序的二叉树，称为CSG树。其终端结点或是体素，如长方体、圆锥等；或是刚体运动的变换参数，如平移参数Tx等；非终端结点或是正则的集合运算，一般有交、并、差运算；,或是刚体的几何变换，如平移、旋转等。 采用BNF
20、范式可定义CSG树若下： :=| CSG树是无二义性的，但不是唯一的，其定义域取决于所用体素以及所允许的几何变换和正则集合运算算子。 CSG表示的优点： 数据结构比较简单，数据量比较小，内部数据的管理比较容易；,每个CSG表示都和一个实际的有效形体所对应； CSG表示可方便地转换成Brep表示，从而可支持广泛的应用； 比较容易修改CSG表示形体的形状。 CSG表示的缺点： 产生和修改形体的操作种类有限，基于集合运算对形体的局部操作不易实现； 由于形体的边界几何元素(点、边、面)是隐含地表示在CSG中，故显示与绘制CSG表示的形体需要较长的时间。,并,2 特征表示 特征表示是从应用层来定义形体，
21、因而可以较好地表达设计者的意图，为制造和检验产品和形体提供技术依据和管理信息。从功能上看可分为形状、精度、材料和技术特征。 形状特征：体素、孔、槽、键等 精度特征：形位公差、表面粗糙度等； 材料特征：材料硬度、热处理方法等； 技术特征：形体的性能参数和特征等。 形状特征单元是一个有形的几何实体，是一组可加工表面的集合。如采用长、宽、高三尺寸表示的长方体；采用底面半径及高度表示的圆柱体均是可选用的形状特征单元。,形状特征单元的BNF范式可定义如下： :=|; :=长方体|圆柱体|球体|圆锥体|棱锥体|棱柱体|棱台体|圆环体|楔形体|圆角体|； :=并|交|差； :=外圆角|内圆角|倒角。,3 边
22、界表示 边界表示详细记录了构成形体的所有几何元素的几何信息及其相互连接关系拓扑关系，便于直接存取构成形体的各个面、面的边界以及各个顶点的定义参数，有利于以面、边、点为基础的各种几何运算和操作。 形体的边界表示就是用面、环、边、点来定义形体的位置和形状。例如，一个长方体由六个面围成，对应有六个环，每个环由四条边界定义，每条边又由两个端点定义。而圆柱体则由上顶面、下底面和圆柱面所围成，对应有上顶面圆环、下底面圆环。,Brep表示的优点是： 表示形体的点、边、面等几何元素是显式表示的，使得绘制Brep表示形体的速度较快，而且比较容易确定几何元素间的连接关系； 对形体的Brep表示可有多种操作和运算。
23、 Brep表示的缺点是： 数据结构复杂，需要大量的存储空间，维护内部数据结构的程序比较复杂； 修改形体的操作比较难以实现； Brep表示并不一定对应一个有效形体，即需要有专门的程序来保证Brep表示形体的有效性、正则性等。,八叉树 假设要表示的形体V可以放在一个充分大的正立方体C内,C的边长为2n,形体V C ,它的八又树表示可以递归定义为: 八叉树每个结点与C的一个子立方体对应，树根就和C本身对应。如果V=C,那么V八叉树仅有树根。如果VC,则将C均分为八个子立方体,每个子立方体对应根结点的一个子结点。只要某个子立方体不是完全空白或完全被V所占据,它就要被八等分,从而它对应的结点也有了八个子
24、结点。这样的递归判断及可能分割一直进行,直到结点对应的立方体或完全空白,或完全被占据,或其大小已是预先规定的体素大小.,这时对它与V之交作一定的“舍入”,使体素或认为是空白,或认为是被V占据的。这里所谓的体素,就是指被分割后得到的小立方体。 通常称对应立方体被形体V完全占据的结点为黑结点,完全不占据的为白结点,部分被占据的为灰结点。 存贮结构, 有常规的、线性的、一对八式的八叉树等等。,八叉树方法的主要优点在于,可以非常方便地实现形体的集合运算 。 八叉树表示的三维形体的几何变换 比例变换 旋转变换 相对通过原点的一条任意方向的直线做旋转任意角度的旋转变换。 构成原形体的直立的正立方体经绕原点
25、任意轴线旋转任意角度后, 一般都成为斜置的。为了使变换后形体的八叉树仍对应一系列直立的正立方体,必须对被斜置立方体部分占据体素做出选择,即或认为是占据,为黑结点,或认为不占据,为白结点,这就必然带来一定的误差。而且执行多次变换后,误差积累会大到产生严重的错误。,第一项措施是保持一个原始的八叉树做为参考的源树。设指定了一次变换R1,接着又要做变换R2,可以计算出复合变换R=R1R2,然后对原始的八叉树做一次变换。这样来避免误差的积累。 第二项措施是为了尽量减少“舍入“误差,可以规定一个当前正要重建的八叉树,如果它的最底层叶结点对应的体素是部分地为显示对象所占据，那么当且仅当这个体素的中心位于某个
26、黑变换后立方体内时,这个体素才被规定为黑,否则就规定为白。这样规定使得一般不会产生原来不存在的孔洞，而不这样规定,例如简单地规定部分被占据的体素都为白,则可能在做450左右旋转时原来黑立方体变换为部分占据若干体素而被指定为白,在变换后形体中间出现断裂。,设己采取了上述两项措施,已知形体变换前的八叉树表示T1,己计算出 要做的复合变换R,要确定变换后形体的八叉树表示T2,可以写出如下的算法框架： 1. 遍历形体原来的八叉树T1,对遇到的每个黑结点,做下述步2。 2. 对遇到黑结点对应的正立方体做相应变换,得它新的一般来说是斜置的新位置。若这位置已超出定义八叉树的充分大正立方体C之外,报告出错;否
27、则执行下述的步3。 3. 从要计算求出的目标树T2的根开始,检查2中确定的处于新位置立方体与T2中结点对应的直立的正立方体是否相交,分以下三种情况进行处理:,(1) 不相交,说明正考查直立正立方体未被占据,可保持为白结点,不做处理。 (2) 直立的正立方体整个被占据,即它在变换后“斜置“立方体内,置对应结点为黑结点。 (3) 在上述两条均不成立时,生成当前结点的八个子结点,对八个子结点对应的八个直立子立方体,依次再递归执行步3。如果最终这八个结点被标上同样特性,比方为黑结点,则应再删掉这八个子结点而把它们的共同父结点置为黑。 算法中,主要工作是检查某个直立的正立方体与一个斜置的正立方体是否相交
28、,。对所有黑结点对应正立方体处理相同,使得操作可以并行进行。,线性八叉树 在对立方体做八等分时,按一致的方式, 对分出的子立方体进行编号。若再分共进行n层，则每个结点可以用n位的八进制数的数串来表示,数串从左至右,第一位对应第一次划分，第二位对应第二位划分，依此类推。据此整个八叉树就可以根据对其做深度第一遍历而依次列出的黑结点的编号序列来表示 。 前图所示三维形体,其线性八叉树表示是: 0x,10,12,13,14,2x,4x,6x,7x,求并运算 C1UC2 两棵线性八叉树: C1=122,123,301,302,303,305,307 C2=12x,300,302,304,306 将C2的
29、各结点依次插入到C1的适当位置,使插入后编号渐增这一性质保持不变。当C2中结点可以包含C1中若干结点时,则取而代之。另外,如果插入后可以进行结点“压缩“,也应该立即进行: C1UC2=12x,300,301,302,303,304,305,306,307 =12x,30x,线性八叉树表示形体的显示 当观察位置是x10,y10时,最可能被遮挡看不见的是编号2的子立方体,全部依次排出可以是26034715,zl0,y10 优先级26034715。 前图表示形体的线性八叉树0x,10,12,13,14,2x,4x,6x,7x 按结点应显示次序排出的序列就是: 2x,6x,0x,4x,7x,12,10
30、,13,14,第三节 分形,分形的概念 三分康托(Cantor)集 设E0是闭区间0,1,即E0是满足0x1的实数x组成的点集;E1是E0去掉中间1/3之后的点集,即E1是两个闭区间0，1/3和1/3，2/3;E2是分别去掉E1中两个区间的中间1/3之后的点集,即E2已经是四个闭区间。此过程要继续进行,Ek是2k个长度为1/3k的闭区间组成的点集。三分康托集F是属于所有的Ek的点组成的集,即 。 F可以看成是集序列Ek当k趋于无穷时的极限。只能画出k取定时的某个Ek。当k充分大时,Ek是对F的很好的近似的表现,三分康托集是区间0,1中的可以展成以3为底的幕级数的下面形式的数组成的: a13-1
31、+a23-2+a33-3 其中ai的取值限制为0或2,不取1。为看清这一事实,注意从E0得到E1时,去掉的是ai=1的数,从E1得E2时,去掉的是a2=1的数,并以此类推。 三分康托集具有的一些值得注意的特征,这些特征对许多其它的分形也是大体上适合的。 (1) F是自相似的。E1的两个区间0，1/3，1/3，2/3的每一个,其内部F的部分与F整体相似,相似比为1/3。,(2) F具有“精细结构”，即它包含有任意小比例的细节。 (3) F的实际定义是简单的和明确的。 (4) 传统的几何学很难描述F的性质,因为F不是满足某些简单条件的点的轨迹,也不是任何简单的方程的解的集合。 (5) F的局部几何
32、性质也很难描述,在它的每点附近都有大量被各种不同间隔分开的其它点。 (6) 按传统几何学中的长度概念,F的长度为零。就是说,尽管从不可数集合这点上说F是一个相当大的集,但它却没有长度,或者说长度不能对F的形状或大小提供有意义的描述。,von Koch曲线,称集合F是分形,即认为它具有 下面典型的性质: (1) F具有精细的结构，即有任意小比例的细节。 (2) F是如此的不规则以至它的整体和局部都不能 用传统的几何语言来描述。 (3) F具有某种自相似的形式,可能是近似的或是统 计的。 (4) 一般地,F的“分形维数“大于它的拓扑维数。 (5) 在大多数令人感兴趣的情形下,F以非常简单 的方法定
33、义,可能由迭代产生。,Hausdorff维数 考虑一个简单的几何图形,取一个边长为1的正方形,若每边扩大2倍,则正方形面积放大4倍,其数学表达式为22=4,这是2维图形。对3维图形,如考虑边长为1的立方体,令每边长放大2倍,则立方体体积扩大8倍,其数学表达式为23=8。 类似地,对一个Df维的几何对象,若每边长扩大L倍,则这个几何对象相应地放大K倍,归纳前述结果,Df,L,K三者间的关系式应为: LDf=K 解Df, Df=lnK/lnL （1） 这里Df不必是整数。这就是Hausdorff引人的维数概念,可以称为Hausdorff维数。,假定有一个单位正方形,把它每边三等分得九个小的正方形,
34、九个小正方形面积总和是原单位正方形面积,即9(1/3)2=1。现在我们把Df维的几何对象等分为N个小的几何图形,则每个小图形每维缩小为原来的r倍,而N个小图形的总和应有NrDf=1。 这时解出 ,有: （2） 容易看出式(1)和(2)本质上是相同的,即这样引入的也是Hausdorff维数,von Koch曲线,每次分为4个小图形,每个小图形缩小1/3倍,故其Hausdorff维数 为：,分形一般算法,规则分形的生成算法。对算法的输入是事先给定的一个整数k、源形E0及生成规则,算法操作步骤如下:,1.初始化i0,j1,队Q,A0Eo;用在第i层表示正处在生成Ei的阶段。对m2,设生成规则指明了E
35、i由m个Ei+1组成,则在第i层共应生成mi个部分图形。用A0记一个部分图形,j是己生成部分图形的数目。第i层部分图形要在第i+1层再分,故生成后要送到一个先进先出的队Q中等待; 2.一次生成依据生成规则,由一个部分图形A0,计算它的m个分解部分A1,A2, Am; 3.图形绘制对Al,A2, ,Am做图形绘制; 4.存贮队Q(A1,A2,Am)生成各部分图形依次加到队尾;,5.准备下次A0队Q;从队取出一个部分图 形; 6.第i层是否结束jj+1,若jmi,则j1;ii+1; 7.结束判断若ik,则算法结束;否则返回步2 von Koch曲线 其源形E0可以是一条线段, 记其端点坐标为P0,
36、P1。在算法步1,应令A0=E0=(Po,Pl ),在算法步2,需要依据Po,P1 ,计算图中P2,P3,P4三点的坐标。 这样m=4,分别得到四个部分图形是A1=(P0,P2),A2=(P2,P3),A3=(P3,P4),A4=(P4,P1)。在算法步3,可画出四条线段P0P2,P2 P3, P3 P4, P4P1,擦去前次画线时可能画出的P2P4部分。,Von Koch算法 利用自相似变换来绘制分形 设D是欧氏空间Rn的闭子集,映射S:DD称为是D上的压缩，如果对所有D上的点x,y,存在一个数c,0c1,能使|S(x)-S(y)| c|x-y|。如果其中等号成立,即若|S(x)-S(y)|
37、=c|x-y|,则S把一个集变成了它的几何相似集,此时映射S称为是相似的。 设S1,Sn是压缩,称D的子集F对变换S1, ,Sn是不变的,如果,三分康托集的情形,这时令S1,S2是RR的变换,分别由,P0和P1的坐标是(0,0)和(1,0),则可以计算求出P2,P3,P4的坐标是,自相似变换S1和S2是平面变换,可一般地设变换矩阵为:,第一个变换S1把点P0,P1,P3,依次变到Po, P3,P2,这就得到:,于是有,第二个变换S2把点P0,P1,P3,依次变到P3,P1,P4，这就得到：,因此,绘制von Koch曲线 1.初始化x10,y10,s1,u1;(x1,y1)为初始点。 2.变换
38、 3.画点在显示表面画点(x2,y2)和(x3,y3); 4.存贮Ps(x2,y2),Ps+1(x3,y3),ss+2; 5.准备下次(x1,y1)Pu,uu+1; 6.是否结束若uk则算法结束,否则返步2。,上面的变换能产生很紧松树树枝的图象。,Julia和Mandelbrot集 设有复数域上如下形式的二次函数: f(z)=z2+c 其中c是复数值常数,做迭代操作: zn+1= zn2+c,n=0,1,2, 研究的问题是: 1.给定z0,当参数c在什么范围内取值能保证|zn|有界 2.当c给定,如何选取z0,使|zn|有界?,上述迭代,当c=0时,可以有以下三种情况: 1. 序列中的数按模来
39、说越来越小,且趋于零。这时说零是zz2的吸引子。所有与坐标原点相距小于1的点都产生趋向零的序列。 2. 序列中的数按模来说越来越大,且趋向无穷,这时“无穷“也称为过程的吸引子。与坐标原点的距离超过1的所有点都产生趋向无穷的序列; 3. 距坐标原点为1的点,序列总是产生在上面两个吸引区域之间的边界上,此时边界恰为复平面上的单位圆周。 对于上述迭代,当c 0时,吸引子不再是零,吸引区域的边界不再是光滑的,而是具有自似形的分形结构,这种边界称为Julia集。,在复平面上，使zz2+c的迭代过程成为有界的复参数c的集合叫做Mandelbrot。 设复平面上的迭代过程是: zk+1=zk2+c 分离实部
40、和虚部,记zk =xk+yki,c=p+qi,有,设计算机显示屏幕的图形分辨率是ab点,可显示颜色是k+1种,以数字0到k表示,0表示黑色。取定p和q的值,考虑平面上每一点(x,y),探讨吸引区域的结构及其边界即Julia集。 1.选定参数xmin -1.5,ymin -1.5,xmax 1.5,ymax 1.5,M 100,并令x (xmax - xmin )/(a-1), y (ymax- ymin)/(b-1);这里(xmin , ymin)(xmax, ymax)区域是考查的复平面范围,M是指定的一个阈值,超过它算是已达到无穷;K是可显示颜色的数目 2.逐点着色对所有点(nx,ny),
41、nx=0,1,a-1, ny=0,1,b-1,完成以下循环后算法结束。,2.1置初值x0 xmin + nxx ,y0 ymin + ny y ,k 0; 2.2一次迭代 ,k k+1; 2.3判断r 。 若rM,则选择颜色k,转步2.4; 若k=K,则选择颜色0,即黑色,转步2.4; 若r M且kK,则返回步2.2; 2.4一点着色对点(nx,ny)着颜色k,对(nx,ny) 的下一点,返回步2.1。,固定点(x,y),在不同的p和q值之下追踪其迭代点列,在(p,q)平面上记录结果,从而产生Mandelbrot集。设要考查的(p,q)平面范围是-2.25p0.75,-1.5q1.5,对计算机
42、显示屏幕的假定如前。实施步骤为: 1.选定参数pmin -2.25,qmin -1.5,pmax 0.75,qmax 1.5,M 100,并令p (pmax - pmin )/(a-1), q (qmax- qmin)/(b-1);这里(pmin , qmin)(pmax, qmax)区域是考查的复平面范围,M是指定的一个阈值;K是显示颜色的数目 2.逐点着色对所有点(np,nq),np=0,1,a-1, nq=0,1,b-1,完成以下循环后算法结束。,2.1置初值p0 pmin + nxp ,q0 qmin + nq q ,k 0; x0 0,y0 0 2.2一次迭代 k k+1; 2.3判
43、断r 。 若rM,则选择颜色k,转步2.4; 若k=K,则选择颜色0,即黑色,转步2.4; 若r M且kK,则返回步2.2; 2.4一点着色对点(np,nq)着颜色k,对(np,nq) 的下一点,返回步2.1。,void Julia(int a,int b,int K1,int M1,double p1,double q1) double xmin=-1.5,ymin=-1.5,xmax=1.5,ymax=1.5; int M=M1,nx,ny,k,K;K=K1; double tx,ty,x0,y0,p,q,xk,yk,r;p=p1;q=q1; tx=(xmax-xmin)/(a-1);ty
44、=(ymax-ymin)/(b-1); for(nx=0;nxM) SetPixel(nx,ny,RGB(k,0,0); if(k=K) SetPixel(nx,ny,RGB(255,255,255); ,void Mandelbrot(int a,int b,int K1,int M1) double pmin=-2.25,qmin=-1.5,pmax=0.75,qmax=1.5; int M=M1,np,nq,k,K;K=K1; double tp,tq,p0,q0,p,q,xk,yk,r,x0,y0; tp=(pmax-pmin)/(a-1);tq=(qmax-qmin)/(b-1); for(np=0;npM) SetPixel(np,nq,RGB(k,0,0); if(k=K) SetPixel(np,nq,RGB(255,255,255); ,