Method of searching for points of closest approach, and preprocessing

Abstract

A method of searching for a point of closest approach between two convex polyhedrons K.sub.1, K.sub.2, wherein each convex polyhedron is expressed by creating directed-graph structure data. The method uses a processing unit for searching for points of closest approach. The method includes the step of successively obtaining points of closest approach to a difference convex polyhedron, which is a difference of sets (K.sub.1 -K.sub.2) between the two convex polyhedrons K.sub.1, K.sub.2, and finally obtaining the point of closest approach on each convex polyhedron K.sub.1, K.sub.2. In the evaluation of inner products executed in the course of searching for points of closest approach, the method further includes the step of judging whether the point of closest approach on each convex polyhedron corresponding to the successively obtained point of closest approach to the difference convex polyhedron resides on a vertex, edge or polygon. This judging step is also performed by the processing unit. In each particular case, the vertices used in the inner-product evaluation are obtained from the directed-graph structure data and the inner product evaluation is performed using the position vectors of these vertices.