Пересекаются эти 2 прямоугольника или нет

Автор темы egor230 
ОбъявленияПоследний пост
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
ОбъявлениеКниги по математике и экономике в добрые руки!10.08.2023 09:45
01.03.2021 00:13
Пересекаются эти 2 прямоугольника или нет
Скажите, пожалуйста, формулу, что определения пересекаются эти 2 прямоугольника или нет?

Есть 2 прямоугольника на плоскости.
Мы знаем углы их поворота и координаты их 8 вершин.



Редактировалось 1 раз(а). Последний 01.03.2021 03:38.
01.03.2021 05:25
хм
знаете координат вершины скажите прямоугольников 8 нафика углом поворотов плоскости на пожалуйста?
01.03.2021 05:38
Пересекаются эти 2 прямоугольника или нет
Дело в том, что Есть игра gta vice city.
авто там прямоугольники.
Мы можем узнать угол авто и координаты всех четырех вершин(x1,y1,x2,y2,x3,y3,x4,y4)
Также мы знаем всё вышеперечисленное у другого авто.

Как определить было ли столкновения двух авто или нет?
Нужна формула.

Проверки пересекаются 2 прямоугольника или нет?
01.03.2021 22:02
Алгоритм
Сначала немного простой теории. Рассмотрим общее уравнение прямой на плоскости A*x+B*y+C=0 и введём функцию двух переменных f , определённую формулой f(x,y) = A*x+B*y+C . Тогда указанная прямая разбивает всю плоскость на 2 полуплоскости, в одной из которых функция f принимает только отрицательные значения, а в другой - только положительные. Это важнейший момент, который Вы должны чётко усвоить, т.к. сам алгоритм основан именно на этом свойстве.
Прямая, проходящая через точки с координатами (x1,y1) и (x2,y2) , задаётся уравнением (x-x1)*(y2-y1) - (y-y1)*(x2-x1) = 0 .
Таким образом любой прямоугольник на плоскости задаётся системой 4-х линейных неравенств, т.к. является пересечением 4-х полуплоскостей. Например прямоугольник с вершинами (0;1) , (2;0) , (4;4) , (2;5) задаётся системой неравенств {-x-2*y+2<=0, 2*x-y-4<=0, x+2*y-12<=0, -2*x+y-1<=0} . Все неравенства здесь получены по формуле выше. Все неравенства будут вида <= , если вершины обходим последовательно против часовой стрелки. Например, первое неравенство получено считая, что (0;1) -первая точка, а (2;0) - вторая точка и так далее. Если для некоторой точки (x,y) все неравенства будут строгими, это означает, что эта точка лежит внутри прямоугольника. Проверьте этот вывод например для точки (1;2) .
Если Вам известны в любой момент времени координаты вершин каждого прямоугольника (проходимые последовательно против часовой), то теперь Вы можете зафиксировать момент столкновения. Оно произойдёт в тот момент, когда некоторая вершина первого прямоугольника окажется внутри второго или некоторая вершина второго прямоугольника окажется внутри первого.
01.03.2021 22:13
Пересекаются эти 2 прямоугольника или нет
спасибо большое за Ваш ответ, я его перечитываю, пытаюсь понять.
вот мой код на с++, как проверить было ли столкновения или нет?


pos = car->m_placement.pos + car->m_placement.right * width + car->m_placement.up * length;
x = pos.x; y = pos.y;//правый верхний угол первого авто.

pos = car->m_placement.pos + car->m_placement.right * (width * -1) + car->m_placement.up * length;
x1 = pos.x; y1 = pos.y;//левый верхний угол первого авто.

pos = car->m_placement.pos + car->m_placement.right * (width * -1) + car->m_placement.up * (length * -1);
x2 = pos.x; y2 = pos.y;//левый нижний угол первого авто.

pos = car->m_placement.pos + car->m_placement.right * width + car->m_placement.up * (length * -1);
x3 = pos.x; y3 = pos.y;//правый нижний угол первого авто.
float angle;// переменная хранить угол авто.
angle = car->GetHeading();// получить угол первого авто.

pos = car1->m_pHandlingData->m_vDimensions; length = pos.x; width = pos.y; height = pos.z;
length =+0.6 ; width = width / 2;


pos = car1->m_placement.pos + car1->m_placement.right * width + car1->m_placement.up * length;
ruangle_x1 = pos.x; ruangle_y1 = pos.y;//правый верхний угол второго авто.


pos = car1->m_placement.pos + car1->m_placement.right * (width * -1) + car1->m_placement.up * length;
luangle_x1 = pos.x; luangle_y1 = pos.y;//левый верхний угол второго авто.


pos = car1->m_placement.pos + car1->m_placement.right * (width*-1) + car1->m_placement.up * (length * -1);
ldwangle_x1 = pos.x; ldwangle_y1 = pos.y;//левый нижний угол второго авто.


pos = car1->m_placement.pos + car1->m_placement.right * width + car1->m_placement.up * (length * -1);
rdwangle_x1 = pos.x; rdwangle_y1 = pos.y;//правый нижний угол второго авто.

float angle1;// переменная хранить угол авто.
angle1 = car1->GetHeading();// получить угол второго авто.



Редактировалось 1 раз(а). Последний 01.03.2021 22:14.
01.03.2021 22:42
Re
Я не программист, а математик. C++ не знаю, работаю только в Maple. Так что с кодом сами разбирайтесь, по существу я не вижу здесь каких-то проблем, если сам принцип Вам понятен.
01.03.2021 22:49
Пересекаются эти 2 прямоугольника или нет
Напишите пожалуйста, формулу, а я перенесу в с++.

помню перенос формулу проверки находится авто в круге с радиусом.

function car_in_radius_mod(car, x1, y1, z1, rx, ry, rz)
local x,y,z=getcarcoordes(car)
if rx == 0 and ry == 0 and x == x1 and y == y1
then return true
else r2 = rx * rx + ry * ry + rz * rz;
x = x - x1 y = y - y1 z = z - z1
end
if x * x + y * y + z * z <= r2
then return true
else return false
end
end
01.03.2021 23:00
Формулы
Все нужные Вам формулы я уже написал. Похоже Вы в них ещё не разобрались должным образом.
05.03.2021 16:55
Через отрезки
Цитата
egor230
Скажите, пожалуйста, формулу, что определения пересекаются эти 2 прямоугольника или нет?

Есть 2 прямоугольника на плоскости.
Мы знаем углы их поворота и координаты их 8 вершин.
Если известны вершины, значит, есть четыре отрезка (пусть даже сочетание отрезков, это по 2 из 4 =6). Проверяем на пересечение отрезки одного прямоугольника с отрезками другого, и всё.
Что касается пересечения самих отрезков, то тут где-то совсем недавно даже тема была. В любом случае, таких тем, например, на киберфоруме вагон и маленькая тележка.
05.03.2021 21:18
хм
Рассмотрим один из прямоугольников - ABCD. Возьмем два вектора, построенные на любых двух смежных сторонах, например, векторы AB и AD. Обозначим любую точку второго прямоугольника как F. Вектор AF можно рассматривать как линейную комбинацию векторов AB и AD, т.е. AF=s*AB+t*AD. Если коэффициенты s и t оба больше 0 и меньше 1, то точка F лежит внутри прямоугольника ABCD. Таким образом, нужно решить систему уравнений относительно неизвестных s и t:

$\{\begin{array}{|}(x_B-x_A)s+(x_D-x_A)t=x_F-x_A\\(y_B-y_A)s+(y_D-y_A)t=y_F-y_A\end{array}$,

и если 0<s<1 и 0<t<1, то точка F лежит внутри прямоугольника ABCD.
Проверяете так все четыре точки второго прямоугольника. Если хотя бы одна лежит внутри первого прямоугольника ABCD, то машинки столкнулись.
14.03.2021 13:09
Пересекаются эти 2 прямоугольника или нет
oneman, zklb (Дмитрий) большое спасибо за неоценимую помощь, спустя 13 лет, пришлось вспоминать математику. Понял, что все забыл.
решил представить 2 прямоугольника, как 4 и 4 отрезка, хотел с помощью 16 проверок, узнать пересекают они друг друга.

bool check_segment(float x1_1, float x1_2, float x2_1, float x2_2, float y1_1, float y1_2, float y2_1, float y2_2) {
float y3 = y1_1 - y1_2;
float x2 = x1_2 - x1_1;
float a = x1_1 * y1_2 - x1_2 * y1_1;
float b = y2_1 - y2_2;
float c = x2_2 - x2_1;
float d = x2_1 * y2_2 - x2_2 * y2_1;
float x, y;
if (x2 * b - c * y3 && y3) {
y = (d * y3 - a * b) / (x2 * b - c * y3);
x = (-a - x2 * y) / y3;
if (min(x1_1, x1_2) <= x <= max(x1_1, x1_2)) {
return true; }
else {
return false;
}

}
else{
if (x2 * b - c * y3 && b) {
y = (d * y3 - a * b) / (x2 * b - c * y3);
x = (-d - c * y) / b;
if (min(x1_1, x1_2) <= x <= max(x1_1, x1_2)) {
return true;
}

else {
return false;
}
}
else { return false;
} }

};
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти