A fast procedure for computing the distance between complex objects in three-dimensional space
E.G. Gilbert, Daniel Johnson, S. Sathiya Keerthi · IEEE Journal on Robotics and Automation · 1988
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.>
Cited by 1,513 works. doi:10.1109/56.2083
Authors
References
- Convex Analysis
- Real-Time Obstacle Avoidance for Manipulators and Mobile Robots
- Spatial Planning: A Configuration Space Approach
- A subdivision algorithm in configuration space for findpath with rotation
- Interference detection among solids and surfaces
- On the “piano movers'” problem I. The case of a two‐dimensional rigid polygonal body moving amidst polygonal barriers
- Computational Geometry—A Survey
- Collision Detection for Moving Polyhedra
- Distance functions and their application to robot path planning in the presence of obstacles
- An Iterative Procedure for Computing the Minimum of a Quadratic Form on a Convex Set