How to check if an object is moving in direction of a target

• Feb 12th 2011, 11:53 AM
kerrymaid
How to check if an object is moving in direction of a target
Hi,

I need a sanity check on a problem I’m trying to solve. I know where a number of moving objects are positioned at t=6 and t=7. I know where the destination is at t=7. So my goal is that I need to pick the “best” object i.e. the object moving most in the direction of the destination.

So for every object I’m doing the following:

I know position of object at t=7 is (x1,y1)
I know position of destination at t=7 is (x2,y2)

dot_product = (x1*x2)+(y1*y2)
length_a = sqrt(x1*x1 + y1*y1)
length_b = sqrt(x2*x2 + y2*y2)
result_degrees = result_radians * 180 / PI

So my first question is do you think this is correct? It doesn’t seem to give me the right answer e.g. if an object A is at (2,5) at t=6 and (2,2) at t=7 and the destination is at (4,2) at t=7, I seem to get an angle of approx 57 degrees when I would expect an angle of 90 degrees.

Also am I approaching the problem correctly? After I determine the angle of every object with the destination, is it true to say that to pick the “best” object i.e. the one moving towards the destination, is by picking the one with the smallest angle?

• Feb 12th 2011, 12:14 PM
earboth
Quote:

Originally Posted by kerrymaid
Hi,

I need a sanity check on a problem I’m trying to solve. I know where a number of moving objects are positioned at t=6 and t=7. I know where the destination is at t=7. So my goal is that I need to pick the “best” object i.e. the object moving most in the direction of the destination.

So for every object I’m doing the following:

I know position of object at t=7 is (x1,y1)
I know position of destination at t=7 is (x2,y2)

dot_product = (x1*x2)+(y1*y2)
length_a = sqrt(x1*x1 + y1*y1)
length_b = sqrt(x2*x2 + y2*y2)
result_degrees = result_radians * 180 / PI

So my first question is do you think this is correct? It doesn’t seem to give me the right answer e.g. if an object A is at (2,5) at t=6 and (2,2) at t=7 and the destination is at (4,2) at t=7, I seem to get an angle of approx 57 degrees when I would expect an angle of 90 degrees.

Also am I approaching the problem correctly? After I determine the angle of every object with the destination, is it true to say that to pick the “best” object i.e. the one moving towards the destination, is by picking the one with the smallest angle?

1. To answer your question you have to state for each moving object not only the position but the direction of the movement too (vulgo course).

2. You calculated the value of the angle between the two position vectors of a moving object and the target.
• Feb 12th 2011, 12:26 PM
kerrymaid
Ok, Well if I know an object is at position (2,5) at t=6 and (2,2) at t=7 I can assume by working out its speed (assuming no change) that it will be at (2,-1) at t=8. So can this information be used to infer a direction (if so how?) and how is then compared against the destination to pick the best object? Am I even looking at the right thing with my above calculations?

Many thanks.
• Feb 13th 2011, 12:59 AM
earboth
Quote:

Originally Posted by kerrymaid
Ok, Well if I know an object is at position (2,5) at t=6 and (2,2) at t=7 I can assume by working out its speed (assuming no change) that it will be at (2,-1) at t=8. So can this information be used to infer a direction (if so how?) and how is then compared against the destination to pick the best object? Am I even looking at the right thing with my above calculations?

Many thanks.

1. Draw a sketch (see attachment)

2. I assume that you are allowed to use vectors (?). If so:

3. The object moves along a line which passes through the point (2, 5) (at t = 6) and the point (2, 2) (at t = 7). That means the direction is determined by the vector $\vec d = (2,2)-(2,5)=(0,-3)$.Therefore the equation of the line is

$l: (x,y)=\underbrace{(2,5)}_{\rm start point}+(t-6) \cdot \underbrace{(0, -3)}_{\rm direction}$

4. The direction from the start point to the target is determined by the vector $\vec a = (4,2)-(2,5) = (2,-3)$

5. To judge which objects is moving best in the direction to the target you only have to calculate the angle (I've labeled it aberration) between the direction of the move and the direction to the target. In your case the angle $\alpha$ has a value of:

$\cos(\alpha)=\dfrac{(0,-3) \cdot (2, -3)}{\sqrt{9} \cdot \sqrt{13}}=\dfrac 3{\sqrt{13}}~\implies~\alpha \approx 33.69^\circ$
• Feb 13th 2011, 09:47 AM
kerrymaid
Hi Earboth,

That was a really helpful answer. Thanks so much for taking the time to do that.

I have what is hopefully my final query (apologies for the length). The moving objects that I’m referring to are actually cars moving around a city. The reason that I will simply “know” my current and previous position is that I’m assuming that in reality a car will be able to access its current (x,y) position from GPS which in the case of my program will be a file where I can simply read in the cars current and past position (this is a valid enough assumption to make). From this I can work out the distance travelled by the car in a given time interval and thus the cars speed at that time. Also, from your previous answer, I can now infer a direction. This is all great so far.

Finally, I want to ensure that I’m implementing everything correctly. According to the algorithm that I’m implementing, it says the following.

“The following notations are used in the subsequent discussion:
v(I,T): motion vector of node I at time T and p(I,T): position vector of node I at time T”. So it assumes that I know these.

Firstly can I confirm the following: From the above definition, I assume if the current time t=7 that the position vector, , for node I (based on our previous examples) is its position at time t=6 and t=7 i.e. (2,5) and (2,2). I also assume the motion vector is its direction and speed. So the motion vector is direction (0,-3) and speed of 3m/s. is this correct in your opinion?

Secondly: Part of the algorithm expects me to work out the “future” position of a car at time Tc + Δt where Tc is the current time and Δt is a small time slot such as 1 second. I can work this out by assuming the vehicle will move in a straight line. E.g. I know the position of the car at t=6 is (2,5) and at t=7 is (2,2) so calculating the direction vector as (0,-3) (based on your previous example) I can then add the direction vector to (2,2) to get (2, -1). All good.

However obviously a car can make a turn at an intersection. The paper seems to address this by saying “we rely on the accuracy of the motion vector of each vehicle. To handle sudden changes in movement, such as turning at a junction, a vehicle cannot directly report its motion vector accessed from GPS but should refer to past moving behaviour. Let m denote the motion vector access from GPS. Mold and Mnew are the reported motion vectors at the last time and this time respectively.
Mnew = α*Mold +(1- α)*m, 0<= α<=1
Where α=0.3 if the car is located in a junction and 0.7 otherwise”.

So I assume from the above they’re trying to somehow add a weight to the “predictability” of estimating the future position based on linear motion. I can assume that I simply know when a vehicle is located in a junction (this again is a valid assumption).
Now, I’m getting a bit confused about what to sub into the above formula.
So lets assume it’s currently t=7. Do I assume Mold is my old motion vector from t=6 to t=7 i.e. in the example above it is (0,-3) with speed 3m/s or does it represent the motion vector before that from t=5 to t=6. And what do you think lower case ‘m’ actually is? I would have thought ‘m’ and Mnew are the same thing. I would really appreciate if you could show me an example (based on our previous figures) of what you think this formula should be.

Really appreciate the help.
• Feb 15th 2011, 01:34 AM
earboth
Quote:

Originally Posted by kerrymaid
Hi Earboth,

That was a really helpful answer. Thanks so much for taking the time to do that.

You're welcome!
Quote:

I have what is hopefully my final query (apologies for the length). The moving objects that I’m referring to are actually cars moving around a city. The reason that I will simply “know” my current and previous position is that I’m assuming that in reality a car will be able to access its current (x,y) position from GPS which in the case of my program will be a file where I can simply read in the cars current and past position (this is a valid enough assumption to make). From this I can work out the distance travelled by the car in a given time interval and thus the cars speed at that time. Also, from your previous answer, I can now infer a direction. This is all great so far.

Finally, I want to ensure that I’m implementing everything correctly. According to the algorithm that I’m implementing, it says the following.

“The following notations are used in the subsequent discussion:
v(I,T): motion vector of node I at time T and p(I,T): position vector of node I at time T”. So it assumes that I know these.

Firstly can I confirm the following: From the above definition, I assume if the current time t=7 that the position vector, , for node I (based on our previous examples) is its position at time t=6 and t=7 i.e. (2,5) and (2,2). I also assume the motion vector is its direction and speed. So the motion vector is direction (0,-3) and speed of 3m/s. is this correct in your opinion?
As far as I understand the situation you have a position vector p(I, T) and a motion vector v(I, T). (This motion vector contains the direction vector and the speed = absolute value of the direction vector). Then the next place can roughly predicted by:
$p(I+1, T+\Delta t) = p(I, t)+\Delta t \cdot v(I,T)$
where T means the actual time and Δt menas the elapsed time, a time interval.

Quote:

Secondly: Part of the algorithm expects me to work out the “future” position of a car at time Tc + Δt where Tc is the current time and Δt is a small time slot such as 1 second. I can work this out by assuming the vehicle will move in a straight line. E.g. I know the position of the car at t=6 is (2,5) and at t=7 is (2,2) so calculating the direction vector as (0,-3) (based on your previous example) I can then add the direction vector to (2,2) to get (2, -1). All good.
To be exact you add the direction vector multiplied by the elapsed time. With the given example of the previous post the elapsed time was Δt = 1. If you want to go directly from (2, 5) to (2, -1) you have to multiply the direction vector by Δt = 2.
Quote:

However obviously a car can make a turn at an intersection. The paper seems to address this by saying “we rely on the accuracy of the motion vector of each vehicle. To handle sudden changes in movement, such as turning at a junction, a vehicle cannot directly report its motion vector accessed from GPS but should refer to past moving behaviour. Let m denote the motion vector access from GPS. Mold and Mnew are the reported motion vectors at the last time and this time respectively.
Mnew = α*Mold +(1- α)*m, 0<= α<=1
Where α=0.3 if the car is located in a junction and 0.7 otherwise”.

So I assume from the above they’re trying to somehow add a weight to the “predictability” of estimating the future position based on linear motion. I can assume that I simply know when a vehicle is located in a junction (this again is a valid assumption).
Now, I’m getting a bit confused about what to sub into the above formula.
So lets assume it’s currently t=7. Do I assume Mold is my old motion vector from t=6 to t=7 i.e. in the example above it is (0,-3) with speed 3m/s or does it represent the motion vector before that from t=5 to t=6. And what do you think lower case ‘m’ actually is? I would have thought ‘m’ and Mnew are the same thing. I would really appreciate if you could show me an example (based on our previous figures) of what you think this formula should be.

Really appreciate the help.
The last part of your question is a bit foggy to me: Where these values of 0.3 and 0.7 come from?
In my opinion $\alpha = 1$ if there isn't any change in direction and speed:
$M_{new} = 1 \cdot M_{old}+(1-1) \cdot m$
where m is derived from previous GPS data. So in my opinion this m could be calculated by:
$m = M_{oldold}-M_{old}$
so that are always three positions are involved: The current position and the positions one or two steps (one or two Δt) before the momentary position.

Let us assume the car is in a junction. Then $\alpha = 0.3$ according to the text of your question. That means:
$M_{new} = 0.3 \cdot M_{old}+\underbrace{(1-0.3)}_{\rm{= 0.7}} \cdot m$
And this result looks somehow funny to me.

Let's assume the car is at (2, 5) and is moving with $\vec v = (0, -3)$. The time intervall between two measures is $\Delta t = 1$. After 1 s the car makes a right turn, the speed doesn't change. Then the new direction vector is $\vec v = (-3,0)$. The car passes through the points: (2, 5) --> (2, 2) --> (-1, 2)

According to the text of the question (as I understand it!) the car would be at the position (-0.1 , 1.1) (see attachment)