Имеются два движущихся навстречу прямоугольника с вершинами А1(x1, y1) и A2(x2, y2), размерами H1, W1 и H2, W2 а также скоростями движения V1 и V2. Стороны прямоугольников параллельны осям координат.
Рассчитать время столкновения двух прямоугольников.
IE>Имеются два движущихся навстречу прямоугольника с вершинами А1(x1, y1) и A2(x2, y2), размерами H1, W1 и H2, W2 а также скоростями движения V1 и V2. Стороны прямоугольников параллельны осям координат. IE>Рассчитать время столкновения двух прямоугольников.
М-м, а скорости V1, V2 — это скалярные или векторные величины? Наверное, всё-таки второе, т.к. в первом случае ответ слишком простой будет
A>М-м, а скорости V1, V2 — это скалярные или векторные величины? Наверное, всё-таки второе, т.к. в первом случае ответ слишком простой будет
Векторные величины.
Здравствуйте, inok-etude, Вы писали:
IE>Имеются два движущихся навстречу прямоугольника с вершинами А1(x1, y1) и A2(x2, y2), размерами H1, W1 и H2, W2 а также скоростями движения V1 и V2. Стороны прямоугольников параллельны осям координат. IE>Рассчитать время столкновения двух прямоугольников.
Для начала проверим, что они не пересекаются. Пусть это так.
Тогда пусть x1 <= x2 (иначе все то же самое, только поменять 1<->2). Представим, что второй стоит на месте, а первый движется со скоростью V=(Vx,Vy)=V1-V2. Первый может въехать только в верхнюю, левую или нижнюю сторону второго. Причем, грани, в которые он может въехать зависят от его скорости по x и по y (я считаю, что ось y направлена ВНИЗ):
* Vx <= 0 -- верхняя, нижняя
* Vx > 0 -- все три
* Vy < 0 -- левая, нижняя
* Vy = 0 -- левая
* Vy > 0 -- верхняя, левая
Например, если его скорость Vx<=0, Vy<0, то он может въехать только в нижнюю грань.
Осталось проверить, въедет ли он в каждую из возможных граней. На примере левой грани (заметим, ее имеет смысл проверять только при Vx>0): если он в нее въезжает в момент t, то его правая сторона имеет ту же координату x, что и левая сторона второго квадрата: (x1+W1) + Vx*t == x2, т.е. t = (x2-x1-W1)/Vx, при этом он действительно въехал тогда и только тогда, когда его верхняя сторона не ниже нижней стороны второго квадрата, а нижняя сторона не выше верхней стороны второго квадрата: y1 + Vy*t <= y2 + H2, y1 + H1 + Vy * t >= y2, т.е. надо, чтобы H2 + H1 >= (x2 — x1 — W1) * Vy/Vx + y1 — y2 + H1 >= 0. Аналогично для двух других сторон.
Здравствуйте, vadimcher, Вы писали:
V>Здравствуйте, inok-etude, Вы писали:
IE>>Имеются два движущихся навстречу прямоугольника с вершинами А1(x1, y1) и A2(x2, y2), размерами H1, W1 и H2, W2 а также скоростями движения V1 и V2. Стороны прямоугольников параллельны осям координат. IE>>Рассчитать время столкновения двух прямоугольников.
V>Для начала проверим, что они не пересекаются. Пусть это так.
V>Тогда пусть x1 <= x2 (иначе все то же самое, только поменять 1<->2). Представим, что второй стоит на месте, а первый движется со скоростью V=(Vx,Vy)=V1-V2. Первый может въехать только в верхнюю, левую или нижнюю сторону второго. Причем, грани, в которые он может въехать зависят от его скорости по x и по y (я считаю, что ось y направлена ВНИЗ): V>* Vx <= 0 -- верхняя, нижняя V>* Vx > 0 -- все три V>* Vy < 0 -- левая, нижняя V>* Vy = 0 -- левая V>* Vy > 0 -- верхняя, левая V>Например, если его скорость Vx<=0, Vy<0, то он может въехать только в нижнюю грань.
V>Осталось проверить, въедет ли он в каждую из возможных граней. На примере левой грани (заметим, ее имеет смысл проверять только при Vx>0): если он в нее въезжает в момент t, то его правая сторона имеет ту же координату x, что и левая сторона второго квадрата: (x1+W1) + Vx*t == x2, т.е. t = (x2-x1-W1)/Vx, при этом он действительно въехал тогда и только тогда, когда его верхняя сторона не ниже нижней стороны второго квадрата, а нижняя сторона не выше верхней стороны второго квадрата: y1 + Vy*t <= y2 + H2, y1 + H1 + Vy * t >= y2, т.е. надо, чтобы H2 + H1 >= (x2 — x1 — W1) * Vy/Vx + y1 — y2 + H1 >= 0. Аналогично для двух других сторон.
Ну и забыл, конечно, добавить, что если он может "въехать" в более чем одну из возможных граней, то он въедет в ту, для которой рассчитанное время меньше.
Здравствуйте, inok-etude, Вы писали:
IE>Здравствуйте, vadimcher, Вы писали:
V>>Ну и?
IE>Я не смог решить эту задачу
В том алгоритме, что я написал, стоять должен на месте всегда "правый" прямоугольник, т.е. тот, у которого x не меньше. Но это сути не меняет. Можно и так, как на картинке. Тогда левый-верхний стоит на месте, правый-нижний "пытается врезаться" со скоростью V1-V2. В случае, когда мы останавливаем тот, у которого координата x1 меньше, второй может въехать в него только снизу, справа или сверху (зависит от направления его движения, а также можно еще добавить анализ начальных координат). В твоем случае (я по-прежнему предполагаю, что ось y направлена вниз):
V=V1-V2=(Vx,Vy), причем Vx<0, Vy<0, т.е. въехать он может только снизу или справа. Если въезжает снизу, то это происходит через время t такое, что y1+Vy*t=y2+H2, т.е. t=(y2+H2-y1)/Vy. Здесь проверяешь, что t>=0, другими словами это то же самое, что проверить, что y1>=y2+H2, т.е. что первый изначально ниже второго. Если это так, то через это время левая сторона: x1+(y2+H2-y1)*Vx/Vy, правая: x1+(y2+H2-y1)*Vx/Vy+H1. Тебе надо x1+(y2+H2-y1)*Vx/Vy <= x2+H2, x1+(y2+H2-y1)*Vx/Vy+H1 >= x2, т.е. 0 <= x1-x2+H1+(y2+H2-y1)*Vx/Vy <= H1+H2. С правой стороной аналогично.
Можно еще добавить всяких проверок, например, в данной ситуации он может въехать в правую сторону, только если при проверке на то, въехал ли он в нижнюю сторону оказалось, что левая координата x 1-го больше правой координаты x 2-го. Ну и т.д.
Здравствуйте, inok-etude, Вы писали:
IE>Имеются два движущихся навстречу прямоугольника с вершинами А1(x1, y1) и A2(x2, y2), размерами H1, W1 и H2, W2 а также скоростями движения V1 и V2. Стороны прямоугольников параллельны осям координат. IE>Рассчитать время столкновения двух прямоугольников.
Перейдём в систему координат, в которой первый прямоугольник неподвижен и находится левым нижним углом в нуле, а второй движется влево-вниз.
(Возможно, для этого придётся отзеркалить координаты).
Если второй прямоугольник никак не попадает в квадрант I, то столкновения нет.
Мировая линия второго прямоугольника — полоска между лучами P и Q, проходящими через левый-верхний и правый-нижний углы, соответственно.
Если P пересекает горизонталь 0 правее w1, либо если Q пересекает вертикаль 0 выше h1, то столкновения нет.
Ищем моменты tp и tq, когда P пересекает горизонталь h1, и когда Q пересекает вертикаль w1.
Перекуём баги на фичи!
