Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Определить пересечение прямоугольников

Автор: anmig 1.1.2017, 12:17

С Новым Годом! Поиск в гугле выдает не совсем то что мне нужно. Когда-то мне на этом форуме очень помогли, поэтому обращаюсь снова к вам, господа. Есть рабочий алгоритм определения пересечения прямоугольников, которые НЕ вращаються: Код if (rect1.right() > rect2.left() && rect1.left() < rect2.right() && rect1.bottom() < rect2.top() && rect1.top() > this.bottom())    return true; Особенность моего движка в том, что проверку эту я выполняю в каждом кадре (перед перерисовкой графики), тоесть 30 - 60 раз в секунду (зависит от производительности устройства). Из-за этого при больших скоростях одного из прямоугольников пересечение не всегда получается поймать. По моему это называется тоннельный эффект. На прикрепленном рисунке показано что при проверке в первом кадре прямоугольники еще не пересекаются, на втором кадре уже не пересекаются. Но мы то знаем что столкновение должно было произойти. Вопрос Какую проверку и как ее нужно проводить во втором кадре чтобы узнать пересеклись ли прямоугольники в промежуточное время между последним кадром и текущим?

Автор: baldman88 1.1.2017, 13:33

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

Автор: vpf 1.1.2017, 15:43

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

Автор: Akina 1.1.2017, 19:04

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

Автор: миг 2.1.2017, 20:09

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

Автор: anmig 8.1.2017, 00:33

Извините за столь долгое отсутствие. Спасибо всем за ответы, но возможно я их не понял. baldman88, Но ведь пересечение прямых не дает нам пересечение прямоугольников. Цитата(vpf @  1.1.2017,  15:43 ) И наконец рассматриваем пересечение двух вот этих получившихся фигур А как их рассматривать? Я не селен в математике. Akina, то же самое. Пересечение траекторий объектов не гарантирует пересечение самих объектов, ведь у них могут быть разные скорости. миг, понять с какой стороны один от другого можно, но как определить было ли пересечение? На картинке я показал два случая. На первой картинке объекты пересекаются на второй милисекунде. На второй картинке красный объект имеет большую скорость, и можно увидеть что на второй милисекуде они уже не пересекаються, ни на первой, ни на третей, никогда... Лет 5 назад читал книгу о разработке игр и там описывалось определение столкновений двух кругов независимо от кадров. Но в книге было все так сжато написано, что я ничего не понял, но там все сводилось до создания квадратного уравнения основанного на позиции кругов и времени. Еще нашел гдето алгоритм на C++ но уже без квадратных уравнений. Я как мог перевел его на java, но он не работал. Там почему-то получалось деление на ноль. Решение точно есть. Иначе как в физических движках происходят точные вычисления столкновений.

Автор: Akina 8.1.2017, 12:16

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

Автор: anmig 8.1.2017, 13:54

Цитата(Akina @  8.1.2017,  12:16 ) когда растояние между центрами фигур будет минимальным А как это рассчитать?

Автор: Akina 8.1.2017, 18:06

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

Автор: baldman88 8.1.2017, 19:49

Цитата(anmig @ 8.1.2017,  00:33) baldman88, Но ведь пересечение прямых не дает нам пересечение прямоугольников. Да, я не учел скорость движения прямоугольников и то, что их центры могут не пересектись, хотя прямоуголиники пересекутся. Вы уже получили весьма полный ответ от Akina (осталось скомбинировать): Цитата Движение объектов можно считать прямолинейным. Тогда траекторию движения объекта можно заменить на "истоптанную" им полосу, и соответственно искать пересечения прямых - границ таких полос. Цитата Есть два момента времени, есть координаты двух объектов (точек-центров) в эти моменты, соответственно получишь уравнение координат для них в любой промежуточный момент, посчитаешь расстояние, возьмёшь производную по времени, найдёшь, где она равна нулю, и в этой точке посчитаешь расстояние. Десятый (или теперь одиннадцатый?) класс средней школы. Хотя счас в школах мож и не учат ничему - тогда первый курс института. Добавлено через 4 минуты и 19 секунд Hint: вектор скорости движения центра отрезка между центрами масс равен полусумме векторов скоростей концов этого отрезка - то есть этот центр движется по прямой...

Автор: anmig 9.1.2017, 14:03

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

Автор: Akina 9.1.2017, 14:32

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

Автор: Курсант 14.1.2017, 12:29

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

Автор: миг 18.1.2017, 19:07

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)