Point-Segment Proximity

In various problems, it is necessary to know the distance between a point $\mathbf {p}$ and a polyline formed by multiple segments. The computational weight of this problem grows linearly with the number of points that make up the line: in order to perform these analyses, it is essential that the comparison with the single point is therefore very fast.

In this section, a segment will be defined as that part of the line bounded by the points $\mathbf{a}$ and $\mathbf{b}$. The point $\mathbf {p}$ and the segment can relate in 3 ways: the closest point is $\mathbf{a}$, the closest point is $\mathbf{b}$, or the closest point is a point between the two endpoints.

From a strictly computational point of view, calculating these 3 distances would require 9 multiplications, 6 additions, and one division, in addition to the necessary 3 comparisons. This section shows how the comparison can be computationally improved by using the dot product.

Without loss of generality, one can assume that $\mathbf{a}=(0,0)^{\top}$. From the definition of the dot product

$$\mathbf{p} \cdot \mathbf{b} = \cos \alpha \Vert \mathbf{p} \Vert \Vert \mathbf{b} \Vert$$ (1.34)

and the length of the orthogonal projection of $\mathbf {p}$ onto $\mathbf{b}$

$$\cos \alpha \Vert \mathbf{p} \Vert = \frac { \mathbf{p} \cdot \mathbf{b} } { \Vert \mathbf{b} \Vert }$$ (1.35)

it is possible to compute the point-segment distance more efficiently. The nearest point to $\mathbf {p}$ is $\mathbf{a}$ if and only if $\alpha > \pi/2$, that is $\mathbf{p} \cdot \mathbf{b} <0$, while the nearest point is $\mathbf{b}$ if and only if the projection of $\mathbf {p}$ onto $\mathbf{b}$ is greater than $\Vert\mathbf{b}\Vert$, that is $\mathbf{p} \cdot \mathbf{b} > \Vert \mathbf{b} \Vert^2$. In this case, to obtain just the information about proximity, 4 multiplications and 2 additions are sufficient. If and only if the nearby point is found to be internal, one can proceed with the traditional point-line distance.