shilov's blog

By shilov, 11 years ago, In Russian

Доброго времени суток!

Возникла следующая задача. Имеется пара пересекающихся невыпуклых тел на плоскости. Необходимо переместить одно из тел на минимальный вектор так, чтобы ликвидировать пересечение. Для выпуклых тел существует известный алгоритм EPA. Для решения описанной задачи рекомендуют разбивать тело на выпуклые части и уже для них применять алгоритм EPA, но мне так и не понятно как выпуклая декомпозиция может помочь. Больше ничего по этому вопросу нагуглить не удалось.

Буду благодарен за любые разъяснения или ссылки на другие подходящие алгоритмы.

  • Vote: I like it
  • +8
  • Vote: I do not like it