4

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.

  • This is a mathematics question rather than a programming question, isn't it? – Kirk Broadhurst Oct 11 '12 at 22:52
  • @KirkBroadhurst I was worried about that but I didn't see a 'Stack Exchange Algorithms' site, and there are lots of algorithms on this site--and FWIW I want this because I need to code it... – Matt Phillips Oct 11 '12 at 22:54
  • 3
    You best bet is probably math.stackexchange.com – Robert Harvey Oct 11 '12 at 22:59
  • 1
    I think we could use an appliedmath.stackexchange for this kind of question. So we could quit bothering the serious mathematicians 8^) – comingstorm Oct 11 '12 at 23:01
  • Wouldn't the computer science exchange be a better fit than the math? – sunnyrjuneja Oct 11 '12 at 23:46
8

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

1

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.

  • Hmm, I'm pretty sure derivatives aren't part of the standard 1st semester Calculus curriculum--they weren't in mine--but anyway, thanks. – Matt Phillips Oct 12 '12 at 1:32
  • @Matt, PLEASE tell me you're joking. If you didn't cover the basics of integration and differentiation of functions of one variable in 1st semester calculus, what DID you cover? – John R. Strohm Oct 12 '12 at 3:19
  • Ha, well it was a while ago now but certainly integration, and calculation of the derivative as the limit of (f(x+Dh) - f(x))/Dh. But DiffEq was a second year course, which is my biggest regret not taking as a math major. Tufts U., which is not a bad school. – Matt Phillips Oct 12 '12 at 18:19
0

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.