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



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

23 января 2011


Оглавление:
1. Алгоритм Гилберта Джонсона Кёрти
2. Описание
3. Использование



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

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

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


Просмотров: 2018


<<< Алгоритм Ву
Алгоритм Грэхема >>>