资源描述：
《求两凸多面体间距离的快速算法-陈亮》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一99月年12月高等学校计算数学学报第4期求两凸多面体间距离的快速算法‘“陈亮黄文奇宋恩民(华中理工大学)AFASTALGORITHMFORCOMPUTINGTHEDISTANCEBET叭了EENT丫VOCONVEXPOLYHEDRAChenLiangHuangWenqiSongEnmin(HuazhongUniversityofSeieneeTeehnology)&A比tractedistancetweentwocon,Polyhra15herereferrtothelengthofPaththatoneofThbeexededthetooeranov,inan
2、orienonaraeoaratline,untnter:wPlyhdcabemedtatiPllltfixedstighilit15i.er一飞eresee忱dwiththeotherConsidingthecaseswithlotsofPraetiealbaeksroundsiwhiehthlateddataofeaehPolyhedroncanbethoughttohavebeenstoredinthememoryofaeomPuterandeach,-PolyhedronhasfurtherbeenPreProeessedseParatelyafastal
3、gorithm15obtainedtoeomPutethediseena.e,taneetwPairofeonvexPolyhraThisalgorithrn15thfastest50farandit,5alsotheonlybeednaeene,algorithmthatcanobtaikindofdistancebetwtwoPolyhedrawithinsublineartim1引言,为了快速有效地对航天火箭弹舱中诸仪器进行合理的布局以及有效地利用计算机进,,行v比I设计己有文献口~叼探讨几何布局工作的计算机辅助设计此种设计在技术上的核心问题即为如何快速地算
4、出二凸多边形或凸多面体之间的距离。文献[4一9]讨论了平面情形,本文考虑的是空间情形,即两凸多面体间的距离。本文考虑两个:已知互不相交的凸多面体间的这样一种距离其值为让它们中的一个平1903年,4月23日收到,国家自然科学基金资助项目‘.2此作者现在工作单位为00魂33上海复且大学计算机系:346陈亮等求两凸多面体间距离的快速算法第4期行;于一条给定的直线作单向移动直至与另一个相交所经过的路径长度若这种移动不可能,。使它们相交则其值为无穷大人们一般会认为求两凸多面体间距离的时间复杂度下界至少应是关于这两个凸多面体,顶点总数的线性函数因为输入这两个凸多面体的有关参数
5、的时间复杂度就是它们顶点总数的线性函数。然而在许多实际情况下,例如在计算机制作动画片、计算机模拟空战飞行等过程中,要处理的凸多面体往往是预先存在于计算机中的,且随着两凸多面体的相对位置的不断变化需要反复多次地求它们之间的距离。在这种情况下,对于每次求距离来说,可以认为关于凸多面体的有关参数是预先存贮于计算机中的。本文给出的算法就是针对参数存贮于计算机中的凸多面体的。,,。本文所采用的术语和概念遵循文献〔123〕对凸多面体数据描述及有关术语和记号(一)对凸多面体的数据描述,。对于任意一个给定的凸多面体我们可以建立一个固结于其上的空间直角坐标系我们称这个直角坐标系为属
6、于此凸多面体的相对直角坐标系。,若给定了一个凸多面体的各顶点在其相对直角坐标系中的坐标也就给定了该凸多而。,体本身(形状和大小)因此我们称一个凸多面体的各顶点在其相对直角坐标系中的坐标的集合为该凸多面体的基本参数。,。,要确定一个凸多面体给出它的基本参数也就足够了但为了计算方便在具体求两凸,,多面体之间的距离时我们还希望有其它的一些辅助信息能被提供使用它们是由计算机根,,,据基本参数一次性求出或由实际部门一次性给出计算机将它们存贮在内存中供每次求距离时使用。,对z于一个给定的凸多面体称过此凸多面体的一个顶点且垂直于其相对坐标系的轴的平面为此;;凸多面体的过顶面称凸
7、多面体的过顶面与此凸多面体的交面为过顶面块称过顶面上平行x;于相对坐标系的轴且过过顶面块的一个顶点的直线为该过顶面块的平线称夹在两相邻过顶面之间的凸多面体的棱的部分为节棱。我们可以很自然地依位置的顺序、(坐标从小到大或从大到小顺时针或逆时针)给一个,给定的;凸多面体的所有的过顶面编号对应地也可给所有的过顶面块编号对于每一个过顶,,;;面给它的所有平线编号对于每个过顶面块给它的所有的顶点编号对于每两相邻过顶,,。面给它们间的所有的节棱编号;对凸多面体的每个顶点给所有与它关联的棱编号,,:在本文中对于给定的凸多面体与编号相对应的以下这些信息被称为辅助信息各过顶面、各平
8、线、各棱、
