Доброго времени суток!
Возникла следующая задача. Имеется пара пересекающихся невыпуклых тел на плоскости. Необходимо переместить одно из тел на минимальный вектор так, чтобы ликвидировать пересечение. Для выпуклых тел существует известный алгоритм EPA. Для решения описанной задачи рекомендуют разбивать тело на выпуклые части и уже для них применять алгоритм EPA, но мне так и не понятно как выпуклая декомпозиция может помочь. Больше ничего по этому вопросу нагуглить не удалось.
Буду благодарен за любые разъяснения или ссылки на другие подходящие алгоритмы.
Тебя интересует точное решение в общем случае или какое-то более частное или приближенное?
Обычно GJK/EPA применяется в физических движках для устранения взаимного проникновения. Т. к. при симуляции происходит интегрирование координат и скоростей за небольшие промежутки времени, проникновение как правило получается небольшим по сравнению с размерами тел. В этом случае декомпозия выручает: мы просто тестируем все возможные пары выпуклых частей на пересечение и выбираем максимальное. EPA также подскажет нам точку и вектор проникновения.
В общем случае, когда тела сложные, а проникновение очень большое (т. е. общее пересечение очень большое и затрагивает несколько выпуклых фрагментов) не очень понятно, как решить задачу.
Да, в моем случае проникновение может быть достаточно большим, поэтому и возникли проблемы. При этом длина вектора перемещения не обязательно должна достигать глобального минимума (сначала хочется научиться хоть как-нибудь решать эту задачу))
Для выпуклых фигур можно посчитать множество тех сдвигов, при которых пересечение не пусто (на этом, по-видимому, основан этот ваш известный алгоритм). Такое же множество можно построить для невыпуклых фигур примерно так:
Если найти на границе этого множества точку, ближайшую к началу координат, получим ответ на задачу.
Спасибо, попробую.