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.

  • 1
    $\begingroup$ Looks like the sphere plays no role whatsoever in the question. Why mention it? $\endgroup$ – Dan Shved Mar 6 '13 at 18:40
  • $\begingroup$ @DanShved No argument there - I forgot to change it. $\endgroup$ – AffiDavid Mar 6 '13 at 18:57
  • $\begingroup$ 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. $\endgroup$ – user856 Mar 6 '13 at 22:28
  • $\begingroup$ @RahulNarain I did not google either, I did not even read your comment...Unfortunately. $\endgroup$ – Julien Mar 6 '13 at 23:38
  • $\begingroup$ @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. $\endgroup$ – AffiDavid Mar 7 '13 at 5:14

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 $q$ and $p$, namely $$ d(q,p)=\|\vec{qp}\|. $$

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 $p$ is the orthogonal projection of $q$ on the line. There are three cases:

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

b) The projection $p$ 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(q,p_1)=\|\vec{qp_1}\|$.

c) The projection $p$ 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(q,p_2)=\|\vec{qp_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 $p$ and return $d(q,p)=\|\vec{qp}\|$.

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

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

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

  • $\begingroup$ This is for a line, not a line segment, right? $\endgroup$ – AffiDavid Mar 6 '13 at 20:27
  • $\begingroup$ 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. $\endgroup$ – AffiDavid Mar 6 '13 at 20:29
  • $\begingroup$ @AffiDavid Correct, this is for the distance to the line. I forgot the word segment. I'll edit. $\endgroup$ – Julien Mar 6 '13 at 23:03
  • $\begingroup$ @AffiDavid Here you go. I think this should answer your question now. $\endgroup$ – Julien Mar 6 '13 at 23:19
  • 3
    $\begingroup$ It seems that p in the first sentence should be q? $\endgroup$ – combinatorial Dec 3 '14 at 22:40

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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