Point-Segment Proximity

In several problems, it is necessary to determine the distance between a point $\mathbf {p}$ and a polyline consisting of multiple segments. The computational cost of this problem grows linearly with the number of points making up the line; therefore, to perform these analyses, comparison with an individual point must be very fast.

In this section, a segment is defined as the portion of a line bounded by the points $\mathbf{a}$ and $\mathbf{b}$. The point $\mathbf {p}$ and the segment can be related in three ways: the closest point is $\mathbf{a}$, the closest point is $\mathbf{b}$, or the closest point lies between the two endpoints. From a purely computational standpoint, calculating these three distances would require nine multiplications, six additions, and one division, in addition to the necessary three comparisons. This section shows how the comparison can be improved computationally using the dot product.

Without loss of generality, we 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.70)

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.71)

it is possible to calculate the point-segment distance more efficiently. The point closest to $\mathbf {p}$ is $\mathbf{a}$ if and only if $\alpha > \pi/2$, that is, $\mathbf{p} \cdot \mathbf{b} <0$, whereas the closest 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, only four multiplications and two additions are needed to determine proximity. If and only if the nearest point lies inside the segment, the conventional point-line distance can then be computed.