Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.15 No.3, pp.353-373 (May 1999)
Computing the Minimum Directed Distances Between
Convex Polyhedra

Ching-Long Shih and Jane-Yu Liu
Department of Electrical Engineering
National Taiwan Institute of Technology
Taipei, Taiwan 106, R.O.C.

Given two disjointed objects, the minimum distance (MD) is the short Euclidean 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, computation of the distance between two polyhedra in three- dimensional space, and robotics path-planning problems.

Keywords: mimimum distance, minimum directed distance, Minkowski sum, collision detection, path planning

Full Text () Retrieve PDF document (199905_02.pdf : 140,838 bytes)

Received January 4, 1997; accepted September 5, 1997.
Communicated by Youn-Long Lin.