Computing the closest point on a segment to a point


Posted by Diego Assencio on 2014.04.13 under Computer science (Computational geometry)

In a previous post, I described how one can compute the point ${\bf S}$ on a line $r$ which is closest to a given point ${\bf X}$. There I assumed the line $r$ passed through two distinct points ${\bf P}$ and ${\bf Q}$ (see figure 1). In this post I will describe how one can use that technique to compute the closest point on a segment ${\bf PQ}$ to a point ${\bf X}$.

Before we consider the segment case, let's consider again the problem with a line. For a line, the coordinates of ${\bf S}$ can be computed using the equation below: $$ {\bf S} = {\bf P} + \lambda_{\bf S}({\bf Q} - {\bf P}) \label{post_ec3d5dfdfc0b6a0d147a656f0af332bd_eq_S} $$ where: $$ \displaystyle \lambda_{\bf S} = \frac{({\bf X} - {\bf P})\cdot ({\bf Q} - {\bf P})}{({\bf Q}-{\bf P})\cdot ({\bf Q}-{\bf P})} \label{post_ec3d5dfdfc0b6a0d147a656f0af332bd_lambda_closest_point_line_to_point} $$

Fig. 1: ${\bf S}$ is the point on the line $r$ which is closest to ${\bf X}$.

There are three cases which we need to consider in order to solve the problem with a segment instead of a line: $0 \lt \lambda_{\bf S} \lt 1$, $\lambda_{\bf S} \leq 0$ and $\lambda_{\bf S} \geq 1$. To understand why this is so, notice first that equation \eqref{post_ec3d5dfdfc0b6a0d147a656f0af332bd_eq_S} can be written as follows: $$ {\bf S} = {\bf P} + \lambda_{\bf S}({\bf Q} - {\bf P}) = {\bf P} + \lambda_{\bf S}{\bf v} \label{post_ec3d5dfdfc0b6a0d147a656f0af332bd_eq_S_v} $$ where ${\bf v} = {\bf Q} - {\bf P}$ is the vector which connects (and is directed from) ${\bf P}$ to ${\bf Q}$ (as shown in figure 1). Hence, since ${\bf S}$ is equal to the sum of ${\bf P}$ and $\lambda_{\bf S}{\bf v}$, it must be in between ${\bf P}$ and ${\bf Q}$ if $0 \lt \lambda_{\bf S} \lt 1$. If $\lambda_{\bf S} \geq 1$, ${\bf S}$ will be either directly at or "after" ${\bf Q}$ (indeed, for $\lambda_{\bf S}=1$, ${\bf S} = {\bf P} + ({\bf Q} - {\bf P}) = {\bf Q})$. When $\lambda_{\bf S} \leq 0$, ${\bf S}$ will be either "before" or directly at ${\bf P}$ since $\lambda_{\bf S}{\bf v}$ will then point away from ${\bf Q}$ or be the zero vector (if $\lambda_{\bf S} = 0$).

Since we want to compute the point ${\bf S}$ on the segment ${\bf PQ}$ which is closest to ${\bf X}$, we cannot have the point ${\bf S}$ lying outside of ${\bf PQ}$. This means whenever ${\bf S}$ would lie "before" ${\bf P}$ on the line $r$, the closest point from ${\bf PQ}$ to ${\bf X}$ is then ${\bf P}$. Similarly, if ${\bf S}$ would lie "after" ${\bf Q}$, the closest point from ${\bf PQ}$ to ${\bf X}$ is ${\bf Q}$. Figure 2 illustrates these facts.

Fig. 1: ${\bf S}$ is the point on the segment ${\bf PQ}$ which is closest to ${\bf X}$. The figure shows the three possible cases of interest. From left to right, the corresponding $\lambda_{\bf S}$ is such that $0 \lt \lambda_{\bf S} \lt 1$, $\lambda_{\bf S} \leq 0$ and $\lambda_{\bf S} \geq 1$.

To summarize, here is the algorithm which determines the point ${\bf S}$ on a segment ${\bf PQ}$ which is closest to a point ${\bf X}$ (it also works if ${\bf X}$ lies on ${\bf PQ}$):

1.compute $\lambda_{\bf S}$ using equation \eqref{post_ec3d5dfdfc0b6a0d147a656f0af332bd_lambda_closest_point_line_to_point}
2.if $\lambda_{\bf S} \leq 0$, then ${\bf S} = {\bf P}$
3.if $\lambda_{\bf S} \geq 1$, then ${\bf S} = {\bf Q}$
4.if $0 \lt \lambda_{\bf S} \lt 1$, then ${\bf S} = {\bf P} + \lambda_{\bf S}({\bf Q} - {\bf P})$

Comments

Andrew on Feb 27, 2019:
Diego, thank you very much for this article.
Carlos Silva on Mar 31, 2019:
hello, this math works for 3D plane?
Diego Assencio on Mar 31, 2019:
@Carlos: The analysis above applies to any number of dimensions, but only for a point and a segment. It is not valid for planes in three dimensions.
Carlos Silva on Mar 31, 2019:
Yes, understood. Thank you so much. I have a segment and a point in the same 3D plane, so it works. Great job
Olly Crowe on Oct 05, 2019:
I'm not sure I understand equation 2. When we subtract (X-P) or (Q-P) we are subtracting a point from another point, as in two values? So how does that become one value that can be multiplied?
Diego Assencio on Oct 05, 2019:
@Olly: In order to understand this post, you need to be familiar with vector algebra. I could give you a quick introduction to the topic here, but this would hardly help you understand things from a geometrical point of view, so I recommend you take a course in vector algebra first and then read this post again.
Olly Crowe on Oct 05, 2019:
I figured it out, my problem was just that I forgot about dot products. Thank you so much for this algorithm, it's exactly what I was looking for :)
Johan Kotze on Oct 22, 2022:
I have used this a while back to analyse vehicle traffic through a road network based on GPS data. The process I used was matrix based which made determining lambda-S simpler, but I cannot remember where I got the formulas and I do not have access to the database (tSQL) on which I did it. It worked very well, though.