基于分支矩阵的计算机生成树

《基于分支矩阵的计算机生成树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第15卷第2期华侨大学学报(自然科学版)Vol.15No。2ournaouaaoversaturaeneer.1994年4月JlfHqiUniity(NlSci)AP1994基于分支矩阵的计算机生成树’范慧琳张全伙,(华侨大学计算机科学系泉州362011),摘要介绍分支矩阵概念及应用它随机生成树的图象的基本思想给出用T盯boPascal实现含有分支矩阵的随机生成树的算法,最后对这一方法进行简要的讨论.,,,关键词树分支矩阵算法计算机图象分类号TP391.41在过去几年中,树和植物的计算机图象的综合生成已成为许多文

2、章研讨的主题.树的计:;算机模拟朝着两个主要的途径发展虚构树的逼真图象生成使用抽象的物理和生物学上的模,.,现在,式模拟其物理形式和特性已导出各种模型以便对不同种类的树进行描述诸如地貌.,,人类或狗的支气管树的生理研究等等学中河流排泄系统的模拟各种稀有树种的植物分析,,在实际应用方面生成虚构树的逼真图象广泛应用于航空模拟器中它能使驾驶员信服自己是.,在实地地形上空飞行城市规划者把树加入到计算机生成的发展提案中能更清楚地展现出.,到目前为止,比较发展后的环境研究者们已形成了多种较为成熟的树的计算机图象的模型典型的有

3、粒子系统、碎片模型、嫁接和L一系统等,并提出了许多算法.在这些方法中,树的生,,成一般分为两个层次即先生成二叉或三叉拓扑树作为1棵树的基础然后把较为完善的几何.,,生成几何树模型加到拓扑树上最终的树形实际上隐含在树的整个生长变化过程中它是树.n的生长模式的结果本文介绍的方法是基于Horto和Strahler提出的分支矩阵及其阶和双,,、,阶等概念允许规定某些数值参数对树形进行某些度量对树的基本形态(如棘刺状稠密状.细长状等,)进行数值估计本方法不同于其它方法之处在于树的形态与其生长过程是分离的,因此能更好地控制树

4、的最终形态.这种方法首先选择一个分支矩阵,然后随机生成拓扑..,,树该拓扑树的分支矩阵能恰好或极类似于所选择的分支矩阵通常给定一个分支矩阵可.,反之,得到多种形态不同的树对于当前得到的某一树形其拓扑结构所对应的分支矩阵一定.,、,与给定的分支矩阵相符合最后通过用阶和双阶的线性多项式(或指数规律)控制分支的宽度、长度和分支结点的角度,并在二维空间作图,从而得到满足要求的几何树.1基本概念在讨论分支矩阵前,先给出几个与之相关的基本概念.带一一本文199311。7收到华侨大学学报(自然科学版)1994年.,11,1定义

5、对于棵二叉树其结点可通过下列的递归过程加以标记叶结点标记为如vi,v果1个结合的两个儿子标记为和j那么结点的标记。··,一”’,“,特j时{骂;:蓦~j时.,vy。ord(。)~ord(y)连接结点及其儿子的边的标记一个结点(或边)的标记称为该结点(或边)的阶.从,.(也是根的阶)称为树的根结点增加一条额外的边并称其为根边根边的阶...er,Strahl数如图1所示二叉树上所标的数字为相应结点(或边)的阶Strahler数S一3另.,把二叉树中的叶子称为端结点其余结点称为分支结点端结点—‘二三一分支结点丫根边丫a

6、()(b)1Strahler2图二叉树的阶和数图双阶,i,定义2二叉树中阶为k的分支结点带两个儿子阶分别为和j则该点的双阶是一个数对,,,,(ki)当j一k且i

7、一1k一1)的结点数(4)当i(j毛k尸~b*,/a是阶为k的分支结点含有双阶(k,j)的概率.erra,定义3带有Strahl数S的二叉树T的分支矩阵m(T)是如下形式的一个(S一l)XS的随机矩阵Pz已只⋯PZ,:00⋯OP3.zPs,30⋯OfamT一:,Z:,::.3一。PPPPJ,.1.,若令P~1该分支矩阵是一方形的下三角随机矩阵如图1所示的二叉树的分支矩阵则是3/52/5ram(T)-「〕l/201/2/:2第2期范慧琳等基于分支矩阵的计算机生成树31由此可见,分支矩阵的每一元素均确切地体现了二叉

8、树的“形态”的有关信息.2随机生成树的算法GEyrolles,本算法沿用了eorges等人关于分枝模型的组合分析和树的计算机成象的若..又SR,er干基本思想给定1个(S一l)的随机三角矩阵首先随机地生成一棵含有Strahl数.、S的拓扑二叉树T,在此基础上再根据边的长宽和分支结点的角度的选择规律而形成几何·.,,TURBOPASCA树最后在靠近末端的枝干附上叶子达到良好