## 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})$

 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 :)