Implement GJK algorithm

[mforets]

GJK (Gilbert-Johnson-Keerthi) is an algorithm that can be used for checking intersection between polytopes in v-rep (works in n-dimensions).

Refs:

• A fast procedure for computing the distance between convex objects in 3D space, Gillbert, Johnson, Keerthi.
• Chapter 9, Real-time collision detection. Christer Ericson.
• https://en.wikipedia.org/wiki/Gilbert%E2%80%93Johnson%E2%80%93Keerthi_distance_algorithm

[roccaa]

I think it is a classic algorithm in robotic for collision detection. Maybe you can find some example of it in this domain.

[schillic]

The algorithm can return a certificate, which is useful when applied in a loop with similar sets.

If the positions in the new frame are close to those in the old frame, the algorithm will converge in one or two iterations. This yields collision detection systems which operate in near-constant time.

[ueliwechsler]

Other Ref:

• https://modiasim.github.io/Modia3D.jl/resources/documentation/CollisionHandling_Neumayr_Otter_2017.pdf

• https://github.com/ModiaSim/Modia3D.jl/tree/9edc974cb97854a7e087f7da166ab58c0fac2597

[mforets]

Thanks for the link! Interesting indeed.

[mforets]

Other ref: https://swt.informatik.uni-freiburg.de/staff/bogom/resources/hscc2015-33

[mforets]

Another reference: (contains a very nice tutorial) https://github.com/kroitor/gjk.c

[mforets]

A Julia implementation:

• https://github.com/JuliaRobotics/EnhancedGJK.jl
• referenced from https://discourse.julialang.org/t/julia-interface-to-bullet-physics/12617/17

[mforets]

That was not the end of the related packges, there is more :)

• https://github.com/arlk/ConvexBodyProximityQueries.jl
• https://github.com/arlk/CurveProximityQueries.jl

[mforets]

This feature is now readily available through https://github.com/arlk/ConvexBodyProximityQueries.jl, which has LazySets as an optional dependency.

Hence, i'll add the "documentation" tag for this issue so that searching for "GJK" etc in the LazySets docs returns a pointer to that package.