Модераторы: maxim1000
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Определить пересечение прямоугольников, Пересечение движущихся прямоугольников  
:(
    Опции темы
anmig
Дата 1.1.2017, 12:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 17
Регистрация: 17.5.2016

Репутация: нет
Всего: нет



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

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

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

Это сообщение отредактировал(а) anmig - 1.1.2017, 12:18
PM MAIL   Вверх
baldman88
Дата 1.1.2017, 13:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 209
Регистрация: 18.1.2009

Репутация: нет
Всего: 7



Самое простое (возможно не самое оптимальное) -- это запоминать координаты центров прямоугольников в предыдущем кадре, и, имеея координаты центров в текущем кадре, проверять факт пересечения прямых заданных этими двумя точками (центр в предыдущем кадре и текущем). Только возникает вопрос: допустима ли аппроксимация пути движения прямоугольников между кадрами в виде прямой?
PM MAIL   Вверх
vpf
Дата 1.1.2017, 15:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 119
Регистрация: 14.11.2016
Где: Moscow

Репутация: нет
Всего: нет



Можно попробовать обрабатывать смежные кадры на больших скоростях.
Берем начальное и конечное положение прямоугольника в обоих кадрах, объединяем их в одну фигуру, которая по сути содержит все возможные перемещения прямоугольника за эти два кадра.
Затем тоже самое для второго. И наконец рассматриваем пересечение двух вот этих получившихся фигур. 
PM MAIL IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
Akina
Дата 1.1.2017, 19:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20413
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 449



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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
миг
Дата 2.1.2017, 20:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 156
Регистрация: 15.9.2008

Репутация: нет
Всего: 1



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

Это сообщение отредактировал(а) миг - 2.1.2017, 20:15
--------------------
Oaks may fall when reeds stand the storm.
PM MAIL   Вверх
anmig
Дата 8.1.2017, 00:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 17
Регистрация: 17.5.2016

Репутация: нет
Всего: нет



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

Цитата(vpf @  1.1.2017,  15:43 Найти цитируемый пост)
И наконец рассматриваем пересечение двух вот этих получившихся фигур

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

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

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

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

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

Это сообщение отредактировал(а) anmig - 8.1.2017, 00:38
PM MAIL   Вверх
Akina
Дата 8.1.2017, 12:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20413
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 449



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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
anmig
Дата 8.1.2017, 13:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 17
Регистрация: 17.5.2016

Репутация: нет
Всего: нет



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

PM MAIL   Вверх
Akina
Дата 8.1.2017, 18:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20413
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 449



Цитата(anmig @  8.1.2017,  14:54 Найти цитируемый пост)
как это рассчитать?

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

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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
baldman88
Дата 8.1.2017, 19:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 209
Регистрация: 18.1.2009

Репутация: нет
Всего: 7



Цитата(anmig @ 8.1.2017,  00:33)
baldman88, Но ведь пересечение прямых не дает нам пересечение прямоугольников.

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

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

PM MAIL   Вверх
anmig
Дата 9.1.2017, 14:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 17
Регистрация: 17.5.2016

Репутация: нет
Всего: нет



К сожалению школу я закончил 13 лет назад. Я пытался найти как создать уравнение для двух движущихся тел, но так и не смог.
Что ж, спасибо всем за внимание.
PM MAIL   Вверх
Akina
Дата 9.1.2017, 14:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20413
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 449



Цитата(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. Я школу закончил куда как раньше - и тем не менее... вспомнить не проблема, было бы желание.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
Курсант
Дата 14.1.2017, 12:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 338
Регистрация: 21.2.2009
Где: Балашиха или Воро неж

Репутация: нет
Всего: 4



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

Это сообщение отредактировал(а) Курсант - 14.1.2017, 14:17
PM ICQ Skype   Вверх
миг
Дата 18.1.2017, 19:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 156
Регистрация: 15.9.2008

Репутация: нет
Всего: 1



anmig, можно составлять систему уравнений для определения пересечения прямых, т.е. сторон квадрата. 
--------------------
Oaks may fall when reeds stand the storm.
PM MAIL   Вверх
Google
  Дата 19.8.2019, 17:28 (ссылка)  





  Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1268 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.