Во-первых, если скорости маленькие и движение происходит на маленькие отрезки за итерацию, то можно выталкивать объект в любую сторону.
Если же шаги не настолько мелкие, то нужно, как уже подсказал
Фокс Йовович, сдвигать до пересечения, а не впихивать объект в другой и выталкивать назад.
Есть концептуально простой но далеко не самый эффективный метод - бинарный поиск. Вот вы уже умеете определять, пересекаются ли 2 объекта. Изначально они не пересекались, после сдвигания на 1.0 едениц веремени они пересеклись. Делайте бинарный поиск по времени в отрезке (0, 1): посморите, есть ли пересечение при сдвиге на 0.5 единиц времени. Потом или 0.25 или 0.75 в зависимости от результата проверки. И так пока текущий отрезко в бинпоиске не станет достаточно мал. Но у этого метода большая проблема с большими скоростями - если за время итерации объекты пройдут сквозь друг друга - вы этого не заметите.
Более быстрый метод - это реально искать пересечение тракетории. Для этого пустите лучи из каждой вершины одного объекта параллельные его скорости движения относительно второго объекта. Потом пересеките каждый луч со вторым многоугольником и найдите кратчайший луч. Аналогично надо пустить лучи из всех вершин второго многоугольника в обратную сторону и пересечь их все с первым многоугольником (это если движущийся наткнется на вершину препятствия стороной). Нашли длину минимального луча - на нее и сдвигайтесь. Если задавать лучи параметрически в виде point+t*v, то фактически вы ищете минимальное значение параметра t при пересечении у всех лучей (тут v - вектор скорости за один квант времени,point - вектор координат точки, из который выпустили луч).
В этом методе не надо даже проверять, попадает ли после полного шага объект в препятствие. Нашли минимальное расстояние до пересечения (может быть и бесконечностью, если пересечений нет) - если оно больше сдвига за квант времени, то сдвигайтесь просто на квант времени. в параметрическом подходе, это значит, что сдвигаетесь вы на min(1.0, t).
Этот метод можно соптимизировать с квадратичного до линейного. Представьте, что вектор движения горизонтален (и направлен влево). Можно просто повернуть все точки каждого многоугольника вместе со всем пространством или применять векторные/скалярные произведения для определения, какая точка ниже/левее/правее.
Найдите в каждом многоугольнике самую нижнюю и самую верхнюю точку. Если эти промежутки по OY не пересекаются - то два объекта не столкнутся, можно останавливать проверки. Если промежутки по OY пересекаются, но второй обхект находится правее первого - то они отдаляются и опять можно дальше не проверять. Тут можно сравнить по одной любой точке с каждого объекта.
Потом, как в алгоритме слияния двух отсортированных массивов, берете 2 указателя на 2 самые нижние точки в объектах. В левом объекте указатель будет двигаться против часовой стрелки, а в правом - по. Так вы будете обходить лицевые стороны объектов. Смотрите, какая из двух точек ниже. Пускаете луч из нее и пересекаете с одним отрезком - выходящим из текущей точки на втором многоугольнике вверх, и только с ним. Сдвигаете указатель с той самой нижней точки на следующую. Отстанавливаетесь, когда дошли до обеих высших точек.
Этот метод быстрее, потому что не надо проверять пересечения со всеми отрезками многоугольника у луча, а только с одним.
Можно его до сублинейного соптимизировать через бинарный поиск опять, но тут уже очень сложно. Можно низшую и высшую точки искать за логарифм бинпоиском, а не как выше полным перебором всех точек. Потом тернарным поиском перебираете значение координаты Y и считаете расстояние между двумя многоугольниками вдоль этого горизонтального отрезка. Для этого, опять же бинпоиском, находите 2 отрезка пересекающих эту горизонталь в обоих многоуголниках и пересекаете с горизонталью, чтобы найти 2 конца расстояния. Эта функция расстояния dist(y) будет выпуклой. Поэтому уможно найти ее минимум тернарным поиском.
Простой
