С Новым Годом! Поиск в гугле выдает не совсем то что мне нужно. Когда-то мне на этом форуме очень помогли, поэтому обращаюсь снова к вам, господа.
Есть рабочий алгоритм определения пересечения прямоугольников, которые НЕ вращаються:

Особенность моего движка в том, что проверку эту я выполняю в каждом кадре (перед перерисовкой графики), тоесть 30 - 60 раз в секунду (зависит от производительности устройства). Из-за этого при больших скоростях одного из прямоугольников пересечение не всегда получается поймать. По моему это называется тоннельный эффект. На прикрепленном рисунке показано что при проверке в первом кадре прямоугольники еще не пересекаются, на втором кадре уже не пересекаются. Но мы то знаем что столкновение должно было произойти.
Вопрос Какую проверку и как ее нужно проводить во втором кадре чтобы узнать пересеклись ли прямоугольники в промежуточное время между последним кадром и текущим?


Это сообщение отредактировал(а) anmig - 1.1.2017, 12:18

Самое простое (возможно не самое оптимальное) -- это запоминать координаты центров прямоугольников в предыдущем кадре, и, имеея координаты центров в текущем кадре, проверять факт пересечения прямых заданных этими двумя точками (центр в предыдущем кадре и текущем). Только возникает вопрос: допустима ли аппроксимация пути движения прямоугольников между кадрами в виде прямой?

Можно попробовать обрабатывать смежные кадры на больших скоростях.
Берем начальное и конечное положение прямоугольника в обоих кадрах, объединяем их в одну фигуру, которая по сути содержит все возможные перемещения прямоугольника за эти два кадра.
Затем тоже самое для второго. И наконец рассматриваем пересечение двух вот этих получившихся фигур. 

Движение объектов можно считать прямолинейным. Тогда траекторию движения объекта можно заменить на "истоптанную" им полосу, и соответственно искать пересечения прямых - границ таких полос.

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

Это сообщение отредактировал(а) миг - 2.1.2017, 20:15

Извините за столь долгое отсутствие. Спасибо всем за ответы, но возможно я их не понял.
baldman88, Но ведь пересечение прямых не дает нам пересечение прямоугольников.


А как их рассматривать? Я не селен в математике.

Akina, то же самое. Пересечение траекторий объектов не гарантирует пересечение самих объектов, ведь у них могут быть разные скорости.

миг, понять с какой стороны один от другого можно, но как определить было ли пересечение?

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

Лет 5 назад читал книгу о разработке игр и там описывалось определение столкновений двух кругов независимо от кадров. Но в книге было все так сжато написано, что я ничего не понял, но там все сводилось до создания квадратного уравнения основанного на позиции кругов и времени.
Еще нашел гдето алгоритм на C++ но уже без квадратных уравнений. Я как мог перевел его на java, но он не работал. Там почему-то получалось деление на ноль.
Решение точно есть. Иначе как в физических движках происходят точные вычисления столкновений.


Это сообщение отредактировал(а) anmig - 8.1.2017, 00:38

Начни с простейшей вещи - рассчёта момента времени, когда растояние между центрами фигур будет минимальным, и проверки, пересекаются ли сами фигуры. Задача аналитически решаемая и достаточно несложная.

А как это рассчитать?

Есть два момента времени, есть координаты двух объектов (точек-центров) в эти моменты, соответственно получишь уравнение координат для них в любой промежуточный момент, посчитаешь расстояние, возьмёшь производную по времени, найдёшь, где она равна нулю, и в этой точке посчитаешь расстояние. Десятый (или теперь одиннадцатый?) класс средней школы. Хотя счас в школах мож и не учат ничему - тогда первый курс института.

Добавлено через 4 минуты и 19 секунд
Hint: вектор скорости движения центра отрезка между центрами масс равен полусумме векторов скоростей концов этого отрезка - то есть этот центр движется по прямой...

Да, я не учел скорость движения прямоугольников и то, что их центры могут не пересектись, хотя прямоуголиники пересекутся. Вы уже получили весьма полный ответ от Akina (осталось скомбинировать):

К сожалению школу я закончил 13 лет назад. Я пытался найти как создать уравнение для двух движущихся тел, но так и не смог.
Что ж, спасибо всем за внимание.

Пффф... есть координата Х1 точки в момент времени t1, есть координата X2 в момент времени t2. Точка движется прямолинейно без ускорения. Тогда в любой момент времени t1 < t < t2 её координата X = (X1*(t2-t) + X2*(t-t1)) / (t2-t1). Аналогично считается координата Y. Аналогично считаются координаты для второй точки. Квадрат расстояния между ними равен сумме квадратов разностей координат. Нам нужен минимум расстояния - но при этом и квадрат расстояния тоже будет минимальным. В общем, получаем формулу квадрата расстояния от времени, берём производную, приравниваем нулю, считаем время. Если оно лежит в диапазоне между начальным и конечным временем - то смотрим пересечение именно в это время, если нет - то фигуры либо ещё сближаются, либо уже отдаляются, и надо смотреть в той точке из крайних, для которой расстояние меньше.

Добавлено через 1 минуту и 25 секунд
PS. Я школу закончил куда как раньше - и тем не менее... вспомнить не проблема, было бы желание.

Можно построить для каждого прямоугольника 4 прямые, каждая прямая через одну из вершин прямоугольника, и направленные по вектору движения. Найти точки пересечения этих прямых - это будет 16 точек и 32 момента времени, когда вершины прямоугольников приходят в эти точки. В этих 32 моментах времени нужно анализировать взаимное расположение прямоугольников. Т.е. в эти моменты времени вычислить новые положения всех вершин и взаимное расположение прямоугольников - будут пересечены или не будут. Если не пересекутся ни в один из 32 моментов времени, значит пролетели мимо.
Вообще эти точки можно разделить на "точки входа сторон в зону пересечения" и точки выхода сторон из зоны пересечения, и анализировать время входа и выхода, но это более замороченные вычисления. Обратите внимание, что движущиеся прямоугольники всегда врезаются либо горизонтальная сторона с горизонтальной, либо вертикальная с вертикальной. При пересечении хотя бы у одного прямоугольника хотя бы одна из вершин горизонтальной стороны попадает на горизонтальную сторону другого прямоугольника (или одна из вершин вертикальной стороны попадает на вертикальную сторону другого).

Это сообщение отредактировал(а) Курсант - 14.1.2017, 14:17

anmig, можно составлять систему уравнений для определения пересечения прямых, т.е. сторон квадрата.