Sign in to follow this  
xorjesus

How do I find shortest distance...

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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this