Nearest point on line

you mean the direction of the line?

2D, 3D?

you also need a reference point on the line, with the dircection of the line.

ClosestPoint = PointOnLine + ((Point - PointOnLIne) * LineDir) * LineDir;


if your line is made of two points [P1, P2]

ClosestPoint = P1 + ((P2 - P1) * (Point - P1)) * (P2 - P1) / ((P2 - P1) * (P2 - P1))

The theory:
The nearest point on a line to any point is at right-angles to the line (assuming the line is infinatly long)

The practice, thefore, construct a new point using the normal to your line and calculate an intersect:

line 1 is:
r = P1 + sV1
where P1 is a point on your original line, s is a scalar and V1 is your direction vector for that line.

line 2 is:
r = P2 + tV2
where P2 is the point you are testing, V2 is the normal to your original line, and t is a scalar


Now all you do is equate the two:
P1 + sV1 = P2 + tV2

solve for either s or t,
put s of t back into your equation and you have your point!

(PS this can only be guaranteed in 2D space, as in 3D space, your normal to the line might not lie on the same plane as the point you are testing)


-------   

Does it matter? Even if it does matter, does it matter that it matters?

Actually, SonOfNed, there will always be a perpendicular line from a point to a line in 3d space.

As for the solving the nearest point on the line to the point q.

Express p parametrically: p = lineorigin + t.linedirection

Your linedirection is the vector from lineorigin to your line's end point. You must now solve for t. t for the closest point to the line is given by the formula:

t =  (linedirection . (point - lineorigin)) / (linedirection . linedirection)

where . above is the dot product between the vectors above. Be careful of the divide above. If the length of the line direction vector is zero you will get divide by zero, but this shouldn't be a problem. I can give a derivation of the above formula if you need it.

This will give you your parameter t along the line (basically a percentage along the line). If you are dealing with a line segment (ie. a line of limited length) then you must clamp t to the range (0..1) otherwise t will be a parameter along an infinite ray.

Now simply substitute t into the formula
p = lineorigin + t.linedirection

the resultant p is the closest point on the line to the point q.

Hope that helped.
FReY

[edit]
oops Olii's final formula and mine are the same, sorry Olii, just noticed now :D
[/edit]





[edited by - FReY on October 14, 2003 8:06:09 AM]

Just to clear it up:

Yeah FReY your right, any line will have a normal, but in 3D space, any line can have an INFINITE number of normals (i.e. rotated around it,) the point I was making was that his computed normal might not be the correct one.

Secondly, all three of our equations are in essence the same, just come at the problem from different angles.
I do however think that you implementation is probably simpler than mine! (or at least better explained!) :D

------------


Does it matter? Even if it does matter, does it matter that it matters?

Ah, I understand what you mean now SonOfNed. I had just assumed that the normal that he had calculated was the normalized line direction vector. Ooops... he he :D

Anyway, to derive the formula I gave above is pretty simple. It makes use of the fact that the dotproduct between 2 perpendicular vectors is zero. Use your line direction as one vector and use the line from your parametric p to your point in space as the other. Express the dotproduct (formula, not definition) of these 2 vectors = 0, then simply solve for t.

why not simply paramaterize the line... then make a general formula for the distance (squared) from the line to the point. Differentiate, and solve for t=0, then substitute this value of t back into the equation for the line. This will specify the coordinates of the point on the line closest to the general point (and will work in any number of dimensions). This gives the same formula as is specified above in fact... But my method is probably more work.

EDIT: looked at earlier post

[edited by - dmounty on October 15, 2003 1:05:04 PM]