Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

closed as off topic by Walter, gnat, Yusubov, StuperUser, ChrisF Oct 17 '12 at 20:23

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

    
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? –  Sunny Juneja Oct 11 '12 at 23:46

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
Terrific! Thank you! –  Matt Phillips Oct 12 '12 at 1:36

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.

share|improve this answer

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.

share|improve this answer
    
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

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