| 计算两个凸多面体间距离的一个新算法 |
| |
| 引用本文： | 周水生,容晓锋,周利华. 计算两个凸多面体间距离的一个新算法[J]. 苏州科技学院学报(自然科学版), 2003, 20(2): 11-16 |
| |
| 作者姓名： | 周水生 容晓锋 周利华 |
| |
| 作者单位： | 1. 西安电子科技大学理学院,陕西,西安,710071;西安电子科技大学多媒体研究所,陕西,西安,710071
2. 西安电子科技大学多媒体研究所,陕西,西安,710071 |
| |
| 基金项目： | “十五”国家部委科技(电子)预研资助项目(413160501)。 |
| |
| 摘 要： | 文章讨论了计算两个凸多面体间的距离的问题。首先分析了不相交凸多面体间的距离的特点，证明了该距离恰是其公垂线段的长度，再利用正交投影把确定此距离转化为一个优化问题。给出了此优化问题的两种解法——5变量的线性观划算法和2变量的区域搜索算法，并对计算复杂性进行了分析。该方法的优点是存储量小，只需存储凸多面体的顶点信息，并可推广来确定移动凸多面体间的距离及一个凸多面体的最大(小)跨度。
|
| 关 键 词： | 凸多面体 距离 投影 线性规划 算法 |
| 文章编号： | 1672-0687(2003)02-0011-06 |
| 修稿时间： | 2003-02-15 |
A Novel Method for Computing the Distance Between Convex Polyhedra |
| |
| ZHOU Shui-sheng ,,RONG Xiao-feng ,ZHOU Li-hua. A Novel Method for Computing the Distance Between Convex Polyhedra[J]. Journal of University of Science and Technology of Suzhou, 2003, 20(2): 11-16 |
| |
| Authors: | ZHOU Shui-sheng RONG Xiao-feng ZHOU Li-hua |
| |
| Affiliation: | ZHOU Shui-sheng 1,2,RONG Xiao-feng 2,ZHOU Li-hua 2 |
| |
| Abstract: | A novel method to compute the distance between convex polyhedra is provided in this paper.First of all,we prove the distance between convex polyhedra just equating with the length of their common perpendicular segment ,and then an optimization problem is proposed to obtain the length by vertical projection.Finally,two methods are extended to solve the problem.The com-plexity of the methods is discussed.The main advantage of the method is a few storages needed and only the vertexes information of the two convex polyhedra needed.It can be generalized to computing the distance between moving objects and the maximum or minimum span of a convex polyhedron. |
| |
| Keywords: | the distance between convex polyhedra common perpendicular line projection linear programming algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
