Определить пересечение прямоугольников

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


if (rect1.right() > rect2.left() && rect1.left() < rect2.right() && rect1.bottom() < rect2.top() && rect1.top() > this.bottom())
    return true;


Особенность моего движка в том, что проверку эту я выполняю в каждом кадре (перед перерисовкой графики), тоесть 30 - 60 раз в секунду (зависит от производительности устройства). Из-за этого при больших скоростях одного из прямоугольников пересечение не всегда получается поймать. По моему это называется тоннельный эффект. На прикрепленном рисунке показано что при проверке в первом кадре прямоугольники еще не пересекаются, на втором кадре уже не пересекаются. Но мы то знаем что столкновение должно было произойти.
Вопрос Какую проверку и как ее нужно проводить во втором кадре чтобы узнать пересеклись ли прямоугольники в промежуточное время между последним кадром и текущим?
user posted image
Kommentare (4)
ava
baldman88 | 01.01.2017, 13:33 #
Самое простое (возможно не самое оптимальное) -- это запоминать координаты центров прямоугольников в предыдущем кадре, и, имеея координаты центров в текущем кадре, проверять факт пересечения прямых заданных этими двумя точками (центр в предыдущем кадре и текущем). Только возникает вопрос: допустима ли аппроксимация пути движения прямоугольников между кадрами в виде прямой?
ava
vpf | 01.01.2017, 15:43 #
Можно попробовать обрабатывать смежные кадры на больших скоростях.
Берем начальное и конечное положение прямоугольника в обоих кадрах, объединяем их в одну фигуру, которая по сути содержит все возможные перемещения прямоугольника за эти два кадра.
Затем тоже самое для второго. И наконец рассматриваем пересечение двух вот этих получившихся фигур. 
ava
Akina | 01.01.2017, 19:04 #
Движение объектов можно считать прямолинейным. Тогда траекторию движения объекта можно заменить на "истоптанную" им полосу, и соответственно искать пересечения прямых - границ таких полос.
ava
миг | 02.01.2017, 20:09 #
по координатам прямоугольников можно составить уравнения прямых. решение системы уравнений дает координаты пересечения прямых. если координаты заданной точки пересечения находятся между двумя вершинами любого из прямоугольников, то прямоугольники пересеклись.
Registrieren Sie sich oder melden Sie sich an, um schreiben zu können.
Unternehmen des Tages
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Mitwirkende
  Akina   миг ava  baldman88   anmig   vpf
advanced
Absenden