Jump to content
  • Advertisement
Sign in to follow this  
xorjesus

How do I find shortest distance...

This topic is 5116 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

Hi there. I have a line and point. How do I figure out a point on the line that is the shortest distance to the actual point? This is a on a 2D plane mind you. If it can be done with just trig and geometry great! I hope I asked this question properly. I'm not asking for the distance formuli, I'm asking for an equation that will figure out the nearest point on a line to any random point on a 2d plane. And I don't want to brute force this. This is part of a fractal zooming program I'm working on. I'm trying to make it interactive. So I'm dealing with numbers that have ridiculous amount of decimals(needed precision). Thanks for any help :]

Share this post


Link to post
Share on other sites
Advertisement
Hmm. I KNOW I remember hearing solution to this in some high school geometry class, but I've completely forgotten it.

You can do it with calculus (just find a globabl minimum on teh distance formula withe the line equation plugged in) pretty easily, but I don't know whether or not that leads staright to a general solution.

Share this post


Link to post
Share on other sites
It's damn easy.
Let's line passes point P and have direction D. (that is,line equation is P+t*D)
We have some point A and we need to find closest point on line.

Let B=A-P

(i prefer to do things relatively to P)

Let C is closest point.
C=P+D*(DotProduct(D,B))/(DotProduct(D,D))

where
DotProduct(D,D)
it's squared length of D.(=1 if normalized)

How i derived it: i just know that DotProduct(a,b) is equal to cosine of angle between vectors * ||a|| * ||b||, and i know what's cosine is (i imagined "projection" of one vector onto other, that's how i think about dot product if one of vectors is unit-length) and then wrote that equation instantly.

How can be derived:
First, remember that in closest point C , vector A-C is perpendicular to line direction. Remember that dot product is 0 for perpendicular vectors.
So you need to find t that
DotProduct(t*D-B,D)=0
(simplified by doing everything relatively to P.)
Expanding:
DotProduct(t*D,D)-DotProduct(B,D)=0
t*DotProduct(D,D)-DotProduct(B,D)=0
t*DotProduct(D,D)=DotProduct(B,D)
t=DotProduct(B,D)/DotProduct(D,D)

Substitute t into line equation, note that DotProduct(a,b)=DotProduct(b,a). Voila,problem solved.

Calculus:
Take the derivative of squared distance and note that it's equal to DotProduct(t*D-B,D)

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!