I hope it is correct here, I feel like this question is more math related than programming.
Table of Contents
- What is question about / problem description
- What way I figured out
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
- Lets say we are in 2D Space.
- All rectangles are axis alligned
- 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$:
new $A'$ will NOT collide rectangle $B$
$V_2$ has same orientation as $V$ (only length changes)
new $A'$ will be touching rectangle $B$
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:
- 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)
- using $P_1'$ $P_2'$ ..., having $V$, we can get $P_1$, $P_2$ ...
- Following will be done for ALL the points $P_1$, $P_2$, $P_3$..., I name current working point as WP
- We ,,set" our vector to the WP point ( vector starts there )
- Create limited line (line that has minimum and maximum) from V starting in point WP, name it WL (working line L)
- Count intersection point I from WL and $B$ (here I have no idea what to do if i have more of them...)
- Get vector FinalV from points WP and I
- 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....?
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
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....