0
$\begingroup$

I'm trying to find the intersection point of two moving objects(O1, O2). I used the solution from here https://stackoverflow.com/a/10359399/3091856 previously but the requirements changed and sadly it isn't accurate enough anymore.

O1 has a known current location (everything is 2D), target location and the path between those is separated into multiple(number known) path segments. Each path segment has a known start speed(Sv0), end speed(Sv1), start position(Ss0), end position(Ss1), duration(St), and acceleration(Sa).

O2 has a known current location(s0), current speed(v0), ideal speed(v1), and an acceleration from current to ideal speed(a). The acceleration should get added until the ideal speed is reached independently from factors like intersection point distance for example.

enter image description here

Since I'm not very math-savvy I wasn't even certain about adding accelerations to the quadratic equation (from the linked answer) let alone multiple segments instead of one path so some help would be very appreciated. I hope the question/problem is clear. Otherwise let me know with a comment.

Edit: The direction of O2 isn't given here. I'm basically looking for a good position where O2 can catch/collide with O1 which O2 will actively try to do with one linear path from the O2 original location to the projected O1 intersection location. I know that there might be multiple points or no points at all. The objects don't really have a radius.

$\endgroup$
  • $\begingroup$ -1. Unclear. Intersection point of 2 moving objects does not make sense unless they collide, which is not guaranteed to happen. Do you want to find the point at which the two tracks intersect? Or the point at which the two objects collide or come closest? $\endgroup$ – sammy gerbil Mar 26 '17 at 17:00
  • $\begingroup$ @sammygerbil I updated my question with an edit $\endgroup$ – Vider7CC Mar 26 '17 at 18:40
1
$\begingroup$

What you want to do is calculate four functions of t, call them x1(t), y1(t), x2(t), and y2(t), which are the x,y coordinates of object 1 and 2. These four functions are completely independent, you can get each one without ever looking at any of the other 3 simply by looking at one coordinate at a time and one object at a time. Since every segment involves constant acceleration, all you need is how to get functions like x(t) when there is constant acceleration (that quadratic you mentioned, using only the component of the acceleration and the velocity that is in the x direction for an x calculation, etc.), and then all the rest is simply breaking up the t into the appropriate intervals (which is easy because you say the explicit intervals in the x and y coordinates are known for object 1, and for object 2 there are only two segments, the first at constant acceleration and the second at zero acceleration). So find those four functions, and you are ready to move on to the next issue.

Then comes the important question-- do you want to know if there is a location where the two objects collide, i.e., if they are ever at the same place at the same time, or do you just want to know the point where their paths cross and don't care if both objects are at that point at the same time or not? It is much more likely that the paths will cross, then that the objects will collide when the paths cross, indeed the latter issue will depend on how large the objects are and you didn't mention that. If the objects are small, it is unlikely that they would ever collide at all, for example.

So let's start by assuming you just want the intersection point of the paths, but not of the objects themselves, since we are not expecting the objects to collide. To get this, you want to get rid of the time variable, because you don't care when things happen if you only want the point of intersection of the paths. It is easy to get rid of t, you would simply take x1(t) and y1(t) and invert one of those functions, like find t(y2), and then find x1(y1) by saying x1(y1) = x1(t=t(y1)). Since t is broken up into intervals, it's better to use the fact that y1 is also broken up into intervals explicitly, and so to find x1(y1), you first ask which interval y1 lies in, then pick out the appropriate y1(t) for that interval, invert that to t(y1) for that interval, and use that t(y1) in x(t=t(y1)) to yield x1(y1) for that interval. Watch out-- since you have quadratic equations in t, you will have two t solutions when you invert t(y1), you have to pick the t that actually falls in the correct time interval, the other one won't if the velocity does not reverse sign (if it does, you have to further break the segment up until it doesn't, or you won't have a unique x(y) for that segment). So now you have x1(y1) in each y1 interval (though see later for a good way to avoid having to do this much work.)

Then do the same for particle 2. Now you are simply looking for the y where x1(y)=x2(y), and that will be the path intersection point {x,y}. It's still a bit tricky because the analytic form of every one of the x1(y) and x2(y) functions in each interval will likely give some y where x1=x2, but you only want solutions where the y you get actually falls within that y interval. There is no guarantee that any of them will, and there is no guarantee that only one of them will, because the paths can cross any number of times, but that's the only way to find those crossing points, you have to manually check that the analytic solutions for y of x1(y)=x2(y) for each interval give a y within that interval.

Honestly, all this is probably too much analytic work, so you could proceed graphically instead, where you create what are called parametric plots-- you just run through all t and plot the locus of points {x1(t),y1(t)} and the locus {x2(t),y2(t)}, and visually inspect where the graphs cross. Since you cannot plot a continuous variable, you will have to break t up into discrete closely-spaced values and proceed sequentially through those values, but if you make the steps in t short enough, you should get a good approximation for where the curves cross. If you want it to be exact, you could use the graph to tell you which analytic interval a crossing occurs in, and then solve for the crossing point in the above way but just for those intervals for x1(y1) and x2(y2). In fact, you should definitely start with the graphical approach, because you know the segment endpoints for object 1 already, so a graph of the motion of object 2 already tells you which endpoints that path will cut between, and you can likely assume that this will be the only interval in which an intersection is possible. Hence, you only need to do the analytic work I mentioned above for that single interval-- none of the others will matter, so that's vastly less work!

If you also want to know if the objects collide, you need to further ask at what times each object was at the intersection points, and ask how big the objects are, and see if that implies a collision. This will be much harder, because the objects might collide without the paths intersecting, they could just pass close enough to each other. Again, manual inspection of a graph will probably be key for identifying potential collisions, but you still have to check if the times are close enough, so it's tricky.

$\endgroup$
  • $\begingroup$ First of all thank you very much for the detailed response! To respond to your question about the intersection of paths or objects: Sorry, I just realized that wasn't clear at all in my question. I'm actually looking for a good position where O2 can intersect / collide with O1 so the direction of O2 isn't known at all and O2 is kinda trying to catch O1. So I guess that's a problem when I want to create the methods x2(t) and y2(t) because the direction depends on x1(t) and y1(t). $\endgroup$ – Vider7CC Mar 26 '17 at 18:30
  • $\begingroup$ Again sorry that I'm clearing that up after you responded but thoughts on how to modify the approach for the unknown direction would still be very much appreciated. $\endgroup$ – Vider7CC Mar 26 '17 at 18:46
  • $\begingroup$ It sounds like you want object 2 to reach some sort of ideal ramming speed and then collide with object 1. The guts of such a calculation are the same as the above, just pick a reasonable seeming interval to get the collision, and find x1(t) and y1(t) for that interval, and pick any t within that interval. Then solve for the acceleration needed to get x2(t)=x1(t) and y2(t)=y1(t) at that t. If the acceleration is unreasonable, try a different interval. $\endgroup$ – Ken G Mar 26 '17 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.