Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Imagine I have a line segment defined by endpoints $p_1$ and $p_2$, and some 3-space coordinate $q$.

Is there a robust (in the sense of never giving divide-by-zero errors) way to quickly determine the distance between the point and line segment?

Update - The neat answer provided by julien seems to provide the distance to a line, not a line segment as specified in the problem description.

share|improve this question
1  
Looks like the sphere plays no role whatsoever in the question. Why mention it? –  Dan Shved Mar 6 '13 at 18:40
    
@DanShved No argument there - I forgot to change it. –  AffiDavid Mar 6 '13 at 18:57
    
Have you considered trying Google? The first hit for "distance point line segment" is the StackOverflow question Shortest distance between a point and a line segment. Also pretty high in the results list is David Eberly's article Distance Between Point and Line, Ray, or Line Segment. –  Rahul Mar 6 '13 at 22:28
    
@RahulNarain I did not google either, I did not even read your comment...Unfortunately. –  1015 Mar 6 '13 at 23:38
    
@RahulNarain I looked through StackOverflow and also the other link you mention. However, Julien's answer is clearer and more helpful than anything at these locations IMO. –  AffiDavid Mar 7 '13 at 5:14
add comment

2 Answers 2

up vote 1 down vote accepted

1) I will first show how to compute the distance between $p$ and the line $(p_1,p_2)$.

Let $u$ be the vector $\vec{p_1p_2}$ and let $v$ be the vector $\vec{p_1q}$.

You want to find the orthogonal projection $p$ of $q$ on the line.

This is given by the formula $$ p=p_1+\frac{(u,v)}{\|u\|^2}u. $$

Once you have $p$, you distance is simply the distance between $p$ and $q$, namely $$ d(p,q)=\|\vec{pq}\|. $$

Note: $(u,v)$ denotes the Euclidean inner-product and $\|u\|=\sqrt{(u,u)}$ the Euclidean norm.

2) Now let us consider the distance to the segment $[p_1,p_2]$. Recall that $q$ is the orthogonal projection of $p$ on the line. There are three cases:

a) The projection $q$ belongs to $[p_1,p_2]$, then your distance is $d(p,q)=\|\vec{pq}\|$.

b) The projection $q$ belongs to $(-\infty,p_1)$, the infinite portion of the line which starts at $p_1$ excluded and does not contain $p_2$. Then your distance is $d(p,p_1)=\|\vec{pp_1}\|$.

c) The projection $q$ belongs to $(p_2,+\infty)$, the infinite portion of the line which starts at $p_2$ excluded and does not contain $p_1$. In this case, it is $d(p,p_2)=\|\vec{pp_2}\|$.

3) How to make this an algorithm.

3.1) Compute $$ \frac{(u,v)}{\|u\|^2}. $$

3.2) If this is in $[0,1]$, you are in case a), so compute $q$ and return $d(p,q)=\|\vec{pq}\|$.

3.3)If this is negative, you are in case b), so return $d(p,p_1)=\|\vec{pp_1}\|$.

3.4) If this is greater than $1$, you are in case c), so the answer is $d(p,p_2)=\|\vec{pp_2}\|$.

I believe this is robust, since this never leads to a division by $0$.

share|improve this answer
    
This is for a line, not a line segment, right? –  AffiDavid Mar 6 '13 at 20:27
    
In Mathematica, computing: EuclideanDistance[PointCoordinate, (LineEndPointOne + Dot[LineVector, LinePointVector]/Norm[LineVector]^2*LineVector)], seems to give the distance to a line, not the line segment. –  AffiDavid Mar 6 '13 at 20:29
    
@AffiDavid Correct, this is for the distance to the line. I forgot the word segment. I'll edit. –  1015 Mar 6 '13 at 23:03
    
@AffiDavid Here you go. I think this should answer your question now. –  1015 Mar 6 '13 at 23:19
    
Thanks, I appreciate the answer for the line segment as well as your previous one! Sorry for the lack of etiquette, I've just been having a difficult time chasing down an actual solution for the line segment question. –  AffiDavid Mar 7 '13 at 5:13
show 1 more comment

Well for a segment you have to consider three situations. If the solution p is in the segment then it is the projection. Otherwise the closest point is either p_1 or p_2 depending on which is closer to p.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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