Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Гилберта Джонсона Кёрти

Алгоритм Гилберта — Джонсона — Кёрти — алгоритм для определения минимального расстояния между двумя выпуклыми множествами. В отличие от многих других алгоритмов нахождения расстояния, GJK не требует, чтобы геометрические данные были сохранены в каком-либо специфическом формате. Вместо этого алгоритм GJK полностью полагается на носитель функции и итерационным методом генерирует ближайшие симплексы для корректного определения минимального расстояния между двумя выпуклыми объектами. При этом алгоритм GJK в своей работе использует понятия суммы Минковского для двух выпуклых форм.

В случае нахождения минимального расстояния между двумя невыпуклыми объектами можно:

1. разбить невыпуклый объект на несколько выпуклых и затем применить метод для образовавшихся выпуклых объектов;
2. представить геометрию как триангулярную поверхность и использовать общий алгоритм столкновения триангулярных сеток, что опять включает использование алгоритма столкновений выпуклых объектов.