4
$\begingroup$

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.

example

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?

$\endgroup$
  • 2
    $\begingroup$ I would have expected the yellow box to have rounded caps, though $\endgroup$ – Hagen von Eitzen Feb 2 '16 at 13:56
  • $\begingroup$ @HagenvonEitzen yes, that's true! I was just trying to show the general idea of what I'm trying to do, I've changed the drawing! $\endgroup$ – tibsar Feb 2 '16 at 13:57
  • $\begingroup$ The relative scale of coordinates, ranging from $0$ to $10$ for $x$, does not match the $20$ "units" of the corridor. $\endgroup$ – mvw Feb 2 '16 at 19:54
  • $\begingroup$ @mvw that's true. I was just trying to sketch out the idea of what I was asking. $\endgroup$ – tibsar Feb 2 '16 at 20:07
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Would it be possible for both scalar products to be negative? $\endgroup$ – tibsar Feb 2 '16 at 15:33
  • $\begingroup$ I've tried implementing this, and it seems to be checking that a point is near an end point, but not near the rest of the line. Any ideas? $\endgroup$ – tibsar Feb 2 '16 at 16:24
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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'')|$.

enter image description here

$\endgroup$
  • $\begingroup$ Why are we assuming the numbers are complex? $\endgroup$ – tibsar Feb 2 '16 at 15:02
  • $\begingroup$ Just for notational convenience, this makes the formulas very compact. But... why not ? $\endgroup$ – Yves Daoust Feb 2 '16 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.