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

No comments posted yet.

Leave a reply

NOTE: A name and a comment (max. 1024 characters) must be provided; all other fields are optional. Equations will be processed if surrounded with dollar signs (as in LaTeX). You can post up to 5 comments per day.