Computing the Minimum Directed Distances between Convex Polyhedra

Abstract

Given two disjointed objects, the minimum distance (MD) is the short Euclid-ean distance between them. When the two objects intersect, the MD between them is zero. The minimum directed Euclidean distance (MDED) between two objects is the shortest relative translated Euclidean distance that results in the objects coming just into contact. The MDED is also defined for intersecting objects, and it returns a measure of penetration. Given two disjointed objects, we also define the minimum directed L ¥ distance (MDLD) between them to be the shortest size either object needs to grow proportionally that results in the objects coming into contact. The MDLD is equivalent to the MDED for two intersecting objects. The computation of MDLD and MDED can be recast as a Minkowski sum of two objects and finished in one routine. The algorithms developed here can be used for collision detection, compu-tation of the distance between two polyhedra in three-dimensional space, and robot-ics path-planning problems.