Minimum distance between a point and a bounded line in 3D

DHeshMan

I have a point in 3D specified by its coordinates (x0, y0, z0)

I have a line in 3D specified and bounded by its end points (x1, y1, z1) and (x2, y2, z2)

How do I calculate the minimum distance between the point and the line, keeping in mind that it may not be the perpendicular distance between the point and the extrapolated line because the line is bounded by its end points.

I would also like to know the point (x4, y4, z4) on the line that is closest to the external point.

mathman

Calculate the distance to the extended line (perpendicular). Check if the minimum point is between the bounds. If it is, you're done. If not, check the distances to the end points. The smaller of the two is then the minimum.

DHeshMan

Can you provide details on how to calculate the perpedicular distance to the extended line?

mathman

It is best done using vector notation.
Let Pk=(xk,yk,zk)
Let A=(P3-P1)x(P2-P1), (x = vector cross product) A is a vector perpendicular to the plane of the Pk's.
Let B=P3-P2, B is the direction of the line joining P2 and P3.
Let C=AxB, C is a vector (used in the plane of the Pk's) perpendicular to B.

The line from P1 to the line containing the P2 to P3 interval is P1+sC.
The line through P2 and P3 is P2+tB.
In the above s and t are scalars.
To find s and t you need to set P1+sC=P2+tB. (3 equation in 2 unknowns - use 2 to solve and the third one is a check.) The point of intersection of the 2 lines is given by the solution.

DHeshMan

I'm a little confused. My original problem statement used P0, P1, P2, and P4 (I inadvertently skipped P3). P0 is the external point, P1 and P2 are the end points of the line, and P4 was the point on the line closest to P0.

Your solution uses P1, P2, and P3? If I follow your theory correctly, your P1 is my P0? your P2 is my P1? your P3 is my P2? and your P1 + sC = P2 + tB = my P4?

HallsofIvy

The line through [itex]P1= (x_1, y_1, z_1)[/itex] and [itex]P2= (x_2, y_2, z_2)[/itex] is given by parametric equations [itex]x= x_1+ t(x_2- x_1)[/itex], [itex]y= y_1+ t(y_2- y_1)[/itex], [itex]z= z_1+ t(z_2- z_1)[/itex]. The plane, perpendicular to that line and containing [itex]P0= (x_0, y_0, z_0)[/itex], is given by [itex](x_2- x_1)(x- x_0)+ (y_2- y_1)(y- y_0)+ (z_1- z_0)(z- z_0)= 0[/itex].

Replacing x, y, and z in the equation of the plane by the parametric equations for the line gives an equation for t where the line intersects the plane. That point is the point, P4, on the line closest to P0.

DHeshMan

Thank you. For those that want a little more clarification, I have the following:

Using the dot product:

point Pn = <xn, yn, zn>
direction dPn = (dxn, dyn, dzn)

A = The line through P1 and P2 = <x1, y1, z1> + t(x2-x1, y2-y1, z2-z1)

B = The line through P0 and P4 = <x0, y0, z0> + s(x4-x0, y4-y0, z4-z0)

If A and B are perpedicular, the dot product dA . dB = 0
(x2-x1) (x4-x0) + (y2-y1) (y4-y0) + (z2-z1) (z4-z0) = 0

Knowing that P4 is a point somewhere on line A
x4 = x1 + t(x2-x1); y4 = y1 + t(y2-y1); z4 = z1 + t(z2-z1)

(x2-x1) (x1 + t(x2-x1) -x0) + (y2-y1) (y1 + t(y2-y1) -y0) + (z2-z1) (z1 + t(z2-z1) -z0) = 0

Solving for t we get

t = ( (x2-x1) (x0-x1) + (y2-y1) (y0-y1) + (z2-z1) (z0-z1) ) / ( (x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 )

Knowing t we can find P4, since t is bounded by P1 and P2; 0 <= t <= 1

If t < 0 then P4 = P1; If t > 1 then P4 = P2; otherwise P4 is calculated using t and the parameterization of A

And the distance can be calculated

dist = sqrt ( (x4-x0)^2 + (y4-y0)^2 + (z4-z0)^2 )

mathman

You are correct. I was careless - I should have said P0, P1, P2 not P1, P2, P3.