Jump to content
  • Advertisement
Sign in to follow this  
xorjesus

How do I find shortest distance...

This topic is 5196 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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!