Алгоритм GJK
Метод, который определяет, сталкиваются ли два выпуклых тела, отыскивая начало координат внутри их разности Минковского.
Назван по именам Элмера Гилберта, Дэниела Джонсона и Сатьи Киэрти, описавших его в 1988 году. Ключевая идея: два выпуклых множества пересекаются ровно тогда, когда их разность Минковского содержит начало координат. GJK ищет начало координат, не строя разность целиком: он запрашивает только опорные точки — самые дальние точки фигуры в заданном направлении — и наращивает крошечный симплекс (не больше тетраэдра), который либо охватывает начало координат, либо доказывает, что до него не добраться.
Поскольку всё идёт через опорные функции, один и тот же код работает для многогранников, сфер, цилиндров и капсул — для любых выпуклых тел. Если фигуры разделены, GJK возвращает расстояние; глубину проникновения для уже пересёкшихся тел считают в паре с EPA. Алгоритм — краеугольный камень физических движков вроде Bullet и работает в узкой фазе.