A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)
In 1988, three engineers came together and developed one of the most clever solutions to the problem of detecting when two complex objects collide.
Their solution, the Gilbert Johnson Keerthi (GJK) algorithm, named after the authors, made an incredible impact in the fields of robotics, control, and computer graphics. This video is about understanding this ingenious algorithm from first principles.
The video covers a broad range of topics from Minkowski sums and differences to support functions to the full implementation of the 2D GJK algorithm.
But what I hope you get out of this is an appreciation of the incredible shifts in perspective that lead to the final algorithm. Coming up with the algorithm is an amazing feat and useful for specific applications, but the overarching problem solving techniques that come through in the journey to the solution is truly invaluable.
Do not forget to share your opinion with us to provide you with the best posts !
Would this work, as a less efficient but I think simpler algorithm? Compute the minkowski difference by using every pair of vertices. Then check if the minkowski difference contains the origin.