A fast procedure for computing the distance between complex objects in three-dimensional space

作者：Éric Gilbert, Daniel Johnson, S. Sathiya Keerthi · 发表于：IEEE Journal on Robotics and Automation · 年份：1988 · DOI：10.1109/56.2083 · 被引用次数：1516 · 研究领域：Robotic Path Planning Algorithms、Computational Geometry and Mesh Generation、Optimization and Packing Problems

An algorithm for computing the Euclidean distance between a pair of convex sets in R/sup m/ is described. Extensive numerical experience with a broad family of polytopes in R/sup 3/ shows that the computational cost is approximately linear in the total number of vertices specifying the two polytopes. The algorithm has special features which makes its application in a variety of robotics problems attractive. These features are discussed and an example of collision detection is given.>