资源描述：
《多面体面上任意两点间最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第!"卷第#期北京理工大学学报8-69!":-9#!$$"年#月%&’()’*+,-()-./0,1,(23()+,+4+0-.%0*5(-6-27;<&9!$$""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""文章编号=>$$>?$@#"A!$$"B$#?$CC!?$"多面体面上任意两点间最短路径算法周培德A北京理工大学信息科学技术学院计算机科学工程系D北京>$$$E>B摘要=提出计算多面体面上任意两点之间最短
2、路径的算法=近似算法F最短路径或近似最短路径算法G近似算法的思想是采用将折线不断嵌入三角形串上的方法D而另!个算法则是通过特定法线寻找三角形串D而且将这些三角形旋转到同一平面上D从而得到最短路径G前者的时间复杂性为HAIBD而后者的时间复杂性分别是HAI!B及低于HI!A!IBG关键词=多面体面J最短路径算法J嵌入平面J三角形串J时间复杂性中图分类号=%KC$>L@文献标识码=;MNOPQRSTUVWPQSTXYTPQSXVSZ[STXS]XX^_]PMQ‘RSQ[QaZPR^SVP^[ZPNa
3、TXbQ[NYcQW[dXefghK0,?i0Aj0<’&+k0(+-.l-k<4+0&m*,0(*0’(in(2,(00&,(2Dm*5--6-.3(.-&k’+,-(m*,0(*0’(i%0*5(i-27D/0,1,(23()+,+4+0-.%0*5(-6-27D/0,1,(2>$$$E>Dl5,(’BM‘VSQ[dS=%5&00’62-&,+5k)’&0<&0)0(+0i.-&*-k<4+,(2+50)5-&+0)+<’+5o0+p00(+p-’&o,+&’&7<-,(+)-(’<-6750
4、i&’6)4&.’*0=g(0,)’(’<<&-q,k’+0’62-&,+5kJ+50-+50&+p-*’(-o+’,(+50)5-&+0)+<’+5-&’(’<<&-q,k’+067)5-&+0)+<’+59%50’<<&-q,k’+0’62-&,+5k,)+-’i-<+’k0+5-i.-&p5,*5+50o&-r0(6,(0)’&0*-()+’(+670ko0ii0i,(’)0&,0)-.+&,’(260)Dp50&0’)+50-+50&+p-’&0+-.,(i’)0&,0)-.+&,’(26
5、0)o74),(2’)<0*,.,*(-&k’66,(0D’(i+50)0+&,’(260)’&0&-+’+0i-(+-+50)’k0<6’(0)-’)+--o+’,(+50)5-&+0)+<’+59%50+,k0*-k<60q,+7-.+50.-&k0&,)HAIBDo4+!I!+50+,k0*-k<60q,+,0)-.+506’++0&+p-’&0HAIB’(i6-p0&+5’(HA!IB&0)<0*+,s0679tXa]PQbV=<-6750i&’6)4&.’*0J)5-&+0)+<’+5’
6、62-&,+5kJ0ko0ii0i<6’(0J’)0&,0)-.+&,’(260)J+,k0*-k<60q,+7设w是三维空间中任意多面体面D并且它有I机器人和地理信息系统等领域中研究过的问题D特个顶点G不失一般性D设w的每个面均为平面三角形别是当w为凸多面体面时D这个问题已研究得比较成熟}>~C!A有限BG给定!个点xDyzwD要求计算位于w上由xG但w为非凸多面体面时D很少见到相关报至y最小长度路径D该路径记为{wAxDyBG{wAxDyB通道G而实际应用中D出现非凸多面体面及曲面的情况常是唯
7、一的D但不总是唯一G令
8、表示路径{更多D因此D研究非凸多面体面及曲面A已用许多三wAxDyBwAxDyB的长度G角形面表示B上任意两点之间的最短路径具有重要计算多面体面上最短路径问题已是计算几何F的应用价值G收稿日期万方数据=!$$#$">u作者简介=周培德A>u#>vBD男D教授G第9期周培德T多面体面上任意两点间最短路径算法&&&!算法思想1基本概念作者对非凸多面体面"#设计了寻求"上任意为讨论问题方便起见#假设多面体面"的每个两点$与%之间最短路径的&个算法’假设"由许多面都是四边形#图(示
9、出"面的&种不同情况’图(2平面三角形组成’第(个算法的思想是首先计算$#%中/个四边形3#4有(条公共边#$#%分别位于/个所在三角形平面的交线)#然后沿)扩展$所在平面#四边形中’将四边形4所在平面5绕公共边旋转至4找出%在扩展平面上的像%*#$%*与)的交点是+(#$%*与3所在平面53#并计算点%在平面53的像点%*’连接$所在三角形边的交点为,(#而+(%与%所在三角形边$与%*成线段$%*#$%*与公共边交于点,#再连接,与%’的交点为-继而将折线,嵌入到$#%所在三角
