Determining the distance of a point from a line segment given a starting and ending point

Question

I've found a lot of answers on how to find the distance from a point to a line, but not so much from a point to a line segment.

I am given the $x$ and $y$ coordinates of the start point and end point of a line segment. I am also given another point. I want to find if that point is a certain distance away from anywhere on the line. For instance, if I'm given the line segment with the starting coordinates $(0, 0)$ and $(10, 1)$, is the point $(3, 4)$ less than $20$ units away from the line segment at the closest point?

In the example below, I would want to be able to theoretically tell that any point in the yellow box is within range of the line.

UPDATE: Right now I am calculating the distance of the point to the line and making sure that the point is within the threshold that I want, however, my calculation continues the line indefinitely. How would I cap it at the threshold past the end points?

Answer 1

Your line segment from $(x_1,y_1)$ to $(x_2,y_2)$ has length $\ell=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$.

The triangle formed by these endpoints and $(x,y)$ has area $A=\frac12\left|(x-x_1)(y-y_2)-(x-y_1)(y-x_2)\right|$.

So the first necessary condition is that $\frac {2A}\ell\le d$, where d is the distance to the line.

Additionally, if the scalar product $(x-x_1)(x_2-x_1)+(y-y_1)(y_2-y_1)$ is negative, we require that $(x-x_1)^2+(y-y_1)^2\le d^2$.

And if the scalar product $(x-x_2)(x_1-x_2)+(y-y_2)(y_1-y_2)$ is negative, we require that $(x-x_2)^2+(y-y_2)^2\le d^2$.

Answer 2

The segment can be parameterized as $$ u(\lambda) = (1-\lambda) u_1 + \lambda u_2 \quad (\lambda \in [0, 1]) $$ where $u_i = (x_i, y_i)$ are the end points of the segment. If $\lambda \not\in I$ we are still on the line, but outside the segment.

The yellow bounding box is the union of the discs with center at $u(\lambda)$ and radius $r$: $$ BB = \bigcup_{\lambda \in [0, 1]} \left\{ u \mid \lVert u - u(\lambda) \rVert \le r \right\} $$

So we know $u\in BB$ if we can find a $\lambda \in I = [0,1]$ with $$ d(\lambda) = \lVert u - u(\lambda) \rVert \le r $$ or $$ 0 \le q(\lambda) = \lVert u - u(\lambda) \rVert^2 \le r^2 $$ where \begin{align} q(\lambda) &= (u - (1-\lambda)u_1 - \lambda u_2)^2 \\ &= (u - u_1 + \lambda(u_1 - u_2))^2 \\ &= \underbrace{(u - u_1)^2}_c + 2\lambda \underbrace{(u - u_1)\cdot (u_1-u_2)}_b + \lambda^2 \underbrace{(u_1-u_2)^2}_a \\ &= a \lambda^2 + 2 b \lambda + c \\ &= a (\lambda + b/a)^2 + c - (b^2/a) \end{align} is a quadratic function in $\lambda$, if $u_1 \ne u_2$, which we assume. We note the dot in the expression for $b$ is a scalar product, and $a > 0$, $b \in \mathbb{R}$ and $c \ge 0$.

\begin{align} d_{01} &= u - u_1 \\ d_{12} &= u_1 - u_2 \\ a &= d_{12}^2 \\ b &= d_{01} \cdot d_{12} \\ c & = d_{01}^2 \end{align}

As $a > 0$ we know that the parabola is upwards open, $q$ has a minimum. Left to the minimum it decreases, right to the minimum it increases.

From the above form (or by inspecting where the derivative vanishes) we can read that the minimum is at $$ (\lambda^*, m) = (-b/a, c - (b^2 / a)) $$

Case 1:

If $\lambda^* \in I$, then our test if $u \in BB$ consists of $$ m \le r^2 $$

Case 2:

If $\lambda^* < 0$, the minimum is to the left of $I$, and $q$ increases on $I$. So the minimum on $I$ is at $\lambda = 0$ and we test for $$ q(0) = c \le r^2 $$

Case 3: Else $\lambda^* > 1$, the minimum is to the right of $I$, and $q$ decreases on $I$. The minimum on $I$ is at $\lambda = 1$ and we test for $$ q(1) = a + 2b + c \le r^2 $$

Example:

For $u_1 = (0,0)$, $u_2 = (10, 1)$ and $u = (3,4)$ we have \begin{align} a &= (u_1 - u_2)^2 = (0 - 10)^2 + (0 - 1)^2 = 101 \\ b &= (u - u_1) \cdot (u_1 - u_2) = (3, 4) \cdot (-10, -1) = -30 - 4 = -34 \\ c &= (u - u_1)^2 = (3,4)^2 = 9 + 16 = 25 \end{align} This gives $\lambda^* = -b/a = 34/101 \in I$ and $m = c - (b^2/a) = 25 - 34^2/101 = 13.55$ For $r=20$ the test would be $$ m = 13.55 \le 20^2= 400 $$ which $u$ would pass.

Answer 3

There are three cases:

Calculate the equations of two line perpendicular to the segment and through the two point and the plane is divided into three parts:

Three parts of the division

1. If the point is in the first part or third part, just calculate the distance from the specified point to starting point or to the end point. (Choose a point that is closer to the specified point than the other)
2. If the point is in the second part, use the formula: abs(ax0+by0+c)/sqrt(a^2+b^2) where x0,y0 is the coordinate of the point and the equation of the line is ax+by+c = 0, reference: https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line

Answer 4

Let ${\bf a}$ and ${\bf b}\ne{\bf a}$ be the endpoints of the given segment, and let ${\bf p}$ be the given extra point.Then you want the minimum of the function $$f(t):=|(1-t){\bf a}+ t{\bf b}-{\bf p}|^2\qquad(0\leq t\leq1)\ .$$ Given the coordinates of ${\bf a}$, ${\bf b}$, and ${\bf p}$ the function $f$ assumes the form $$f(t)=At^2+2Bt+C$$ with certain constants $A>0$, $B$, $C$. Now we have to find the minimum of $f$ in the $t$-interval $[0,1]$. Note that the graph of $t\mapsto f(t)$ is a parabola with a global minimum at some $t_*\in{\mathbb R}$. Compute the zero $t_*:=-{B\over A}$ of $f'(t)$. If $t_*\in\ ]0,1[\ $ then the point on the segment $[{\bf a},{\bf b}]$ nearest to ${\bf p}$ is the point ${\bf x}_*:=(1-t_*){\bf a}+ t_*{\bf b}$. If $t_*<0$ this point is ${\bf a}$, and if $t_*>1$ this point is ${\bf b}$.

Answer 5

For efficiency:

Assume that the segment is given by the complex numbers $p, q$, and let $r$ be the distant point.

• translate $p$ to the origin by computing $q'=q-p,r'=r-p$;
• compute the length $L=|q'|$ and normalize $q''=q'/L$;
• counter-rotate around the origin to make the segment horizontal, $r''=r'\overline{q''}$.

Now the segment is (implicitly) from $0$ to $L$.

• if $\Re(r'')<0$ return the norm $|r''|$;
• else if $\Re(r'')>L$ return the norm $|r''-L|$;
• else return $|\Im(r'')|$.