Алгоритмы обнаружения коллизий плоских двумерных объектов произвольной формы

Аннотация

Файзрахманов Р.А., Мурзакаев Р.Т., Швецов М.Д., Мехоношин А.С., Хабибулин А.Ф.

Дата поступления статьи: 29.09.2015

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

Ключевые слова: алгоритм обнаружения коллизий, плоские двумерные объекты, невыпуклые контуры, выпуклая декомпозиция, алгоритм GJK/EPA, сумма Минковского, теорема о разделяющих осях

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Читать статью в формате PDF