Алгоритм расстояния Гилберта-Джонсона-Кирти

Алгоритм расстояния Гилберта–Джонсона–Кирти — это метод определения минимального расстояния между двумя выпуклыми множествами , впервые опубликованный Элмером Г. Гилбертом , Дэниелом У. Джонсоном и С. Сатией Кирти в 1988 году. В отличие от многих других алгоритмов расстояния, он не требует, чтобы геометрические данные хранились в каком-либо определенном формате, а вместо этого полагается исключительно на вспомогательную функцию для итеративной генерации более близких симплексов к правильному ответу с использованием препятствия в конфигурационном пространстве (CSO) двух выпуклых фигур, более известного как разность Минковского .

Алгоритмы "Enhanced GJK" используют информацию о ребрах для ускорения алгоритма путем отслеживания ребер при поиске следующего симплекса. Это существенно повышает производительность для многогранников с большим количеством вершин.

GJK использует подалгоритм расстояния Джонсона, который в общем случае вычисляет точку тетраэдра, ближайшую к началу координат, но, как известно, страдает от проблем с числовой надежностью. В 2017 году Монтанари, Петринич и Барбьери предложили новый подалгоритм, основанный на знаковых объемах, который избегает умножения потенциально малых величин и достиг ускорения от 15% до 30%.

Алгоритмы GJK часто используются пошагово в системах моделирования и видеоиграх. В этом режиме окончательный симплекс из предыдущего решения используется как начальное предположение в следующей итерации или «кадре». Если позиции в новом кадре близки к позициям в старом кадре, алгоритм сойдется за одну или две итерации. Это дает системы обнаружения столкновений, которые работают почти за постоянное время.

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

GJK опирается на две функции:

• ${\displaystyle \mathrm {Опора} (\mathrm {shape}, {\vec {d}})}$, который возвращает точку на фигуре , имеющую наибольшее скалярное произведение с .${\displaystyle {\vec {d}}}$
• ${\displaystyle \mathrm {NearestSimplex} (с)}$, который берет симплекс s и возвращает симплекс на s, ближайший к началу координат, и направление к началу координат, нормальное к новому симплексу. Если сам s содержит начало координат, NearestSimplex принимает s , и две фигуры определяются как пересекающиеся.

Симплексы, обрабатываемые NearestSimplex , могут быть любым симплексным подпространством R ⁿ . Например, в 3D они могут быть точкой, отрезком прямой, треугольником или тетраэдром ; каждый из них определяется 1, 2, 3 или 4 точками соответственно.

функция GJK_intersection(форма p, форма q, начальная_ось вектора): вектор A = Support(p, initial_axis) − Support(q, −initial_axis) симплекс s = {A} вектор D = −A петля : A = Поддержка(p, D) − Поддержка(q, −D) если точка(A, D) < 0: отклонять с = с ∪ {А} s, D, содержит_источник := NearestSimplex(s) если содержит_источник: принимать

• Усовершенствование портала Минковского
• Теорема о разделении гиперплоскостей

• «Быстрая процедура вычисления расстояния между сложными объектами в трехмерном пространстве», Гилберт, Джонсон и Кирти — первая публикация
• «Вычисление расстояния между объектами», реализация GJK профессором Оксфордского университета Стивеном Кэмероном
• «Странный, но элегантный подход к удивительно сложной проблеме (алгоритм GJK)»
• 52-минутная видеолекция о внедрении метода Гилберта-Джонсона-Керти
• «Улучшение алгоритма GJK для более быстрых и надежных запросов расстояния между выпуклыми объектами», Монтанари, Петринич и Барбьери.
• "Ускоренное обнаружение столкновений: перспектива оптимизации", Монто, Ле Лидек, Петрик, Сивич и Карпентье. В этой исследовательской статье в частности показано, как можно ускорить исходный алгоритм GJK, используя стратегии ускорения типа Нестерова, что способствует снижению общей вычислительной сложности GJK.
• «алгоритм Гилберта–Джонсона–Керти, объясненный максимально просто»

Эта статья по прикладной математике – заглушка . Вы можете помочь Википедии, расширив ее.

• в
• т
• е