Gilbert–Johnson–Keerthi distance algorithm: Difference between revisions

Revision as of 02:37, 24 May 2008

Revision as of 14:43, 6 June 2008

Line 1:

The '''Gilbert-Johnson-KeerthiGilbert–Johnson–Keerthi distance [[algorithm]]''' is a method of determining the minimum distance between two [[convex set]]s. 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 (mathematics)|support function]] to iteratively generate closer [[Simplex_algorithm|simplexes]] to the correct answer using [[minkowski sum]](CSO) of two convex shapes.

"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.

Line 8:

==External links==

*[http://intl.ieeexplore.ieee.org/xpl/abs_free.jsp?arNumber=614298 "The Gilbert-Johnson-KeerthiGilbert–Johnson–Keerthi distance algorithm: a fast version for incremental motions", Ong and Gilbert]

*[http://web.comlab.ox.ac.uk/oucl/work/stephen.cameron/distances "Computing the Distance between Objects", Oxford professor Stephen Cameron's implementation of GJK]

Line 14:

[[Category:Convex geometry]]

*[http://code.google.com/p/gjkd/ A 2D implementation of the Gilbert-Johnson-KeerthiGilbert–Johnson–Keerthi (GJK) algorithm, written in the D programming language]

{{Math-stub}}