【摘要】 文章讨论了计算两个凸多面体间的距离的问题。首先分析了不相交凸多面体间的距离的特点,证明了该距离恰是其公垂线段的长度,再利用正交投影把确定此距离转化为一个优化问题。给出了此优化问题的两种解法———5变量的线性规划算法和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.更多还原