Author Topic: Intersection of a moving point and a moving line (Read 3246 times)

ZippyDee · « **on:** May 26, 2011, 03:17:10 am »

Hey, I'm working on a program that requires me to calculate the intersection of a moving point and a moving line. The point (and each endpoint of the line) has a known x, y, x-velocity, and y-velocity. I am aware that I'll need to integrate this, but I'm not sure how to go about writing that equation in such a way that I can use it in my program. (Speed and size of the resulting equations when translated into code are both obsolete, so don't worry about 'optimizing' calculations.)

Let's assume that an intersection DOES exist between the current point/line locations and the point/line locations after translation from velocity.

Basically, the way I see it I can either integrate between the starting and ending locations of the points and solve for the intersection, or I can have my program just step through and interpolate when it sees that the point has crossed to the other side of the line.

Either way, I'm not sure exactly how to go about writing equations for either method.

Thanks in advance for any help!

AngelFish · « **Reply #1 on:** May 26, 2011, 03:43:40 am »

There's guaranteed to be a analytic solution if 1) there is an intersection between the two and 2) if the equations describing their trajectories are of a degree less than 4. For simplicity, I'll assume the trajectories are linear. I'll assume a couple of things, first. For one thing, you need math. If you're doing this in Axe or ASM, then you're pretty much out of luck, because it wouldn't be pretty to do math in those languages. If you're doing this in BASIC or another language with decent math support, then this will be much easier. I'll assume that you have math. There also needs to be an intersection at some point in time. If there isn't an intersection, any method is going to produce absurd results and inequalities like 2=0.

To get started, visualize the point as having a direction (which is equal to sqrt(x^2+y^2) and we'll call it m) and a location (x,y). From this, if the trajectory is linear, the position of the point at time t [(t,a)] is equal to a=m(t-x )+y. We can do the same for the line, starting from the first point [(t,b)] . The position of the second point can derived from the first point given the length of the line L and is equal to c=m((t-L)-x )+y, where x and y are the coordinates of the first point [(t,c)] .

We can see that the point can intersect anywhere along the line. This means that it can hit the first point at time t or the second point. This is also the only section where a hit can occur and we know the endpoints. So, what you need to do is for every time t that you want to test, just compute the coordinates (t,a), (t,c), (t,b). If (t,a) is on the line between (t,c) and (t,b), then there's a hit. Otherwise, there isn't a hit. You can also see that if the point (t,a) is ever on the line between (t,c) and (t,b) while they're not there, then a hit will never occur.

Hope this helps a bit

Horrowind · « **Reply #2 on:** May 26, 2011, 03:57:39 am »

as I understand this problem, you have 3 points which are moving with constant speed and now you want to figure out, when they are collinear. Lets say, the points are starting in the vectors a0, b0 and c0 and move along the vectors a b and c so that after time t they are at:

a0+t*a, b0+t*b and c0+t*c

To test for collinearity you can check if the vectors

v1 = b0+t*b - a0+t*a

and

v2 = c0+t*c - a0+t*a

are multiples, so there is a k with v1*k = v2. Now you have these two equations:

(b0_x + t*b_x - a0_x + t*a_x) * k = c0_x+t*c_x - a0_x+t*a_x
(b0_y + t*b_y - a0_y + t*a_y) * k = c0_y+t*c_y - a0_y+t*a_y

which lead to:

(b0_x + t*b_x - a0_x + t*a_x) * (c0_y+t*c_y - a0_y+t*a_y) = (c0_x+t*c_x - a0_x+t*a_x) * (b0_y + t*b_y - a0_y + t*a_y)

This is a equation of 2. degree, but the terms are becoming huge, I hope if you could follow me up to this point, you are able to solve it.

EDIT: Okay, I assumed linearity here but anything else would be far more complex.

ZippyDee · « **Reply #3 on:** May 26, 2011, 04:38:28 am »

Thanks to both of you! I think I got it!

I was able to take that equation and solve for the two values of t.

Quote from: Qwerty.55 on May 26, 2011, 03:43:40 am

For one thing, you need math. If you're doing this in Axe or ASM, then you're pretty much out of luck, because it wouldn't be pretty to do math in those languages.

I'm using java, so math is not an issue.

Author Topic: Intersection of a moving point and a moving line (Read 3246 times)

ZippyDee

Intersection of a moving point and a moving line

AngelFish

Re: Intersection of a moving point and a moving line

Horrowind

Re: Intersection of a moving point and a moving line

ZippyDee

Re: Intersection of a moving point and a moving line