2D AABB count vector for not having collision after movement

Question

I hope it is correct here, I feel like this question is more math related than programming.

Table of Contents

1. Introduction
2. What is question about / problem description
3. What way I figured out
4. Other

Introduction

I have a mathematical problem (more geometry), and I am trying to work out working algorithm (I mean, way to count it, find formula) to get to result. However, after two days I am still unsure about my ,,solution...?" and I would like to kindly ask you for opinions.

What is question about / problem description

1. Lets say we are in 2D Space.
2. All rectangles are axis alligned
3. Rectangle is represented by 4 points

We are given a rectangle $A$. We are alo given a vector $V$. We will move rectangle in direction (and force, it length) of a vector. $A$ new positioned rectangle will be $A'$. We are also given a rectangle $B$. We are sure that $A'$ collides with $B$.

We want to find vector $V_2$ such as, that if we move rectangle $A$ using vector $V_2$:

1. new $A'$ will NOT collide rectangle $B$

2. $V_2$ has same orientation as $V$ (only length changes)

3. new $A'$ will be touching rectangle $B$

4. when ,,moving" $A$, when first $A$ touches $B$, that will be $A'$ (we do not want to touch it on the opposite side) ... images will show it...

   Here is a sketch of a situation (image): I had to remove sketch image, as I do not have reputation points to post more than 2 links. The answer below, however is more clear for understanding the problem

What way I figured out

I was thinking, that:

1. We can all points of rectangle $A'$ that is inside $B$, name it $P_1'$ $P_2'$ $P_3'$ $P_4'$ (or we will have less of them)
2. using $P_1'$ $P_2'$ ..., having $V$, we can get $P_1$, $P_2$ ...
3. Following will be done for ALL the points $P_1$, $P_2$, $P_3$..., I name current working point as WP
4. We ,,set" our vector to the WP point ( vector starts there )
5. Create limited line (line that has minimum and maximum) from V starting in point WP, name it WL (working line L)
6. Count intersection point I from WL and $B$ (here I have no idea what to do if i have more of them...)
7. Get vector FinalV from points WP and I
8. Here we will then have more FinalV, and we choose the smallest one (smallest length). That should be final vector

Question is, whether this will be working in every situation. Allthough I have drawn many images and tried to draw many various situations, I am not sure about this, whether this algorithm is bullet proof.

I am not asking for code, as we are in math forum, I am asking for formula, way to compute this using mathematics / geometry....?

Other

Now any proven working way or way of computing this more efficiently world be awesome. Any help would be appreciated, thanks.

Have a nice day

Edit - Reaction to answer

I tried to count that for one situation.

I set that A rectangle has Upper left corner

(1, 10)

And width and height are

Width = 2, Height = 2

For B rectangle:

Point = (2, 6)
Width = 2, Height = 2

Vector V is

u = 2, v = 5

The situation is shown on the sketch in phoho i add. Here are photos of my counting. I came to result Alpha = -0.5 FinalVector = (-1, -2.5)

Check the graph sketch in part1, might be usefull Counting the equations in hand, part1 Counting the equations in hand, part2

Unfortunatelly I can not add a ling to image to the program results, I do not have reputation points. But program came to same result, only alpha3 and alpha4 are different, as in programming we are in different quadrant

According to your post, when it is negative, the rectangles already collide. But they do not. If, theoretically I would multiply X by -1, I would get FinalVector = (1, -2.5)

wich would be valid result for this case ( it would require rounding, as expected vector is (1, -2) ) I am not sure, whether I made misstake somewhere, wich I find unlikely, as program I wrote confirmed the result. (please notice that PC rounded the final vector)

Could you please help? I tried to understand the equations, but I gues I would have to dive in it for few days to fully understand it....

Thanks

Answer 1

Lets say $A$ is the rectangle $[x_1,x_2]\times [y_1,y_2]$ (i.e., the vertices are $(x_1,y_1)$, $(x_2,y_1)$, $(x_2,y_2)$, $(x_1,y_2)$) and $B$ is the rectangle $[\xi_1,\xi_2]\times [\eta_1,\eta_2]$, and your vector $V$ is $(u,v)$.

We are given that translating $A$ by $V$ makes it intersect $B$, i.e., $$x_1+u\le \xi_2,\quad x_2+u\ge \xi_1,\quad y_1+v\le \eta_2,\quad y_2+v\ge \eta_1. $$ We want to find $\lambda$ with $0\le \lambda\le 1$ such that $$x_1+\lambda u\le \xi_2,\quad x_2+\lambda u\ge \xi_1,\quad y_1+\lambda v\le \eta_2,\quad y_2+\lambda v\ge \eta_1 $$ just barely holds, i.e., at least one of these for inequalities is in fact an equality. This makes the computation feasible:

For each inequality, we determine the value $\lambda$ that turns it into an equality, that is: $$\lambda_1=\frac{\xi_2-x_1}{u}, \quad\lambda_2=\frac{\xi_1-x_2}{u},\quad\lambda_3=\frac{\eta_2-y_1}{v},\quad\lambda_4=\frac{\eta_1-y_2}{v}.$$

Then $A+\lambda V$ intersects (touching or overlapping) $B$ if and only if $\lambda$ is between $\lambda_1$ and $\lambda_2$, inclusive, as well as between $\lambda_3$ and $\lambda_4$, inclusive. In other words, if and only if $$\tag1\begin{align}\lambda &\in[\min\{\lambda_1,\lambda_2\}, \max\{\lambda_1,\lambda_2\}]\cap [\min\{\lambda_3,\lambda_4\},\max\{\lambda_3,\lambda_4\}] \\ &=\Bigl[\max\bigl\{\min\{\lambda_1,\lambda_2\},\min\{\lambda_3,\lambda_4\}\bigr\},\min\bigl\{\max\{\lambda_1,\lambda_2\},\max\{\lambda_3,\lambda_4\}\bigr\}\Bigr]\end{align}$$

Note that we are given that this interval is non-empty, as it must at least contain $1$. Thus we have "first contact" for $$\tag2 \lambda = \max\bigl\{\min\{\lambda_1,\lambda_2\},\min\{\lambda_3,\lambda_4\}\bigr\}.$$ After this, we let $$V_2=(\lambda u,\lambda v). $$

However, we have to watch out for some special cases:

• It may happen that $u=0$. In that case, $\lambda_1$ and $\lambda_2$ are undefined. But $u=0$ also means that the horizontal component does not place a restriction at all. In that case, $(2)$ becomes $$ \tag{2'}\lambda =\min\{\lambda_3,\lambda_4\}.$$
• Similarly, if $v=0$, $$ \tag{2''}\lambda =\min\{\lambda_1,\lambda_2\}.$$
• If both $u=0$ and $v=0$, we are screwed: $A$ does not actually move and we cannot change the length of $V$ as asked to do
• Finally, it may happen that the value obtained from $(2)$ (or $(2')$ or $(2'')$) is negative. This means that already $A$ overlaps $B$ and that $V_2$ is antiparallel to $V$. While this solution, i.e., to move "backwards", is formally valid, it may depend on your application whether or not that is allowed. Or maybe you are additionally given that $A$ and $B$ are disjoint.