A Minimum Translational Distance Algorithm of Convex Polyhedra Based on Nonlinear Programming Theory
基于非线性规划理论的凸多面体最小平移距离算法

The problem of minimum translational distance(MTD for short) of convex polyhedra is always an active subfield of computer graphics.The current distance algorithms are deficient in such requirements as stability,realizability,accuracy and efficiency more or less.In order to overcome these limitations,the generalized separable plane is introduced based on the definition of MTD and a new algorithm of the MTD problem using nonlinear programming is presented in the paper.This algorithm is carried out as follow.Firstly,the MTD measure is determined by defining the optimal generalized separable plane-pair.Secondly,the problem of searching the optimal plane-pair is equivalent with nonlinear programming problem under some transforms.Finally,a nonlinear optimization software is used to solve the equivalent model,and therefore MTD measure is determined by the solution.The results show that the proposed algorithm performs linearly with the size of model and over the other algorithms in most of the tests.Besides,it can provide both an accurate measure and the witness vector in a few iterations,which are gently linear with the vertex number.In addition,the implementation is simple and reliable,because only the information of vertex is required and the cycle can be avoided.So,it is a fast and efficient distance algorithm.