Jump to content
  • Advertisement
Sign in to follow this  
Phillipe

Check out my tutorial please :)

This topic is 4956 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey all, I've seen lately in some game-developing forums that the question "How to calculate the shortest distance between a point and a line?" is being asked quite too often - so I decided I'll make a tutorial which'll explain how to accomplish this - you can all download it from here: http://planet.nana.co.il/xpilox/distance.pdf Any comments/enlightenments/suggestions/question/etc... are extremely welcome! :) Thanks a lot in advance, your's, Arie.

Share this post


Link to post
Share on other sites
Advertisement
When you use a line equation in the form y = mx + b it is not possible (if sticking to real numbers) to represent a vertical line - the slope would be infinite. In fact I think horizontal lines (slope = 0) won't work with your method either since you're also using the inverse of the slope.

A more general way is to use a parametric form: P(t) = A + Bt (which goes through points A and A + B). You can then find the distance to point Q, d(t) = |A + Bt - Q|, and minimize that. To make things simpler we can use the square of the distance, D(t) = (Ax + Bx*t - Qx) ^ 2 + (Ay + By*t - Qy) ^ 2. To minimize D(t), find d/dt D(t), set it to zero, and solve for t. Finally plug that value of t into P(t).

If you do this in 3D you can turn it into a ray-sphere test - if the minimum distance is less than the radius of the sphere, then the line intersects it (with some slight additional fiddling to deal with the fact that the ray is only infinite in one direction).

Share this post


Link to post
Share on other sites
Good idea to make tutorial! I answered this question really waaay too many times there, but forum search sucks and i can't find my posts....

Haven't readed your tutorial, but how it should be done to make it work in all cases and any dimension:

If we have point P and line A+B*t where P,A,B is vectors(2d, 3d, 4d, doesn't matter, works with any) and t is scalar,
closest point is at
tcp=((P-A) dot B)/(B dot B)
It can be derived as uavfun said(from minimization), or from definition of dot product(edit:see other thread) (and second way is much easier).

Note that for unit-length B, (B dot B) = 1

Then, closest point on line is
A+B*tcp

and distance to closest point is
length(A+B*tcp-P) // P->B typo fixed.

It is applicable to any number of dimensions, including 2d.

In this post, "dot" stands for dot product; B dot B gives squared length.

[Edited by - Dmytry on November 29, 2004 3:17:35 AM]

Share this post


Link to post
Share on other sites
A non mathematical comment:

Why in pdf form? I HATE pdfs.. I think it would be easier for everyone if you just made in an HTML page.
..just my little piece of advice..

It does look very helpful by the way, I jotted some of that stuff down.

Share this post


Link to post
Share on other sites

Just to clear something up, I think that when Dymtry said:
Quote:

and distance to closest point is
length(A+B*tcp-B)

he probably meant:

length(A+B*tcp-P)

Anyway... Thanks for the tut, I'm sure folk will find it very useful and I've rated accordingly. One extremely general comment though: a lot of people seem to try and adopt an overly cheerful, chatty tone in tutorials. While this can be useful I personally find it a little distracting if something detailed and technical is being discussed. That's just personal preference though, and somewhere among the pages of most professionally published books you'll find at least an awful pun or two...

Thanks again,

John

P.S. I think the worst computer book pun I've read was in an early Andre La Mothe (can't remember which) -- something like, "Now you're able to produce color values 'til you're RGB( 0, 0, 255 ) in the face!".. I still wake up in cold sweats thinking of it, but then it did stay in my head.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!