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