Gilbert–Johnson–Keerthi distance algorithm: Difference between revisions

Revision as of 02:21, 12 February 2023

Latest revision as of 14:57, 18 June 2024

(2 intermediate revisions by 2 users not shown)

Line 1:

{{Short description|Method of determining minimum distance between two convex sets}}

The '''Gilbert–Johnson–Keerthi distance [[algorithm]]''' is a method of determining the minimum distance between two [[convex set]]s, first published by [[Elmer G. Gilbert]], Daniel W. Johnson, and S. Sathiya Keerthi in 19981988. 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 [[simplex|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.

Line 30:

'''if''' dot(A, D) < 0:

reject

s = s ∪ {A}

s, D, contains_origin := NearestSimplex(s)

'''if''' contains_origin:

Line 50:

*[https://ora.ox.ac.uk/objects/uuid:69c743d9-73de-4aff-8e6f-b4dd7c010907/download_file?safe_filename=GJK.PDF&file_format=application%2Fpdf&type_of_work=Journal+article "Improving the GJK algorithm for faster and more reliable distance queries between convex objects"], Montanari, Petrinic and Barbieri.

*[https://arxiv.org/pdf/2205.09663.pdf "Collision Detection Accelerated: An Optimization Perspective"], Montaut, Le Lidec, Petrik, Sivic and Carpentier. This research article notably shows how the original GJK algorithm can be accelerated by exploiting Nesterov-type acceleration strategies, contributing to lowering the overall computational complexity of GJK.

*[https://computerwebsite.net/writing/gjk "the Gilbert–Johnson–Keerthi algorithm explained as simply as possible"]

{{DEFAULTSORT:Gilbert-Johnson-Keerthi distance algorithm}}