Search This Blog

Wednesday, November 28, 2007

Exercise for the Reader

Oh no, not another one of Q's easy but slightly tricky quiz questions. Today it's regarding finding the shortest distance between a point and a line. This explains the theory behind it, and how to calculate it.

But if you are only interested in the distance between P and P3 itself, and you don't care what P is, this math is moderately wasteful, as you have to first find P, then calculate the distance between P and P3. Surely there must be a way to calculate the distance without ever calculating P. And in fact, there is.

Find it, without cheating (looking up the answer online of through friends. It's actually pretty easy and simple. I just thought it was kind of neat.


rgov said...

sqrt((xB * yA - xP * yA - xA * yB + xP * yB + xA * yP - xB * yP)^2 / ((xA - xB)^2 + (yA - yB)^2)

where (xA, yA) and (xB, yB) are the endpoints to your line, and (xP, yP) is your point.

Note that this extends your line infinitely. you could do a simple check to make sure that yP falls between yA and yB. If not, use the distance formula to both endpoints and take the minimum.

If you're doing many comparisons to the same line segment, you could cache the products xB * yA, xA * yB, and the square of the distance of the line (in the denominator).

If you have an infinite line (no endpoints), but have its slope and y-intercept, you can find the distance with:

sqrt((xP - (-bAB * mAB + xP + mAB * yP) / (1 + mAB^2))^2 + (-(xP / mAB) + ( -bAB * mAB + xP + mAB * yP) / (mAB * (1 + mAB^2)))^2)

Justin Olbrantz (Quantam) said...

Err. (yA, yB, yP) x (xA, xB, xP)? I'm not familiar with using the cross product in that manner - only the standard (xA, yA, zA) x (xB, yB, zB).