Go to index of notes. ~ Go to home page.

Find the Closest Points Between Two 4D Lines ... or... find the points where two objects on linear paths, at a constant velocity, come closest together (or touch).

The travel of the objects must be linear, at a constant velocity, and during the same time period.

This method will find the point along an object's travel where it comes closest to the other object. If the objects are both spheres (or both circles in 2D) the result gained from using this method can then be used to feed-in to the method described in NOTES4# which will in turn tell you where in their travel the spheres will actually collide.

This method is useful for collision detection... especially in a game where objects are traveling so fast that they travel a great distance in a single frame (e.g.: cannon balls, bullets, etc). More simple collision detection methods may get confused when objects move further than, typically, 10% of their size in a single frame, allowing objects to erroniously pass through each other. This method can be used as linear interpolation, with the advantage that it has a constant overhead -- you could, for example, instead get a similar result by comparing the distance between two objects at may points along their path to make sure the objects do not erroniously pass through each other, but as the objects get faster (and travel further in a frame) the CPU overhead will increase (whereas you won't get that problem with my method).

I came-up with this method myself after many days of experimenting and head-scrathing, and I was dead chuffed with myself because it does the job really well... but for all I know it's an already known method hidden-away in some text book I've not seen. :-)

(When I say: 'the point along an object's travel', I mean it as a proportion of the travel i.e.: 0.0 to 1.0 and NOT in any kind measurement like mm or cm.)

The result is a proportion of both of the objects' travel -- the proportion will be exactly the same for either object's travel no matter how the lengths of their travel differ from each other (assuming the travel of both objects is linear, of constant velocity, and during the same period of time)

Because this is a 4 dimensional method it is not suitible to find the intersection between two 3D or 2D lines.

See sphere_collision() for example of how to implement this formula in C source code