Computing the closest point on a line to a point


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

Let $r$ be a line passing through two distinct points ${\bf P}$ and ${\bf Q}$ (see figure 1). We wish to compute the point ${\bf S}$ on the line $r$ which is closest to the point ${\bf X}$.

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

We can parameterize $r$ as follows: $$ \label{post_cec5e38d29aae1b00e0d488b0088e952_param_line_from_points} r := \left\{ {\bf R}(\lambda) = {\bf P} + \lambda ( {\bf Q}-{\bf P} ), \; \forall \lambda \in \mathbb{R} \right\} $$ The point ${\bf S}$ of $r$ which is closest to ${\bf X}$ is such that: $$ d({\bf X},{\bf S}) = \min_{\lambda \in \mathbb{R}} d({\bf X},{\bf R}(\lambda)) $$ where $d(\cdot,\cdot)$ is the Euclidean distance function. The value of $\lambda$ for which $d({\bf X},{\bf R}(\lambda))$ is a minimum, $\lambda_{\bf S}$, must satisfy: $$ \frac{d({\bf X},{\bf R}(\lambda))}{d\lambda} \bigg|_{\lambda = \lambda_{\bf S}} = 0 $$ Using the definition of the Euclidean distance $d(\cdot,\cdot)$ on the equation above yields: $$ \frac{d}{d\lambda}\sqrt{ ({\bf R}( \lambda ) - {\bf X})^2 } \bigg|_{\lambda = \lambda_{\bf S}} = \frac{2 ({\bf R}( \lambda_{\bf S} ) - {\bf X})\cdot{\bf R}'( \lambda_{\bf S} )} {2\sqrt{ ({\bf R}( \lambda_{\bf S} ) - {\bf X})^2 }} = 0 $$ where it was assumed that ${\bf X}$ does not fall on the line $r$ (otherwise the denominator would vanish; the result derived at the end will be valid even if ${\bf X}$ falls on $r$ though). From equation \eqref{post_cec5e38d29aae1b00e0d488b0088e952_param_line_from_points}, we have that $$ {\bf R}'( \lambda ) = {\bf Q}-{\bf P} $$ and therefore: $$ \frac{d({\bf X},{\bf R}(\lambda))}{d\lambda} \bigg|_{\lambda = \lambda_{\bf S}} = \frac{({\bf R}( \lambda_{\bf S} ) - {\bf X})\cdot({\bf Q}-{\bf P} )}{d\left( {\bf X},{\bf R}( \lambda_{\bf S} ) \right)} = 0 \label{post_cec5e38d29aae1b00e0d488b0088e952_eq_frac_eq_0} $$ Hence, using equation \eqref{post_cec5e38d29aae1b00e0d488b0088e952_param_line_from_points} with $\lambda=\lambda_{\bf S}$ on equation \eqref{post_cec5e38d29aae1b00e0d488b0088e952_eq_frac_eq_0}, we obtain: $$ ({\bf P} + \lambda_{\bf S} ( {\bf Q}-{\bf P} ) - {\bf X})\cdot ( {\bf Q} - {\bf P} ) = 0, $$ which implies: $$ \boxed{ \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_cec5e38d29aae1b00e0d488b0088e952_lambda_closest_point_line_to_point} $$ The point ${\bf S}$ on the line $r$ can now be directly obtained: $$ \boxed{ {\bf S} = {\bf P} + \lambda_{\bf S}({\bf Q} - {\bf P}) } \label{post_cec5e38d29aae1b00e0d488b0088e952_eq_S} $$ The case in which ${\bf X}$ lies on $r$ yields the same result. To see that, notice that in this case we have ${\bf S} = {\bf X}$ and hence $d({\bf S},{\bf X}) = 0$. Then: $$ {\bf X} = {\bf P} + \lambda_{S}({\bf Q} - {\bf P}) \Longrightarrow {\bf X} - {\bf P} = \lambda_{S}({\bf Q} - {\bf P}) $$ Taking the dot product of both sides of this equation with $({\bf Q}-{\bf P})$ yields again equation \eqref{post_cec5e38d29aae1b00e0d488b0088e952_lambda_closest_point_line_to_point}.

Comments

No comments posted yet.