Distance from point to n-dimensional line

Question

The solution for the 3-d case can be found here; I would like to get the generalized version. There's no simple generalization of the Mathworld algorithm since the cross product is defined only for 3 and 7 dimensions, so I understand.

Answer 1

If you use vector algebra (which is easy with a vector algebra library), there is no real difference between the 3-d case and the N-d case. Unfortunately, the page you link to has written out the vector math element by element, which tends to obscure this.

So, paraphrasing from the article: given a line through two points A and B, the minimum distance d to a point P can be computed as:

   n_vector pa = P - A
   n_vector ba = B - A
   double t = dot(pa, ba)/dot(ba, ba)
   double d = length(pa - t * ba)

Note that adding two n_vector's is just like adding a 3-vector, except you add N corresponding elements instead of 3 of them, and scaling an n_vector by scalar t is just like scaling a 3-vector except you scale N elements instead of 3.

Evaluating the length() of an n_vector is only slightly more complicated: you sum up the squares of all N elements (instead of just the 3), and take the sqrt() of the result. Finally, as you may have guessed, the dot() product is the sum of the products of the N corresponding elements (again, instead of just the 3).

Answer 2

Express the line as a function of a single parameter t. Call it X(t).

The distance from a point P to a point on the line X(t0) is just u(t) = || X(t0) - P ||, and you don't actually need to do the square root.

Now find the value of t that minimizes u(t). The standard method from first-semester calculus is to form the derivative du/dt, set it to zero, and solve for t.

If the line is actually a straight line, you will get one solution. If the line is a curve, you may get many solutions, and you'll have to look at all of them to find the actual minimum.

Answer 3

The algorithm is to minimise the distance between the point and the line.

The line is a set of points. Write an equation to express the distance between the given point and each point in the line - it will be something like d = sqrt((a1 - b1)^2 + (a2-b2)^2 + ... + (an-bn)^2).

Now minimise that equation.

Rather than implement this algorithm yourself, I'd suggest you find a library for linear equations in your chosen language. I've heard of JAMA (for Java), but I have never needed to do this so haven't researched it.