Common
Gilbert–Johnson–Keerthi distance algorithm
Method of determining minimum distance between two convex sets
Gilbert–Johnson–Keerthi distance algorithm
The Gilbert–Johnson–Keerthi distance algorithm is a method of determining the minimum distance between two convex sets, first published by Elmer G. Gilbert, Daniel W. Johnson, and S. Sathiya Keerthi in 1988. Unlike many other distance algorithms, it does not require that the geometry data be stored in any specific format, but instead relies solely on a support function to iteratively generate closer simplices to the correct answer using the configuration space obstacle (CSO) of two convex shapes, more commonly known as the Minkowski difference. "Enhanced GJK" algorithms use edge information to speed up the algorithm by following edges when looking for the next simplex. This improves performance substantially for polytopes with large numbers of vertices. GJK makes use of Johnson's distance sub algorithm, which computes in the general case the point of a tetrahedron closest to the origin, but is known to suffer from numerical robustness problems. In 2017 Montanari, Petrinic, and Barbieri...
Open boosters, collect cards and trade them. Free to play.
Play for free