Computing the distance between a point and a line without cross product

Question

Let P be an arbitrary point. Let S be a segment.

Is there any way of computing the shortest distance between P and S without using cross product?

I found a formula that uses cross product. However, I need to calculate the distance for millions of points. (~ 100 million points)

I am using MATLAB, and using the profiler I realized that the cross product function is taking most of the computation time.

Any ideas would be greatly appreciated.

Answer 1

Let the line segment be $x(t) = x_0 + t d_0$ with $t \in [0,1]$.

You want to solve $\min_{t \in [0,1]} \|x(t) -p_0\|$.

Let $\phi(t) = \|x(t) -p_0\|^2 = ||x_0-p_0\|^2+t^2 \|d_0\|^2-2 t \langle p_0 -x_0, d_0 \rangle$. $\phi$ is a convex quadratic, hence it has a unique minimum, and distance increases as $t$ moves away from the minimizing $t$. Hence we can solve the unconstrained problem first, and then 'project' the solution $t'$ back onto $[0,1]$.

The unconstrained solution is found by solving $\phi'(t') = 0$, which gives $t' = \frac{\langle p_0 -x_0, d_0 \rangle}{\|d_0\|^2}$. Now let $t_0 = \min(1, \max(0, t'))$. Then the shortest distance is given by $\|x(t_0) - p_0\|$.

Answer 2

If you actually want to check the distance to the segment and not to the line, you will have to check that it is not "beyond" one of the endpoints. That is, that the orthogonal projection of the point $x_0$ is between $x_1$ and $x_2$. If not, the answer will be the distance to the closest of the two endpoints.

Here is some pseudocode:

input vectors x0,x1,x2

// if x0,x1,x2 form an obtuse angle, then x0 is closest to x1
if dotprod(x0-x1,x2-x1) < 0 then
    return dist(x0,x1)

// if x0,x2,x1 form an obtuse angle, then x0 is closest to x2
else if dotprod(x0-x2,x1-x2) < 0 then
    return dist(x0,x2)

else 
    return abs(crossprod(x0-x1,x2-x1))/dist(x2,x1)

Cross products and dot products should be relatively inexpensive in terms of compute cost, as they are only a handful of floating point operations each. I know nothing about matlab, but you might want to check if another language would yield performance increases.