自然路径求解.docx

本文采用的近似最短路径算法是：（1） 生成曲面三角形网格（2） 由三角形网格模型上的顶点和边构成图，并由曲面的特性构成边的 权值，进而生成一个带权图G3） 利用Dijkstra算法计算带权图上两点间的最短距离来得到最初近似最短 路径4） 细分最短路径周围的三角形网格边来生成新的带权子图5） 重复步骤（3） （4）不断计算出新的最短路径，使的近似最短路径趋向 真实的最短路径，设定一个精度要求，当前后两条最短路径之差小于精 度要求时停止计算3. 2.1 Dijkstra算法狄克斯特拉算法将网格上所有的顶点的集合V分为S,T两个集合：S用来 存放己知最短路径的顶点，既他们到初始点的距离己经确定了而T存放 未知最短路径的顶点假定(u,v)是一条边，c(u,v)为边的长度，同时，把 源顶点u到T中顶点x的距离d(u,x),定义为从u出发，经过S中的顶点， 但不经过T中其它顶点，而直接到达T中的顶点x的最短路径的长度，D(x)存储着d(u,x)中对应的一系列顶点算法步骤如下：开始时，S={u), T=V-So对T中的所有顶点x,如果u到x存在边，置d (u,x)=c(u,x);否则d(u,x)=oo0然后，对T中的所有顶点x,寻找d(u,x)最小 的顶点t,既：d(u,t)=min(d(u,x) ;xgT)••…-D (t) =(u,t)d(u,t)就是顶点t到顶点u的最短距离。

同时，顶点t也是集合T中的 所有顶点中距离u最近的顶点把t从T中删去，把它加入S然后，对 T中与t相邻接的所有顶点x,用下面的公式更新d(u,x)的值：d(u,x)=min{ d(u,x), d(u,x)+d(u,t) )—-D (x) =(u x}继续上面的步骤，一直到T为空3.2.2细分图生成方法：1在图R上最短路径经过的三角形上的边插入细分点为了使插入的细分点的间距比较均衡，首先指定每个边上插入点的个数u (大小由用户决定，和精度成正比关系)，在根据图U上个边的平均长度百计 算出插入点间的平均距离?=£7)1，这样每一条需要细分的边e(vj,总),产生 的细分点的个数为：m=mod(|(vj 一帛]网).1 (mod取余运算符)2细分图的生成确定了细分图G+1上所有的顶点后，还要确定图上的边对细分图Gi+i中的 每一个点对(v[]+i, v特])，生成边的集合Ej(ei+1( (vi+1, vgi) ) : Onsame Triangle( (vj+1, 皆)户TRUE}；同时生成边集Ei{q(lnGraphG(v昔】)), InGraphG(vpi)}： §如°}；最后Ei+1=EiUE2既为细分图上的边集。

OnsameTriangle((忒】,v[")表示判断图G「+i上的顶点是否在原始图中的 同一三角形上的顶点InGraphGCv；/1)表示判断图上的顶点是否是原网格图G中的顶点参考资料：[1] 赵渠森主编.先进复合材料手册[M] .北京:机械工业出版社,2003, 5.[2] 贺福编著.碳纤维及其应用技术[M] .北京:化工工业出版社,2004, 9.[3] 陈祥宝.先进树脂基复合材料的发展和应用[J] .航空材料学报，2003, 23(10): 19矿204.[4] 赵渠森.先进复合材料及其应用[J] .航空制造技术,2002, (10) :22~34.[5] 陈绍杰.先进复合材料的近期发展趋势[J],高科技纤维与应用> 2004, 29(1) :1~7[6〔赵渠曷.材料与工艺在“买得起的复合材料”中的应用[J] .航空制造技术,2000, (6):47 飞 1.[7] 李勇，肖军.复合材料纤维铺放技术及其应用[J].纤维复合材料,2002, 37(1):39^41.[8] 陈亚莉.复合材料在飞机上的新应用[J] .航空维修与工程,2005,3:31^32.[9] 赵群力.低成本制造——美国JSF计划走向成功的关键[J].国际航空,2000, 11:44^48.[10] Carrol 1 G G. Fiber placement process utilization within the worldwide aerospace industry[J].SAMPE Journal, 2000, 36 ⑷：35~39.[11] 植村益次，木广.贾丽霞，白淳岳译.高性能复合材料最新技术[M] .北京:中 国建筑工业出版社,1998, 2.[12] 沃丁柱编著.复合材料大全围].北京:化工工业出版社,2000, 1.[13] 陈祥宝主编.先进复合材料低成本技术[ML北京:化学工业出版社.2。